Multiplex communications – Network configuration determination – In a bus system
Reexamination Certificate
2002-03-04
2004-04-06
Pham, Chi (Department: 2663)
Multiplex communications
Network configuration determination
In a bus system
C370S403000, C370S242000
Reexamination Certificate
active
06717922
ABSTRACT:
COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
The invention disclosed herein relates to network configuration protocols and, in particular, to improved configuration protocols and methods for facilitating rapid traffic recovery following a link failure while still preventing loops from occurring in ring topologies.
Two basic requirements for computer networks are the availability of redundancy and the prevention of loops. Redundancy is needed so that a fault or break in a device or path in the network does not cut off traffic flow in the network. Loops occur when a network has multiple active paths between devices at any given time, resulting in the duplication of messages. Loops are prevented by keeping only one path between devices active at any given time. Since both redundancy and loop prevention involve configuration and selection of active and inactive paths, a network must carefully manage the states of its paths to meet both needs.
One solution to the problem of providing redundancy while preventing loops is the spanning tree algorithm or protocol. The spanning tree protocol, defined in IEEE 802.1, is used by bridges in a network to dynamically discover a subset of the network topology that provides path redundancy while preventing loops. Spanning tree protocol provides redundancy by defining a single tree that spans the bridges and maintaining all other paths and connections in a standby or blocked state. The protocol allows bridges to transmit messages to one another that allow each bridge to select its place in the tree and which states should be applied to each of its ports to maintain that place. For example, a port in a given bridge that is connected to an active path at a given time is kept in a forwarding state, in which all data traffic is received and transmitted to the next portion of the network, and a port in the bridge that is connected to an inactive path is kept in a non-forwarding state such as a blocking state in which traffic is blocked through that port.
In particular, bridges in a spanning tree network pass bridge protocol data units, or BPDUs, to one another which contain information including root, bridge and port identifiers and path cost data. This information is used by the bridges, among other things, to “elect” one of the bridges in the spanning tree network to be a unique root bridge for the network, to calculate the shortest, least cost path from each bridge to the root bridge, to select which ports will be blocking, and for each LAN, elect one of the bridges residing in the LAN to be a designated bridge. In brief, the election of a root is performed by each bridge initially assuming itself to be the bridge, each bridge transmitting root BPDUs, each bridge comparing its BPDU information with that received from other bridges, and each bridge deciding whether to stop serving as a root and stop transmitting BPDUs when the configuration of another bridge as root is better than this bridge serving as root. Ports being converted from blocking to forwarding states and back again undergo several possible transition states depending upon the BPDUs received. Once the bridges have all reached their decisions, the network stabilizes or converges, and is eventually loop-free. A similar process is followed after a link failure has occurred in the network, in which case a new root and/or new active paths must be found.
The spanning tree algorithm presents several difficulties, particularly for large networks such as metropolitan area or wide area networks. The spanning tree protocol requires each bridge to perform complex calculations and comparisons related to path costs, which requires substantial processing resources and time. In addition, convergence under the spanning tree algorithm does not occur until all bridges have exchanged messages and evaluated the path costs. Thus, spanning tree has a relatively high convergence time and requires the use of heavy computing resources. Moreover, spanning tree has a seven bridge topology limitation. Thus, spanning tree protocol reduces performance in, and is not entirely adequate for use with, large networks such as MANs and WANs.
Other existing protocols, such as the health check mechanism available in devices offered by, for example, Extreme Networks, provide simplistic fault recovery solutions for use in very basic network configurations. However, no mechanism is available to the best of the inventors' knowledge for allowing such simple solutions to be extended to more complex network configurations, except through the use of spanning tree protocol as discussed above. There is therefore a need for alternative network configuration solutions which provide redundancy and loop free operation but which use minimal computing resources and converge quickly even when used in large networks.
SUMMARY OF THE INVENTION
The present invention provides a network configuration protocol and algorithm which resolves deficiencies with prior protocols. The present invention relies on the appreciation that a large network having many bridges may be built as a combination of smaller networks, many of which may each be arranged in a ring topology. Because ring topology configuration is predetermined, a shorter configuration control packet protocol may be used for each ring to manage redundancy and loop free operation. In addition, each ring may be controlled by a single master bridge, selected for example by a system administrator, and each other bridge in the ring need not and does not make decisions with respect to its status. Finally, only the master bridge needs to change the status of its ports to effect redundancy. Thus, the use of computing resources in each ring and in the network as a whole is kept to a minimum, and redundancy is provided with minimal looping and extremely rapid convergence times.
Thus, in accordance with the invention, a ring loop free topology is achieved by means of selectively blocking and unblocking data traffic in one of the ring ports of a single master bridge for the ring. All other bridges in the ring keep their ports in non-blocked states. In multiple ring topologies, each ring has a single master bridge which chooses one of its ports to be blocking. In case of any link failure inside a given ring, the master bridge quickly detects the failure and automatically changes its blocking port to a non-blocking state in which traffic may flow and follow an alternate path, avoiding the failed link. When a failed link gets restored, the master bridge quickly detects the link restoration and converts its port back to a blocking state to avoid a loop from occurring. Since each ring in the network governs its own link redundancy and loop avoidance, each ring may be connected to other rings or other network environments running other protocols, including spanning tree protocols or other proprietary protocols.
To support large network configurations consisting of connected rings, the invention provides methodologies and data fields in the control packet protocol for coordinating control between connected rings. When two rings are connected through a shared link formed between two shared bridges, e.g., bridges which have ports belonging to the two connected rings, at least one of the rings carries the control packets being forwarded around the other ring. In some embodiments, the ring having the higher priority as between the two connected rings carries the control packets of the lower priority ring. The control packets are preferably marked as native to the lower priority ring, and thus foreign to the higher priority ring, before they are forwarded on to the higher priority ring.
In the event of failure of the shared link, the two connected
Hsu Ivy Pei-Shan
Jalan Rajkumar
Kamat Gurudeep
Kuo Andrew Tai-Chin
Moncada-Elias Jordi
Brown & Raysman Millstein Felder & Steiner LLP
Ferris Derrick W
Foundry Networks Inc.
Pham Chi
LandOfFree
Network configuration protocol and method for rapid traffic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network configuration protocol and method for rapid traffic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network configuration protocol and method for rapid traffic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3203580