Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
1999-07-09
2002-10-15
Lefkowitz, Sumati (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
C710S105000
Reexamination Certificate
active
06467006
ABSTRACT:
TECHNICAL FIELD
This invention provides a priority arbitration mechanism for selecting a “master” frame switch from a plurality of stacked frame switches. The mechanism is independent of the topology used to interconnect the switches.
BACKGROUND
“Stackable” Ethernet switches are emerging as a possible alternative to chassis-based modular Ethernet switches, offering some of the same expandability and unified management capabilities as chassis-based systems without the concomitant start-up cost and configuration problems. These switches usually consist of one or more identical boxes, “stacked” one on top of another, and interconnected by means of cables carrying Ethernet packet data as well as control information. Switches interconnected in this fashion perform as a single entity (with respect to management protocols) rather than as a collection of isolated units. This simplifies the network manager's task by facilitating presentation of a unified view of a large network.
Each of the individual units constituting a stack of switches normally contains a stack controller central processing unit (CPU) that serves to configure and manage the system. Because the individual units are identical, a stacked system contains multiple stack controller CPUs. It is necessary to prevent conflicts and contention among the multiple CPUs by allowing only one CPU to function as a controller (for the entire stack) at a time, and by preventing the other CPUs from interfering with the management operations. Support for stackable switches thus typically involves implementing some means whereby only one of several CPUs in the stack is permitted to operate at a time.
It is possible to manually select a particular stack controller CPU to act as the overall stack controller, or “master”. However, this can create problems stemming from user error or CPU failure. It is preferable to implement some form of autonomous process whereby each of the multiple stack controller CPUs contend with one another in an “election” or priority arbitration scheme for control of the stack, with a single “winner” being permitted to assume stack mastership and perform the required configuration and management operations. This has the further advantage of allowing an automatic switchover of mastership from one CPU to another in the event of a CPU failure. Thus, if a previously determined “winner” fails during operation, then a new “winner” can be automatically “elected”, without human intervention, to take over the management of the stack.
Current implementations of stackable switches use some form of auxiliary hardware, requiring special connections or support logic, to resolve contention between multiple stack controller CPUs in a single system. This has the disadvantage of increased cost, as well as rendering the election process dependent on the specific system topology (i.e., the pattern of interconnections between units in a stack). In addition, these approaches are difficult to scale, and hence restrict the number of units that may be placed in a single stack. Examples of such prior art implementations include “Futurebus+Logical Protocol Specification”, ISO/IEC 10857:1994 (IEEE 896.1, 1994); and, The Philips Semiconductors “12C-Bus Specification”, Version 2.0, December, 1998.
A preferable priority arbitration process for implementing the stack controller CPU election process should satisfy the following objectives:
1. The process must be completely automatic, requiring no manual intervention or configuration.
2. The process must function properly with unknown stack interconnect topologies, because the topology may be unknown at the time that a stack controller CPU is required to begin performing its duties.
3. The process must support automatic switchover from any “winner” stack controller CPU to a backup CPU if the “winner” CPU fails for any reason during switch operation.
4. The process must be capable of dealing with the addition or removal of new stack controllers at random times without failure. This may occur, for example, as individual units within the same stack are powered on at slightly varying intervals, or when a new unit is added to a stack and interconnected to the existing units.
5. The process must be robust in the face of errors, and must not rely on any precise timing relationships between signals in different units in the stack. In particular, the process should not rely on any centralized mechanism, but should use a completely distributed approach to avoid creating a single point of failure that could potentially prevent a backup CPU from taking over from a failed CPU.
6. The process algorithm should be simple and reliable, and the implementation should not be expensive in terms of hardware or bandwidth resources.
7. The process algorithm should be capable of being implemented without consuming a large amount of interconnect bandwidth (in the form of additional physical interconnects, or data transfer capacity within existing interconnects) during the arbitration process.
The present invention satisfies the foregoing objectives.
SUMMARY OF THE INVENTION
The invention provides a topology-independent priority arbitration mechanism for realizing the stack controller arbitration process, and is preferably implemented as a combination of hardware and software. The hardware performs basic, primitive operations respecting the transfer of individual bits of information between stack controller CPUs. The software utilizes the hardware to perform the actual priority arbitration process and “elect” a single CPU to be the “master” of the stacked system.
The priority arbitration mechanism is implemented in a distributed manner, with each stack controller CPU running an dentical copy of the software and possessing an identical set of hardware resources. This eliminates the possibility of a single point of failure that would prevent a backup CPU from taking over “mastership” of the stack in the event of a catastrophic failure of the current stack master. To deal with the situation where the currently elected stack controller CPU is removed from the stack (either by system failure, or by the removal of the unit containing the CPU), the priority arbitration procedure is continuously repeated while the stack is powered on. A resolution mechanism is provided to determine when a backup stack controller CPU should be allowed to assume mastership if the current stack master is no longer present, or is not functioning. In addition, this simplifies the process of dealing with the insertion or removal of units containing stack controller CPUs at arbitrary times; the removal of a unit may be treated equivalently to the failure of a controller, and no special considerations are required to handle this event.
The general architectural model within which the priority arbitration mechanism is expected to operate is that of a set of stack controller CPUs (typically, one CPU is located within one unit within the stack) interconnected by means of a switching fabric. The fabric is required to switch data from one physical port to another, to fulfill the functions of a network switching system. The priority arbitration mechanism consumes a very small portion of the transfer bandwidth of the switching fabric in order to transfer control information between CPUs and implement the controller arbitration algorithm.
REFERENCES:
patent: 4467418 (1984-08-01), Quinquis
patent: 4470110 (1984-09-01), Chiarottino et al.
patent: 4626843 (1986-12-01), Szeto et al.
patent: 4633394 (1986-12-01), Georgiou et al.
patent: 4654655 (1987-03-01), Kowalski
patent: 4667192 (1987-05-01), Schmid et al.
patent: 4719458 (1988-01-01), Miesterfeld et al.
patent: 5101482 (1992-03-01), Kipnis
patent: 5263163 (1993-11-01), Holt et al.
patent: 5398243 (1995-03-01), Aguilhon et al.
patent: 5555420 (1996-09-01), Sarangdhar et al.
patent: 5557754 (1996-09-01), Sone et al.
patent: 5689657 (1997-11-01), Desor et al.
patent: 5740174 (1998-04-01), Somer
patent: 5754803 (1998-05-01), Regis
patent: 5781745 (1998-07-01), Ramelson et al.
patent: 5968154 (1999-10-01),
Alexander Thomas
Smith Matt
Lefkowitz Sumati
Oyen Wiggs Green & Mutala
PMC-Sierra Inc.
LandOfFree
Topology-independent priority arbitration for stackable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Topology-independent priority arbitration for stackable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topology-independent priority arbitration for stackable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2992134