Multiple instance spanning tree protocol

• US 8,165,043 B2
• Filed: 07/20/2005
• Issued: 04/24/2012
• Est. Priority Date: 10/17/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Di Benedetto, Marco, Mellacheruvu, Ramana, Finn, Norman W., Mahajan, Umesh
• Primary Examiner(s): Phan, Man
• Assistant Examiner(s): Kaur, Pamit
• Application Number:
  US11/185,057
• Publication Number:
  US 20050259597A1
• Time in Patent Office: 2,470 Days
• Field of Search: 370/402, 370/395, 370/256
• US Class Current: 370/256
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 12/4691 GVRP [GARP VLAN registration protocol]
• CPC Class Codes: H04L 12/4695 VTP [VLAN trunking protocol]
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A multiple instance spanning tree protocol (MI-STP) creates a plurality of active topologies (i.e., loop-free paths) within a computer network. These active topologies may be established through the exchange and processing of multiple instance spanning tree bridge protocol data unit messages (MI-STP BPDUs) by the intermediate network devices within the network. The active topologies are preferably created independently of any virtual local area network (VLAN) designations defined within the network. Once the active topologies are defined, each VLAN designation is then mapped to a single active topology, although multiple VLAN designations are preferably mapped to the same active topology to provide load balancing.

Claims

1. A device comprising:

a plurality of ports for interconnecting the device to a computer network having a plurality of virtual local area networks (VLANs), each VLAN associated with a corresponding VLAN identifier (VID);

a spanning tree engine in communicating relationship with the plurality of ports, the spanning tree engine configured to exchange bridge protocol data unit (BPDU) messages with one or more neighboring devices to establish a plurality of loop-free paths through the computer network independent of any VLANs in the computer network, each loop-free path associated with a respective spanning tree instance identifier of a plurality of spanning tree instance identifiers, the spanning tree engine configured to elect a root bridge for each spanning tree instance identifier, each BPDU message to specify one of the spanning tree instance identifiers of the plurality of spanning tree instance identifiers and to include information regarding the loop-free path associated with that the specified spanning tree instance identifier;

mapping logic configured to map each VID to one spanning tree instance identifier of a loop free path, wherein the root bridge for a given spanning tree instance identifier specifies which VIDs are mapped to the given spanning tree instance identifier, wherein at least some VIDs are mapped to the same spanning tree instance identifier; and

at least one forwarding engine configured to forward a network message associated with a given VID from at least one port that is in the forwarding spanning tree port state for the spanning tree instance identifier to which the given VID is mapped.

2. An intermediate network device comprising:

a plurality of ports for interconnecting the intermediate network device to a computer network having a plurality of virtual local area networks (VLANs), each VLAN associated with a corresponding VLAN identifier (VID);

a spanning tree engine in communicating relationship with the plurality of ports wherein the spanning tree engine exchanges bridge protocol data unit (BPDU) messages with one or more other intermediate network devices to establish a plurality of loop-free paths through the computer network independent of any VLANs in the computer network, each loop-free path associated with a respective spanning tree instance identifier of a plurality of spanning tree instance identifiers, each of the plurality of spanning tree instance identifiers being a unique identifier that is not a VID, each BPDU message to specify one of the spanning tree instance identifiers of the plurality of spanning tree instance identifiers and to include information regarding the loop-free path associated with the specified spanning tree instance identifier; and

a VLAN association engine that maps each VID to a spanning tree instance identifier associated with a loop-free path so that data messages associated with a given VID follow at least part of the loop-free path established for the spanning tree instance identifier to which the given VID is mapped, wherein at least some VIDs are mapped to the same spanning tree instance identifier of the plurality of spanning tree instance identifiers.

3. The intermediate network device of claim 2 wherein at least some of the BPDU messages also include an indication of each VID that is mapped to the one of the spanning tree instance identifiers specified in the BPDU message.

4. The intermediate network device of claim 2 further comprising a plurality of state machines, each state machine associated with a spanning tree instance identifier and configured to transition the ports among a plurality of spanning tree port states for the respective spanning tree instance identifier, the spanning tree port states including a discarding state and a forwarding state.

5. The intermediate network device of claim 2 wherein each BPDU also specifies an identifier of a root bridge for the one of the spanning tree instance identifiers specified in the BPDU message.

6. The intermediate network device of claim 5 wherein the spanning tree instance identifier specified in a given BPDU message is part of the identifier of the root bridge.

7. The intermediate network device of claim 2 wherein each BPDU message further specifies the port from which the respective BPDU message is being sent.

8. The intermediate network device of claim 2 further comprising a table that is accessible by the VLAN association engine, the table configured with a mapping of VIDs to spanning tree instance identifiers.

9. The intermediate network device of claim 2 wherein the VLAN mapping engine is further configured to, upon detection that a given VID is mapped to more than one spanning tree instance identifier, block messages associated with the given VID from being forwarded by the intermediate network device.

10. The intermediate network device of claim 2 wherein

a subset of the ports are associated with a first VID, and

the spanning tree engine is further configured to exclude all ports not associated with the first VID when establishing the loop-free topology for the spanning tree instance identifier to which the first VID is mapped.

11. The intermediate network device of claim 2 wherein the mapping of the plurality of VIDs to respective spanning tree instance identifiers is specified by a network administrator.

12. A device comprising:

a plurality of ports for interconnecting the device to a computer network having a plurality of virtual local area networks (VLANs), each VLAN associated with a corresponding VLAN identifier (VID);

a spanning tree engine in communicating relationship with the plurality of ports, wherein the spanning tree engine exchanges bridge protocol data unit (BPDU) messages with one or more neighboring devices to establish a plurality of loop-free paths through the computer network independent of any VLANs in the computer network, each loop-free path associated with a respective spanning tree instance identifier of a plurality of spanning tree instance identifiers, each of the plurality of spanning tree instance identifiers being a unique identifier that is not a VID, each BPDU message to specify one of the spanning tree instance identifiers of the plurality of spanning tree instance identifiers and to include information regarding the loop-free path associated with the specified spanning tree instance identifier;

mapping logic configured to map each VID to one spanning tree instance identifier of a loop free path, wherein at least some VIDs are mapped to the same spanning tree instance identifier of the plurality of spanning tree instance identifiers; and

at least one forwarding engine configured to forward a network message associated with a given VID from at least one port that is in the forwarding spanning tree port state for the spanning tree instance identifier to which the given VID is mapped.

13. The device of claim 12 wherein at least some of the BPDU messages also include an indication of each VID that is mapped to the one of the spanning tree instance identifiers specified in the BPDU message.

14. The device of claim 12 wherein the at least one forwarding engine is further configured to, upon detection of a given VID being associated with more than one spanning tree instance identifier, ensure no messages associated with the given VID are forwarded by the device.

15. The device of claim 12 wherein the mapping logic is configured through network administrator action.

16. An apparatus comprising:

means for interconnecting the apparatus to a computer network;

means for exchanging bridge protocol data unit (BPDU) messages with one or more neighboring apparatus to establish a plurality of loop-free paths through the computer network independent of any virtual local area networks (VLANs) in the computer network, each loop-free path associated with a respective spanning tree instance identifier of a plurality of spanning tree instance identifiers, each of the plurality of spanning tree instance identifiers being a unique identifier that is not a VID, each BPDU message specifying one of the spanning tree instance identifiers of the plurality of spanning tree instance identifiers and including information regarding the loop-free path associated with the specified spanning tree instance identifier;

means for mapping each VID of the plurality of VIDs to a spanning tree instance identifier of a loop free path, wherein at least some VIDs are mapped to the same spanning tree instance identifier of the plurality of spanning tree instance identifiers; and

means for forwarding a network message associated with a given VID from at least one port that is in the forwarding spanning tree port state for the spanning tree instance identifier to which the given VID is mapped.

17. The apparatus of claim 16 wherein at least some of the BPDU messages also include an indication of each VID that is mapped to the one of the spanning tree instance identifiers specified in the BPDU message.

18. The apparatus of claim 16 further comprising means for electing a root bridge for each spanning tree instance identifier, the root bridge for a given spanning tree instance identifier being configured to specify which VIDs are mapped to the given spanning tree instance identifier.

19. The apparatus of claim 16 further comprising means for detecting a given VID being associated with more than one spanning tree instance identifier and ensuring that no messages associated with the given VID are forwarded by the apparatus.

20. A method comprising:

interconnecting a plurality of ports to a computer network having a plurality of virtual local area networks (VLANs), each VLAN associated with a corresponding VLAN Identifier (VID);

establishing a plurality of loop-free paths through the computer network independent of any VLANs in the computer network by exchanging bridge protocol data unit (BPDU) messages, each loop-free path associated with a respective spanning tree instance identifier of a plurality of spanning tree instance identifiers, each of the plurality of spanning tree instance identifiers being a unique identifier that is not a VID, each BPDU message specifying one of the spanning tree instance identifiers of the plurality of spanning tree instance identifiers and including information regarding the loop-free path associated with the specified spanning tree instance identifier;

mapping each VID to a spanning tree instance identifier, wherein at least some VIDs are mapped to the same spanning tree instance identifier of the plurality of spanning tree instance identifiers; and

forwarding a network message associated with a given VID from at least one port that is in the forwarding spanning tree port state for the spanning tree instance identifier to which the given VID is mapped.

21. The method of claim 20 wherein at least some of the BPDU messages also include an indication of each VID that is mapped to the one of the spanning tree instance identifiers specified in the BPDU message.

22. The method of claim 20 wherein, upon detection of a given VID being associated with more than one spanning tree instance identifier, no messages associated with the given VID are forwarded.

23. The method of claim 20 wherein the establishing elects a root bridge for each spanning tree instance identifier, and the root bridge for a given spanning tree instance identifier specifies which VIDs are mapped to the given spanning tree instance identifier.

24. A method comprising:

interconnecting a plurality of ports to a computer network having a plurality of virtual local area networks (VLANs), each VLAN associated with a corresponding VLAN Identifier (VID);

establishing a plurality of loop-free paths through the computer network independent of any VLANs in the computer network by exchanging bridge protocol data unit (BPDU) messages, each loop-free path associated with a respective spanning tree instance identifier of a plurality of spanning tree instance identifiers, the exchange of BPDU messages to elect a root bridge for each spanning tree instance identifier, wherein each BPDU message specifies one of the spanning tree instance identifiers of the plurality of spanning tree instance identifiers and includes information regarding the loop-free path associated with the specified spanning tree instance identifier;

mapping each VID to a spanning tree instance identifier based on a determination by the root bridge for a given spanning tree instance of which VIDs are to be mapped to the given spanning tree instance identifier, wherein at least some VIDs are mapped to the same spanning tree instance identifier;

forwarding a network message associated with a given VID from at least one port that is in the forwarding spanning tree port state for the spanning tree instance identifier to which the given VID is mapped.