Arbitration using dual round robin matching with exhaustive service of winning virtual output queue
View Patent ↗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.
1. 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.
2. The method of claim 1 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 continue to request and win a subsequent consecutive arbitrations for the output port until the virtual output queue is empty.
3. The method of claim 1 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 continue to request and win a subsequent consecutive arbitrations for the output port until a predetermined number of consecutive cells have been sent from the virtual output queue.
4. The method of claim 1 wherein the act of choosing a next non-empty virtual output queue is performed by updating a position of a pointer, associated with the virtual output queue, in accordance with a fixed scheme.
5. The method of claim 4 wherein the position of the pointer associated with the virtual output queue is updated if and only if the request associated with the virtual output queue was not granted.
6. The method of claim 4 wherein the position of the pointer associated with the virtual output queue is maintained if the request associated with the virtual output queue was granted.
7. The method of claim 1 wherein the act of choosing a next non-empty virtual output queue is performed by updating a position of a pointer, associated with the virtual output queue, in accordance with a round-robin scheme.
8. The method of claim 7 wherein the position of the pointer associated with the virtual output queue is updated if and only if the request associated with the virtual output queue was not granted.
9. The method of claim 7 wherein the position of the pointer associated with the virtual output queue is maintained if the request associated with the virtual output queue was granted.
10. The method of claim 1 wherein the act of selecting a next input port associated with a request sent to the arbiter, thereby defining an input-output match, is performed by updating a position of a pointer, associated with the input ports, in accordance with a fixed scheme.
11. The method of claim 10 wherein the position of the pointer is maintained if any request to the output port arbiter is granted.
12. The method of claim 1 wherein the act of selecting a next input port associated with a request sent to the arbiter, thereby defining an input-output match, is performed by updating a position of a pointer, associated with the input ports, in accordance with a round-robin scheme.
13. The method of claim 12 wherein the position of the pointer is maintained if any request to the output port arbiter is granted.
14. 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.
15. The apparatus of claim 14 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 continue to request and win a subsequent consecutive arbitrations for the output port until the virtual output queue is empty.
16. The apparatus of claim 14 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 continue to request and win a subsequent consecutive arbitrations for the output port until a predetermined number of consecutive cells have been sent from the virtual output queue.
17. The apparatus of claim 14 wherein the means for choosing a next non-empty virtual output queue updates a position of a pointer, associated with the virtual output queue, in accordance with a fixed scheme.
18. The apparatus of claim 17 wherein the means for choosing updates the position of the pointer associated with the virtual output queue if and only if the request associated with the virtual output queue was not granted.
19. The apparatus of claim 17 wherein the means for choosing maintains the position of the pointer associated with the virtual output queue if the request associated with the virtual output queue was granted.
20. The apparatus of claim 14 wherein the means for choosing a next non-empty virtual output queue updates a position of a pointer, associated with the virtual output queue, in accordance with a round-robin scheme.
21. The apparatus of claim 20 wherein the means for choosing updates the position of the pointer associated with the virtual output queue if and only if the request associated with the virtual output queue was not granted.
22. The apparatus of claim 20 wherein means for choosing maintains the position of the pointer associated with the virtual output queue if the request associated with the virtual output queue was granted.
23. The apparatus of claim 14 wherein the means for selecting a next input port associated with a request sent to the arbiter, thereby defining an input-output match, updates a position of a pointer, associated with the input ports, in accordance with a fixed scheme.
24. The apparatus of claim 23 wherein the means for selecting maintains the position of the pointer if any request to the output port arbiter is granted.
25. The apparatus of claim 14 wherein the means for selecting a next input port associated with a request sent to the arbiter, thereby defining an input-output match, updates a position of a pointer, associated with the input ports, in accordance with a round-robin scheme.
26. The apparatus of claim 25 wherein the means for selecting maintains the position of the pointer if any request to the output port arbiter is granted.