Short and long term fair shuffling for crossbar switch arbiter

Details Short and long term fair shuffling for crossbar switch arbiter Short and long term fair shuffling for crossbar switch arbiter

2000-04-17

2004-05-11

Pham, Chi (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S386000, C370S462000

Reexamination Certificate

active

06735212

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to packet switched data handling systems and, more particularly, to a high speed router or ATM (asynchronous transfer mode) switch employing a crossbar type switch controlled in a manner which can very rapidly and efficiently allocate available connection points.
2. Description of the Background Art
There is increasing interest in providing communications between disparate computer systems and even between networks of differing characteristics. Further, with the availability of very high bandwidth trunk lines, e.g., using fiber optic cables, there is increasing interest in combining traffic from a great variety of sources for transmission through a single trunk line. For wide area networks, packet switching technology is widely used where information to be transmitted is broken into packets of data which are preceded by headers containing information useful in routing. The header may also identify the source and the destination. Whether truly packet switched or not, most digital communication systems employ message formats in which there is an identifying header of some sort.
As is well known, data network usage is expanding at a great rate both in terms of private networks and also public networks such as the Internet. While transmission link bandwidths keep improving, the technology of the systems which connect the links has lagged behind. In particular, routers are needed which can keep up with the higher transmission link bandwidths. A high speed router needs to achieve three goals. First, it needs to have enough internal bandwidth to move packets between its input and output interfaces at the desired rates. Second, it needs enough packet processing power at the interfaces to forward the packets and, third, the router needs to be able to redirect the packets between possible paths at the requisite rates.
Conventional routers are bus based, that is, a high speed bus is provided which can link a single input to a single output at one time. The router of the present invention utilizes a crossbar switch type interconnection scheme between inputs and outputs.
One problem which exists in the context of packet switching via a crossbar switch is the allocation of available paths through the crossbar. As is understood by those skilled in the art, for unicast traffic, only a limited number of switch points can be utilized at any one time since a single input should not be connected to more than one output at a given time and, likewise, each output should only be connected to a single input.
Allocation of the available paths through a crossbar switch is performed by a device called an arbiter. An arbiter is so named because it resolves (arbitrates) conflicting resource demands. Such arbiters are discussed, for example, in the publication “Symmetric Crossbar Arbiters for VLSI Communication Switches,” by Yuval Tamir and Hsin-Chou Chi,
IEEE Transactions on Parallel and Distributed Systems,
Vol. 4, No. 1, 1993 [hereinafter “Tamir and Chi (1993)”], the disclosure of which is incorporated by reference.
In order to provide high efficiency and throughput, an arbiter has to operate at very high speed in determining which of competing possibilities will be accommodated. Further, in many circumstances, the arbiter is preferably fair in the sense it does not overly favor one source or destination over another or one form of data communication over another. Given that very disparate patterns can exist in data communication demands, particularly when accommodating data originating from disparate systems, the allocation problem is not a simple one.
One prior art system for allocating crossbar connection points is described in U.S. Pat. No. 5,734,649, titled “Data Packet Router,” with named inventors Philip Carvey and Thomas Clarke. As described in that patent, sources are assigned in accordance with a first pseudo-random shuffle pattern, and destinations are assigned in accordance with a second pseudo-random shuffle pattern. A new set of pseudo-random shuffle patterns is generated for each interval. An incremental testing is performed across the data array to locate matches not previously allocated and each match found is successively allocated to the switch element corresponding to the data element. After testing, the complete array of switch elements are operated during a subsequent interval in accordance with the previously determined allocations.
However, the prior art system has substantial drawbacks. First, the prior art system is based on pseudo-random numbers and so merely tends to be fair; actual long-term fairness in the allocation of switching resources is not necessarily ensured by the prior art system.
Second, short-term fairness is not provided by the prior art system. Because the prior art switching algorithm is random in nature, the likelihood of short-term unfairness is built into the prior art process. The likelihood of short-term unfairness is to be expected from any random process. For example, short-term unfairness exists when a “pass” or “don't pass” streak occurs when rolling dice in a game of craps. While the expected distribution is close to 50-50 for “passes” or “don't passes” in that game, several passes or don't passes in a row frequently occur. For example, over say 20 rolls of the dice, 10 passes and 10 don't passes may be expected according to probability, but the actual number of passes is likely to outnumber the number of don't passes, or vice-versa.
SUMMARY OF THE INVENTION
The present invention provides a method and system that overcome the above described problems and disadvantages. The method and system includes a short and long term fair shuffling procedure in an arbitration algorithm for a crossbar switch.
In accordance with the present invention, the shuffling algorithm is deterministic, rather than random, in nature. The shuffling sequence is chosen to ensure a high level of short-term fairness. To ensure long-term fairness, all permutations are eventually used.
Further in accordance with the present invention, both row (input) and column (output) shufflers are used to shuffle priorities of requests. In a preferred embodiment, permuters and shifters are utilized in the shuffler circuits.


REFERENCES:
patent: 4630045 (1986-12-01), Georgiou
patent: 5072366 (1991-12-01), Simcoe
patent: 5517495 (1996-05-01), Lund et al.
patent: 5734649 (1998-03-01), Carvey et al.
patent: 6370148 (2002-04-01), Calvignac et al.
Tamir, Yuval, “Symmetric Crossbar Arbiters for VLSI Communication Switches,”IEEE Transactions on Parallel and Distributed Systems,vol. 4, No. 1, pp. 13-27 (1993).

Affiliated with

Also associated with

Rating

Short and long term fair shuffling for crossbar switch arbiter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Short and long term fair shuffling for crossbar switch arbiter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Short and long term fair shuffling for crossbar switch arbiter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3198508