Method and apparatus for preventing spanning tree loop during traffic overload condition

The present invention relates to the design of a computer network. More specifically, the present invention relates to methods and devices that execute spanning tree protocol across bridges in a network while preventing loops from occurring in the event of lost spanning tree configuration messages.

Computer networks are often connected through transparent bridges. The most basic form of transparent bridge is to connect to two or more local area networks (LANs) (each connection to the bridge is called a "port"). Such a bridge listens indiscriminately on every packet transmitted and stores each packet received until it can be transmitted on a different LAN than the one received.

The transparent bridge was developed to allow stations designed to operate on only one LAN to work in a multi-LAN environment. The station expects the packet to be transmitted and delivers the packet, just as if it were a single LAN environment. Therefore, the bridge must transmit exactly as it did when it received the packet. If the bridge modifies the packet in any way (eg, by overwriting the source address portion of the header with its own address), the protocol cannot work properly on the station.

Note that the bridge can potentially loop the packet, which can replicate the packet exponentially. This replication can increase network congestion to the point where the network ceases to function.

This looping problem is generally addressed using the Spanning Tree Protocol defined in the Institute of Electrical and Electronics Engineers (IEEE) standard 802.1D. This spanning tree protocol is loop-free (tree) and has sufficient connectivity, which allows routes between each pair of LANs, if physically possible (tree is spanning). It works by using a bridge that dynamically discovers a subset of the network topology.

The basic idea behind the Spanning Tree Protocol is that the bridge periodically transmits special configuration messages, which allows the bridge to calculate the spanning tree. With reference to Figure 2, these configuration messages contain enough information to allow the bridge to do the following: They (1) elect one of all bridges on all LANs as the root bridge (step 202). (2) Calculate the shortest path distance from all bridges themselves to the root bridge (step 204). (3) The designated bridge of each LAN is selected from the bridges existing in that LAN (step 206), where the selected bridge is the closest bridge to the root bridge and forwards the packet to the root bridge. To do. (4) Select the port that gives the best route to the root bridge for each bridge (step 208). (5) Select the ports on each bridge that should be included in the spanning tree (step 210). (6) Put the selected port in a forwarding state in which messages are forwarded to and from the port (step 212). (7) Put the other port in a backup state where messages are not forwarded to or from the port (step 214).

This protocol is a poem called "Algorhyme" by Radia Perlman, the inventor of the present invention. I don't think I see graphs that are more beautiful than trees.

The decisive property of the tree is loop-free connectivity.

The tree must be spanned reliably and packets reach all LANs.

First, the route must be selected.

It is elected by ID.

The lowest cost route from the route is traced.

These routes are arranged in the tree.

The mesh is made by a close person like me.

The bridge then finds the spanning tree. It is summarized in.

It is important that the bridge is operated with sufficient CPU power so that the Spanning Tree Protocol works properly in the event of network congestion. Otherwise, a temporarily congested network can cause the loss of configuration messages, which can cause the Spanning Tree Protocol to accidentally turn on additional bridge ports. This can cause loops and can dramatically increase the amount of congestion until the spanning tree never recovers.

<p> Unfortunately, the IEEE802.ID standard does not specify performance requirements, and as a result, some of the bridge hardware currently being developed handles spanning tree configuration messages during worst-case traffic. I can't. Therefore, messages can be lost and loops can be created.</p><p> Therefore, what is needed is a method and device to prevent loops from occurring in the event of lost spanning tree configuration messages.</p>

<p> The method according to the invention is a method of executing the spanning tree protocol over a bridge in the network while preventing the occurrence of a loop when the spanning tree configuration message is lost, and the spanning tree protocol is applied on the bridge. A step to perform, the Spanning Tree Protocol, puts each port attached to the bridge in a forwarding state in which messages are forwarded to and from that port, or messages are sent to and to that port. A step that configures a backup state that is not forwarded from, and a step that monitors the port attached to the bridge to determine when a message was lost by that port, and one or more messages on the port. If lost above, it includes the step of refraining from forwarding the message to or from the port for a period of time until the message is no longer lost by the port, thereby achieving the above objectives.</p><p> The time may be greater than the time interval provided by the bridge between consecutive spanning tree configuration messages.</p><p> The step of monitoring the port attached to the bridge may include communicating with the hardware associated with the port to determine if the message was lost by the port.</p><p> The step of executing the Spanning Tree Protocol puts the port coupled to the bridge into the forwarding state or backup to ensure that messages are forwarded without repetition across the spanning tree that connects the bridges in the network. It may include steps to bring it into a state.</p><p> The step of executing the Spanning Tree Protocol is to elect one of all the bridges of all the links on the network as the root bridge and to calculate the distance of the shortest route from each node to the root bridge. And the step of selecting the bridge specified for each link from all the bridges of the link, the designated bridge being the closest to the root bridge, and the packet being sent from the link to the root bridge. A step of selecting a route port for each bridge that provides the best route to the route bridge, and a step of selecting a port on each bridge to be included in the spanning tree. The selected port comprises a root port and any port coupled to a link in which the bridge is utilized as the designated bridge, and a step of putting the selected port into the forwarding state. , All other ports may include the step of putting them into the backup state.</p><p> The Spanning Tree Protocol may generally operate in accordance with the Institute of Electrical and Electronics Engineers (IEEE) standard 802.1D.</p><p> The link may be a LAN (local area network).</p><p> Computer-readable media according to the invention, when run by a computer, describe a method of running the Spanning Tree Protocol across bridges in a network while preventing loops in the event of lost spanning tree configuration messages. A computer-readable storage medium that stores instructions to be executed by a computer, the method of which is a step of executing the Spanning Tree Protocol on a bridge, wherein the Spanning Tree Protocol is a port coupled to the bridge. Configure the message in a forwarding state in which the message is forwarded to and from the port, or in a backup state in which the message is not forwarded to or from the port, the step and the message is lost by the port. To determine when, the step of monitoring the port attached to the bridge and, if one or more messages are lost on the port, for a period of time until no messages are lost by the port. It includes a step of refraining from forwarding messages to and from the port, thereby achieving the above objectives.</p><p> The time may be greater than the time interval provided by the bridge between continuous spanning tree configuration messages.</p><p> The step of monitoring the port attached to the bridge may include communicating with the hardware associated with the port to determine if the message was lost by the port.</p><p> The step of executing the Spanning Tree Protocol puts the port coupled to the bridge into the forwarding state or backup to ensure that messages are forwarded without repetition across the spanning tree that connects the bridges in the network. It may include steps to bring it into a state.</p><p> The step of executing the Spanning Tree Protocol calculates the step of electing one of all the bridges of all the links on the network as the root bridge and the distance of the shortest route from each node to the root bridge. A step and a step of selecting a bridge specified for each link from all bridges of the link, the specified bridge being closest to the root bridge and delivering packets from the link to the root bridge. A step of forwarding, a step of selecting a route port for each bridge that provides the best route to the route bridge, and a step of selecting a port on each bridge to be included in the spanning tree. The port is a step comprising the root port and any port coupled to a link in which the bridge is utilized as the designated bridge, and a step of putting the selected port into the forwarding state. It may include the step of putting all other ports into the backup state.</p><p> The Spanning Tree Protocol may generally operate in accordance with the Institute of Electrical and Electronics Engineers (IEEE) standard 802.1D.</p><p> The link may be a LAN (local area network).</p><p> The device according to the present invention is a device that executes the spanning tree protocol across bridges in the network while preventing the occurrence of loops when the spanning tree configuration message is lost, and the spanning tree protocol is applied on the bridge. A spanning tree mechanism configured to perform, the spanning tree protocol is a forwarding state in which a message is forwarded to or from each port attached to the bridge, or the message is A spanning tree mechanism that configures a backup state that is not forwarded to or from the port, and to monitor the port attached to the bridge to determine when messages were lost by the port. With a configured monitoring mechanism, if one or more messages are lost on a port, the spanning tree mechanism also sends messages to that port for a period of time until the message is no longer lost by the port. It is configured to refrain from forwarding from, thereby achieving the above objectives.</p><p> The time may be greater than the time interval provided by the bridge between consecutive spanning tree configuration messages.</p><p> The monitoring mechanism may be configured to communicate with the hardware associated with the port to determine if the message was lost by the port.</p><p> The spanning tree mechanism puts a port coupled to the bridge into the forwarding state or the backup state to ensure that messages are forwarded without repetition across the spanning tree that connects the bridges in the network. It may be configured in.</p><p> The spanning tree mechanism elects one of all the bridges of all the links on the network as the root bridge, calculates the shortest route distance from each node to the root bridge, and specifies it for each link. The bridge is elected from all bridges on the link, where the designated bridge is closest to the root bridge and forwards packets from the link to the root bridge, providing the best route. The root port to be provided to the root bridge is selected for each bridge, and the ports on each bridge that should be included in the spanning tree are selected, where the selected ports are the root port and the bridge. It may be configured to include any port coupled to a link utilized as the designated bridge, putting the selected port in the forwarding state and all other ports in the backup state.</p><p> The spanning tree mechanism may generally operate in accordance with the Institute of Electrical and Electronics Engineers (IEEE) standard 802.1D.</p><p> The link may be a LAN (local area network).</p><p> (Abstract) An embodiment of the present invention provides a system that runs the Spanning Tree Protocol on a bridge in a network while preventing loops from occurring if the spanning tree configuration message is lost. During operation, the system runs the Spanning Tree Protocol on the bridge. This Spanning Tree Protocol configures each port attached to the bridge in a forwarding state in which messages are forwarded to and from the port, or in a backup state in which messages are not forwarded to or from the port. The system also monitors the port attached to the bridge to determine if the message was lost by the port. If one or more messages are lost on a port, the system refrains from forwarding the message to or from the port for a period of time until the port no longer loses the message.</p><p> In one variant of this embodiment, this amount of time is greater than the time interval provided by the bridge between consecutive spanning tree configuration messages.</p><p> In one variant of this embodiment, the step of monitoring a port attached to a bridge involves communicating with the hardware associated with the port to determine if a message was lost by the port.</p><p> In one variant of this embodiment, the step of executing the Spanning Tree Protocol forwards the bridge-bound ports to ensure that messages are forwarded without repeating across the spanning tree that connects the bridges in the network. Includes steps to put into a state or backup state.</p><p> In one variant of this embodiment, the steps to implement the Spanning Tree Protocol are the step of electing one bridge between all bridges of all links on the network as the root bridge and the shortest route from each node to the root bridge. The step of calculating the distance and the step of selecting the bridge specified for each link from all the bridges of that link, and the specified bridge is the closest to the root bridge and from that link to the root bridge. A step that forwards packets, a step that selects the root port that provides the best route to the root bridge for each bridge, and a step that selects the port on each bridge that should be included in the spanning tree. A port comprises a root port and any port coupled to a link in which the bridge is used as a designated bridge, a step, a step that puts the selected port in a forwarding state, and all other ports. Includes the step of putting it in a backup state.</p><p> In one variant of this embodiment, the Spanning Tree Protocol generally operates according to the IEEE (Electrical and Electronics Engineers) standard 802.1D.</p><p> In one variant of this embodiment, the link is a LAN (Local Area Network).</p>

<p> According to the present invention, the spanning tree protocol can be executed across bridges in the network while preventing loops from occurring in the event of lost spanning tree configuration messages.</p>

(Detailed Description) The following description is provided to allow those skilled in the art to make and use the present invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein do not deviate from the gist and scope of the present invention. It can be applied to embodiments and applications. Accordingly, the present invention is not intended to be limited to the embodiments shown, but is intended to be consistent with a very broad range consistent with the principles and features disclosed herein.

The data structures and codes described in this detailed description are typically stored in a computer-readable storage medium that can be any device or medium that can store the code and / or data used by the computer system. This involves magnetic and optical storage devices such as disk drives, magnetic tables, CDs (compact discs), and DVDs (digital versatile discs or digital video discs), as well as transmission media (carriers on which signals are modulated). Includes, but is not limited to, computer command signals embodied in. For example, the transmission medium may include a communication network such as the Internet.

(Network) FIG. 1 shows an exemplary network 100 having a bridge according to an embodiment of the present invention. As shown in FIG. 1, the network 100 includes a plurality of links 106 to 110. In certain embodiments of the present invention, links 106-110 are LANs (local area networks) that connect local computing nodes (stations), such as Ethernet®-based networks. More specifically, in FIG. 1, the link 106 connects the nodes 112 to 114 and the bridge 102, the link 107 connects the nodes 115 to 116 and the bridges 102 to 103, and the link 108 connects the nodes 119 to 120. And bridges 103 to 104, link 109 connects nodes 117 to 118 and bridges 103 to 104, and link 110 connects nodes 121 to 123 and bridge 104.

Note that bridges 102-104 are designed to transparently connect links 106-110 so that they appear to be part of a single combined network.

(Spanning Tree Protocol) The spanning tree protocol generally behaves as already described with reference to FIG. However, in some cases, network congestion can cause spanning tree configuration messages to be lost, which can cause the spanning tree protocol to accidentally turn on additional bridge ports. This can also cause loops, which can dramatically increase the amount of congestion to the point where the Spanning Tree Protocol never recovers.

FIG. 3 provides a flowchart showing how the Spanning Tree Protocol processes lost messages and prevents the occurrence of such loops according to embodiments of the present invention. The system generally implements the Spanning Tree Protocol as already described with reference to Figure 2 (step 302). At the same time, the system monitors the port attached to the bridge (step 304). During this monitoring process, the system determines if the message has been "lost" by any port. Note that if the system is unable to send or receive one or more messages through the port (step 306), the messages are "lost" on the port.

There are implementation examples depending on how the bridge knows that it is not maintaining traffic. In one embodiment of the invention, the NIC card increments the counter to notify the driver that incoming messages have been lost (eg, incoming messages are lost due to buffer overrun conditions). If). These counters are available for inspection by the upper layers.

Another case where a spanning tree meltdown occurs is when the bridge is unable to carry its spanning tree message. A typical case where this happens is when there is a link configured as half-double in one direction and full-double in the other direction. In this case, if the full dual side has sufficient traffic, the half dual side cannot transmit. (Note that this system may try to send a message more than once before abandoning it.) This situation is only detectable by the half-duplex side. If you are confident that the bridge (the bridge that is considered half-double on that link) is the designated bridge for that link and that this bridge cannot carry the spanning tree message, then the scenario described above. As in, this bridge continues to be at the forefront for the spanning tree algorithm itself to work, but does not forward data traffic to and from the link.

At step 306, the system determines that no messages have been lost, and the system returns to step 302 to continue running the Spanning Tree Protocol.

Otherwise, if a message is lost by a port, the system waits for a sufficient amount of time before forwarding the message to or from the port until the next spanning tree configuration message is lost. Is received on the port (step 308). This ensures that the port does not accidentally forward messages as a result of lost spanning tree configuration messages. This reduces the probability that the spanning tree protocol will accidentally create a loop.

If a message is lost on a port that is in the forwarding state, the associated bridge cannot recognize that this should have changed the port to the backup state, because another bridge is on the specified bridge. Please note that this is because they are more qualified to be. On the other hand, if a message is lost on a port that is in backup state, the bridge can assume that the bridge is the bridge designated for the port (probably the root bridge), and is actually a more qualified bridge. Can be inadvertently changed to the forwarding state when is present.

The previous descriptions of embodiments of the present invention have been provided for purposes of illustration and illustration only. These statements are not intended to cover the invention or limit it to the disclosed form. Therefore, multiple modifications and variants will be apparent to those skilled in the art. It will be understood by those skilled in the art that from the description of specific preferred embodiments of the present invention, an equivalent range can be implemented based on the description of the present invention and common general technical knowledge. Moreover, the above disclosure is not intended to limit the invention. The scope of the invention is defined by the appended claims. (wrap up) One embodiment of the present invention provides a system that runs the Spanning Tree Protocol over a bridge in a network while preventing loops from occurring in the event of lost spanning tree configuration messages. During operation, the system runs the Spanning Tree Protocol on the bridge. This Spanning Tree Protocol configures each port attached to the bridge in a forwarding state in which messages are forwarded to and from the port, or in a backup state in which messages are not forwarded to or from the port. The system also monitors the port attached to the bridge to determine if the message was lost by the port. If one or more messages are lost on a port, the system refrains from forwarding the message to or from the port until the message is no longer lost by the port for a period of time.

<figref num="1">FIG. 1 shows an exemplary network with bridges according to an embodiment of the invention.</figref><figref num="2">FIG. 2 provides a flowchart showing the Spanning Tree Protocol.</figref><figref num="3">FIG. 3 provides a flowchart showing how the Spanning Tree Protocol, according to an embodiment of the present invention, handles lost messages.</figref>

Code description

100 Network 102 ~ 104 Bridge 106 ~ 110 Link 112 ~ 123 Node