Method and apparatus for establishing spanning trees

• US 8,953,499 B2
• Filed: 05/11/2005
• Issued: 02/10/2015
• Est. Priority Date: 05/11/2005
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Johannes de Heer, Arie, van Haalen, Ronald
• Primary Examiner(s): O CONNOR, BRIAN T
• Application Number:
  US11/126,504
• Publication Number:
  US 20060268747A1
• Time in Patent Office: 3,562 Days
• Field of Search: 370/217, 370/219, 370/248, 370/255, 370/256, 370/400, 370/401, 370/389, 370/408, 709/220, 709/221, 709/222, 709/231, 709/239, 709/240
• US Class Current: 370/256
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

The invention includes a method and apparatus for configuring a spanning tree. Specifically, one method according to the present invention includes determining a network topology associated with at least a portion of a network where the network topology includes at least one bridge and at least one link, obtaining network information associated with the network, and computing the spanning tree according to the network topology information and the network information. The network information is operable for evaluating the at least one bridge and the at least one link for inclusion in the spanning tree. The spanning tree includes at least one spanning tree segment, where the at least one spanning tree segment includes at least one communication path operable for supporting network traffic.

Claims

1. A method for establishing a spanning tree in a network comprising a plurality of bridges and a plurality of links, the method comprising:

obtaining information comprising at least one of network topology information for at least a portion of the network or network information for at least a portion of the network;

computing the spanning tree based on at least a portion of the obtained information, wherein the computed spanning tree comprises a plurality of spanning tree segments, wherein each of the spanning tree segments comprises a respective communication path between a respective pair of the bridges of the network;

setting spanning tree parameters for the computed spanning tree, wherein the spanning tree parameters are adapted for establishing the computed spanning tree within the network; and

establishing the computed spanning tree within the network by transmitting the spanning tree parameters toward the bridges associated with the spanning tree segments of the computed spanning tree.

2. The method of claim 1, wherein the plurality of spanning tree segments comprises a plurality of active spanning tree segments.

3. The method of claim 2, wherein the plurality of spanning tree segments comprises at least one protection spanning tree segment associated with at least one of the active spanning tree segments.

4. The method of claim 1, wherein the computed spanning tree is computed in a manner for improving at least one network parameter, wherein the at least one network parameter comprises at least one of a network throughput and a spanning tree throughput.

5. The method of claim 1, wherein the method is performed by a management system.

6. The method of claim 1, further comprising:

receiving, at the bridges associated with the spanning tree segments of the computed spanning tree, respective portions of the spanning tree parameters associated with the respective bridges associated with the spanning tree segments of the computed spanning tree; and

configuring the bridges associated with the spanning tree segments of the computed spanning tree, using the respective portions of the spanning tree parameters, to establish the computed spanning tree within the network.

7. The method of claim 1, wherein the spanning tree parameters comprise bridge priorities and link costs.

8. The method of claim 1, wherein the spanning tree parameters comprise bridge parameters and port parameters.

9. The method of claim 8, wherein at least one of:

for at least one of the bridges associated with at least one of the spanning tree segments of the computed spanning tree, the bridge parameters comprise at least one of;

a bridge priority, a hello time, a maximum wait time, a forward delay, a path cost, a topology change trap suppression, and a transmit hold count;

or

for at least one of the bridges associated with at least one of the spanning tree segments of the computed spanning tree, the port parameters comprise at least one;

of a port state, a link cost, and a link priority.

10. The method of claim 1, further comprising:

computing a second spanning tree using the network topology information based on a determination that a first traffic class associated with the computed spanning tree is different than a second traffic class associated with the second computed spanning tree.

11. The method of claim 1, wherein the network topology information comprises at least one of bridge information associated with at least a portion of the bridges of the network, port information associated with ports of at least a portion of the bridges of the network, link information associated with at least a portion of the links of the network, or connectivity information.

12. The method of claim 1, wherein computing the spanning tree comprises analyzing potential combinations of the bridges and the links for use in the computed spanning tree.

13. The method of claim 1, wherein the network information comprises at least one of link cost information or network performance information.

14. The method of claim 13, wherein the network performance information comprises at least one of estimated traffic volume information or actual traffic volume information.

15. The method of claim 1, wherein the computed spanning tree is computed based on traffic volume information, wherein computing the spanning tree based on traffic volume information comprises prioritizing bridges, ports of bridges, and links for selection for use in the computed spanning tree.

16. The method of claim 1, wherein the computed spanning tree is computed based on network performance information, wherein computing the spanning tree based on network performance information comprises prioritizing bridges according to respective bridge capacity and prioritizing links according to respective link capacity.

17. The method of claim 16, wherein computing the spanning tree based on network performance information comprises preferring establishment of a spanning tree segment between a pair of high-capacity bridges connected via a low-cost link to establishment of a spanning tree segment between a pair of low-capacity bridges connected via a high-cost link.

18. The method of claim 1, wherein the computed spanning tree is computed using a shortest path algorithm.

19. An apparatus for establishing a spanning tree in a network comprising a plurality of bridges and a plurality of links, the apparatus comprising:

a processor and a memory communicatively connected to the processor, the processor configured to;

obtain information comprising at least one of network topology information for at least a portion of the network or network information for at least a portion of the network;

compute the spanning tree based on at least a portion of the obtained information, wherein the computed spanning tree comprises a plurality of spanning tree segments, wherein each of the spanning tree segments comprises a respective communication path between a respective pair of the bridges of the network;

set spanning tree parameters for the computed spanning tree, wherein the spanning tree parameters are adapted for establishing the computed spanning tree within the network; and

establish the computed spanning tree within the network by transmitting the spanning tree parameters toward the bridges associated with the spanning tree segments of the computed spanning tree.

20. A non-transitory computer-readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method for establishing a spanning tree in a network comprising a plurality of bridges and a plurality of links, the method comprising:

obtaining information comprising at least one of network topology information for at least a portion of the network or network information for at least a portion of the network;

computing the spanning tree based on at least a portion of the obtained information, wherein the computed spanning tree comprises a plurality of spanning tree segments, wherein each of the spanning tree segments comprises a respective communication path between a respective pair of the bridges of the network;

setting spanning tree parameters for the computed spanning tree, wherein the spanning tree parameters are adapted for establishing the computed spanning tree within the network; and

establishing the computed spanning tree within the network by transmitting the spanning tree parameters toward the bridges associated with the spanning tree segments of the computed spanning tree.