Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1999-04-22
2003-03-18
Olms, Douglas (Department: 2661)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S254000, C370S401000, C370S255000, C370S408000, C370S428000, C709S239000, C709S242000
Reexamination Certificate
active
06535490
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to network protocols and to 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 Institute of Electrical Electronic Engineers (“IEEE”) Standards for Local and Metropolitan Area Networks under section 802.x of all types may be connected together by media access control (“MAC”) bridges. MAC Bridges interconnect LAN segments so that stations connected to the LANs operate as if they were attached to a single LAN for many purposes. Thus a bridged LAN provides for the interconnection of stations attached to LAN segments of different MAC types, for an increase in the physical extent, for the number of permissible attachments and the total performance of a LAN, and for the partitioning of 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.).
When a bridged network is established, it is possible to create loops in the network by providing more than one path through bridges and LAN segments between two points. Thus, according to the 802.1D standard, an active topology for the bridged network is maintained according to the spanning tree protocol which is described in the standard. The spanning tree protocol automatically establishes a fully connected (spanning) and a 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 the 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 the shortest path to the root for that LAN, through the bridge of which the designated port is a part. The bridge is known as the “designated bridge” for that LAN.
Thus, bridges other than the root bridge at the root of the network can be termed a branch bridge. Every branch bridge has a “root port” which is the port providing the shortest path to the root for that 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 into a blocking state so that frames are not forwarded through that port.
Thus, the frame forwarding path through any bridge is between its root port and its designated ports. When spanning tree information has been completely distributed and is stable, this connectivity will connect all of the LANs in a loop-free tree.
When a bridge first receives spanning tree information that dictates new connectivity through that bridge, it does not establish the new connectivity immediately. Ports that were previously connected as either the root port or as a designated port, but are no longer in the forwarding state, are immediately made blocking. However, the transition to a forwarding state of ports that were previously not connected in a forwarding role is delayed. The delay serves two purposes:
(1) Frames forwarded on the previous topology may still be buffered by bridges in the network. Thus, an instantaneous bridge to the new topology can cause these frames to be forwarded back to their LAN of origin, causing duplication of the frame once; and
(2) New spanning tree information in the network may not have been fully distributed yet. Thus an immediate change to a new topology may cause temporary loops. These loops could generate high traffic volumes, disrupting end stations, causing frame loss in bridges, and possibly delaying the propagation of spanning tree information further.
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, and 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 bridge protocol data unit (“BPDU”) frames or other 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 the BPDU frames and other information related to the 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 frame enters the forwarding state. Upon expiration of the forward delay timer in the learning state, 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 two times the forward delay timer interval. A significant amount of time may pass from the time of detection of a change in topology causing a transition from the blocking state to the forwarding state, until the time in which the forwarding state is assumed. This time may be as long as 20 to 50 seconds in some cases.
Convergence of a bridged network in situations involving changing of spanning tree topology can therefore cause significant loss of service situations, particularly in networks that carry real time data. For example, the use of data networks and the Internet for audio and video transmissions of real time signals is increasing. Twenty to fifty second convergence times for these uses of the data network can cause unacceptable glitches. Accordingly, it is desirable to provide a technique to improve the availability of a bridged network in the face of changes in topology.
Work is being done in the Institute of Electrical Electronic Engineers (“IEEE”) 802.1 working group to speed up the convergence of the spanning tree in the face of topology changes. One such proposal converts an alternate port to the root port of the bridge if the original root port fails. An alternate port on a bridge is connected to a segment on another path to be root bridge. According to the proposals, addresses are also transferred from the failed root port to the new root port. The new root port goes into a forwarding state immediately after the transition. This process is described in our previous U.S. patent application Ser. No. 09/141,803 which is incorporated by reference above.
An alternate port on a bridge has information about the designated bridge/port and the designated cost on the segment to which it is connected. When the alternate port assumes the root port role, BPDUs are sent by the bridge with information indicating the change. The spanning tree proposal also requires downstream bridges to accept inferior information from a designated bridge. Since an alternate port is chosen as the root port, the new information will be inferior to the previously held information. When the changing bridge advertises the inferior information on its designated ports, downstream bridges receive this information and calculate the report and root path cost using. As a result of the calculation, downstream bridges either remain attached to the original root port, or find an alternate and better root port. The new and inf
3Com Corporation
Haynes Mark A.
Haynes Beffel & Wolfeld LLP
Nguyen Van
Olms Douglas
LandOfFree
High availability spanning tree with rapid reconfiguration... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High availability spanning tree with rapid reconfiguration..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High availability spanning tree with rapid reconfiguration... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3032269