Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
2001-07-16
2004-10-19
Lefkowitz, Sumati (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
C370S395310
Reexamination Certificate
active
06807594
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates generally to flow control, and more particularly, to data flow control and arbitration.
B. Description of Related Art
Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting and policing functionality, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at line rate when the new functionality was added.
To meet the new demands, purpose-built routers were designed. Purpose-built routers are designed and built with components optimized for routing. They not only handled higher line rates and higher network traffic volume, they also added functionality without compromising line rate performance.
A purpose-built router may include a number of input and output ports from which it transmits and receives information packets. A switching fabric may be implemented in the router to carry the packets between the ports. In a high-performance purpose-built router, the switching fabric may transmit a large amount of information. If too much information is simultaneously sent to the switching fabric, or if too much information is destined for a specific destination on the switching fabric, the switching fabric or portions of the switching fabric may become congested.
In an effort to efficiently use the switching fabric and to ensure that any particular destination is not unfairly favored over other destinations, arbiters are used to control the timing of data flowing from a source to various destinations on the switching fabric. Separate arbiters control data at each source. With this architecture, however, a problem can occur when different sources try to send data to the same set of destinations. The different arbiters have a tendency to come into synchronism (also called in-stride) with one another, and may thus send a high concentration of data to a single destination, potentially overwhelming the portions of the switch fabric leading to that destination, and then all move on to the next destination and overwhelm it, and so on.
Synchronization of arbiters is a problem which can occur in any system having multiple arbiters operating in parallel. Therefore, the problem exists in many environments other than routing and networking.
It therefore would be desirable to implement arbiters at various data transmission sources that do not tend to come in-stride with one another, even when different sources attempt to send to the same set of destinations.
SUMMARY OF THE INVENTION
Systems and methods consistent with the invention provide, among other things, arbiters that control the sending of information in a manner such that arbiters do not become in-stride.
One aspect of the present invention is directed to an arbiter. The arbiter comprises a randomization table, a mapping component, an arbiter component, a de-randomization table, and an unmapping component. The randomization table stores randomization values. The mapping component modifies data items based on the randomization values. The arbiter component selects certain ones of the modified versions of the data items based on an arbitration scheme. The de-randomization table stores de-randomization values based on the randomization values stored in the randomization table, and the unmapping component converts the selected modified data items from the arbiter component back to original versions of the data items based on the de-randomization values.
An arbiter consistent with a second aspect of the present invention includes a register, a random generator, and an arbiter. The register stores representations of data items and includes a plurality of bits. Each bit represents information of a data item and is set when the data item is waiting to be transmitted. A random generator generates a random pointer that refers to one of the bits of the register. The arbiter selects data items by checking each of the plurality of bits of the register.
A third aspect of the present invention is directed to a method of arbitrating among multiple data items. The method includes randomizing the data items, selecting certain ones of the data items in accordance with an arbitration scheme based on the randomized the data items, and de-randomizing the selected data items.
REFERENCES:
patent: 5267235 (1993-11-01), Thacker
patent: 6343066 (2002-01-01), Magill et al.
patent: 2003/0081548 (2003-05-01), Langevin et al.
Gupta Anurag P.
Lacroute Phil
Sindhu Pradeep
Zhang Song
Harrity & Snyder LLP
Juniper Networks, Inc.
Lefkowitz Sumati
LandOfFree
Randomized arbiters for eliminating congestion does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Randomized arbiters for eliminating congestion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized arbiters for eliminating congestion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300779