Title: Multiple instance spanning tree protocol
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.
Patent Number: 6,937,576 Issued on 08/30/2005 to Di Benedetto, et al.
| Inventors:
|
Di Benedetto; Marco (Santa Clara, CA);
Mellacheruvu; Ramana (San Jose, CA);
Finn; Norman W. (Livermore, CA);
Mahajan; Umesh (Cupertino, CA)
|
| Assignee:
|
Cisco Technology, Inc. (San Jose, CA)
|
| Appl. No.:
|
690619 |
| Filed:
|
October 17, 2000 |
| Current U.S. Class: |
370/256; 370/408 |
| Intern'l Class: |
H04L 012/56 |
| Field of Search: |
370/254,255,256,395.5,395.53,400,401,402,408
709/220,221,222
|
References Cited [Referenced By]
U.S. Patent Documents
Other References
Fine et al. "Shared Spanning Trees". Cisco Systems. Jan. 15, 1999. pp. 1-30.
Finn, Norman. "Shared Spanning Trees IEEE 802.1s Multiple Spanning Trees for
.1q" Cisco Systems. Jan. 27, 1999. pp. 1-11.
"ISO/IEC 15802-3: 1998 ANSI/IEEE Std 802.1d, 1998", IEEE, pp. 58-109.
U.S. Appl. No. 09/283,111, Dey.
"Understanding VLAN Truck Protocol", http://www.cisco/univered/home/home.htm,
Cisco Systems, Inc., (c) 1997, pp. 1-2.
"White Paper: VLAN Truck Protocol", http:www.cisco.com/warp/public/473/21.html,
Cisco Systems, Inc., (c)2000, pp. 1-22.
"Multiple Spanning Trees", IEEE P802.1s/D6, Draft Supplement to Virtual Bridged
Local Area Networks: Institute of Electrical and Electronics Engineers, Inc., pp.
1-44, Jun. 8, 2000.
"Standards for Local and Metropolitan Area Networks-Supplement to 802, 1Q Virtual
Bridged Local Area Networks: Mulitiple Spanning Tress", IEEE Draft P802.1s/D8,
pp. 1-50, Sep. 27, 2000.
|
Primary Examiner: Pham; Chi
Assistant Examiner: Ferris; Derrick W
Attorney, Agent or Firm: Cesari and McKenna, LLP, Reinemann; Michael R.
Claims
1. A method of creating multiple spanning trees within a computer network, each
spanning tree defining a loop-free path among a plurality of intermediate devices
within the network, the network configured with a plurality of virtual local area
network (VLAN) designations, the method comprising the steps of:
receiving a plurality of multiple instance spanning tree protocol bridge protocol
data unit (MI-STP BPDU) messages at one or more of the intermediate devices from
remaining ones of the intermediate devices, each MI-STP BPDU containing a spanning
tree instance identifier;
processing the received MI-STP BPDU messages at the one or more intermediate
devices so as to define a loop-free path for each spanning tree instance identifier;
mapping, in response to defining a loop-free path for each spanning tree instance
identifier, each VLAN designation of the computer network to a spanning tree instance
identifier; and
distributing messages tagged with a given VLAN designation across the loop-free
path for the spanning tree instance identifier to which the given VLAN designation
is mapped.
2. The method of claim 1 further comprising the step of configuring one or more
intermediate devices with the spanning tree instance identifiers for the computer network.
3. The method of claim 1 further comprising the step of configuring one or more
intermediate devices with the mapping of VLAN designations to spanning tree instance identifiers.
4. The method of claim 3 wherein the step of configuring is performed by a VLAN
distribution protocol.
5. The method of claim 4 wherein the VLAN distribution protocol is the VLAN Trunk
Protocol (VTP).
6. The method of claim 1 wherein the step of processing received MI-STP BPDU
messages comprises the steps of:
electing a root device for each spanning tree instance;
identifying a root port at each intermediate device for each spanning tree instance,
each root port providing a lowest cost path to the root device of the respective
spanning tree instance;
identifying zero, one or more designated ports at each intermediate device for
each spanning tree instance; and
transitioning the root port and each designated port for each spanning tree instance
at the intermediate devices to a forwarding spanning tree port state.
7. The method of claim 6 further comprising the step of transitioning all non-root
and non-designated ports for each spanning tree instance to a blocking spanning
tree port state.
8. The method of claim 7 further comprising the step of, in response to receiving
a conventional configuration BPDU message at a given intermediate device, forwarding
the conventional configuration BPDU message from all designated ports of the intermediate
device for a selected spanning tree instance.
9. The method of claim 1 wherein at least one MI-STP BPDU message for a given
spanning tree instance has a VLAN mapping message unit that includes each VLAN
designation mapped to the given spanning tree instance.
10. The method of claim 1 wherein each MI-STP BPDU message includes a destination
service access point (DSAP) that contains a value other than the DSAP value specified
in the IEEE 802.1D standard for configuration BPDU messages so that MI-STP BPDU
messages received by legacy intermediate devices are dropped and not processed.
11. The method of claim 1 further comprising the step of blocking traffic associated
with a VLAN designation that is mapped to more than one spanning tree instance.
12. The method of claim 1 further comprising the steps of waiting a preselected
time before distributing messages tagged with a given VLAN designation to confirm
that the VLAN mapping is correct.
13. The method of claim 12 wherein the VLAN mapping is considered correctly mapped
provided that no MI-STP BPDUs are received within the preselected time that map
the given VLAN designation to either a different spanning tree instance identifier
or to no spanning tree instance identifier.
14. The method of claim 12 wherein the preselected time is a forward delay time
specified in the MI-STP BPDU.
15. The method of claim 1 further comprising the step of tunneling untagged IEEE
bridge protocol data unit (BPDU) messages utilizing the loop-free path of a preselected
spanning tree instance identifier.
16. The method of claim 15 wherein the step of tunneling comprises the step of
forwarding the IEEE BPDU message unmodified from each intermediate device port
that is in the forwarding state for the preselected spanning tree instance identifier
other than the port on which the IEEE BPDU message was received.
17. The method of claim 16 further comprising the steps of:
examining a topology change (TC) flag of IEEE BPDU messages received at a given
intermediate device; and
for each spanning tree instance for which the given intermediate device is the
root, setting a TC flag of the MI-STP BPDU messages sourced by the given intermediate
device as the root.
18. The method of claim 15 further comprising the step of tunneling un-tagged
IEEE Topology Change Notification (TCN) messages utilizing the loop-free path of
the preselected spanning tree instance identifier.
19. The method of claim 1 further comprising the step of tunneling BPDU messages
that are tagged with a given VLAN designation along the loop-free path established
for the spanning tree instance to which the given VLAN designation is mapped.
20. The method of claim 19 further comprising the steps of:
examining a topology change (TC) flag of BPDU messages tagged with a VLAN designated
and received at a given intermediate device; and
provided that the given intermediate device is the root for the spanning tree
instance to which the VLAN of the BPDU message is mapped, setting a TC flag of
the MI-STP BPDU messages sourced by the given intermediate device the spanning
tree instance.
21. The method of claim 19 further comprising the step of tunneling IEEE Topology
Change Notification (TCN) messages tagged with the given VLAN designation along
the loop-free path established for the spanning tree instance to which the given
VLAN designation is mapped.
22. An intermediate device for use in a computer network having a plurality of
virtual local area network (VLAN) designations, the intermediate device comprising:
a plurality of ports for use in interconnecting the intermediate device to the
computer network;
a spanning tree engine in communicating relationship with the plurality of ports,
wherein the spanning tree engine is configured to:
generate and send from the plurality of ports one or more multiple instance spanning
tree protocol bridge protocol data unit (MI-STP BPDU) messages, each MI-STP BPDU
containing a spanning tree instance identifier; and
process received MI-STP BPDU message so as to cooperate in establishing a loop-free
path for each spanning tree instance identifier; and
a VLAN association engine for mapping, in response to defining a loop-free path
for each spanning tree instance identifier, each VLAN designation to a spanning
tree instance identifier so that messages tagged with a given VLAN designation
may be forwarded along the loop-free path established for the spanning tree instance
identifier to which the given VLAN designation is mapped.
23. The intermediate device of claim 22 further comprising at least one memory
structure configured to store the mapping of VLAN designations to spanning tree instances.
24. The intermediate device of claim 23 further comprising a plurality of state
machines, each state machine associated with a spanning tree instance and configured
to transition the ports of the device among a plurality of spanning tree port states,
including a blocking, a listening, a learning and a forwarding spanning tree port
state, in response to the processing of received MI-STP BPDU messages by the spanning
tree engine.
25. The intermediate device of claim 23 further comprising means for blocking
messages tagged with a given VLAN designation upon determining that the given VLAN
is mapped to zero or more than one spanning tree instance.
26. A computer readable medium containing executable program instructions for
creating multiple spanning trees within a computer network, each spanning tree
defining a loop-free path among a plurality of intermediate devices within the
network, the network configured with a plurality of virtual local area network
(VLAN) designations, the executable program instructions comprising steps for:
processing received multiple instance spanning tree protocol bridge protocol
data unit (MI-STP BPDU) messages, each MI-STP BPDU containing a spanning tree instance
identifier, so as to define a loop-free path for each spanning tree instance identifier;
mapping, in response to defining a loop-free path for each spanning tree instance
identifier, each VLAN designation of the computer network to a spanning tree instance
identifier; and
distributing messages tagged with a given VLAN designation across the loop-free
path for the spanning tree instance identifier to which the given VLAN designation
is mapped.
27. An intermediate device for use in a computer network having a plurality of
virtual local area network (VLAN) designations, the intermediate device comprising:
a plurality of ports for use in interconnecting the intermediate device to the
computer network;
means for generating and sending from the plurality of ports one or more multiple
instance spanning tree protocol bridge protocol data unit (MI-STP BPDU) messages,
each MI-STP BPDU containing a spanning tree instance identifier;
means for processing received MI-STP BPDU message so to transition the ports
among a plurality of spanning tree port states, including blocking, listening,
learning and forwarding states, for each spanning tree instance;
means for mapping, in response to defining a loop-free path for each spanning
tree instance identifier, each VLAN designation to a spanning tree instance identifier; and
means for forwarding messages tagged with a given VLAN designation from ports
in the forwarding spanning tree port state for the spanning tree instance to which
the given VLAN designation is mapped.
Description
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is related to the following co-pending, commonly owned U.S.
Patent Applications:
- U.S. patent application Ser. No. 08/997,297 entitled SHARED SPANNING
TREE PROTOCOL, filed Dec. 23, 1997; and
- U.S. patent application Ser. No. 09/283,111 entitled METHOD AND APPARATUS
FOR PROVIDING FAST SPANNING TREE RE-STARTS, filed Mar. 31, 1999.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer networks and, more specifically,
to a protocol for defining multiple instances of loop-free paths within a computer network.
2. Background Information
Many organizations, including businesses, governments and educational institutions,
utilize computer networks so that employees and others may share and exchange information
and/or resources. A computer network typically comprises a plurality of entities
interconnected by means of one or more communications media. An entity may consist
of any device, such as a computer, that "sources" (i.e., transmits) or "sinks"
(i.e., receives) data frames over the communications media. A common type of computer
network is a local area network ("LAN") which typically refers to a privately owned
network within a single building or campus. LANs typically employ a data communication
protocol (LAN standard), such as Ethernet, FDDI or token ring, that defines the
functions performed by data link and physical layers of a communications architecture
(i.e., a protocol stack). In many instances, several LANs may be interconnected
by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form
a wide area network ("WAN") or internet that may span an entire country or continent.
One or more intermediate devices is often used to couple LANs together and allow
the corresponding entities to exchange information. For example, a switch may be
utilized to provide a "switching" function for transferring information, such as
data frames, among entities of a computer network. Typically, the switch is a computer
and includes a plurality of ports that couple the switch to the other entities.
The switching function includes receiving data at a source port from an entity
and transferring that data to at least one destination port for receipt by another entity.
In addition, most computer networks include redundant communications paths so
that a failure of any given link does not isolate any portion of the network. Such
networks are typically referred to as meshed or partially meshed networks. The
existence of redundant links, however, may cause the formation of circuitous paths
or "loops" within the network. Loops are highly undesirable because data frames
may traverse the loops indefinitely.
Furthermore, some devices, such as bridges or switches, replicate frames
whose destination is not known resulting in a proliferation of data frames along
loops. The resulting traffic effectively overwhelms the network. Other intermediate
devices, such as routers, that operate at higher layers within the protocol stack,
such as the Internetwork Layer of the Transmission Control Protocol/Internet Protocol
("TCP/IP") reference model, deliver data frames and learn the addresses of entities
on the network differently than most bridges or switches, such that routers are
generally not susceptible to sustained looping problems.
Spanning Tree Algorithm
To avoid the formation of loops, most bridges and switches execute a spanning
tree algorithm which allows them to calculate an active network topology that is
loop-free (i.e., a tree) and yet connects every pair of LANs within the network
(i.e., the tree is spanning). The Institute of Electrical and Electronics Engineers
(IEEE) has promulgated a standard (the 802.1D standard) that defines a spanning
tree protocol to be executed by 802.1D compatible devices. In general, by executing
the IEEE spanning tree protocol, bridges elect a single bridge to be the "root"
bridge. Since each bridge has a unique numerical identifier (bridge ID), the root
is typically the bridge with the lowest bridge ID. In addition, for each LAN coupled
to more than one bridge, only one (the "designated bridge") is elected to forward
frames to and from the respective LAN. The designated bridge is typically the one
closest to the root. Each bridge also selects one port (its "root port") which
gives the lowest cost path to the root. The root ports and designated bridge ports
are selected for inclusion in the active topology and are placed in a forwarding
state so that data frames may be forwarded to and from these ports and thus onto
the corresponding paths or links of the network. Ports not included within the
active topology are placed in a blocking state. When a port is in the blocking
state, data frames will not be forwarded to or received from the port. A network
administrator may also exclude a port from the spanning tree by placing it in a
disabled state.
To obtain the information necessary to run the spanning tree protocol, bridges
exchange special messages called configuration bridge protocol data unit (BPDU)
messages. FIG. 1 is a block diagram of a conventional BPDU message 100.
The BPDU message 100 includes a header 102 compatible with the Media
Access Control (MAC) layer of the respective LAN standard. The header 102
comprises a destination address (DA) field 104, a source address (SA) field
106, a Destination Service Access Point (DSAP) field 108, and a Source
Service Access Point (SSAP) 110, among others. The DA field 104 carries
a unique bridge multicast destination address assigned to the spanning tree protocol,
and the DSAP and SSAP fields 108, 110 carry standardized identifiers
assigned to the spanning tree protocol. Appended to header 102 is a BPDU
message area 112 that also contains a number of fields, including a Topology
Change Acknowledgement (TCA) flag 114, a Topology Change (TC) flag 116,
a root identifier (ROOT ID) field 118, a root path cost field 120,
a bridge identifier (BRIDGE ID) field 122, a port identifier (PORT ID) field
124, a message age (MSG AGE) field 126, a maximum age (MAX AGE) field
128, a hello time field 130, and a forward delay (FWD DELAY) field
132, among others. The root identifier field 118 typically contains
the identifier of the bridge assumed to be the root and the bridge identifier field
122 contains the identifier of the bridge sourcing (i.e., sending) the BPDU.
The root path cost field 120 contains a value representing the cost to reach
the assumed root from the port on which the BPDU is sent and the port identifier
field 122 contains the port number of the port on which the BPDU is sent.
Upon start-up, each bridge initially assumes itself to the be the root and transmits
BPDU messages accordingly. Upon receipt of a BPDU message from a neighboring device,
its contents are examined and compared with similar information (e.g., assumed
root and lowest root path cost) stored by the receiving bridge in non-recoverable
memory. If the information from the received BPDU is "better" than the stored information,
the bridge adopts the better information and uses it in the BPDUs that it sends
(adding the cost associated with the receiving port to the root path cost) from
its ports, other than the port on which the "better" information was received.
Although BPDU messages are not forwarded by bridges, the identifier of the root
is eventually propagated to and adopted by all bridges as described above, allowing
them to select their root port and any designated port(s).
In order to adapt the active topology to failures, the root periodically (e.g.,
every hello time) transmits BPDU messages. The hello time utilized by the root
is also carried in the hello time field 128 of its BPDU messages. The default
hello time is 2 seconds. In response to receiving BPDUs on their root ports, bridges
transmit their own BPDUs from their designated ports, if any. Thus, every two seconds
BPDUs are propagated throughout the bridged network, confirming the active topology.
As shown in FIG. 1, BPDU messages stored by the bridges also include a message
age field 124 which corresponds to the time since the root instigated this
generation of BPDU information. That is, BPDU messages from the root have their
message age field 124 set to "0". Thus, every hello time, BPDU messages
with a message age of "0" are propagated to and stored by the bridges.
After storing these BPDU messages, bridges proceed to increment the message
age value. When the next BPDU message is received, the bridge examines the contents
of the message age field 124 to determine whether it is smaller than the
message age of its stored BPDU message. Assuming the received BPDU message originated
from the root and thus has a message age of "0", the received BPDU message is considered
to be "better" than the stored BPDU information (whose message age has presumably
been incremented to "2" seconds) and, in response, the bridge proceeds to re-calculate
the root, root path cost and root port based upon the received BPDU information.
The bridge also stores this received BPDU message and proceeds to increment its
message age field 124. If the message age of a stored BPDU message reaches
a maximum age value, the corresponding BPDU information is considered to be stale
and is discarded by the bridge.
Normally, each bridge replaces its stored BPDU information every hello
time, thereby preventing it from being discarded and maintaining the current active
topology. If a bridge stops receiving BPDU messages on a given port (indicating
a possible link or device failure), it will continue to increment the respective
message age value until it reaches the maximum age threshold. The bridge will then
discard the stored BPDU information and proceed to re-calculate the root, root
path cost and root port by transmitting BPDU messages utilizing the next best information
it has. The maximum age value used within the bridged network is typically set
by the root, which enters the appropriate value in the maximum age field 126
of its transmitted BPDU messages 100. Neighboring bridges similarly load
this value in their BPDU messages, thereby propagating the selected value throughout
the network. The default maximum age value under the IEEE standard is twenty seconds.
As BPDU information is up-dated and/or timed-out and the active topology is recalculated,
ports may transition from the blocking state to the forwarding state and vice versa.
That is, as a result of new BPDU information, a previously blocked port may learn
that it should be in the forwarding state (e.g., it is now the root port or a designated
port). Rather than transition directly from the blocking state to the forwarding
state, ports transition through at least two intermediate states: a listening state
and a learning state. In the listening state, a port waits for information indicating
that it should return to the blocking state. If, by the end of a preset time, no
such information is received, the port transitions to the learning state. In the
learning state, a port still blocks the receiving and forwarding of frames, but
received frames are examined and the corresponding location information is stored
in the filtering database, as described above. At the end of a second preset time,
the port transitions from the learning state to the forwarding state, thereby allowing
frames to be forwarded to and from the port. The time spent in each of the listening
and the learning states is referred to as the forwarding delay and is entered by
the root in field 126.
As ports transition between the blocked and forwarding states, entities may appear
to move from one port to another. To prevent bridges from distributing messages
based upon incorrect address information, bridges quickly age-out and discard the
"old" information in their filtering databases. More specifically, upon detection
of a change in the active topology, a bridge begins transmitting Topology Change
Notification Protocol Data Unit (TCN-PDU) messages on its root port. The format
of the TCN-PDU message is well known (see IEEE 802.1D standard) and, thus, will
not be described herein. A bridge receiving a TCN-PDU message sends a TCN-PDU of
its own from its root port, and sets the TCA flag 112 in BPDUs that it sends
on the port from which the TCN-PDU was received, thereby acknowledging receipt
of the TCN-PDU. By having each bridge send TCN-PDUs from its root port, the TCN-PDU
is effectively propagated hop-by-hop from the original bridge up to the root. The
root confirms receipt of the TCN-PDU by setting the TC flag 114 in the BPDUs
that it subsequently transmits for a period of time. Other bridges, receiving these
BPDUs, note that the TC flag 114 has been set, thereby alerting them to
the change in the active topology. In response, bridges significantly reduce the
aging time associated with their filtering databases which, as described above,
contain destination information corresponding to the entities within the network.
Specifically, bridges replace the default aging time of five minutes with the forwarding
delay time, which by default is fifteen seconds. Information contained in the filtering
databases is thus quickly discarded.
Virtual Local Area Networks
A computer network may also be segmented into a series of logical networks. U.S.
Pat. No. 5,394,402, issued Feb. 28, 1995 to Ross (the "'402 patent"), for example,
discloses an arrangement for associating any port of a switch with any particular
network segment. Specifically, according to the '402 patent, any number of physical
ports of a particular switch may be associated with any number of groups within
the switch by using a virtual local area network (VLAN) arrangement that virtually
associates the port with a particular VLAN designation. More specifically, the
'402 patent discloses a switch or hub that associates VLAN designations with its
ports and further associates those VLAN designations with messages transmitted
from any of the ports to which the VLAN designation has been assigned.
The VLAN designation for each port is stored in a memory portion of the switch
such that every time a message is received on a given access port the VLAN designation
for that port is associated with the message. Association is accomplished by a
flow processing element which looks up the VLAN designation in the memory portion
based on the particular access port at which the message was received. In many
cases, it may be desirable to interconnect a plurality of these switches in order
to extend the VLAN associations of ports in the network. The '402 patent, in fact,
states that an objective of its VLAN arrangement is to allow all ports and entities
of the network having the same VLAN designation to exchange messages by associating
a VLAN designation with each message. Thus, those entities having the same VLAN
designation function as if they are all part of the same LAN. Message exchanges
between parts of the network having different VLAN designations are specifically
prevented in order to preserve the boundaries of each VLAN segment or domain. For
convenience, each VLAN designation is often associated with a different color,
such as red, blue, green, etc.
In addition to the '402 patent, the Institute of Electrical and Electronics Engineers
(IEEE) has promulgated the 802.1Q standard for Virtual Bridged Local Area Networks.
The 802.1Q standard, among other things, defines a specific VLAN-tagged message
format for use in VLAN-aware networks.
Having defined a segregated computer network, several "solutions" have been
proposed for overlaying spanning trees on these virtually segregated network groups.
The IEEE 802.1Q standards committee, for example, has proposed defining a single
spanning tree for all VLAN designations in the computer network. That is, the switches
exchange conventional BPDUs in the accustomed manner so as to define a single forwarding
topology irrespective of the various VLAN designations that have been defined for
the network. Thus, either all VLAN tagged frames may be forwarded and received
through a given port or no tagged frames may be forwarded or received through the
port. Since bridges and switches are typically pre-configured to exchange and process
conventional BPDUs, this is a simple solution to implement. It also conserves processing
resources by limiting the computations that must be performed to determine the
bridged network's active topology.
Nonetheless, the IEEE solution has several drawbacks. For example, by
defining a single spanning tree for a network having numerous VLAN designations,
the IEEE solution does not allow for load balancing. That is, all data communication
within the network follows the single forwarding topology defined by the one spanning
tree. This may significantly degrade performance over certain, heavily utilized,
portions of the network, limiting message throughput.
An alternative to the 802.1Q single spanning tree approach is to define a separate
spanning tree for each VLAN designation within the network. This alternative is
currently being implemented within networking equipment from Cisco Systems, Inc.
of San Jose, Calif. See Cisco IOS VLAN Services document. With this approach, BPDUs
are tagged with each of the VLAN designations defined within the network and exchanged
among the switches. That is, as shown in FIG. 1, the BPDU header 102 is
modified by adding a VLAN identifier field 134. Upon receipt, these tagged
BPDUs are then processed by the switches so as to define a separate active topology
or spanning tree for each VLAN designation within the bridged network. Thus, for
a given port, messages associated with one VLAN designation may be forwarded and
received while messages associated with a second VLAN designation may be blocked.
By defining a separate forwarding topology for each VLAN designation which spans
all entities associated with that designation, this solution supports load balancing
throughout the network. It also avoids possible lost connectivity problems with
portions of the network that may occur with the IEEE solution. There are, nonetheless,
other drawbacks. First, this approach may not scale well to large networks. That
is, as the number of VLAN designations increases, the number of tagged BPDUs being
exchanged correspondingly increases. Accordingly, more communications bandwidth
is consumed with BPDU traffic. Each BPDU, moreover, must be processed by the switches
so as to calculate the corresponding spanning trees. Depending on the number of
VLAN designations within the network, this may severely tax the processing and
memory resources of the switches, degrading network efficiency.
SUMMARY OF THE INVENTION
Briefly, the invention relates to a multiple instance spanning tree protocol
(MI-STP) for creating a plurality of active topologies (i.e., loop-free paths)
within a bridged computer network. These active topologies are established through
the exchange and processing of novel multiple instance spanning tree bridge protocol
data unit messages (MI-STP BPDUs) by the intermediate network devices within the
network. Each MI-STP BPDU contains, among other things, information identifying
the particular instance to which it relates. The active topologies, moreover, are
created independently of any virtual local area network (VLAN) designations defined
for the network. Once the active topologies have been 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. In
a preferred embodiment, at least some of the MI-STP BPDU messages, in addition
to specifying a particular STP instance, also contain a list of the VLAN designations
that are mapped to that instance.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention description below refers to the accompanying drawings, of which:
FIG. 1, previously discussed, is a block diagram of a conventional bridge protocol
data unit message;
FIG. 2 is a highly schematic representation of a computer network;
FIG. 3 is a highly schematic, partial block diagram of an intermediate network
device in accordance with the present invention;
FIGS. 4A-D are a block diagram of a preferred multiple instance spanning tree
bridge protocol data unit message in accordance with the present invention;
FIGS. 5 and 6 are schematic illustrations of preferred memory structures in
accordance with the present invention;
FIG. 7 is a highly schematic representation of a heterogeneous computer network
in which the present invention may be operated; and
FIG. 8 is a flow diagram of the method of the present invention.
DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT
FIG. 2 illustrates a partially meshed computer network
200 in accordance
with the present invention. The network
200 preferably comprises a plurality
of local area networks (LANs)
202-
214 and servers
216, such
as file servers, print servers, etc., interconnected by a plurality of intermediate
devices, such as switches
218-
227. One or more entities or hosts
(not shown) are preferably coupled to each LAN
202-
214 so that the
entities may source or sink data frames to one another or to the servers
216
over the network
200. Each switch
218-
227, moreover, preferably
includes a plurality of ports such that each LAN
202-
214 and server
216 is coupled to at least one port of switches
218-
227.
The network
200 may further include one or more routers
228,
230.
Switches
218-
227 and routers
228,
230 are preferably
interconnected by a series of links
232, such as point-to-point links. Links
232 carry messages, such as data frames, between switches
218-
227
and routers
228,
230. Each switch
218-
227 and router
228,
230, moreover, preferably identifies its own ports, e.g., by
port numbers one, two, three, etc. Switches
218-
227 and routers
228,
230 are thus able to associate specific ports with the LANs, switches, routers,
servers, etc. coupled thereto.
It should be understood that the network
200 of FIG. 2 is meant for illustrative
purposes only and that the present invention will operate with other networks having
possibly far more complex topologies.
As set forth in the '402 patent and/or the IEEE 802.1Q standard, selected LANs,
servers and other entities may be segmented within one or more virtual local area
networks (VLANs). For convenience, each VLAN designation may be identified by a
color code, e.g., "R" for red, "B" for blue, "G" for green, "O" for orange, "Y"
for yellow, "V" for violet, "P" for purple, "M" for magenta, etc. Each switch
218-
227,
moreover, associates each port coupled to a LAN or server with at least one VLAN
designation (e.g., a color tag). For example, switches
224 and
227
may each associate their ports coupled to LANs
202 and
212, respectively,
with the "red" VLAN designation, thereby virtually grouping these two LANs together.
Since all entities located on a given LAN (e.g., LAN
202) utilize the same
shared port of the corresponding switch (e.g., switch
224), each of these
entities may also be considered to be associated with the VLAN designation(s) assigned
to that port (e.g., red). Switch
225 may similarly associate its port coupled
to server
216 with the red and blue VLAN designations, thereby allowing
entities associated with either the red or blue VLAN designations to communicate
with this server
216.
Those ports of switches
218-
227 and routers
228,
230
coupled to links
232 are similarly associated with one or more VLAN designation(s).
The VLAN designations associated with these ports preferably correspond to the
VLANs that are reachable through that port. For example, switch
223 may
associate its port coupled to switch
227 via link
232 with at least
the red VLAN designation to provide connectivity to LAN
212 which is associated
with the red VLAN designation.
To identify the various VLAN designations defined throughout the network
200,
switches
218-
227 and routers
228,
230 preferably participate
in some type of VLAN configuration protocol, such as the VLAN Trunk Protocol (VTP)
from Cisco Systems, Inc. or the GARP VLAN Registration Protocol (GVRP), that informs
each switch and router of the current state of VLAN designations in use throughout
the network
200. The VTP protocol is described in
White Paper: VLAN Trunk
Protocol from Cisco Systems, Inc. (Jun. 26, 2000), which is hereby incorporated
by reference in its entirety. In accordance with these protocols, each switch
218-
227
and router
228,
230 transmits predefined advertisements containing
information regarding the current VLAN configuration at the sourcing device. By
listening for the advertisements, devices may learn of any reconfiguration of the
network
200, including the deletion of an existing VLAN or changes to the
membership of an existing VLAN. Thus, the current association of VLAN designations
may be quickly propagated to all intermediate devices.
In addition, each switch
218-
227 preferably maintains a list of
pre-defined numeric identifiers (e.g., numbers) that are available for assignment
as VLAN IDs. As each VLAN designation (e.g., color code) is established by the
network administrator, a particular numeric identifier is assigned thereto from
the list. The list thus represents the maximum number of VLAN designations that
may be supported within the network
200. For example, the IEEE 802.1Q draft
standard specifies a list from "0" to "4095" and thus allows for 4096 different
VLAN IDs. The first VLAN designation that is established (e.g., red) may be assigned
to number "3" and the second VLAN (e.g., blue) may be assigned number "25". The
green, orange, violet and yellow VLAN designations may be assigned to numbers "50",
"51", "79" and "81", and so on.
Once the VLAN designations within network
200 have been established,
any entity associated with a given VLAN designation (e.g., red) may exchange messages
with any other similarly designated entity, even though the two entities may be
physically remote from each other and interconnected by switches that are coupled
to other VLANs. Inter-VLAN traffic (e.g., communication from a "red" designated
entity to a "blue" designated entity), if permitted, is preferably performed only
by the routers
228,
230, which can generally implement higher level
functionality that switches
218-
227.
As shown, network
200 includes redundant links interconnecting switches
218-
227. For example, switch
224 is connected to switch
226
along at least two different paths; first, via switch
222 alone and second,
via switches
220,
218,
219 and
223. Similarly, servers
216 are each preferably coupled to the network
200 by more than one
link. The existence of such redundant links prevents portions of the network
200
from becoming isolated should any constituent link fail. Such redundancy, however,
also results in the creation of loops, which, as described above, are highly undesirable.
Execution of the spanning tree algorithm will prevent loops by defining
a loop-free network topology (i.e., an active topology). As set forth above, however,
current implementations of the spanning tree algorithm are limited to either a
single loop-free topology which precludes load balancing of network traffic or
a separate loop-free topology for every VLAN designation which may result in the
consumption of substantial communications bandwidth and processor resources. To
avoid these disadvantages and to improve the efficient distribution of messages
throughout the network
200, among other reasons, at least some of the intermediate
network devices (e.g., the switches, bridges, etc.) of network
200 execute
a Multiple Instance Spanning Tree Protocol (MI-STP) in accordance with the present invention.
FIG. 3 is a partial block diagram of switch
227. Switch
227 includes
a plurality of ports
302a-
302e each of which is preferably
identified by a number (e.g., port numbers 1 through 5). One or more frame transmission
and reception objects, designated generally
304, are associated with the
ports
302a-e such that network messages, including data frames, received
at a given port
302 may be captured, and frames to be transmitted by switch
227 may be delivered to a given port
302. Frame reception and transmission
objects
304 are preferably message storage structures, such as priority
queues. In the illustrated embodiment, switch
227 includes transmitting
and receiving circuitry, including one or more network interface cards (NICs) establishing
ports for the exchange of network messages, one or more or central processing units
(CPUs) and/or microprocessors and associated memory devices for performing calculations
and one or more bus structures.
Switch
227 further includes at least one protocol entity
306
comprising a plurality of components. In particular, the protocol entity
306
includes at least one multiple instance spanning tree protocol (MI-STP) engine
308, at least one VLAN association engine
310 and at least one forwarding
engine
312. The MI-STP engine
308 preferably includes a plurality
of state machines (SMs)
314 for use in executing the MI-STP. The MI-STP
engine
308 is also in communicating relationship with a non-volatile memory
(NVRAM)
315 and at least one run-time memory
316. NVRAM
315
includes a plurality of records or cells, such as array
317, for storing
default spanning tree related information or parameters including an identifier
for each multiple spanning tree instance within network
200 (FIG. 2), as
well as more conventional spanning tree related information or parameters, such
as the switch's numeric bridge identifier (ID), the assigned path cost for each
port
302a-e, default hello time, maximum age time, etc. Run-time
memory
316 includes a spanning tree memory space
318 that is configured
to contain one or more VLAN association tables
320 and one or more MI-STP
instance tables
322. As described below, VLAN association table
320
maintains the association of VLAN designations with spanning tree instances, while
MI-STP table
322 maintains the current or "best" spanning tree information
for each spanning tree instance.
The forwarding engine
312 is in communicating relationship with the frame
transmission and reception objects
304 and is coupled to at least one forwarding
database
324 that stores address information corresponding to the entities
of network
200 (FIG. 2). Specifically, forwarding database
324 has
a plurality of records or cells (not shown), including a destination address cell,
a destination port cell and a corresponding timer cell. Each record or cell in
the forwarding database
324 preferably corresponds to a particular network
entity. Forwarding database
324 may also contain the association of VLAN
designations to ports
302a-e.
The forwarding engine
312 is configured to switch or bridge data frames
from a source port
302 to one or more destinations ports
302 depending
on information contained in the forwarding database
324 and also on the
spanning tree port states of the respective ports
302 as managed by MI-STP
engine
308. Forwarding engine
312 also relays messages received at
ports
302 relating to the MI-STP to the MI-STP engine
308 with which
the forwarding engine
312 is also in communicating relationship.
It will be understood to those skilled in the art that run-time memory
316
and forwarding database
324 may be implemented as a content addressable
memory (CAM) devices and that MI-STP engine
308, VLAN association engine
310 and forwarding engine
312 may each comprise registers and combinational
logic configured and arranged to produce sequential logic circuits. In the illustrated
embodiment, engines
308,
310 and
312 are preferably software
modules or libraries containing program instructions pertaining to the methods
described herein and executable by one or more processing elements of switch
227
(not shown). Other computer readable media may also be used to store and execute
these program instructions. Nonetheless, those skilled in the art will recognize
that other combinations of software and hardware may be utilized to implement the
present invention.
Suitable intermediate network device platforms for use with the present
invention include, but are not limited to, the commercially available Catalyst
5000 and
6000 series of switches from Cisco Systems, Inc. of San
Jose, Calif.
FIG. 4A is a block diagram of a preferred multiple instance spanning tree protocol
bridge protocol data unit message (MI-STP BPDU)
400. The MI-STP BPDU 400
includes a header
402 that preferably complies with the Media Access Control
(MAC) standard. Header
402 includes a destination address (DA) field
404,
a source address (DA) field
406, a destination SAP (DSAP) field
408,
a source SAP (S SAP) field
410, a control field
411, an organization
unique identifier (OUI) field
412, a protocol type field
413, a protocol
identifier (ID) field
414 and a protocol version field
415. Those
skilled in the art will recognize that header
402 may include additional
fields, such as a length field, padding field, etc. Appended to header
402
is a message area
416. In the preferred embodiment, the message area
416
is configured in type-length-value (TLV) format. That is, message area
416
has one or more message units
418,
420 each of which has a type field
422 that is encoded with a value specifying what type of message unit it
is, a length field
424 specifying the length of the respective message unit,
and a value field
426 that contains the particular information of the message unit.
FIG. 4B is a block diagram of a configuration TLV message unit
428. Configuration
TLV
428 may be appended to header
402 in order to form an MI-STP
BPDU
400. The configuration TLV
428 has a plurality of fields, including
a type field
430 which may be encoded with a first value, e.g., "0", selected
to indicate that this message unit is a configuration TLV, and a length field
432
specifying the length of the configuration TLV
428. The configuration TLV
428 also has a "value" portion that is organized into its own fields, including
one or more flag fields
434, such as a Topology Change Acknowledgment (TCA)
and a Topology Change (TC) flag. The value portion of TLV message unit
428
also has a root identifier (ID) segment
436 that comprises a root priority
field
438, an STP instance ID field
440, a root ID field
442
and a root path cost field
444. A bridge ID segment
446 includes
a bridge priority field
448, an STP instance ID field
450 and a bridge
ID field
452. The configuration TLV
428 also includes a port ID field
454, a message age field
456, a max age field
458, a hello
time field
460 and a forward delay field
462.
FIG. 4C is a block diagram of a VLAN mapping TLV message unit
464. The
VLAN mapping TLV
464 has a type field
466 that may be encoded with
another value, e.g., "2", to indicate it is a VLAN mapping TLV, and a length field
468 specifying the length of TLV
464. The value portion of VLAN mapping
TLV
464 may include an STP instance ID field
470, a revision field
472 and a VLAN mapping field
474.
FIG. 4D is a block diagram of a Topology Change Notification (TCN) TLV message
unit
476. TCN TLV
476 has a type field
478 that may be encoded
with another value, e.g., "1", to indicate it is a TCN TLV, and a length field
480 specifying the length of TLV
476. As a value, the TCN TLV
476
has an STP instance ID field
482.
Creation of Multiple Spanning Tree Instances within the Bridged Network
FIG. 8 is a flow diagram of the method of the present invention. Upon start-up
of switch
227, the MI-STP engine
302 preferably accesses NVRAM
315
to determine how many STP instances have been defined and their identity. NVRAM
315 may be preconfigured with this information by a network administrator
working either locally or remotely to switch
227. Alternatively, switch
227 may obtain this information from some MI-STP source device within network
200. This source may transmit advertisement messages to the switches
218-
227
in order to distribute the MI-STP instance information. In the preferred embodiment,
switches
218-
227 support up to 16 spanning tree instances, and each
instance is assigned or otherwise has a unique 12-bit identifier. After retrieving
the MI-STP instance identifiers, engine
308 preferably establishes a separate
state machine
314 for each instance. Each state machine
314, which
corresponds to a particular MI-STP instance, preferably maintains a spanning tree
port state for each non-disabled port
302a-e of switch
227.
Initially, the state machines
314 transition each port
302a-e
to a stable (i.e., non-transitory), non-forwarding state, such as the blocking
spanning tree port state.
For each MI-STP instance identified in its NVRAM
315, the MI-STP engine
308 generates (e.g., "builds") an MI-STP BPDU 400 having a header
402
and a configuration TLV
428, as indicated at block
802 (FIG. 8).
The fields of the configuration TLV
428 are loaded based on the assumption
that switch
227 is the root for the respective MI-STP instance. These MI-STP
BPDUs 400 are then forwarded from each port
302a-e of switch
227
that is not disabled. More specifically, within the DA field
404 of the
header
402 of these MI-STP BPDUs
400, the MI-STP engine
308
enters a multicast address that will cause other switches within network
200
to capture and process the MI-STP BPDU
400. The MI-STP engine
308
should use the multicast bridge address specified by the IEEE 802.1D standard for
use with conventional configuration BPDU messages. In the SA field
406,
the MI-STP engine
308 preferably loads the MAC address for switch
227.
In the DSAP and SSAP fields
408,
410, the MI-STP engine
308
preferably loads values that differ from the DSAP and SSAP values utilized in conventional
configuration BPDUs. For example, rather than using the conventional hexadecimal
values of "42" for both DSAP and SSAP, the MI-STP engine
308 may load both
the DSAP and SSAP fields
408,
410 with the hexadecimal value "AA".
As explained below, by utilizing DSAP and SSAP values that differ from those specified
in the IEEE 802.1D standard for conventional configuration BPDUs, the present invention
achieves desired interoperability characteristics between MI-STP compliant switches
218-
227 and conventional or "legacy" intermediate devices. Engine
308 loads the control field
411 with the value "03", OUI field
412
in a conventional manner, and protocol type field
413 with a designator
associated with MI-STP, e.g., "0116". In the protocol ID and protocol version fields
414,
415, the MI-STP engine
308 may load the hexadecimal values
"00-00" and "00" respectively.
Within the configuration TLV
428 (FIG. 4B) portion of the MI-STP BPDU
400, the MI-STP engine
308 loads the type field
430 with the
encoded value assigned to configuration TLVs (i.e., "0"). In the length field
432,
the engine
308 specifies the length, preferably in octets, of configuration
TLV
428. The flag(s) field
434 is preferably de-asserted or set to
null. In the root priority field
438, the MI-STP engine
308 loads
the settable priority component of the numeric identifier for the switch assumed
to be the root for this MI-STP instance. In this case, engine
308 assumes
that it (i.e., switch
227) is the root and therefore loads its own identifier
in field
438. In the STP instance ID field
442, the MI-STP engine
308 loads the identifier for the MI-STP instance for which this MI-STP BPDU
400 is being generated. In the preferred embodiment, the MI-STP instance ID is
located or specified within the bit range of the locally assigned system ID extension
of the switch's priority value. This bit range, which is defined in the IEEE P802.1t
draft supplement to the 802.1ID standard, is well known to those skilled in the
art to which the invention pertains. In the root ID field
442, engine
308
loads the non-settable component of the numeric identifier assigned to the switch
assumed to be the root for this MI-STP instance. Here, switch
227 assumes
that it is the root and loads its own bridge identifier in field
442. In
the root path cost field
444, engine
308 loads the cost for reaching
the assumed root from the port through which the MI-STP BPDU message will be sent
(in this case zero as switch
227 assumes that it is the root). In the bridge
priority field
448, the engine
308 enters the settable priority component
of the switch's numeric identifier (i.e., the settable component for switch
227)
which will be sending the MI-STP BPDU 400. In the STP instance ID field
450,
engine
308 loads the identifier for the MI-STP instance for which this MI-STP
BPDU 400 is being generated. As described above in connection with field
440,
the MI-STP instance ID is located or specified within the bit range of the locally
assigned IEEE 802.1t system ID extension. The STP instance ID of field
450
is thus the same as field
440 and may be used by receiving devices as a
check. In the bridge ID field
442, engine
308 loads the non-settable
component of the numeric identifier assigned to switch
227 (i.e., the switch
sourcing MI-STP BPDU 400). In the port ID field
454, engine
308 loads
the identifier associated with the port, e.g., port
302d, from which
the MI-STP BPDU 400 will be sourced. Fields
456-
462, which contain
conventional spanning tree parameters, are loaded with corresponding values from
NVRAM
315. The MI-STP engine
308 also enters the assumed spanning
tree data from the configuration TLV into the MI-STP table
322 of its run-time
memory
316.
FIG. 5 is a highly schematic representation of MI-STP table
322, which
is arranged as an array having a plurality of rows
502 and columns
504-
508
that define a plurality of records or cells. Each row
502, moreover, is
associated with a spanning tree instance. In particular, the records constituting
first column
504 contain the spanning tree instance identifier (e.g., 1-16).
The records constituting second column
506 contain spanning tree information
associated with the respective spanning tree instance, such as root, root port,
root path cost, etc. The records constituting third column
508 contain the
VLANs mapped to the respective spanning tree instance. Preferably, third column
508 has a first sub-column
508a containing a revision number
and a second sub-column
508b containing a list of mapped VLANs. The
list of mapped VLANs of second sub-column
508b may be a linked list
of pointers to the corresponding VLAN designation identifiers. The MI-STP engine
308 preferably loads the spanning tree information column
506 of
table
322 with the data from the configuration TLV
428 (e.g., root,
root port, root path cost, etc.).
The MI-STP BPDU 400 with configuration TLV
428 generated by switch
227
is then forwarded from the port specified in field
454 (i.e., port
302d).
That is, engine
308 hands the MI-STP BPDU 400 to the forwarding engine
312,
which, in turn, passes it to the frame transmission and reception objects
304
for queuing and ultimate tran
