Back to results
US 6,807,594 B1Granted
Randomized arbiters for eliminating congestion
AssigneeJuniper Networks, Inc.
InventorsPradeep Sindhu, Song Zhang, Anurag P. Gupta, Phil Lacroute
Life of this patent
Estimating the term…
Abstract
A system having multiple arbiters is constructed to reduce the chances of arbiters synchronizing with one another. Each arbiter includes a random process that introduces randomness into an arbitration scheme performed by the arbiter. Because of the randomness, the arbiters will not tend to synchronize with one another, even when receiving an identical stream of input values.
Claims30
An arbiter comprising:
- a randomization table storing randomization values;
- a mapping component coupled to the randomization table, the mapping component modifying data items based on the randomization values;
- an arbiter component configured to select certain ones of the modified data items based on an arbitration scheme;
- a de-randomization table storing de-randomization values based on the randomization values stored in the randomization table;
- and
- an unmapping component coupled to the arbiter component and configured to convert the selected modified data items from the arbiter component back to original data items based on the de-randomization values.
3 more elements
An arbiter comprising:
- a register including a plurality of bits, each bit representing a data item, and each bit being set when information associated with the data item is waiting to be transmitted;
- a random generator configured to generate a random pointer that relates to one of the bits of the register;
- and
- an arbiter configured to select data items by checking the plurality of bits of the register including the bit pointed to by the random generator.
1 more element
A method of arbitrating among multiple data items comprising:
- randomizing the multiple data items;
- selecting certain ones of the data items in accordance with an arbitration scheme based on the randomized data items;
- and
- de-randomizing the selected data items.
1 more element
A system comprising:
- a first arbiter receiving a first set of N inputs, where N is an integer, the first arbiter selecting ones of the first set of inputs based on an arbitration scheme that includes an element of randomness when selecting the ones of the first set of inputs;
- and
- a second arbiter receiving a second set of N inputs, the second arbiter selecting ones of the second set of inputs based on an arbitration scheme that includes an element of randomness when selecting the ones of the second set of inputs, the elements of randomness in the first and second arbiters preventing the first and second arbiters from synchronizing with one another.
A network device comprising:
- means for randomizing information associated with an input stream of data items;
- means for arbitrating among the randomized information to select certain ones of the data items;
- and
- means for de-randomizing the selected information.
1 more element
A method comprising:
- selecting ones of a first set of N inputs, where N is an integer, based on an arbitration scheme that includes an element of randomness when selecting the ones of the first set of inputs;
- and
- selecting ones of a second set of N inputs, where N is an integer, based on an arbitration scheme that includes an element of randomness when selecting the ones of the second set of inputs, the elements of randomness in the first and second selections preventing the first and second selections from synchronizing with one another.
Dependencies are inferred from the claim text.