Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1998-11-09
2001-12-11
Olms, Douglas (Department: 2661)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S401000
Reexamination Certificate
active
06330229
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 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, which is incorporated herein by reference.
When a bridged network is established, it is possible to create loops in the network caused 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 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 LANs shortest path to the root, through the bridge at which the designated port is a part. The bridge is known as the designated bridge for that LAN.
A bridge 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 that bridges shortest path to the root. 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 arc not forwarded through that port.
The connectivity through any bridge is thus between its root port and designated ports. When spanning tree information has been completely distributed and is stable, this connectivity will connect all of the LANs 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, 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. Incoming frames on the port are blocked if their destination address is listed in the forwarding database as accessible through the port, else they are accepted and forwarded on one or more other ports in the forwarding state in the bridge. 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. While the bridges are in the process of recreating the spanning tree topology and relearning MAC addresses, data packets are not forwarded by them. This causes network disconnectivity as the ports transitioning go through the listening and learning states, followed by data flooding after the ports enter the forwarding state but before the forwarding databases have been completely relearned. The flooding of the network after a transition can result in loss of performance. Such loss of performance can be critical in real time networks, such as those transmitting live audio, video or other real time messages such as telephone signals.
Accordingly, it is desirable to provide a technique for improving the management of the forwarding databases in bridges operating according to the spanning tree protocol.
SUMMARY OF THE INVENTION
The present invention addresses the problems of management of forwarding databases in the case of topology changes, such as those caused by link failures on bridges, in response to the changing roles of ports on the bridge. The invention limits the propagation of notifications of topology change to only those parts of the network which are affected by the changes, and triggers partial flushing, as opposed to complete flushing, of learned MAC addresses, in the forwarding database for the sets of addresses associated with ports affected by the change in topology.
According to the prior art algorithm, when a topology change is detected a topology change notification TCN message is sent towards the root bridge from protocol entities in the network. The root bridge originates a configuration BPDU with a topology change TC flag set. All of the bridges in the network start a fast timeout timer on the MAC address database and start flushing the databases. The algorithm results in flushing databases everywhere in the network independent of the port roles, and results in flushing of data that remains valid, or which could be more efficiently managed. The present invention provides a set of techniques to limit flooding to parts of a database and parts of a network, which can be considered localized flooding. The invention includes the idea of separating the flushing algorithms into a flush designated FD and a flush root FR process. Th
Jain Vipin K.
Seaman Michael John
3Com Corporation
McDonnell & Boehnen Hulbert & Berghoff
Olms Douglas
Vanderpuye Ken
LandOfFree
Spanning tree with rapid forwarding database updates 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 forwarding database updates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning tree with rapid forwarding database updates will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2566573