Method And System For Controlled Tree Management

• US 20110080854A1
• Filed: 01/18/2008
• Published: 04/07/2011
• Est. Priority Date: 01/19/2007
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Farkas, János, Takács, Attila, Antal, Csaba, Saltsidis, Panagiotis
• Granted Patent: US 8,837,329 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 41/069 using logs of notifications; Post-processing of notifications
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/0856 by backing up or archiving configuration information
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees

Abstract

There is disclosed a method and apparatus for facilitating a network, such as an Ethernet LAN, for efficient forwarding of data traffic by collecting neighbor information, generating and distributing link state advertisements, populating a topology database for the network, and calculating trees for each bridge serving as a root bridge. In a preferred embodiment the method and system also prepare one or more backup topologies, and store them for use if they are needed due to a failure condition detected in the network. In a particularly preferred embodiment, probabilities are assigned to various potential failure conditions, and the probability values are used to decide which backup topologies to calculate, store, or use.

Claims

1. A method for setting up and updating multiple trees in an Ethernet network having a plurality of bridges controlled in a link state manner wherein topology database is available at each network node and each bridge has a single forwarding tree, said method comprising:

calculating the single forwarding tree at a root bridge;

the root bridge advertising the forwarding tree to other bridges participating in the forwarding tree;

configuring the forwarding tree according to the received advertisement;

distributing the tree advertisement only within the forwarding tree.

2. The method of claim 1, wherein:

each root bridge manages its own tree in a Shortest Path Bridging (SPB) network; and

at least one tree is assigned to each bridge.

3. The method of claim 1, wherein only a root bridge calculates a tree in a Shortest Path Bridging (SPB) network based on its link state topology database for reducing overall computational complexity in the network.

4. The method of claim 1, wherein the root bridge advertises its tree to non-root bridges participating in the tree.

5. The method of claim 1, wherein non-root bridges:

set a tree associated with the non-root bridges according to the received tree advertisement;

set blocked links prior to active links; and

send a modified tree advertisement, which only contains a relevant subtree in a direction of leafs along the tree being configured.

6. The method of claim 1, wherein only the root bridge recalculates the tree after a topology change and initiates the update of its tree in non-root bridges by issuing a new tree advertisement message.

7. The method of claim 1, wherein the tree is a spanning tree determining the active topology of the root bridge.

8. The method of claim 1, wherein the tree belongs to a service and maintained in order to provide connectivity for that service.

9. The method of claim 1, wherein all trees of a Shortest Path Bridging (SPB) network are managed by a master bridge, the master bridge calculating all trees based on its link state topology database and issuing tree advertisement messages for all trees.

10. The method of claim 1, further comprising a tree controller which calculates a backup tree for specified topology changes.

11. The method of claim 1, wherein:

the backup tree is stored in the root bridge; and

the backup tree is advertised as the corresponding topology change appears.

12. The method of claim 1, wherein:

the backup tree is stored in a non-root bridge; and

the root bridge only signals a request for activation of the corresponding backup tree to non-root bridges when the topology change appears.

13. The method of claim 12 wherein the non-root bridges set the backup tree.

14. A system for setting up and updating multiple trees in an Ethernet network having a plurality of bridges controlled in a link state manner wherein topology database is available at each network node and each bridge has a single forwarding tree, comprising:

means for calculating the single forwarding tree at a root bridge;

means for advertising the forwarding tree from said root bridge to other bridges participating in the forwarding tree;

means for configuring the forwarding tree according to the received advertisement;

means for distributing the tree advertisement only within the forwarding tree.

15. The system of claim 14, wherein:

each root bridge manages its own tree in a Shortest Path Bridging (SPB) network; and

at least one tree is assigned to each bridge.

16. The system of claim 14, wherein only a root bridge calculates a tree in a Shortest Path Bridging (SPB) network based on its link state topology database for reducing overall computational complexity in the network.

17. The system of claim 14, wherein non-root bridges further comprises:

means for setting a tree associated with the non-root bridges according to the received tree advertisement;

means for setting blocked links prior to active links; and

means for sending a modified tree advertisement, which only contains a relevant subtree in a direction of leafs along the tree being configured.

18. The system of claim 14, further comprising a tree controller which calculates a backup tree for specified topology changes.

19. The system of claim 14, wherein:

the backup tree is stored in the root bridge; and

the backup tree is advertised as the corresponding topology change appears.

20. The system of claim 14, wherein:

the backup tree is stored in a non-root bridge; and

the root bridge only signals a request for activation of the corresponding backup tree to non-root bridges when the topology change appears.