Method and apparatus for quality of service (QoS) planning for an Ethernet based network

Patent metadata

Field	Value
Publication number	US-9509526-B2
Application number	US-10592608-A
Country	US
Kind code	B2
Filing date	Apr 18, 2008
Priority date	Apr 4, 2007
Publication date	Nov 29, 2016
Grant date	Nov 29, 2016

Abstract

A method for determining required routes through an Ether based network associated with VLANs by determining a set of spanning trees. The set of spanning trees is determined to provide a number of routes for consideration. Each spanning tree comprising a plurality of links, sorts the VLANs into an order based on one or more VLAN criteria for the network topology, and maps the sorted VLANs onto the set of spanning trees in an order to optimise one or more characteristics relating to the combination of spanning tree and VLAN to determine an optimised VLAN tree mapping for each set of spanning trees for each route. A best primary tree for each route is selected. Possible failures for each link in the best primary tree for each route are analyzed to derive for a backup tree optimised to determine one or more best backup trees in the event of a possible failure.

First claim

The invention claimed is:

1. A method, utilizing a computing device operating a network planning for an Ethernet based network having a network topology and a plurality of VLANs to be associated therein wherein the network requires a number of routes therethrough, the method comprising the steps of:
determining a set of spanning trees within the network for providing one or more of the number of routes for consideration, each spanning tree comprising a plurality of links;
sorting the VLANs into an order based on one or more VLAN criteria for the network topology;
mapping each of the sorted VLANs onto the set of spanning trees in order to optimize one or more characteristics relating to the network or any associated feature thereof for the or each combination of spanning tree and VLAN to thereby determine an optimized VLAN tree mapping for each set of spanning trees for each route;
selecting a best primary tree for each of the sorted VLANs, based on the order in which the VLANS were sorted, from the set of spanning trees on which the each of the sorted VLANs is mapped for each route in the network topology;
analysing possible failures for each link in the best primary tree for each route to derive for each possible failure a backup tree which is optimized in terms of the characteristics and criteria to determine one or more best backup trees to replace the or each best primary tree in the event of a possible failure of the analysed possible failures;
translating the best primary tree and the determined one or more best backup trees for each best primary tree for each route in the network into a set of Multiple Spanning Tree Protocol configuration parameters which in combination form a network plan, and
outputting information relating to the best primary tree and the determined one or more best backup trees for each best primary tree for each route in the network.

2. The method of claim 1 , further comprising iterating the determining, sorting and mapping steps to optimize the characteristics and criteria for the or each step to determine if a better best VLAN tree mapping is available.

3. The method of claim 1 , wherein the step of determining a set of spanning trees comprises determining a set of spanning trees according to at least one criterion from a group of criteria comprising
a random basis,
according to a minimum number of trees specified by an operator, and
a selection of a minimized number of disjoint trees.

4. The method of claim 1 , wherein the step of sorting the VLANs into an order comprises:
determining a VLAN type of each VLAN and using the VLAN type to order the VLANs.

5. The method of claim 1 , wherein the step of sorting the VLANs into an order comprises:
determining a VLAN class of service of each VLAN and using the VLAN class of service to order the VLANs.

6. The method of claim 1 , wherein the step of sorting the VLANs into an order comprises:
determining a VLAN expected level of congestion of each VLAN and using the VLAN level of congestion to order the VLANs.

7. The method of claim 1 , wherein the step of mapping the VLANs onto the set of spanning trees comprises:
determining a cost of each link in the or each spanning tree in order to determine the spanning trees with the lowest total cost.

8. The method of claim 1 , wherein the step of mapping the VLANs onto the set of spanning trees comprises:
determining a bandwidth of each link in the or each spanning tree in order to determine the spanning trees with a lowest total bandwidth.

9. The method of claim 1 , wherein the step of determining one or more backup trees, comprises:
determining a root node for each backup tree such that the backup tree has a minimum possible number of VLANs to achieve a backup link.

10. The method of claim 1 , wherein the step of determining one or more backup trees, comprises:
attempting to find a local backup link for the possible failure,
if no local backup link is available, attempting to find a non-local backup link for the possible failure.

11. The method according to claim 1 , further comprising the step of
outputting the set of spanning tree protocol configuration parameters as the information relating to the best primary tree and the determined one or more best backup trees for each best primary tree for each route in the network.

12. The method of claim 11 , wherein the step of translating the output to a spanning tree protocol configuration parameter set, comprises:
for each node in a primary tree determining a root port to represent the port chosen for the primary link;
and for each node in a backup tree determining a preferred port to represent the port chosen for the backup link.

13. The method of claim 12 , further comprising deriving a sequence of root ports in order to define the primary tree for the network plan.

14. The method of claim 12 , further comprising deriving a sequence of preferred ports in order to define the backup tree for the network plan.

15. The method of claim 12 , further comprising calculating the root port to be that port that presents a minimum root path cost (RPC) to a root node.

16. The method of claim 12 , further comprising calculating the preferred port to be that port that presents a minimum root path cost (RPC) to a root node other than that for the root port.

17. A network planning apparatus for an Ethernet based network having a network topology and a plurality of VLANs to be associated therein wherein the network requires a number of routes therethrough, the apparatus comprising:
means for determining a set of spanning trees within the network for providing one or more of the number of routes for consideration, wherein each spanning tree comprising a plurality of links;
means for sorting the VLANs into an order based on one or more VLAN criteria for the network topology;
means for mapping each of the sorted VLANs onto the set of spanning trees in an order to optimize one or more characteristics relating to the network or any associated feature thereof for the or each combination of spanning tree and VLAN to thereby determine an optimized VLAN tree mapping for each set of spanning trees for each route;
means for selecting a best primary tree for each of the sorted VLANs, based on the order in which the VLANs were sorted, from the set of spanning trees on which the each of the sorted VLANs is mapped for each route in the network topology;
means for analysing possible failures for each link in the best primary tree for each route to derive for each possible failure a backup tree which is optimized in terms of the characteristics and criteria to determine one or more best backup trees to replace the or each best primary tree in the event of a possible failure of the analysed possible failures;
means for translating the best primary tree and the determined one or more best backup trees for each best primary tree for each route in the network into a set of Multiple Spanning Tree Protocol configuration parameters which in combination form a network plan; and
means for outputting information relating to the best primary tree and the determined one or more best backup trees for each best primary tree for each route in the network.

18. The apparatus of claim 17 , further comprising iterating the determining, sorting and mapping steps to optimize the characteristics and criteria for the or each step to determine if a better best VLAN tree mapping is available.

19. The apparatus of claim 17 wherein the means for determining a set of spanning trees comprises mea

Assignees

• Iovanna Paola
• Sabella Roberto
• Bartoli Ivano
• Vellante Laura
• Ericsson Telefon Ab L M

Inventors

• Iovanna Paola
• Sabella Roberto
• Bartoli Ivano
• Vellante Laura

Classifications

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/22

  Alternate routing · CPC title

• H04L12/462 Primary

  LAN interconnection over a bridge based backbone · CPC title

• H04L41/5045

  Making service definitions prior to deployment · CPC title

• H04L41/145

  involving simulating, designing, planning or modelling of a network · CPC title