This may occur in response to a number of different situations as reflected in FIG. First, the link coupled to the current root port, port P 1 , of switch may fail, as indicated at block FIG. Alternatively, switch may stop receiving BPDU messages on its root port, as indicated at block It should be understood that these situations may be caused by the addition, removal, failure or recovery of network components such as links, switches, etc. In response to the situations represented by blocks , and , the port role selection state machine selects an alternate port, e.
The port role selection state machine 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 Upon reassigning the affected ports to their new roles, the port role selection state machine then directs the port transition state machine to transition the RSTP states of those ports in accordance with their new roles.
Specifically, the port transition state machine transitions the previous root port, e. Next, state machine transitions the newly selected root port, e. This RSTP BPDU message is likely to have the proposal flag asserted, thereby indicating that neighboring switch wishes to transition its peer port, i.
The BPDU message is passed to the spanning tree protocol engine of switch for processing. Engine preferably determines whether it, i. If it was not just the root, engine invokes the optimal sync mechanism of the present invention, as indicated by No arrow leading to block Specifically, the sync manager in cooperation with the port transition state machine engine confirms that all alternate ports, as well as the previous root port, e. If the previous root port is not in the blocking state, the state machine may transition it to the blocking state at this time.
In the example, the only alternate port is the previous root port, e. Next, the sync manager directs the port transition state machine engine to leave any designated ports at switch , e.
That is, in response to the proposal-BPDU message, the sync manager does not cause the switch's designated ports to be transitioned to the blocking state. The agreement flag of this BPDU message is asserted, as also indicated at block The spanning tree protocol engine causes this BPDU message with the agreement flag asserted to be sent from port P 0 to neighboring switch , as indicated at block , thereby notifying switch that it may transition its peer port, i.
At this point, processing pursuant to the optimal sync mechanism of the present invention is complete, as indicated by end block It should be further understood that once the optimal sync process is complete, e. The 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.
Accordingly, with the optimal sync mechanism of the present invention, if the above described conditions are met, i. Returning to decision block FIG. If it does, the conventional sync mechanism is preferably invoked, as indicated by block In this case, the sync manager directs the port transition state machine to transition all designated ports other than edge ports, e. The spanning tree protocol engine causes this agreement-BPDU message to be sent to neighboring switch , as indicated at block , thereby notifying switch that it may go ahead and transition its peer port to the forwarding state.
Switch also needs to return its own designated ports to the forwarding state. Accordingly, for each non-edge port, e. These BPDU messages are sent from the respective designated ports to the downstream bridges, e.
Assuming the received BPDU messages contain better or the same information than that stored by the switches and , they respond to switch with BPDU messages in which the agreement flag is asserted. In response to receiving such a BPDU message , switch rapidly transitions the respective designated port to the forwarding state, as indicated at block Processing is then complete as indicated by end block If the STP engine determines at decision block that the received proposal-BPDU message contains information indicating that the switch is still the root of the bridged network , then processing proceeds via No arrow to block Processing is then complete as also indicated by end block As 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. It should be understood that, for a root bridge, processing may begin with block FIG. If 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.
As indicated above, switch may include a plurality of line cards not shown comprising the ports established at the switch Switch 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 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. Those skilled in the art understand that the bridged network may be segregated into a series of logical network segments. Specifically, according to the ' 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.
The IEEE's The IEEE Thus, either all VLAN tagged frames may be forwarded and received through a given port or none may be. An alternative to the This alternative is currently being implemented by certain networking equipment from Cisco Systems, Inc.
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.
Rather than providing a separate active topology for each VLAN designation within the bridged network , it is also possible to define more than one active topology but some number less than the total number of VLAN designations.
In addition to the A switch, such as switch , 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 That is, if the switch 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.
The 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.
A method for transitioning ports of an intermediate network device among a plurality of states, the method comprising the steps of: executing a rapid spanning tree protocol RSTP on the intermediate network device, the RSTP designating a first port of the device to a Root Port Role and designating one or more second ports of the device to Designated Port Roles and placing the one or more second ports in a forwarding state;. The method of claim 1 , further comprising the step of: sending a BPDU message on the third port, the BPDU message having an acknowledgment flag that is asserted.
The method of claim 1 , wherein the step of reassigning is performed in response to detecting a failure of a link connected to the first port. The method of claim 1 , wherein the step of reassigning is performed in response to detecting the device failing to receive BPDU messages on the first port for a preset period of time. The method of claim 1 , wherein the step of reassigning is performed in response to receiving a BPDU message indicating the third port is closer to a root device than the first port.
The method of claim 1 , wherein the step of executing further comprises the step of: placing the first port in a forwarding state.
The method of claim 6 , wherein the step of reassigning further comprises the step of: transitioning the first port to the blocking state and the third port to the forwarding state. The method of claim 1 , further comprising the step of: confirming that any ports designated to an Alternate Port Role are in the blocking state.
An intermediate network device configured to forward network messages within a network, the device having a plurality of ports that transition among a plurality of states, the device comprising: means for executing a rapid spanning tree protocol RSTP on the intermediate network device, the RSTP configured to designate a first port of the device to a Root Port Role and to designate one or more second ports of the device to Designated Port Roles and to place the one or more second ports in a forwarding state;.
The intermediate network device of claim 9 , further comprising means for sending a BPDU message on the third port, the BPDU message having an acknowledgment flag that is asserted. The intermediate network device of claim 9 , further comprising: means for transitioning the first port to the blocking state and the third port to the forwarding state.
The intermediate network device of claim 9 , further comprising: means for confirming that any ports designated to an Alternate Port Role are in the blocking state. A computer readable medium containing executable program instructions for transitioning ports of an intermediate network device among a plurality of states, the executable program instructions comprising program instructions operable to: execute a rapid spanning tree protocol RSTP on the intermediate network device, the RSTP to designate a first port of the device to a Root Port Role and to designate one or more second ports of the device to Designated Port Roles and to place the one or more second ports in a forwarding state;.
An apparatus comprising: a plurality of ports;. The apparatus of claim 14 , wherein the port role transition state machine is further configured to reassign the Root Port Role from the first port to the third port step in response to detection of a failure of a link connected to the first port.
The apparatus of claim 14 , wherein the port role transition state machine is further configured to reassign the Root Port Role from the first port to the third port in response to failure to receive BPDU messages on the first port for a preset period of time.
The apparatus of claim 14 , wherein the port role selection state machine is further configured to place the first port in the forwarding state. The apparatus of claim 18 , wherein the port role transition state machine is further configured to transition the first port to the blocking state and the third port to the forwarding state.
The apparatus of claim 14 , wherein the port role transition state machine is further configured to confirm that any ports designated to an Alternate Port Role are in the blocking state. USB1 en.
USB2 en. Method and apparatus for rapidly reconfiguring bridged networks using a spanning tree algorithm. Network system, spanning tree configuration method, spanning tree configuration node, and spanning tree configuration program. Introducing Dark Web Monitoring. Spanning Backup for Microsoft Login Login Start the Conversation. Cloud-to-Cloud SaaS Backup Powerful yet easy-to-use SaaS data protection for Microsoft , G Suite and Salesforce enabling administrators and users to restore data and get back to work in just a few clicks.
Let us show you how. Spanning Advanced capabilities to help prevent, anticipate and mitigate account compromise and data loss. Salesforce See why leading Salesforce admins and developers trust Spanning for in-app backup and restore of data, metadata, and customizations. MSP Edition A modern platform to provide your customers with enterprise-class data protection and business continuity. Why you need SaaS backup. Illegitimate deletion.
Malware and ransomware. Spanning is the best tool on the market for the price, performance and features. 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 The bridge port offering the best, e. Each bridge port offering an alternative, e. Those 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. Like the STP described in the The BPDU messages are also utilized in the handshake employed to rapidly transition designated ports to the forwarding state.
The message header 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 is a BPDU message area that also contains a number of fields, including a protocol identifier ID field , a protocol version number field , a BPDU type field , a flags field , a root ID field , a root path cost field , a bridge ID field , a port ID field , a message age field , a maximum age field , a hello time field , and a forward delay field , among others.
The root identifier field typically contains the identifier of the bridge assumed to be the root and the bridge identifier field contains the identifier of the bridge sourcing i.
The root path cost field 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 contains the identifying number of the port from which the BPDU is sent. As shown, the flags field carries a plurality of single or multiple bit flags that may be set, e. Specifically, the flags field includes a topology change flag , a proposal flag , a port role flag , a learning flag , a forwarding flag , an agreement flag and a topology change acknowledgment ACK flag The learning and forwarding flags and are set to reflect the current port state of the port from which the corresponding BPDU is being sent.
The 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 from that port whose proposal flag is asserted. The port role flag is set to the value associated with the Designated Port Role. In the root ID and root path cost fields and , the upstream bridge loads the corresponding information relative to the port from which the BPDU message is to be sent.
The upstream bridge then sends the BPDU message which is received at the neighboring downstream bridge. Sync is a state machine variable defined by the 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 whose agreement flag 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.
In 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 with their proposal flags asserted are sent from these ports. Briefly, 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.
Specifically, 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. The invention description below refers to the accompanying drawings, of which:.
The network preferably comprises a plurality of local area networks LANs — that are interconnected by a plurality of intermediate devices, such as switches — One or more entities or hosts not shown are preferably coupled to each LAN — so that the entities may source or sink data frames to one another over the network Each switch — , moreover, preferably includes a plurality of ports such that each LAN — is coupled to at least one port of switches — At least some of the switches — may be interconnected by a series of links, such as point-to-point links — , rather than by the LANs.
Links — similarly carry messages, such as data frames, between respective switches. Each switch — , moreover, preferably identifies its own ports , e. It should be understood that the network of FIG. As shown, network includes redundant links interconnecting switches — For example, switch is connected to switch along at least two different paths; first, via switch alone and second, via switches and The existence of such redundant links prevents portions of the network 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. Execution of a spanning tree protocol prevents loops by defining a loop-free network topology i. 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. Switch includes a plurality of ports a — e each of which is preferably identified by a number e.
One or more frame transmission and reception objects, designated generally , are associated with the ports a—e such that network messages, including data frames, received at a given port, e.
Frame reception and transmission objects are preferably message storage structures, such as priority queues. Switch further includes at least one protocol entity comprising a plurality of components. In particular, the protocol entity includes at least one spanning tree protocol STP engine and at least one forwarding engine The STP engine preferably comprises a plurality of subcomponents, including a port role selection state machine , a port transition state machine , a bridge protocol data unit BPDU message generator and a sync manager The STP engine includes or is in communicating relationship with a memory , which may be a volatile or non-volatile random access memory RAM or some other memory device.
The forwarding engine is in communicating relationship with the frame transmission and reception objects and is coupled to at least one filtering database that stores address information corresponding to the entities of network FIG.
Specifically, filtering database 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 preferably corresponds to a particular network entity. The forwarding engine is also in communicating relationship with the STP engine and relays RSTP-related messages received at ports thereto.
It will be understood by those skilled in the art that STP engine and forwarding engine may each comprise registers and combinational logic configured and arranged to produce sequential logic circuits. In the illustrated embodiment, engines and 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 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. Suitable intermediate network device platforms for use with the present invention include, but are not limited to, the commercially available Catalyst and series of switches from Cisco Systems, Inc. Suppose that port P 1 of switch is assigned the Root Port Role and is transitioned to the forwarding state, and that port P 0 is assigned the Alternate Port Role as it represents an alternate path to root Port P 0 is transitioned to the blocking or discarding state.
The terms blocking and discarding are used interchangeably herein. In addition, suppose that ports P 2 —P 4 of switch are assigned the Designated Port Role and that each port is transitioned to the forwarding state.
The optimal sync mechanism of the present invention is invoked in response to receiving a BPDU message whose proposal flag is asserted on the current or newly elected root port. This may occur in response to a number of different situations as reflected in FIG. First, the link coupled to the current root port, port P 1 , of switch may fail, as indicated at block FIG. Alternatively, switch may stop receiving BPDU messages on its root port, as indicated at block It should be understood that these situations may be caused by the addition, removal, failure or recovery of network components such as links, switches, etc.
In response to the situations represented by blocks , and , the port role selection state machine selects an alternate port, e. The port role selection state machine 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 Upon reassigning the affected ports to their new roles, the port role selection state machine then directs the port transition state machine to transition the RSTP states of those ports in accordance with their new roles.
Specifically, the port transition state machine transitions the previous root port, e. Next, state machine transitions the newly selected root port, e. This RSTP BPDU message is likely to have the proposal flag asserted, thereby indicating that neighboring switch wishes to transition its peer port, i.
The BPDU message is passed to the spanning tree protocol engine of switch for processing.
0コメント