Multiplex communications – Network configuration determination
Reexamination Certificate
1999-06-15
2004-04-20
Chin, Wellington (Department: 2664)
Multiplex communications
Network configuration determination
C370S255000
Reexamination Certificate
active
06724734
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to communication networks and in particular to spanning tree algorithms for local networks.
BACKGROUND OF THE INVENTION
A local communication network comprises a plurality of bridging-devices and communication links. Each communication link connects between two or more bridging-devices or between a bridging-device and a non-bridging device, such as an end-station (e.g., a computer), a router or a server. Each bridging-device comprises a plurality of ports which serve as interfaces between the bridging-device and the links to which it is connected. Each port may be active (referred to also as forwarding), blocking or disconnected, for reasons described below. When a source station sends a message to a destination station, the source station sends the message to a nearest bridging-device which sends the message to one of its neighboring bridging-devices (bridging-devices which are directly connected to a common link are referred to herein as neighbors). The neighboring bridging-device passes the message to another bridging-device until the message finally reaches the bridging-device connected to the destination station. In many cases, messages are broadcast to all the bridging-devices in a local network. When a message is broadcast, each bridging-device passes the message through all of its active ports, except for the port through which it was received. This broadcast scheme operates properly only if the active ports do not form a loop in the network. If the network includes a loop of active ports, a single message may be repeatedly sent through the network and the network will fail. A topology of active ports which connects all the bridging-devices in a network without forming loops is referred to as a spanning tree.
In many cases redundant links are added to networks to be used in case one or more of the bridging-devices and/or links fail. To properly use these redundant links instead of the bridging-devices and/or links which failed there is a need for a method for blocking and activating the ports of the various bridging-devices of the network. The method must ensure that a loop is never formed in the network and a spanning tree of active ports is available as often as possible. One common algorithm which performs these tasks is the 802.1D standard spanning tree algorithm (STA) which is described in “Information technology Telecommunications and information exchange between systems—Local and metropolitan area networks—Media access control (MAC) bridges”, International Standard ISO/IEC 15802-3, 1998, ANSI/IEEE Std 802.1D, 1998 edition, the disclosure of which is incorporated herein by reference.
The 802.1D STA is a distributed algorithm, i.e., it is performed separately by a STA software package in each of the bridging-devices of the network. In most cases, no single bridging-device knows the entire topology of the spanning tree. Rather, each bridging-device decides which of its local ports are part of the spanning tree according to predetermined rules and information received from neighboring bridging-devices. Each bridging-device activates its ports accordingly.
According to the 802.1D STA each bridging-device has a unique identifier which represents the priority of the bridging-device. A root bridging-device is chosen as the bridging-device with the lowest priority. The spanning tree is built as a distance-vector tree around the root, according to link costs associated with the links of the network. Each bridging-device designates one of its ports, which leads to the root along a lowest cost path, as a root port. If two paths to the root have the same cost, the path leading through the neighboring bridging-device with the lowest priority determines the root port. In addition, for each link, one of the ports leading to the link is chosen as a designated port of the link. The designated port of the link is chosen as the port of the bridging-device which has a shortest path from the root. Therefore, the designated ports are never root ports. The bridging-devices activate their designated ports and root port and keep all their other ports blocked. It is noted that messages (except control messages described below) pass from a first bridging-device to a second bridging-device over a link only if the ports of both the first and second bridging-devices leading to the link are active.
The operation of the algorithm is based on exchanging STA update messages (referred to as Bridge Protocol data Units—BPDUs) on the state of the network between bridging-devices which are neighbors. The STA BPDUs are sent also through blocking ports, unlike all other messages which are not passed through blocking ports. The BPDUs are identified by receiving bridge devices, either in hardware or software, according to a special destination address which they have. The receiving bridging-device passes the BPDUs to the STA software within the bridging-device and does not forward the BPDU to any other port. Thus, it is ensured that BPDUs are exchanged only between neighboring bridging devices.
The STA software in each bridging-device keeps track of the following parameters:
1) a current supposed ID of the root,
2) a current cost of the shortest path to the current supposed root,
3) a current supposed root port, and
4) a list of local ports which serve as designated ports for their associated links.
These parameters are updated according to received BPDUs, and are used to send updated BPDUs to neighboring bridging-devices. With time, information on the network propagates throughout the bridging-devices of the network and the tree is properly formed. It is noted that between sending a BPDU and sending out an updated BPDU (as a result of new information, for example), the bridging-device waits for a hold-time of a second in order to prevent inaccurate information from spreading throughout the network before the information is corrected. It is possible to change the hold-time to shorter or longer periods, for example to half a second, in some or all of the bridging-devices.
The time required by the 802.1D STA to converge after a change in the network (e.g., failing of a link) is relatively long (many seconds). The convergence time is dependent on the diameter of the network, i.e., the largest number of bridging-devices a message passes in passing between two bridging-devices. With default time-out parameters, the standard 802.1D STA is also limited to networks with a diameter smaller than or equal to seven.
A manager of a network may set a port to a disconnected state, in which the port does not forward any messages, and does not participate in a spanning tree. Usually, a port is set as disconnected by shutting down its hardware. Some bridging devices automatically set a port to the disconnected state if they sense that the port is not connected to any other device and/or if the port is faulty or is connected to a faulty link or device. When a disconnected port begins to operate, it is set to blocking state, and the STA adjusts accordingly.
Use of the standard 802.1D STA allows a user to connect bridging-devices from different manufacturers to a single network. Any deviations from the standard algorithm must be transparent to the bridging-devices of the network in which the changes were not performed.
Many modem LAN bridging-devices support a feature named virtual local area networks (VLANs). Some or all of the messages sent through the network are given a VLAN ID which represents the VLAN to which the messages belong. The ports of the bridging-devices of the network are configured as active or blocking for each VLAN separately. VLANs allow a single physical network to operate as a plurality of independent networks. For example, a station may be connected to a network through a port in which only a VLAN X is enabled. The station therefore can only forward packets to, and receive packets from, stations which are connected to VLAN X. An emerging standard for VLANs is described in “Draft Standard P802.1Q/D9, IEEE Standards for Local and Metropolitan Area Net
Rodrig Benny
Shabtay Lior
Avaya Communication Israel Ltd.
Chin Wellington
Schultz William
LandOfFree
Creating a spanning tree of a network including clusters does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Creating a spanning tree of a network including clusters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Creating a spanning tree of a network including clusters will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3186343