Spanning tree with fast link-failure convergence

Details Spanning tree with fast link-failure convergence Spanning tree with fast link-failure convergence

2000-09-07

2001-04-17

Wiley, David A (Department: 2155)

Electrical computers and digital data processing systems: input/

Intrasystem connection

Bus access regulation

C709S252000, C714S799000

Reexamination Certificate

active

06219739

ABSTRACT:

FIELD OF THE INVENTION
The current invention applies to the field of network configuration protocols which automatically configure a meshed network into a loop-free topology. One such automatic network configuration protocol is known as the Spanning Tree Protocol, and the present invention is directed to an improvement to the Spanning Tree Protocol which is capable of reducing reconfiguration time in the presence of either the failure or intentional removal of existing network equipment or interconnecting cables.
BACKGROUND OF THE INVENTION
Computer networks comprise interconnected bridges and routers which are responsible for the forwarding of frame traffic principally generated by computers at end stations. The function of each of these bridges and routers is to provide an appropriate degree of isolation between various parts of the network, which has the effect of increasing the bandwidth available to each user of the network. The level of desired isolation provided by each of these elements is related to the hierarchy level in which each element operates in the 7 layers defined by the OSI Reference Model.
A bridge (or switch) is a Layer
2
entity that is typically a computer with a plurality of ports that couple the bridge to other entities. The bridging function includes receiving data from a port and transferring that data to other ports for receipt by other entities. A bridge is able to move data frames from one port to another very fast since its decision is based only on end-station MAC address information contained in such frames. The IEEE 802.3 standard specifies a fixed location for these MAC addresses in the frame. In this manner, bridges typically utilize a series of high speed, low cost state machines for the movement of data.
Most computer networks have redundant communication paths. In general, such redundant paths in a network are desirable, as they prevent portions of the network from being isolated due to link failures. Also, multiple paths can be used simultaneously to load-balance data between the paths. However, redundant paths introduce the possibility of circuitous paths or “loops” being formed. Bridges generally make forwarding decisions based on address look-ups which are very fast and simple. The creation of a loop in a bridged network causes data frames to be continuously traversing the loop until the network saturates and also creates ambiguities in the address-table. To permit the existence of redundant communication paths but to avoid the looping problem mentioned, a method of “pruning” a network into a “tree” configuration is described in Chapter 4 of IEEE 802.1D and in Chapter 3 of the book “Interconnections: Bridges and Routers” by Radia Perlman, both of which are incorporated herein by reference. This method is called the “spanning tree protocol”.
OBJECTS OF THE INVENTION
A first object of the invention is to provide a mechanism for quickly reconfiguring a meshed network of switches into a spanning tree topology after the removal of a link which causes a bridge to lose connectivity to the root bridge. A second object of the invention is to maintain operational compatibility with the IEEE Standard 802.1D such that arbitrary mixtures of network bridges which have implemented either the existing standard spanning tree protocol or the fast link-failure converging spanning tree protocol of the present invention will interoperate with improved, or identical network performance as compared to the standard spanning tree protocol. A third object of the invention is to define a class of mechanism for bridges to determine that a spanning tree path to the root bridge still exists after the detection of a fault. A fourth object of the invention is to utilize the information of root bridge path existence to quickly reconfigure the existing network into a spanning tree.
SUMMARY OF THE INVENTION
The present invention is directed to a class of algorithms for the automatic reconfiguration of a network in the event of a link failure. A configured spanning tree comprises a network of bridges, one of which is known as the root bridge. All of the other bridges have a single connecting path to this root bridge through a port known as the root port either directly, or through other bridges participating in the spanning tree, each of which also have a root port. Loops are avoided by placing ports forming redundant paths in a blocked state, wherein they do not receive or send data traffic. An algorithm common to all of the bridges selects which ports are forwarding data in the spanning tree, and which are blocked, and not forwarding traffic, thereby effectively eliminating network loops. Adjoining bridges exchange frames called BPDUs to make the decisions of which port is forwarding and which is blocking. When the network is stable, all bridges in the network have moved their ports into forwarding or blocking states in such a way as to form a spanning tree and remove loops. In such a state, on every port a bridge is either receiving these BPDUs or transmitting them. It may be receiving on some ports and-transmitting on some others at the same time. But on any given port, it is either transmitting or receiving. The network is said to have converged in such a state. The port via which a bridge can reach the root bridge is its root port. The ports via which a bridge provides other bridges in the network a path to the root are called designated ports of that bridge. Under stable conditions, a bridge receives BPDUs from its root port and transmits these BPDUs to all bridges connected to its designated ports. In the event of a failure on a link caused, for example, by a cable fault, the information ordinarily transmitted between bridges to maintain the spanning tree is no longer received at the receiving port of a bridge. Ordinarily, the failure to receive these configuration frames for the time known as max_age having a default time of 20 seconds results in a reconfiguration, which requires an additional default time of 30 seconds before the network is once again configured into a new stable spanning tree, and forwarding traffic. During this 50 second interval from the moment the link is broken to the time the network has reconfigured into a new spanning tree, the network is unable to forward data traffic and users experience a loss in service.
The present invention enables surrounding bridges to detect when a bridge has lost connectivity to the root bridge and enable a faster reconfiguration of the network. When the bridge loses connectivity to the root bridge, as per the IEEE 802.1D standard, it begins reconfiguration by attempting to become the root bridge. It sends out a spanning tree protocol BPDU with itself as the root bridge. As implemented in prior art systems, and as defined in the IEEE standard 802.1D for the spanning tree protocol, this BPDU ignored by the surrounding bridges, because it is an inferior BPDU. The present invention enables surrounding bridges to act upon the reception of these inferior BPDUs. On receiving an inferior BPDU, a bridge sends a new BPDU, known as a Root Link Query (RLQ) request BPDU, to determine if a path to the root bridge is still available. If the path to root is still available, the bridge originating the RLQ request BPDU expires the max_age timer on the port receiving the inferior BPDU and selects the blocked port via which it confirmed the existence of alternate path to the root as its new root port. If the path to the root is no longer available via a port, the bridge immediately expires the max_age timer on that port. Thereafter, the standard spanning tree protocol is applied to re-compute which ports are to be in forwarding state and which are to be in blocking. Following normal spanning tree protocol rules, the bridge then transmits the availability of an alternate path via all its currently designated ports. The bridges attached to these ports may then use these links after the normal 2*Fwd_Delay time. Thus the bridge which lost connectivity to root can re-establish connectivity via a new path. This Root Link Query and

Affiliated with

Also associated with

Rating

Spanning tree with fast link-failure convergence does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Spanning tree with fast link-failure convergence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning tree with fast link-failure convergence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2488861