Arbitration using dual round robin matching with exhaustive service of winning virtual output queue
AssigneePolytechnic University
InventorsHung-Hsiang Jonathan Chao, Yihan Li, Shivendra S. Panwar
Life of this patent
Estimating the term…
Abstract
An exhaustive service dual round-robin matching (EDRRM) arbitration process amortizes the cost of a match over multiple time slots. It achieves high throughput under nonuniform traffic. Its delay performance is not sensitive to traffic burstiness, switch size and packet length. Since cells belonging to the same packet are transferred to the output continuously, packet delay performance is improved and packet reassembly is simplified.
Claims26
For use with a switch having a first number of input ports, a second number of output ports, each of the input ports having the second number of virtual output queues, a method for arbitrating the dispatch of cells or packets stored in the virtual output queues, the method comprising:
- a) for each input port,
- i) choosing a next non-empty virtual output queue, and
- ii) sending a request to an arbiter for the output corresponding to the chosen non-empty virtual output queue;
- and
- b) for each output port arbiter,
- i) selecting a next input port associated with a request sent to the arbiter, thereby defining an input-output match, and
- ii) indicating to each input port associated with a request sent to the arbiter, whether or not its request was granted,
- wherein, for each input-output match, if the virtual output queue of the input corresponding to the output has any remaining cells, the virtual output queue will request and win a next arbitration for the output port.
For use with a switch having a first number of input ports, a second number of output ports, each of the input ports having the second number of virtual output queues, an apparatus for arbitrating the dispatch of cells or packets stored in the virtual output queues, the apparatus comprising:
- a) for each input port,
- i) means for choosing a next non-empty virtual output queue, and
- ii) means for sending a request to an arbiter for the output corresponding to the chosen non-empty virtual output queue;
- and
- b) for each output port arbiter,
- i) means for selecting a next input port associated with a request sent to the arbiter, thereby defining an input-output match, and
- ii) means for indicating to each input port associated with a request sent to the arbiter, whether or not its request was granted,
- wherein, for each input-output match, if the virtual output queue of the input corresponding to the output has any remaining cells, the virtual output queue will request and win a next arbitration for the output port.
Dependencies are inferred from the claim text.