Level of hierarchy in MST for traffic localization and load balancing

• US 10,212,074 B2
• Filed: 07/28/2017
• Issued: 02/19/2019
• Est. Priority Date: 06/24/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Tsai, Chia, Finn, Norman W., Yang, Yibin, Rao, Debashis Patnala
• Primary Examiner(s): Kassim, Khaled M
• Application Number:
  US15/663,503
• Publication Number:
  US 20170331730A1
• Time in Patent Office: 571 Days
• Field of Search: None
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

In one embodiment, a multiple spanning tree (MST) region is defined in a network, where the MST region includes a plurality of network nodes interconnected by links. A MST cluster is defined within the MST region, where the MST cluster includes a plurality of network nodes selected from the plurality of network nodes of the MST region. A network node of the MST cluster generates one or more MST bridge protocol data units (BPDUs) that present the MST cluster as a single logical entity to network nodes of the MST region that are not included in the MST cluster, yet enables per-multiple spanning tree instance (per-MSTI) load balancing of traffic across inter-cluster links that connect network nodes included in the MST cluster and network nodes of the MST region that are not included in the MST cluster.

Claims

1. A method comprising:

defining a multiple spanning tree (MST) region in a network, the MST region comprising a plurality of network nodes interconnected by links;

defining a plurality of non-overlapping MST clusters within the MST region, each of the MST clusters being a subset of at least two of the plurality of network nodes within the MST region, each of the MST clusters presenting itself as a single logical entity and permitting traffic on a plurality of inter-cluster links associated with the subset of the plurality of network nodes; and

enabling load balancing of traffic across the plurality of inter-cluster links, each link of the plurality of inter-cluster links connecting a respective network node in one of the MST clusters to a respective network node of the MST region that is outside of the one of the MST clusters.

2. The method of claim 1, further comprising:

including a bridge identifier of a network node of the one of the MST clusters that has a lowest cost path to a Common and Internal Spanning Tree (CIST) regional root node in one or more MST bridge protocol data units (BPDUs).

3. The method of claim 2, wherein the bridge identifier of the network node of the one of the MST clusters that has the lowest cost path to the CIST regional root node is stored in a CIST Cluster Root Identifier field of the one or more MST BPDUs.

4. The method of claim 1, further comprising:

including a cost within the one of the MST clusters to reach a Common and Internal Spanning Tree (CIST) cluster root node in one or more MST bridge protocol data units (BPDUs).

5. The method of claim 4, wherein the cost within the one of the MST clusters to reach the CIST cluster root node is stored in a CIST Intra Cluster Root Path Cost field of a CIST Cluster Configuration Message in the one or more MST BPDUs.

6. The method of claim 1, further comprising:

generating, by one or more processors, one or more MST bridge protocol data units (BPDUs) that present the one of the MST clusters as a single logical entity to network nodes of the MST region that are not included in the MST cluster; and

including a respective bridge identifier of a particular network node that generated the MST BPDUs in the one or more MST BPDUs.

7. The method of claim 6, wherein the particular network node that generated the MST BPDUs is stored in a MSTI Cluster Root Identifier field of a MSTI Cluster Configuration Message in the one or more MST BPDUs.

8. The method of claim 1, further comprising:

including a number of hops within the one of the MST clusters for a Common and Internal Spanning Tree (CIST) in one or more MST bridge protocol data units (BPDUs).

9. The method of claim 8, wherein the number of hops within the one of the MST clusters for the CIST is stored in a CIST Cluster Remaining Hops field of a CIST Cluster Configuration Message in the one or more MST BPDUs.

10. The method of claim 1, further comprising:

including a respective bridge identifier of a particular node of the one of the MST clusters serving as a root node of the one of the MST clusters for a respective MSTI in one or more MST bridge protocol data units (BPDUs).

11. The method of claim 10, wherein a cost within the one of the MST clusters to reach the root node associated with the respective MSTI cluster is stored in a MSTI Cluster Root Identifier field of a MSTI Cluster Configuration Message in the one or more MST BPDUs.

12. The method of claim 1, further comprising:

including a cost within the one of the MST clusters to reach a cluster root node for a respective MSTI in one or more MST bridge protocol data units (BPDUs).

13. The method of claim 12, wherein the cost within the one of the MST clusters to reach the cluster root node for the respective MSTI is stored in a MSTI Intra Cluster Root Path Cost field of a MSTI Cluster Configuration Message in the one or more MST BPDUs.

14. The method of claim 1, further comprising:

including a number of hops within the one of the MST clusters for a respective MSTI in one or more MST bridge protocol data units (BPDUs).

15. The method of claim 14, wherein the number of hops within the one of the MST clusters for the respective MSTI is stored in a MSTI Cluster Remaining Hops field of a MSTI Cluster Configuration Message in the one or more MST BPDUs.

16. The method of claim 14, wherein the one or more MST BPDUs are intra cluster MST BPDUs.

17. An apparatus comprising:

a network interface configured to couple the apparatus to one or more network nodes of a network;

a processor coupled to the network interface and configured to execute one or more processes; and

a memory configured to store a multiple spanning tree protocol (MSTP) process executable by the processor, the MSTP process when executed operable to;

determine a multiple spanning tree (MST) region has been defined in the network, wherein the MST region comprises a plurality of network nodes interconnected by links;

determine a plurality of non-overlapping MST clusters within the MST region, each of the MST clusters being a subset of at least two of the plurality of network nodes within the MST region, wherein each of the MST clusters presenting itself as a single logical entity and permits traffic on a plurality of inter-cluster links associated with the subset of the plurality of network nodes; and

enable load balancing of traffic across the plurality of inter-cluster links, each link of the plurality of inter-cluster links connecting a respective network node in one of the MST clusters to a respective network node of the MST region that is outside of the one of the MST clusters.

18. The apparatus of claim 17, wherein a bridge identifier is stored in a Common and Internal Spanning Tree (CIST) Cluster Root Identifier field of one or more MST bridge protocol data units (BPDUs), wherein a CIST Cluster Configuration Message in the one or more MST BPDUs comprises a CIST Intra Cluster Root Path Cost field containing a value representing a cost within the one of the MST clusters to reach a Common and Internal Spanning Tree (CIST) cluster root node in the one or more MST BPDUs.

19. The apparatus of claim 17, wherein one or more MST bridge protocol data units (BPDUs) comprise a number of hops within the one of the MST clusters for a Common and Internal Spanning Tree (CIST) regional root node.

20. A non-transitory computer-readable storage medium comprising:

computer-executable instructions stored thereon which, when executed by one or more processors, cause the one or more processors to;

define a multiple spanning tree (MST) region in a network, the MST region comprising a plurality of network nodes interconnected by links;

define a plurality of non-overlapping MST clusters within the MST region, each of the MST clusters being a subset of at least two of the plurality of network nodes within the MST region, each of the MST clusters presenting itself as a single logical entity and permitting traffic on a plurality of inter-cluster links associated with a subset of the plurality of network nodes; and

enable load balancing of traffic across the plurality of inter-cluster links, each link of the plurality of inter-cluster links connecting a respective network node in one of the MST clusters to a respective network node of the MST region that is outside of the one o the MST clusters.