Optimal SYNC for rapid spanning tree protocol

RELATED CASE

0001This Application is a divisional of, and claims priority to, co-pending U.S. patent application Ser. No. 10/012,006 to Shyamasundar S. Kaluve et al., filed Dec. 6, 2001.

BACKGROUND OF THE INVENTION

00021. Field of the Invention

0003The present invention relates generally to computer networks, and more specifically, to a method and apparatus for quickly and efficiently resuming the forwarding of network messages despite network changes and failures.

00042. Background Information

0005A computer network typically comprises a plurality of interconnected entities. An entity may consist of any device, such as a computer or end station, that “sources” (i.e., transmits) or “sinks” (i.e., receives) data frames. 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 the 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 intranet that may span an entire country or continent.

0006One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a “bridging” function between two or more LANs. Alternatively, a switch may be utilized to provide a “switching” function for transferring information between a plurality of LANs or end stations. Typically, the bridge or switch is a computer and includes a plurality of ports that couple the device to the LANs or end stations. The switching function includes receiving data from a sending entity at a source port and transferring that data to at least one destination port for forwarding to the receiving entity.

0007Switches and bridges typically learn which destination port to use in order to reach a particular entity by noting on which source port the last message originating from that entity was received. This information is then stored by the bridge in a block of memory referred to as a filtering database. Thereafter, when a message addressed to a given entity is received on a source port, the bridge looks up the entity in its filtering database and identifies the appropriate destination port to reach that entity. If no destination port is identified in the filtering database, the bridge floods the message out all ports, except the port on which the message was received. Messages addressed to broadcast or multicast addresses are also flooded.

0008Additionally, most computer networks are either partially or fully meshed. That is, they include redundant communications paths so that a failure of any given link or device does not isolate any portion of the network. 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, because switches and bridges replicate (i.e., flood) frames whose destination port is unknown or which are directed to broadcast or multicast addresses, the existence of loops may cause a proliferation of data frames so large that the network becomes overwhelmed.

0009Spanning Tree Protocol

0010To avoid the formation of loops, most bridges and switches execute a spanning tree protocol 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 802.1D spanning tree protocol, bridges elect a single bridge within the bridged network to be the “root” bridge. The 802.1D standard takes advantage of the fact that each bridge has a unique numerical identifier (bridge ID) by specifying that the root is 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.

0011To obtain the information necessary to run the spanning tree protocol, bridges exchange special messages called configuration bridge protocol data unit (BPDU) messages. More specifically, upon start-up, each bridge initially assumes itself to 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 nonrecoverable 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).

0012In order to adapt the active topology to changes and failures, the root periodically (e.g., every hello time) transmits 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. That is, 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 a respective message age value until it reaches the maximum age threshold. The bridge will then discard the stored BPDU information and proceed to recalculate 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 its BPDU messages.

0013As BPDU information is updated 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, the 802.1D standard calls for ports to transition through 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 bridge's filtering database. 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.

0014Although the spanning tree protocol provided in the 802.1D standard is able to maintain a loop-free topology despite network changes and failures, re-calculation of the active topology can be a time consuming and processor intensive task. For example, recalculation of the spanning tree following an intermediate device crash or failure can take approximately thirty seconds. During this time, message delivery is often delayed as ports transition between states. Such delays can have serious consequences on time-sensitive traffic flows, such as voice or video traffic streams.

0015Rapid Spanning Tree Protocol

0016Recently, the IEEE promulgated a new standard (the 802.1w standard) that defines a rapid spanning tree protocol (RSTP) to be executed by otherwise 802.1D compatible devices. The RSTP similarly selects one bridge of a bridged network to be the root bridge and defines an active topology that provides complete connectivity among the LANs while severing any loops. Each individual port of each bridge is assigned a port role according to whether the port is to be part of the active topology. The port roles defined by the 802.1w standard include Root, Designated, Alternate and Backup. The bridge port offering the best, e.g., lowest cost, path to the root is assigned the Root Port Role. Each bridge port offering an alternative, e.g., higher cost, path to the root is assigned the Alternate Port Role. Each bridge port providing the lowest cost path from a given LAN is assigned the Designated Port Role, while all other ports coupled to the given LAN in loop-back fashion are assigned the Backup Port Role.

0017Those ports that have been assigned the Root Port and Designated Port Roles are placed in the forwarding state, while ports assigned the Alternate and Backup Roles are placed in a discarding or blocking state. A port assigned the Root Port Role can be rapidly transitioned to the forwarding state provided that all of the ports assigned the Alternate Port Role are placed in the discarding or blocking state. Similarly, if a failure occurs on the port currently assigned the Root Port Role, a port assigned the Alternate Port Role can be reassigned to the Root Port Role and rapidly transitioned to the forwarding state, providing that the previous root port has been transitioned to the discarding or blocking state. A port assigned the Designated Port Role or a Backup Port that is to be reassigned to the Designated Port Role can be rapidly transitioned to the forwarding state, provided that the roles of the ports of the downstream bridge are consistent with this port being assigned the Designated Port Role. The RSTP provides an explicit handshake to be used by neighboring bridges to confirm that a new designated port can rapidly transition to the forwarding state.

0018Like the STP described in the 802.1D specification standard, bridges running RSTP also exchange BPDU messages in order to determine which roles to assign to the bridge's ports. The BPDU messages are also utilized in the handshake employed to rapidly transition designated ports to the forwarding state.

0019<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of a RSTP BPDU message <b>100</b>. The BPDU message <b>100</b> includes a BPDU message header <b>102</b> compatible with the Media Access Control (MAC) layer of the respective LAN standard. The message header <b>102</b> comprises a plurality of fields (not shown), such as a destination address (DA) field and a source address (SA) field. The DA field carries a unique bridge multicast destination address assigned to the spanning tree protocol. Appended to header <b>102</b> is a BPDU message area <b>104</b> that also contains a number of fields, including a protocol identifier (ID) field <b>106</b>, a protocol version number field <b>108</b>, a BPDU type field <b>110</b>, a flags field <b>112</b>, a root ID field <b>114</b>, a root path cost field <b>116</b>, a bridge ID field <b>118</b>, a port ID field <b>120</b>, a message age field <b>122</b>, a maximum age field <b>124</b>, a hello time field <b>126</b>, and a forward delay field <b>128</b>, among others. The root identifier field <b>114</b> typically contains the identifier of the bridge assumed to be the root and the bridge identifier field <b>118</b> contains the identifier of the bridge sourcing (i.e., sending) the BPDU <b>100</b>. The root path cost field <b>116</b> 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 <b>120</b> contains the identifying number of the port from which the BPDU is sent.

0020As shown, the flags field <b>112</b> carries a plurality of single or multiple bit flags that may be set, e.g., asserted, or cleared, e.g., deasserted. Specifically, the flags field <b>112</b> includes a topology change flag <b>130</b>, a proposal flag <b>132</b>, a port role flag <b>134</b>, a learning flag <b>136</b>, a forwarding flag <b>138</b>, an agreement flag <b>140</b> and a topology change acknowledgment (ACK) flag <b>142</b>. The learning and forwarding flags <b>136</b> and <b>138</b> are set to reflect the current port state of the port from which the corresponding BPDU is being sent.

0021The handshake utilized by adjacent bridges for rapidly transitioning designated ports typically proceeds as follows. When an upstream bridge wishes to rapidly transition a designated port to the forwarding state, it issues a BPDU <b>100</b> from that port whose proposal flag <b>132</b> is asserted. The port role flag <b>134</b> is set to the value associated with the Designated Port Role. In the root ID and root path cost fields <b>114</b> and <b>116</b>, the upstream bridge loads the corresponding information relative to the port from which the BPDU message <b>100</b> is to be sent. The upstream bridge then sends the BPDU message which is received at the neighboring downstream bridge.

0022Assuming the information contained in the BPDU message <b>100</b> is equal to or better than that currently stored by the port of the downstream bridge at which the BPDU is received, the downstream bridge asserts “sync” for all of its other bridge ports. Sync is a state machine variable defined by the 802.1w specification standard. Basically, this has the effect of causing the downstream bridge to transition all of its designated ports, other than “edge” ports, to the discarding state. An edge port is defined as a port which provides the only connection to a respective LAN, thereby representing an edge of the bridged network. Once the designated ports have been transitioned to the discarding state, the downstream bridge responds typically through its root port to the upstream bridge with a BPDU message <b>100</b> whose agreement flag <b>140</b> is asserted. This notifies the upstream bridge that the downstream bridge is in agreement with the respective port of the upstream bridge being transitioned to the forwarding state.

0023In addition, the designated port(s) of the downstream bridge request permission from their downstream bridges to rapidly transition back to the forwarding state following the same process. That is, BPDU messages <b>100</b> with their proposal flags <b>132</b> asserted are sent from these ports. In effect, a “cut” is made in the active topology at the first affected designated port and the cut propagates down from this first designated port through all bridges on the subtree below it, i.e., in a direction away from the root, until the cut reaches the edge of the bridged network.

SUMMARY OF THE INVENTION

0024Briefly, the present invention is directed to an optimization of the rapid spanning tree protocol (RSTP). An intermediate network device operating in accordance with the present invention preferably includes a plurality of ports for receiving and forwarding messages and a spanning tree protocol (STP) engine in communicating relationship with the ports. The STP engine includes a port role selection state machine for assigning RSTP roles to the ports and a port transition state machine for transitioning the ports among a plurality of RSTP states, including a discarding or blocking state, a learning state and a forwarding state. If the device receives a bridge protocol data unit (BPDU) message from a designated port of a neighboring intermediate network device and the BPDU message represents a proposal by the neighboring device to rapidly transition its port to the forwarding state, the device recalculates the roles and states of the ports based on the information contained in the received BPDU message. If the device was not previously the root, and does not become the root following the recalculation, then the device invokes the “optimal sync” mechanism of the present invention.

0025Specifically, if the proposal-BPDU message was received on the device's root port and that port remains the root port taking into account the information in the proposal-BPDU message, then the device confirms that its alternate ports are in the blocking state, and returns an agreement BPDU message to the neighboring device. Significantly, the device leaves all of its designated ports, if any, in the forwarding state. If the proposal-BPDU message was received on a non-root port which becomes the root port as a result of the information contained in the proposal-BPDU message, then the device transitions only the previous root port to the blocking or discarding state, and returns an agreement BPDU message to the neighboring device, while again leaving all of its designated ports, if any, in the forwarding state. Because the device has left its designated ports in the forwarding state, as part of the optimal sync mechanism, it need not issue proposal-BPDUs of its own in order to reactivate these ports.

BRIEF DESCRIPTION OF THE DRAWINGS

0026The invention description below refers to the accompanying drawings, of which:

0027<figref idref="DRAWINGS">FIG. 1</figref>, previously discussed, is a block diagram of a conventional bridge protocol data unit (BPDU) message;

0028<figref idref="DRAWINGS">FIG. 2</figref> is a highly schematic representation of a computer network;

0029<figref idref="DRAWINGS">FIG. 3</figref> is a highly schematic, partial block diagram of an intermediate network device in accordance with the present invention; and

0030FIGS. <b>4</b>A-C is a flow diagram of a preferred method of the present invention.

DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT

0031<figref idref="DRAWINGS">FIG. 2</figref> illustrates a partially meshed bridged network <b>200</b> in accordance with the present invention. The network <b>200</b> preferably comprises a plurality of local area networks (LANs) <b>202</b>-<b>210</b> that are interconnected by a plurality of intermediate devices, such as switches <b>212</b>-<b>217</b>. One or more entities or hosts (not shown) are preferably coupled to each LAN <b>202</b>-<b>210</b> so that the entities may source or sink data frames to one another over the network <b>200</b>. Each switch <b>212</b>-<b>210</b>, moreover, preferably includes a plurality of ports <b>302</b> such that each LAN <b>202</b>-<b>210</b> is coupled to at least one port of switches <b>212</b>-<b>217</b>.

0032At least some of the switches <b>212</b>-<b>217</b> may be interconnected by a series of links, such as point-to-point links <b>220</b>-<b>222</b>, rather than by the LANs. Links <b>220</b>-<b>222</b> similarly carry messages, such as data frames, between respective switches. Each switch <b>212</b>-<b>217</b>, moreover, preferably identifies its own ports <b>302</b>, e.g., by port numbers, such as zero, one, two, three, etc. Switches <b>212</b>-<b>217</b> are thus able to associate specific ports with the LANs and/or switches coupled thereto.

0033It should be understood that the network <b>200</b> of <figref idref="DRAWINGS">FIG. 2</figref> is meant for illustrative purposes only and that the present invention will operate with other networks having possibly far more complex topologies.

0034As shown, network <b>200</b> includes redundant links interconnecting switches <b>212</b>-<b>217</b>. For example, switch <b>212</b> is connected to switch <b>215</b> along at least two different paths; first, via switch <b>213</b> alone and second, via switches <b>214</b> and <b>217</b>. The existence of such redundant links prevents portions of the network <b>200</b> from becoming isolated should any constituent link or device fail. Such redundancy, however, also results in the creation of loops, which, as described above, are highly undesirable.

0035Execution of a spanning tree protocol prevents loops by defining a loop-free network topology (i.e., an active topology). Furthermore, execution of the Rapid Spanning Tree Protocol (RSTP) will allow the ports of the switches <b>212</b>-<b>217</b> that are part of the active topology to transition rapidly to a forwarding state so that network messages can be forwarded with minimal disruption and/or delay. However, as set forth above, in some situations, the current implementation of the RSTP may result in certain operating inefficiencies. To avoid these inefficiencies, among other reasons, at least some of the intermediate network devices (e.g., the switches, bridges, etc.) of network <b>200</b> execute an “optimal sync mechanism” in accordance with the present invention.

0036<figref idref="DRAWINGS">FIG. 3</figref> is a partial block diagram of switch <b>214</b>. Switch <b>214</b> includes a plurality of ports <b>302</b><i>a</i>-<b>302</b><i>e </i>each of which is preferably identified by a number (e.g., P<b>0</b>-P<b>4</b>). One or more frame transmission and reception objects, designated generally <b>304</b>, are associated with the ports <b>302</b><i>a</i>-<i>e </i>such that network messages, including data frames, received at a given port, e.g., P<b>3</b>, may be captured, and frames to be transmitted by switch <b>214</b> may be delivered to a given port, e.g., P<b>1</b>. Frame reception and transmission objects <b>304</b> are preferably message storage structures, such as priority queues. In the illustrated embodiment, switch <b>214</b> includes transmitting and receiving circuitry, including one or more line cards and/or 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.

0037Switch <b>214</b> further includes at least one protocol entity <b>306</b> comprising a plurality of components. In particular, the protocol entity <b>306</b> includes at least one spanning tree protocol (STP) engine <b>308</b> and at least one forwarding engine <b>310</b>. The STP engine <b>308</b> preferably comprises a plurality of subcomponents, including a port role selection state machine <b>312</b>, a port transition state machine <b>314</b>, a bridge protocol data unit (BPDU) message generator <b>316</b> and a sync manager <b>318</b>. Except as described herein, the STP engine <b>308</b> preferably operates substantially in compliance with the IEEE 802.1w Rapid Spanning Tree Protocol (RSTP) supplement to the 802.1D specification standard, which is hereby incorporated by reference in its entirety. The STP engine <b>308</b> includes or is in communicating relationship with a memory <b>320</b>, which may be a volatile or non-volatile random access memory (RAM) or some other memory device. Memory <b>320</b> is preferably organized to include a plurality of records or cells (not shown) for storing spanning tree related information or parameters, such as the switch's numeric bridge identifier (ID), the assigned path cost for each port <b>302</b><i>a</i>-<i>e, </i>the current or “best” spanning tree information for each port P<b>0</b>-P<b>4</b>, etc.

0038The forwarding engine <b>310</b> is in communicating relationship with the frame transmission and reception objects <b>304</b> and is coupled to at least one filtering database <b>322</b> that stores address information corresponding to the entities of network <b>200</b> (<figref idref="DRAWINGS">FIG. 2</figref>). Specifically, filtering database <b>322</b> has a plurality of records (not shown) each containing a plurality of cells, including a destination address cell, a destination port cell and a corresponding timer cell. Each record in the filtering database <b>322</b> preferably corresponds to a particular network entity.

0039The forwarding engine <b>310</b> is configured to switch or bridge network messages, such as packets and/or frames, from a source port <b>302</b> to one or more destinations ports <b>302</b> depending on information contained in the forwarding database <b>322</b> and also on the spanning tree port states of the respective ports <b>302</b> as managed by STP engine <b>308</b>. The forwarding engine <b>312</b> is also in communicating relationship with the STP engine <b>308</b> and relays RSTP-related messages received at ports <b>302</b> thereto.

0040It will be understood by those skilled in the art that STP engine <b>308</b> and forwarding engine <b>310</b> may each comprise registers and combinational logic configured and arranged to produce sequential logic circuits. In the illustrated embodiment, engines <b>308</b> and <b>310</b> are preferably software modules or libraries containing program instructions pertaining to the methods described herein and executable by one or more processing elements (not shown) of switch <b>214</b>. Other computer readable media may also be used to store and execute these program instructions. Nonetheless, those skilled in the art will recognize that various combinations of software and hardware, including firmware, may be utilized to implement the present invention.

0041Suitable intermediate network device platforms for use with the present invention include, but are not limited to, the commercially available Catalyst 4000 and 6000 series of switches from Cisco Systems, Inc. of San Jose, Calif.

0042Execution of the RSTP by the switches <b>212</b>-<b>217</b> (<figref idref="DRAWINGS">FIG. 2</figref>) of the bridged network <b>200</b> results in the convergence to an active topology with one device, e.g., switch <b>212</b>, being elected the root. Suppose that port P<b>1</b> of switch <b>214</b> is assigned the Root Port Role and is transitioned to the forwarding state, and that port P<b>0</b> is assigned the Alternate Port Role as it represents an alternate path to root <b>212</b>. Port P<b>0</b> is transitioned to the blocking or discarding state. The terms blocking and discarding are used interchangeably herein. In addition, suppose that ports P<b>2</b>-P<b>4</b> of switch <b>214</b> are assigned the Designated Port Role and that each port is transitioned to the forwarding state.

0043FIGS. <b>4</b>A-C are a flow diagram of a preferred embodiment of the method of the present invention. The optimal sync mechanism of the present invention is invoked in response to receiving a BPDU message <b>100</b> whose proposal flag <b>132</b> is asserted on the current or newly elected root port. This may occur in response to a number of different situations as reflected in <figref idref="DRAWINGS">FIG. 4A</figref>. First, the link <b>221</b> coupled to the current root port, port P<b>1</b>, of switch <b>214</b> may fail, as indicated at block <b>402</b> (<figref idref="DRAWINGS">FIG. 4A</figref>). Alternatively, switch <b>214</b> may stop receiving BPDU messages <b>100</b> on its root port, as indicated at block <b>404</b>. Switch <b>214</b> may also receive a BPDU message <b>100</b> on its root port, port P<b>1</b>, containing “inferior” information (e.g., root ID, root path cost, etc.) to that received on some other port of switch <b>214</b>, suggesting that the other port should be the root port, as indicated at block <b>406</b>. Conversely, a device, such as switch <b>214</b>, which may or may not be the root of the respective bridged network, may receive a BPDU message <b>100</b> that contains “better” information than that previously received on and/or stored for the port on which the BPDU message was received, as indicated at block <b>408</b>. Also, switch <b>214</b> may receive a BPDU message <b>100</b> on its root port that contains even “better” information than that previously received on the root port, thereby causing the root port to remain the root port, as indicated by block <b>410</b>.

0044It should be understood that these situations may be caused by the addition, removal, failure or recovery of network components such as links, switches, etc. and/or the modification of BPDU-related information, such as bridge IDs, path costs, etc., at one or more devices, among other reasons.

0045In response to the situations represented by blocks <b>402</b>, <b>404</b> and <b>406</b>, the port role selection state machine <b>312</b> selects an alternate port, e.g., port P<b>0</b>, to become the new root port for switch <b>214</b>, and reassigns this port to the Root Port Role, as indicated at block <b>412</b>. In response to the situation of block <b>408</b>, the port role selection machine <b>312</b> selects the port on which the “better” BPDU message <b>100</b> was received to become the new root port, and reassigns this port to the Root Port Role, as indicated at block <b>414</b>. The port role selection state machine <b>312</b> also reassigns the previous root port, if any, to a new role, such as the Alternate Port Role or the Designated Port Role, as indicated at block <b>416</b>. Upon reassigning the affected ports to their new roles, the port role selection state machine <b>312</b> then directs the port transition state machine <b>314</b> to transition the RSTP states of those ports in accordance with their new roles. Specifically, the port transition state machine <b>314</b> transitions the previous root port, e.g., port P<b>1</b>, if any, to the blocking state, as indicated at block <b>418</b>. Next, state machine <b>314</b> transitions the newly selected root port, e.g., port P<b>0</b>, to the forwarding state, as indicated at block <b>420</b>.

0046At some point, switch <b>214</b> may also receive a RSTP BPDU message <b>100</b> (<figref idref="DRAWINGS">FIG. 1</figref>) from switch <b>212</b> on its newly selected root port, e.g., port P<b>0</b>, or on its re-confirmed root port, e.g., port P<b>1</b>, as indicated at block <b>422</b>. This RSTP BPDU message <b>100</b> is likely to have the proposal flag <b>132</b> asserted, thereby indicating that neighboring switch <b>212</b> wishes to transition its peer port, i.e., port P<b>3</b> of switch <b>212</b>, rapidly to forwarding. The BPDU message <b>100</b> is passed to the spanning tree protocol engine <b>308</b> of switch <b>214</b> for processing. Engine <b>308</b> preferably determines whether it, i.e., switch <b>214</b>, was the root of the bridged network <b>200</b>, as indicated at decision block <b>424</b>. If it was not just the root, engine <b>308</b> invokes the optimal sync mechanism of the present invention, as indicated by No arrow <b>425</b> leading to block <b>426</b>.

0047Specifically, the sync manager <b>318</b> in cooperation with the port transition state machine engine <b>314</b> confirms that all alternate ports, as well as the previous root port, e.g., port P<b>1</b>, if any, are in the blocking state, as indicated at block <b>428</b> (<figref idref="DRAWINGS">FIG. 4B</figref>). If the previous root port is not in the blocking state, the state machine <b>314</b> may transition it to the blocking state at this time. In the example, the only alternate port is the previous root port, e.g., port P<b>1</b>, and it is already in the blocking state. Next, the sync manager <b>318</b> directs the port transition state machine engine <b>314</b> to leave any designated ports at switch <b>214</b>, e.g., ports P<b>2</b>-P<b>4</b>, in the forwarding state, as indicated at block <b>430</b>. That is, in response to the proposal-BPDU message, the sync manager <b>318</b> does not cause the switch's designated ports to be transitioned to the blocking state.

0048The sync manager <b>318</b> then directs the BPDU message generator <b>316</b> to generate a BPDU message <b>100</b> (<figref idref="DRAWINGS">FIG. 1</figref>) for responding to neighboring switch <b>212</b>, as indicated at block <b>432</b>. The agreement flag <b>140</b> of this BPDU message <b>100</b> is asserted, as also indicated at block <b>432</b>. The spanning tree protocol engine <b>308</b> causes this BPDU message with the agreement flag <b>140</b> asserted to be sent from port P<b>0</b> to neighboring switch <b>212</b>, as indicated at block <b>434</b>, thereby notifying switch <b>212</b> that it may transition its peer port, i.e., port P<b>3</b>, rapidly to forwarding. At this point, processing pursuant to the optimal sync mechanism of the present invention is complete, as indicated by end block <b>436</b>.

0049It should be understood that the proposal-BPDU message <b>100</b> identified in block <b>422</b> (<figref idref="DRAWINGS">FIG. 4A</figref>) might be received at any point in the process, even prior to the conditions corresponding to blocks <b>402</b>-<b>410</b>.

0050It should be further understood that once the optimal sync process is complete, e.g., after the agreement BPDU message <b>100</b> has been returned to the neighboring device <b>212</b>, the port transition state machine <b>314</b> can transition the previous root port, e.g., port P<b>1</b>, at switch <b>214</b> through the learning state to the forwarding state, if, as part of the transition to the new root port, the previous root port was assigned to the Designated Port Role.

0051The optimal sync mechanism of the present invention takes advantage of a condition identified by the inventors for making RSTP more efficient. Specifically, where the affected bridge is not the root of the bridged network and the proposal-BPDU is received on the bridge's existing or newly elected root port, then the only port of the affected bridge that could create a loop in the bridged network is the previous root port or alternate root port(s), if any. Provided that the previous root port and/or all alternate root port(s) are placed or remain in the blocking state, then transitioning the bridge's designated ports to the blocking states (as required under the RSTP specification standard) is unnecessary. Accordingly, with the optimal sync mechanism of the present invention, if the above described conditions are met, i.e., the bridge is not the root, the proposal-BPDU is or had been received on the bridge's root port, and the bridge's previous root port, if any, and all alternate root ports are in the blocking state, then the bridge can leave its designated ports in the forwarding state and still respond to the upstream bridge with an agreement-BPDU without risking the creation of a loop within the bridged network.

0052Returning to decision block <b>424</b> (<figref idref="DRAWINGS">FIG. 4A</figref>), if the bridge receiving the BPDU message <b>100</b> with its proposal flag <b>132</b> asserted was the root prior to processing the BPDU message, then processing moves via Yes arrow <b>438</b> and jump block <b>440</b> to decision block <b>442</b> (<figref idref="DRAWINGS">FIG. 4C</figref>). Here, the STP engine <b>308</b> determines whether the received BPDU message contains better root information, i.e., engine <b>308</b> determines whether the received BPDU message indicates that the switch should no longer consider itself the root of bridged network <b>200</b>. If it does, the conventional sync mechanism is preferably invoked, as indicated by block <b>444</b>. In this case, the sync manager <b>318</b> directs the port transition state machine <b>314</b> to transition all designated ports other than edge ports, e.g., ports P<b>2</b>-P<b>4</b>, to the blocking state, as indicated at block <b>446</b>. The sync manager <b>318</b> then directs the BPDU message generator <b>316</b> to generate a BPDU message <b>100</b> (<figref idref="DRAWINGS">FIG. 1</figref>) for responding to the neighboring switch with its agreement flag <b>140</b> asserted, as indicated at block <b>448</b>. The spanning tree protocol engine <b>308</b> causes this agreement-BPDU message <b>100</b> to be sent to neighboring switch <b>212</b>, as indicated at block <b>450</b>, thereby notifying switch <b>212</b> that it may go ahead and transition its peer port to the forwarding state.

0053Switch <b>214</b> also needs to return its own designated ports to the forwarding state. Accordingly, for each non-edge port, e.g., ports P<b>2</b>-P<b>4</b>, that is assigned to the Designated Port Role, the BPDU message generator <b>316</b> formulates a BPDU message <b>100</b> (<figref idref="DRAWINGS">FIG. 1</figref>) with the proposal flag <b>132</b> asserted, as indicated at block <b>452</b>. These BPDU messages <b>100</b> are sent from the respective designated ports to the downstream bridges, e.g., to switches <b>216</b> and <b>217</b>, as indicated at block <b>454</b>. Assuming the received BPDU messages contain better (or the same) information than that stored by the switches <b>216</b> and <b>217</b>, they respond to switch <b>214</b> with BPDU messages <b>100</b> in which the agreement flag <b>140</b> is asserted. In response to receiving such a BPDU message <b>100</b>, switch <b>214</b> rapidly transitions the respective designated port to the forwarding state, as indicated at block <b>456</b>. Processing is then complete as indicated by end block <b>458</b>.

0054It should be understood that proposal BPDU messages may be sent from the designated ports before the agreement BPDU message is sent.

0055If the STP engine <b>308</b> determines at decision block <b>442</b> that the received proposal-BPDU message contains information indicating that the switch is still the root of the bridged network <b>200</b>, then processing proceeds via No arrow <b>460</b> to block <b>462</b>. In this case, the switch responds with a proposal-BPDU of its own, and receives an agreement-BPDU message from the neighboring switch. Processing is then complete as also indicated by end block <b>458</b>.

0056As shown, use of the present invention prevents the rippling effect of designated ports being transitioned to blocking only to be subsequently re-transitioned back to forwarding. Operation of the conventional RSTP causes such back-and-forth transitioning to occur at each bridge from the point at which the topology is changed out to the leaves of the active topology.

0057It should be understood that, for a root bridge, processing may begin with block <b>422</b> (<figref idref="DRAWINGS">FIG. 4A</figref>).

0058If a proposal-BPDU is received on a port that is not the current root port and the proposal-BPDU does not cause the port on which it was received to become the new root port, e.g., the proposal-BPDU is received on an alternate port, a designated port or a backup port, then it is processed in a conventional manner as provided by the RSTP specification standard.

0059As indicated above, switch <b>214</b> may include a plurality of line cards (not shown) comprising the ports <b>302</b> established at the switch <b>214</b>. Switch <b>214</b> may also include one or more supervisor cards that contain circuitry configured to perform switching and other functions. The line cards and supervisor card may communicate with each other via one or more bus structures. It should be understood that the spanning tree protocol engine <b>308</b> may be disposed entirely on the supervisor card, referred to as a centralized architecture, or it may be distributed across the line cards, referred to as a distributed architecture. Alternatively, the spanning tree protocol engine may be distributed across two or more supervisor cards or across various combinations of supervisor cards and line cards.

0060Multiple Spanning Tree Instances

0061Those skilled in the art understand that the bridged network <b>200</b> may be segregated into a series of logical network segments. U.S. Pat. No. 5,394,402, issued Feb. 28, 1995 (the “'402 Patent”), for example, discloses an arrangement for associating any port of a switch with any particular segregated network group. 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. These VLAN designations are also associated with the messages that are received on these ports. In particular, every time a message is received on one of these ports, the VLAN designation for that port, as stored in a memory portion of the bridge, is associated with the message. For convenience, each VLAN designation is often associated with a different color, such as red, blue, green, etc.

0062In addition to the '402 Patent, the IEEE has promulgated the 802.1Q specification standard for Virtual Bridged Local Area Networks. The IEEE's 802.1Q standard supports VLANs and defines a specific VLAN-tagged message format for transmission on trunks.

0063With the development of VLANs, several “solutions” have been developed 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. Thus, either all VLAN tagged frames may be forwarded and received through a given port or none may be. 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 by certain networking equipment from Cisco Systems, Inc., as described in the Cisco IOS VLAN Services document. With this approach, BPDUs are preferably tagged with each of the VLAN designations defined within the bridged network. Upon receipt, these tagged BPDUs are then processed by the switches so as to define a separate spanning tree or active topology for each VLAN designation within the bridged network. Thus, for a given port, messages associated with one VLAN designation, e.g., blue, may be forwarded and received while messages associated with a second VLAN designation, e.g., green, may be blocked.

0064Rather than providing a separate active topology for each VLAN designation within the bridged network <b>100</b>, it is also possible to define more than one active topology but some number less than the total number of VLAN designations. The Institute of Electrical and Electronics Engineers (IEEE), for example, is working on a Multiple Spanning Trees (MST) protocol, which is identified as the 802.1s supplement (Draft 10, Jun. 16, 2001) to supplement the 802.1Q specification standard, both of which are hereby incorporated by reference in their entirety. In addition to the 802.1s draft supplement, U.S. Pat. No. 6,188,694, titled Shared Spanning Tree Protocol to Michael Fine et al., describes a system in which a plurality of spanning trees are defined and shared by a number of VLAN designations.

0065A switch, such as switch <b>214</b>, running a multiple spanning tree protocol may utilize the optimal sync mechanism of the present invention for one or more of the active topologies or spanning tree instances being implement by the switch <b>214</b>. That is, if the switch <b>214</b> receives a proposal BPDU message on a port that is the root port for any active topology or spanning tree instance, and the other conditions described above are satisfied, the switch preferably invokes the optimal sync mechanism of the present invention.

0066The foregoing description has been directed to specific embodiments of this invention. It will be apparent, however, that other variations and modifications may be made to the described embodiments, with the attainment of some or all of their advantages. Therefore, it is an object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.