System and method for determining the mergeability of spanning tree instances

• US 7,701,881 B1
• Filed: 07/17/2004
• Issued: 04/20/2010
• Est. Priority Date: 07/17/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sankaran, Genesh Chennimalal
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): SMITH, JOSHUA Y
• Application Number:
  US10/893,071
• Time in Patent Office: 2,103 Days
• Field of Search: 370254-258
• US Class Current: 370/256
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A system and method provide for reducing a number of topology instances in a network portion implementing a multiple instance topology. Various embodiments further provide for determining if one or more of the topology instances are merge-able or conditionally merge-able to form a lesser number of representative topology instances, and if so, for causing merging of the topology instances.

Claims

1. A method for reducing spanning tree instances in a network, the method comprising:

receiving in an instance merger of a network device on the network, first and second spanning tree instances corresponding to a portion of the network, the network having a plurality of participating stations;

determining an optimal root for each of the first and second spanning tree instances;

accessing configuration information from each of the first and second spanning tree instances, wherein the configuration information comprises a forwarding port, a blocked port, and the optimal root;

comparing the configuration information accessed from the first and second spanning tree instances to determine whether the first and second spanning tree instances are merge-able, the merge-able determination implementing a subtree reduction comprising;

determining if at least one of a forwarding port set and a blocking port set of each of the first and second spanning tree instances are substantially equivalent;

determining if one of the first and second spanning tree instances is a superset of remaining spanning tree instances; and

determining, if at least one of a forwarding port set and a blocking port set of each of the first and second spanning tree instances are substantially equivalent and if one of the first and second spanning tree instances is a superset of remaining spanning tree instances, that the first and second spanning tree instances are conditionally merge-able;

merging the first and second spanning tree instances into a merged topology instance when the merge-able determination indicates that the first and second spanning tree instances are merge-able; and

deploying one or more merge indicators to the plurality of participating stations to indicate that the first and second spanning tree instances have been merged into the merged topology instance, the one or more merge indicators being used by the participating stations to perform a corresponding merging of the first and second spanning tree instances.

2. The method of claim 1, wherein at least one of the spanning tree instances comprises an IEEE 802.1s multiple spanning tree protocol (MSTP) topology.

3. The method of claim 1, wherein at least one of the spanning tree instances comprises a spanning tree topology in accordance with at least one of IEEE 802.1s and Multiple Instance Spanning Tree Protocol (MISTP).

4. The method of claim 1, wherein the merge-able determination comprises:

determining if an instance forwarding path of the first and second spanning tree instances are the same, thereby indicating that the first and second spanning tree instances are conditionally merge-able;

determining if the first and second spanning tree instances share a common multiple instance root; and

determining, if the first and second spanning tree instances are conditionally merge-able and share a common multiple instance root, that the first and second spanning tree instances are merge-able.

5. The method of claim 1, wherein the merge-able determination comprises:

determining if only one of the first and second spanning tree instances will be used, thereby indicating that the first and second spanning tree instances are conditionally merge-able;

determining if the first and second spanning tree instances share a common multiple instance root; and

determining, if the first and second spanning tree instances are conditionally merge-able and share a common multiple instance root, that the first and second spanning tree instances are merge-able.

6. The method of claim 1, wherein the merge-able determination comprises implementing a conditional reduction.

7. The method of claim 6, wherein the conditional reduction comprises:

determining a forwarding symmetric difference between a forwarding link set of each of the first and second spanning tree instances;

determining a blocking symmetric difference between a blocking link set of each of the first and second spanning tree instances;

determining an intersection of the forwarding symmetric difference and the blocking symmetric difference; and

determining, if the intersection is empty, that the first and second spanning tree instances are conditionally merge-able.

8. A system operable within a network implementing a multiple parallel topology in at least one network portion of the network, the system comprising:

a topology instance merge-ability analyzer configured to;

receive first and second spanning tree instances corresponding to the at least one network portion, the network having a plurality of participating stations;

determine an optimal root for each of the first and second spanning tree instances;

access configuration information from each of the first and second spanning tree instances, wherein the configuration information comprises a forwarding port, a blocked port, and the optimal root; and

compare the configuration information accessed from the first and second spanning tree instances to determine whether the first and second spanning tree instances are merge-able, the merge-able determination implementing a subtree reduction comprising;

determining if at least one of a forwarding port set and a blocking port set of each of the first and second spanning tree instances are substantially equivalent;

determining if one of the first and second spanning tree instances is a superset of remaining spanning tree instances; and

determining, if at least one of a forwarding port set and a blocking port set of each of the first and second spanning tree instances are substantially equivalent and if one of the first and second spanning tree instances is a superset of remaining spanning tree instances, that the first and second spanning tree instances are conditionally merge-able; and

a topology instance merger coupled to the instance merge-ability analyzer, the topology instance merger being configured to;

merge the first and second spanning tree instances into a merged topology instance when the merge-able determination indicates that the first and second spanning tree instances are merge-able; and

deploy one or more merge indicators to the plurality of participating stations to indicate that the first and second spanning tree instances have been merged into the merged topology instance, the one or more merge indicators being used by the participating stations to perform a corresponding merging of the first and second spanning tree instances.

9. The system of claim 8, wherein the topology instance merge-ability analyzer comprises:

a multiple topology instance root comparer; and

at least one of a multiple instance forwarding path comparer and a topology instance use determiner.

10. The system of claim 8, wherein the topology instance merge-ability analyzer comprises a subtree reduction analyzer.

11. The system of claim 8, wherein the topology instance merge-ability analyzer comprises a conditional reduction analyzer.

12. A non-transitory computer-readable storage medium, storing instructions executed by a computer, comprising:

one or more instructions for receiving in an instance merger of a network device on a network, first and second spanning tree instances corresponding to a network portion of the network, the network having a plurality of participating stations;

one or more instructions for determining an optimal root for each of the first and second spanning tree instances;

one or more instructions for accessing configuration information from each of the first and second spanning tree instances, wherein the configuration information comprises a forwarding port, a blocked port, and the optimal root;

one or more instructions for comparing the configuration information accessed from the first and second spanning tree instances to determine whether the first and second spanning tree instances are merge-able, the merge-able determination implementing a subtree reduction comprising;

determining if at least one of a forwarding port set and a blocking port set of each of the first and second spanning tree instances are substantially equivalent;

determining if one of the first and second spanning tree instances is a superset of remaining spanning tree instances; and

determining, if at least one of a forwarding port set and a blocking port set of each of the first and second spanning tree instances are substantially equivalent and if one of the first and second spanning tree instances is a superset of remaining spanning tree instances, that the first and second spanning tree instances are conditionally merge-able;

one or more instructions for merging the first and second spanning tree instances into a merged topology instance when the merge-able determination indicates that the first and second spanning tree instances are merge-able; and

one or more instructions for deploying one or more merge indicators to the plurality of participating stations to indicate that the first and second spanning tree instances have been merged into the merged topology instance, the one or more merge indicators being used by the participating stations to perform a corresponding merging of the first and second spanning tree instances.

13. The non-transitory computer-readable storage medium of claim 12, wherein at least one of the spanning tree instances comprises an IEEE 802.1s multiple spanning tree protocol (MSTP) topology.

14. The non-transitory computer-readable storage medium of claim 12, wherein at least one of the spanning tree instances comprises a spanning tree topology in accordance with at least one of IEEE 802.1s and Multiple Instance Spanning Tree Protocol (MISTP).

15. A method for reducing spanning tree instances in a network, the method comprising:

receiving in an instance merger of a network device on the network, first and second spanning tree instances corresponding to a portion of the network, the network having a plurality of participating stations;

determining an optimal root for each of the first and second spanning tree instances;

accessing configuration information from each of the first and second spanning tree instances, wherein the configuration information comprises a forwarding port, a blocked port, and the optimal root;

comparing the configuration information accessed from the first and second spanning tree instances to determine whether the first and second spanning tree instances are merge-able, the merge-able determination implementing a conditional reduction comprising;

determining a forwarding symmetric difference between a forwarding link set of each of the first and second spanning tree instances;

determining a blocking symmetric difference between a blocking link set of each of the first and second spanning tree instances;

determining an intersection of the forwarding symmetric difference and the blocking symmetric difference; and

determining, if the intersection is empty, that the first and second spanning tree instances are conditionally merge-able;

merging the first and second spanning tree instances into a merged topology instance when the merge-able determination indicates that the first and second spanning tree instances are merge-able; and

deploying one or more merge indicators to the plurality of participating stations to indicate that the first and second spanning tree instances have been merged into the merged topology instance, the one or more merge indicators being used by the participating stations to perform a corresponding merging of the first and second spanning tree instances.

16. The method of claim 15, wherein at least one of the spanning tree instances comprises an IEEE 802.1s multiple spanning tree protocol (MSTP) topology.

17. The method of claim 15, wherein at least one of the spanning tree instances comprises a spanning tree topology in accordance with at least one of IEEE 802.1s and Multiple Instance Spanning Tree Protocol (MISTP).

18. The method of claim 15, wherein the merge-able determination comprises:

determining if an instance forwarding path of the first and second spanning tree instances are the same, thereby indicating that the first and second spanning tree instances are conditionally merge-able;

determining if the first and second spanning tree instances share a common multiple instance root; and

determining, if the first and second spanning tree instances are conditionally merge-able and share a common multiple instance root, that the first and second spanning tree instances are merge-able.

19. The method of claim 15, wherein the merge-able determination comprises:

determining if only one of the first and second spanning tree instances will be used, thereby indicating that the first and second spanning tree instances are conditionally merge-able;

determining if the first and second spanning tree instances share a common multiple instance root; and

determining, if the first and second spanning tree instances are conditionally merge-able and share a common multiple instance root, that the first and second spanning tree instances are merge-able.

20. The method of claim 15, wherein the merge-able determination comprises a subtree reduction.

21. The method of claim 20, wherein the subtree reduction comprises:

determining if at least one of a forwarding port set and a blocking port set of each of the first and second spanning tree instances are substantially equivalent;

determining if one of the first and second spanning tree instances is a superset of remaining spanning tree instances; and

determining, if at least one of a forwarding port set and a blocking port set of each of the first and second spanning tree instances are substantially equivalent and if one of the first and second spanning tree instances is a superset of remaining spanning tree instances, that the first and second spanning tree instances are conditionally merge-able.