IP Library › Granted Patent US 8,432,927
Granted Patent B2
US 8,432,927 · App. 10/036,809 · Granted Apr 30, 2013

Scalable two-stage virtual output queuing switch and method of operation

View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 8,432,927
App. No.
10/036,809
Filed
Dec 31, 2001
Granted
Apr 30, 2013
Kind
B2
Art Unit
2462
USPC
370/412
Abstract

A fixed-size data packet switch comprising: 1) N input ports for receiving incoming fixed-size data packets at a first data rate and outputting the fixed-size data packets at the first data rate; 2) N output ports for receiving fixed-size data packets at the first data rate and outputting the fixed-size data packets at the first data rate; and 3) a switch fabric interconnecting the N input ports and the N output ports. The switch fabric comprises: a) N input buffers for receiving incoming fixed-size data packets at the first data rate and outputting the fixed-size data packets at a second data rate equal to at least twice the first data rate; b) N output buffers for receiving fixed-size data packets at the second data rate and outputting the fixed-size data packets at the first data rate; and c) a bufferless, non-blocking interconnecting network for receiving from the N input buffers the fixed-size data packets at the second data rate and transferring the fixed-size data packets to the N output buffers at the second data rate.

Claims (92)

1. A switch comprising:

input buffers internal to a switch fabric, the input buffers configured to:

receive, from external input buffers that are external to the switch fabric, fixed-size data packets at a first data rate, and

output the fixed-size data packets at a second data rate, the second data rate at least twice the first data rate;

output buffers internal to the switch fabric, the output buffers configured to:

receive the fixed-size data packets at the said second data rate, and

output, to an external output buffer external to the switch fabric, the fixed-size data packets at the first data rate;

a bufferless, non-blocking interconnecting network configured to transfer the fixed-size data packets from the input buffers to the output buffers;

a scheduling controller configured to:

schedule a transfer of fixed-size data packets from the external input buffers to the input buffers,

determine a maximal matching of input buffers to output buffers for all the fixed-size data packets that are currently queued at the input buffers,

schedule a transfer, based on the determination, of the fixed-size data packets in the input buffers to the output buffers through the bufferless, non-blocking interconnecting network, the transfer identifying a matched head of line of the fixed-size data packets, and

schedule the transfer of fixed-size data packets from the switch fabric to the external output buffer; and

wherein the input buffers, output buffers, and bufferless, non-blocking interconnecting network emulate a buffered crossbar.

2. The switch fabric of claim 1 , wherein said bufferless, non-blocking interconnecting network comprises a bufferless crossbar.

3. The switch fabric of claim 2 , wherein each of the input buffers is at least twice the size of each of the output buffers.

4. The switch fabric of claim 1 , wherein each of the input buffers is at least twice the size of each of the output buffers.

5. A method of operating a switch, the method comprising:

storing, at external input buffers that are external to the switch fabric, fixed-size data packets; a scheduling controller for:

scheduling a transfer of the fixed-size data packets from the external input buffers to input buffers, the input buffers internal to a switch fabric, and the transfer occurring at a first data rate;

scheduling a transfer of the fixed-size data packets from the input buffers to output buffers through a bufferless, non-blocking interconnecting network, the output buffers internal to a switch fabric, the transfer occurring at a second data rate, the second data rate at least twice the first data rate, the scheduling based on a maximal matching determination of input buffers to output buffers for all fixed-size data packets that are currently queued at the input buffers, and the transfer identifying a matched head of line of the fixed-size data packets;

scheduling the transfer of fixed-size data packets from the switch fabric to an external output buffer; and

wherein the input buffers, output buffers, and bufferless, non-blocking interconnecting network emulate a buffered crossbar.

6. The method fabric of claim 5 , wherein said bufferless, non-blocking interconnecting network comprises a bufferless crossbar.

7. The method fabric of claim 6 , wherein each of the input buffers is at least twice the size of each of the output buffers.

8. The method fabric of claim 5 , wherein each of the input buffers is at least twice the size of each of the output buffers.

9. A fixed-size data packet switch comprising:

external input buffers that are external to a switch fabric;

external output buffers that are external to the switch fabric;

input buffers internal to a switch fabric, the input buffers configured to:

receive, from the external input buffers, fixed-size data packets at a first data rate, and

output the fixed-size data packets at a second data rate, the second data rate at least twice the first data rate;

output buffers internal to the switch fabric, the output buffers configured to:

receive the fixed-size data packets at the second data rate, and

output, to the external output buffer, the fixed-size data packets at the first data rate;

a bufferless, non-blocking interconnecting network configured to transfer the fixed-size data packets from the input buffers to the output buffers;

a scheduling controller configured to:

schedule a transfer of the fixed-size data packets from the external input buffers to the input buffers,

determine a maximal matching of input buffers to output buffers for all the fixed data packets that are currently queued at the input buffers,

schedule a transfer, based on the determination, of the fixed data packets in the input buffers to the output buffers through the bufferless, non-blocking interconnecting network, the transfer identifying a matched head of line of the fixed-size data packets, and

schedule the transfer of the fixed-size data packets from the switch fabric to the external output buffer; and

wherein the input buffers, output buffers, and bufferless, non-blocking interconnecting network emulate a buffered crossbar.

10. The switch of claim 9 , wherein said bufferless, non-blocking interconnecting network comprises a bufferless crossbar.

11. The switch of claim 9 , wherein each of the input buffers is at least twice the size of each of the output buffers.

12. A switch comprising:

input buffers internal to a switch fabric, the input buffers configured to:

receive, from external input buffers that are external to the switch fabric, fixed-size data packets at a first data rate, and

output the fixed-size data packets at a second data rate, the second data rate at least twice the first data rate;

output buffers internal to the switch fabric, the output buffers configured to:

receive the fixed-size data packets at the said second data rate, and

output, to an external output buffer external to the switch fabric, the fixed-size data packets at the first data rate;

a bufferless, non-blocking interconnecting network configured to transfer the fixed-size data packets from the input buffers to the output buffers;

a scheduling controller configured to:

schedule a transfer of fixed-size data packets from the external input buffers to the input buffers,

determine a maximal matching of input buffers to output buffers for all the fixed-size data packets that are currently queued at the input buffers,

schedule a transfer, based on the determination, of the fixed-size data packets in the input buffers to the output buffers through the bufferless, non-blocking interconnecting network, the transfer identifying a matched head of line of the fixed-size data packets,

schedule the transfer of the fixed-size data packets from the external input buffer to the input buffer once per time slot, and

schedule the transfer, based on the determination, of the fixed-size data packets in the input buffer to the output buffer through a bufferless, non-blocking interconnecting network twice per time slot; and

wherein the input buffers, output buffers, and bufferless, non-blocking interconnecting network emulate a buffered crossbar.

13. The switch of claim 12 , wherein the scheduling controller is further configured to:

schedule the transfer of the fixed-size data packets from the switch fabric to the external output buffer.

14. The switch of claim 12 , wherein each of the input buffers is at least twice the size of each of the output buffers.

15. A method of operating a switch, the method comprising:

storing, at external input buffers that are external to the switch fabric, fixed-size data packets; a scheduling controller for:

scheduling a transfer of the fixed-size data packets from the external input buffers to input buffers, the input buffers internal to a switch fabric, and the transfer occurring at a first data rate;

scheduling a transfer of the fixed-size data packets from the input buffers to ouput buffers through a bufferless, non-blocking interconnecting network, the output buffers internal to a switch fabric, the transfer occurring at a second data rate, the second data rate at least twice the first data rate, the scheduling based on a maximal matching determination of input buffers to output buffers for all fixed-size data packets that are currently queued at the input buffers, and the transfer identifying a matched head of line of the fixed-size data packets;

wherein the scheduling of the transfer of fixed-size data packets from the external input buffer to the input buffer is carried out once per time slot;

wherein the scheduling of the transfer, based on the determination, of fixed-size data packets in the input buffer to the output buffer through a bufferless, non-blocking interconnecting network is carried out twice per time slot; and

wherein the input buffers, output buffers, and bufferless, non-blocking interconnecting network emulate a buffered crossbar.

16. The method of claim 15 , further comprising:

scheduling the transfer of fixed-size data packets from the switch fabric to the external output buffer.

17. The method of claim 15 , wherein each of the input buffers is at least twice the size of each of the output buffers.

18. A fixed-size data packet switch comprising:

external input buffers that are external to a switch fabric;

external output buffers that are external to the switch fabric;

input buffers internal to a switch fabric, the input buffers configured to:

receive, from the external input buffers, fixed-size data packets at a first data rate, and

output the fixed-size data packets at a second data rate, the second data rate at least twice the first data rate;

output buffers internal to the switch fabric, the output buffers configured to:

receive the fixed-size data packets at the second data rate, and

output, to the external output buffer, the fixed-size data packets at the first data rate;

a bufferless, non-blocking interconnecting network configured to transfer the fixed-size data packets from the input buffers to the output buffers;

a scheduling controller configured to:

schedule a transfer of the fixed-size data packets from the external input buffers to the input buffers,

determine a maximal matching of input buffers to output buffers for all the fixed data packets that are currently queued at the input buffers,

schedule a transfer, based on the determination, of the fixed data packets in the input buffers to the output buffers through the bufferless, non-blocking interconnecting network, the transfer identifying a matched head of line of the fixed-size data packets, and

schedule the transfer of the fixed-size data packets from the external input buffer to the internal input buffer once per time slot, and

schedule the transfer, based the determination, of the fixed-size data packets in the input buffer to the output buffer through a bufferless, non-blocking interconnecting network twice per time slot; and

wherein the input buffers, output buffers, and bufferless, non-blocking interconnecting network emulate a buffered crossbar.

19. The switch of claim 18 , wherein the scheduling controller is further configured to:

schedule the transfer of the fixed-size data packets from the switch fabric to the external output buffer.

20. The method fabric of claim 18 , wherein each of the input buffers is at least twice the size of each of the output buffers.