Multiple instance spanning tree protocol

• US 20050259597A1
• Filed: 07/20/2005
• Published: 11/24/2005
• Est. Priority Date: 10/17/2000
• Status: Active Grant

• Current Assignee: Marco D.I. Benedetto, Norman W. Finn, Ramana Mellacheruvu, Umesh Mahajan
• Original Assignee: Marco D.I. Benedetto, Norman W. Finn, Ramana Mellacheruvu, Umesh Mahajan
• Inventors: Finn, Norman W., Mahajan, Umesh, Mellacheruvu, Ramana, Benedetto, Marco Di
• Granted Patent: US 8,165,043 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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-27. -27. (canceled)

28. An intermediate network device for use in a computer network having a plurality of virtual local area networks (VLANs), each VLAN associated with a corresponding VLAN Identifier (VID), the intermediate network device comprising:

a plurality of ports for interconnecting the intermediate network device to the computer network;

a spanning tree engine in communicating relationship with the plurality of ports, wherein the spanning tree engine cooperates with one or more other intermediate network devices to establish a plurality of loop-free paths through the computer network, each loop-free path associated with a respective spanning tree identifier; and

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

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

30. The intermediate network device of claim 28 wherein the spanning tree engine issues a plurality control messages for use in establishing the plurality of loop-free paths, each control message specifying a spanning tree identifier.

31. The intermediate network device of claim 30 wherein the spanning tree engine receives at least one control message and processes the at least one control message to establish the plurality of loop-free paths.

32. The intermediate network device of claim 30 wherein each control message specifies an identifier of a root bridge for each spanning tree identifier.

33. The intermediate network device of claim 32 wherein the spanning tree identifier specified in a given control message is part of the identifier of the root bridge.

34. The intermediate network device of claim 32 wherein each control message has a plurality of units, and each unit corresponds to a given spanning tree identifier and specifies the identifier of the root bridge for the given spanning tree identifier.

35. The intermediate network device of claim 34 wherein each control message unit further specifies a root path cost for the specified root bridge.

36. The intermediate network device of claim 34 wherein each control message unit further specifies the port from which the respective control message is being sent.

37. The intermediate network device of claim 30 wherein a first control message issued by the spanning tree engine for a given spanning tree identifier indicates which VIDs are associated with the given spanning tree identifier.

38. The intermediate network device of claim 28 wherein at least two VIDs are mapped to a first spanning tree identifier.

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

40. The intermediate network device of claim 28 wherein the VLAN mapping engine, upon detecting that a given VID is mapped to more than one spanning tree instance, blocks messages associated with the given VID from being forwarded by the intermediate network device.

41. The intermediate network device of claim 28 wherein

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

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

42. The intermediate network device of claim 28 wherein the mapping of the plurality of VIDs to respective spanning tree instances is specified by a network administrator.

43. A device for use in a computer network having a plurality of virtual local area network (VLAN) segments, each VLAN segment associated with a corresponding VLAN Identifier (VID), the device comprising:

a plurality of ports for interconnecting the device to the computer network;

a spanning tree engine in communicating relationship with the plurality of ports, wherein the spanning tree engine cooperates with one or more neighboring devices to establish a plurality of loop-free paths through the computer network by transitioning each of the ports among a plurality of spanning tree port states, including a forwarding spanning tree port state and a blocking spanning tree port state, each loop-free path associated with a respective spanning tree identifier;

mapping logic configured to map each VID to one spanning tree 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 identifier to which the given VID is mapped.

44. The device of claim 43 wherein the spanning tree engine elects a root bridge for each spanning tree instance, and the root bridge for a given spanning tree instance specifies which VIDS are mapped to the given spanning tree instance.

45. The device of claim 44 wherein the spanning tree engine issues a plurality control messages for use in establishing the plurality of loop-free paths, each control message specifying a revision number to indicate changes in the mapping of VIDs to spanning tree identifiers.

46. The device of claim 43 wherein, upon detection of a given VID being associated with more than one spanning tree instance, no messages associated with the given VID are forwarded by the device.

47. The device of claim 43 wherein the mapping logic is configured through network administrator action.

48. A computer network control message for use in establishing a plurality of loop-free paths within a computer network, each loop-free path associated with a spanning tree identifier, the control message received by a network device and stored in a memory disposed at the network device, the computer network control message comprising:

a first field carrying an identifier of a first spanning tree instance;

a second field carrying an identifier of a root device for the first spanning tree instance;

a third field carrying an identifier of a second spanning tree instance; and

a fourth field carrying an identifier of a root device for the second spanning tree instance.

49. The computer network control message of claim 48 further comprising:

a fifth field carrying a cost corresponding to a path to the root device for the first spanning tree instance; and

a sixth field carrying a cost corresponding to a path to the root device for the second spanning tree instance.

50. The computer network control message of claim 48 wherein the identifier of the first spanning tree instance is part of the identifier of the root device for the first spanning tree instance.

51. The computer network control message of claim 48 further comprising:

a fifth field that specifies a mapping of Virtual Local Area Network Identifiers (VIDs) to spanning tree instance identifiers.