Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
2003-01-28
2004-01-20
Vanderpuye, Kenneth (Department: 2661)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S401000
Reexamination Certificate
active
06680917
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to network protocols and network intermediate devices executing such protocols; and more particularly to algorithms for managing a tree of network devices for a data network according to a spanning tree protocol.
2. Description of Related Art
Local area networks LANs specified according to IEEE Standards for Local and Metropolitan Area Networks under section 802.x, of all types may be connected together with media access control MAC bridges. Bridges interconnect LAN segments so that stations connected to the LANs operate for many purposes as if they were attached to a single LAN. The MAC bridge according to the IEEE standards is specified for operating below the MAC service boundary, and is transparent to protocols operating above this boundary, including protocols operating in the logical link control sublayer or the network layer. Thus, a bridged local area network provides for interconnection of stations attached to LAN segments of different MAC types, for increases in the physical extent, the number of permissible attachments and the total performance of a LAN, and for the partitioning of a physical LAN support for administrative or maintenance reasons. The MAC bridge is specified according to the IEEE Standard 802.1D (IEEE Std 802.1D-1990, IEEE Standards for Local and Metropolitan Area Networks: Media Access Control (MAC) Bridges.) The 802.1D specification is incorporated by reference as if fully set forth herein.
When a bridged network is established, it is possible to create loops in the network caused by providing more than one path through bridges in LAN segments between two points. Thus, according to the 802.1D standard, an active topology for the bridge network is maintained according to the spanning tree protocol which is described in the standard. The spanning tree protocol automatically establishes fully connected (spanning) and loop-free (tree) bridged network topology. It uses a distributed algorithm that selects a root bridge and the shortest path to that root from each LAN. Tie breakers are used to ensure that there is a unique shortest path to the root, while uniqueness of the root is guaranteed by using one of its MAC addresses as part of a priority identifier.
Every LAN in the network has one and only one “designated port” providing that LAN's shortest path to the root, through the bridge of which the designated port is a part. The bridge is known as the designated bridge for that LAN. Bridges other than the root bridge at the root of the network can be termed branch bridges. Every branch bridge has a “root port” which is the port providing that bridge's shortest path to the root, across a LAN and through the designated port on a designated bridge. Ports other than the root port are designated ports, or alternate ports according to the standard. An alternate port is connected to a LAN for which another bridge is the designated bridge, and is placed in a blocking state so that frames are not forwarded through that port.
The connectivity through any bridge is thus through its root port to a designated port on another bridge, for connection to devices between the bridge and the root of the spanning tree and from the root to other branches of the spanning tree. For connection to devices between the bridge and leaves of the spanning tree, traffic flows through designated ports on the bridge. When spanning tree information has been completely distributed and is stable, this connectivity will connect all of the LANs in a loop free tree.
According to the spanning tree protocol of the standard, each port on a bridge can assume a blocking state in which frames are not forwarded through the port, or a forwarding state in which frames are forwarded through the port. For a transition from the blocking state to the forwarding state, the protocol requires the port to proceed through transitional states referred to as the listening state and the learning state. In the listening state, the port is preparing to participate in frame relay, however frame relay is temporarily disabled to prevent temporary loops. In the listening state, the port monitors information related to the topology in the network for an interval referred to as the forward delay timer. If no information is received which causes a change in state of the port before expiry of the forward delay timer, then the port transitions to the learning state.
In the learning state, the port continues to prepare for participation in frame relay. The relay is temporarily disabled to prevent loops. In this state, in addition to monitoring bridge protocol data units and other information related to operation of the spanning tree algorithm, the port learns information about end stations that are accessible through the port for use in the forwarding of frames once the port enters the forwarding state. Upon expiration of the forward delay timer, if no better information about the protocol is received, then the port assumes the forwarding state. Thus, the transition from a blocking state to the forwarding state takes at least two times the forward delay timer interval. From the time of detection of a change in topology causing a transition from the blocking to the forwarding state, until the time in which the forwarding state is assumed can be a significant amount of time, as much as 30 seconds in some cases.
In a network of bridges which have a topology managed according to the spanning tree protocol, whenever a bridge detects a change in topology, such as for example when an active link fails, the bridge notifies the root of the active topology with a bridge protocol data unit BPDU packet. The protocol entity at the root of the topology then communicates the change to all of the bridges in the tree. Upon receiving such a notification, the bridges time-out their forwarding databases on all ports, recreate the topology and relearn the MAC addresses for the forwarding databases.
The spanning tree protocol uses a distributed algorithm to select a root bridge and the shortest path to the selected root for each LAN. Tie breakers are used to ensure that there is a unique shortest path and a unique root. The topology is maintained by periodic configuration messages known as Bridge Protocol Data Units BPDUs issued by the root, and distributed to all bridges in the tree. There are two types according to the standard known as Configuration BPDUs and Topology Change BPDUs. The information in a Configuration BPDU is accepted and used by a bridge if it carries better information than already received by the bridge on that port, and propagates the BPDU if it carries better information than already received by the bridge on any of the ports on the bridge. Better information received by a bridge port replaces that previously recorded for the port, and is propagated further if it is the best that the bridge has recorded for any port. Information that is better, is defined by the standard, and includes information from a higher priority root, or from the current root, along a lower cost path, or simply more recent information from the current root at the current path cost. All information has a maximum age so current information will be forgotten eventually, if the root or a bridge or link on the shortest path to the root fails. Periodic message transmissions by the root and potential roots together with information aging ensures that the spanning tree maintains full loop-free connectivity even as bridges and links fail, or are added and removed from the network.
The maximum age of spanning tree information can be managed precisely to accommodate worst case message propagation delays, lost messages, the maximum number of bridges between the root and any LAN in the network, and the estimated adjustments in such bridges to the message age. However, in most cases generous worst case “out of the box” defaults are used. Either way the operation of a protocol has the effect that good news, indicating the availability of a better root or link to the root
3Com Corporation
Haynes Mark A.
Haynes Beffel & Wolfeld LLP
Vanderpuye Kenneth
LandOfFree
Spanning tree with rapid propagation of topology changes 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 rapid propagation of topology changes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning tree with rapid propagation of topology changes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3218860