Low complexity scheduling algorithm for a buffered crossbar switch with 100% throughput

1. For use in a buffered crossbar switch having

a plurality of output ports,

a plurality of input ports, each of the plurality of input ports having a virtual output queue corresponding to each of the plurality of output ports, and

a switch fabric coupling each of the input ports with each of the output ports, defining crosspoints and including a buffer in the switch fabric at each input port-output port crosspoint,

a scheduling method comprising:

a) for each input port, selecting either (A) the previously served virtual output queue, or (B) a virtual output queue corresponding to a uniform probability selection output for a time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output, for all of the plurality of input ports;

b) if both (1) the selected virtual output queue is non-empty and (2) the corresponding crosspoint buffer is not full, then serving the selected virtual output queue, otherwise serving another, non-empty, virtual output queue with a corresponding non-full crosspoint buffer, using an alternative selection discipline;

c) for each output port, selecting either (A) the previously served crosspoint buffer, or (B) a crosspoint buffer corresponding to the uniform probability selection output for the time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output, for all of the plurality of input ports; and

d) if the selected crosspoint buffer is non-empty, then serving the selected crosspoint buffer, otherwise serving another, non-empty, crosspoint buffer using an alternative selection discipline.

2. The method of claim 1 wherein each crosspoint buffer is a single cell buffer, and

wherein the act of selecting, for each input port, either (A) the previously served virtual output queue, or (B) a virtual output queue corresponding to a uniform probability selection output for a time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output, for all of the plurality of input ports includes

1) tracking, for each input port, a queue length of a virtual output queue that was served in a last time slot and having a corresponding crosspoint buffer that was served in the last time slot,

2) setting a first variable to the queue length tracked if there is a virtual output queue that was served in the last time slot and having a corresponding crosspoint buffer that was served in the last time slot, otherwise setting the first variable to zero,

3) determining a uniform probability selection output for each time slot,

4) determining, for each input port, a queue length of a virtual output queue corresponding to the uniform probability selection output for the time slot,

5) determining, for each input port, a difference value between the first variable and the queue length of the virtual output queue corresponding to the uniform probability selection output for the time slot,

6) determining a binary value using a sum of the difference values determined by all of the input ports, and

7) for each input port, selecting either (A) the previously served virtual output queue, or (B) the virtual output queue corresponding to the uniform probability selection output for the time slot based on the determined binary value.

3. The method of claim 2 wherein the act of selecting, for each output port, selecting either (A) the previously serve crosspoint buffer, or (B) a crosspoint buffer corresponding to the uniform probability selection output for the time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output for all of the plurality of input ports, includes

1) tracking, for each output port, whether a corresponding crosspoint buffer was served in the last time slot, and

2) for each output port, selecting either (A) the previously served crosspoint buffer, or (B) a crosspoint buffer corresponding to the uniform probability selection output for the time slot based on the determined binary value.

4. The method of claim 2 wherein the act of determining a binary value using a sum of the difference values determined by all of the input ports is performed by a centralized scheduler.

5. The method of claim 2 wherein the acts of

tracking, for each input port, a queue length of a virtual output queue that was served in the last time slot and having a corresponding crosspoint buffer that was served in the last time slot,

setting a first variable to the queue length tracked if there is a virtual output queue that was served in the last time slot and having a corresponding crosspoint buffer that was served in the last time slot, otherwise setting the first variable to zero,

determining, for each input port, a queue length of a virtual output queue corresponding to the uniform probability selection output for the time slot,

determining, for each input port, a difference value between the first variable and the queue length of the virtual output queue corresponding to the uniform probability selection output for the time slot,

for each input port, selecting either (A) the previously served virtual output queue, or (B) the virtual output queue corresponding to the uniform probability selection output for the time slot based on the determined binary value, and

if both (1) the selected virtual output queue is non-empty and (2) the corresponding crosspoint buffer is not full, then serving the selected virtual output queue, otherwise serving another, non-empty, virtual output queue using an alternative selection discipline,

are performed locally by each input port.

6. The method of claim 3 wherein the acts of

tracking, for each output port, whether a corresponding crosspoint buffer was served in the last time slot,

for each output port, selecting either (A) the previously served crosspoint buffer, or (B) a crosspoint buffer corresponding to the uniform probability selection output for the time slot based on the determined binary value, and

if the selected crosspoint buffer is non-empty, then serving the selected crosspoint buffer, otherwise serving another, non-empty, crosspoint buffer using an alternative selection discipline,

are performed locally by each output port.

7. The method of claim 2 wherein the act of determining a uniform probability selection output for each time slot is performed by at least one of (A) looking up a stored, predetermined, Hamiltonian walk schedule, (B) computing a Hamiltonian walk schedule output, (C) looking up a stored, predetermined, pseudo-random schedule, and (D) computing a random output.

8. The method of claim 2 wherein the act of determining a uniform probability selection output is performed collectively by each of the plurality of input ports and each of the plurality of output ports.

9. The method of claim 2 wherein the act of determining a uniform probability selection output for each time slot is performed using a finite state machine as a function of the time slot.

10. The method of claim 2 wherein the act of determining a uniform probability selection output for each time slot is performed using a finite state machine as a function of the time slot at each of the plurality of input ports and at each of the plurality of output ports.

11. The method of claim 3 wherein the acts of serving and scheduling are pipelined such that scheduling and serving can occur in the same time slot.

12. The method of claim 11 wherein the alternative selection can check multiple virtual output queues and multiple crosspoint buffers in a single time slot.

13. The method of claim 2 wherein the act of determining, for each input port, a difference value between the first variable and the queue length of the virtual output queue corresponding to the uniform probability selection output for the time slot, is performed locally by each of the plurality of input ports.

14. The method of claim 1 wherein a delay characteristic of the switch is independent of switch size.

15. The method of claim 1 wherein each crosspoint buffer is a multi-cell buffer, and

wherein the act of selecting, for each input port, either (A) the previously served virtual output queue, or (B) a virtual output queue corresponding to a uniform probability selection output for a time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output, for all of the plurality of input ports includes

1) tracking, for each input port, a queue length of a set of one or more virtual output queues having a corresponding non-empty crosspoint buffer that was served in the last time slot,

2) setting a first variable to a sum of the queue lengths tracked of the set of one or more virtual output queues if there is at least one virtual output queue having a corresponding non-empty crosspoint buffer that was served in the last time slot, otherwise setting the first variable to zero,

3) determining a uniform probability selection output for each time slot,

4) determining, for each input port, a queue length of a virtual output queue corresponding to the uniform probability selection output for the time slot,

5) determining, for each input port, a difference value between the first variable and the queue length of the virtual output queue corresponding to the uniform probability selection output for the time slot,

6) determining a binary value using a sum of the difference values determined by all of the input ports, and

7) for each input port, selecting either (A) the previously served virtual output queue, or (B) the virtual output queue corresponding to the uniform probability selection output for the time slot based on the determined binary value.

16. The method of claim 15 wherein the act of selecting, for each output port, either (A) the previously serve crosspoint buffer, or (B) a crosspoint buffer corresponding to the uniform probability selection output for the time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output, for all of the plurality of input ports, includes

1) tracking, for each output port, whether a corresponding crosspoint buffer was served in the last time slot, and

2) for each output port, selecting either (A) the previously served crosspoint buffer, or (B) a crosspoint buffer corresponding to the uniform probability selection output for the time slot based on the determined binary value.

17. The method of claim 15 wherein the act of determining a binary value using a sum of the difference values determined by all of the input ports is performed by a centralized scheduler.

18. The method of claim 15 wherein the acts of

tracking, for each input port, a queue length of a set of one or more virtual output queues having a corresponding non-empty crosspoint buffer that was served in the last time slot,

setting a first variable to a sum of the queue lengths tracked of the set of one or more virtual output queues if there is at least one virtual output queue having a corresponding non-empty crosspoint buffer that was served in the last time slot, otherwise setting the first variable to zero,

determining a uniform probability selection output for each time slot,

determining, for each input port, a queue length of a virtual output queue corresponding to the uniform probability selection output for the time slot,

determining, for each input port, a difference value between the first variable and the queue length of the virtual output queue corresponding to the uniform probability selection output for the time slot, and

for each input port, selecting either (A) the previously served virtual output queue, or (B) the virtual output queue corresponding to the uniform probability selection output for the time slot based on the determined binary value,

are performed locally by each input port.

19. The method of claim 16 wherein the acts of

tracking, for each output port, whether a corresponding crosspoint buffer was served in the last time slot,

for each output port, selecting either (A) the previously served crosspoint buffer, or (B) a crosspoint buffer corresponding to the uniform probability selection output for the time slot based on the determined binary value, and

if the selected crosspoint buffer is non-empty, then serving the selected crosspoint buffer, otherwise serving another, non-empty, crosspoint buffer using an alternative selection discipline,

are performed locally by each output port.

20. The method of claim 15 wherein the act of determining a uniform probability selection output for each time slot is performed by at least one of (A) looking up a stored, predetermined, Hamiltonian walk schedule, (B) computing a Hamiltonian walk schedule output, (C) looking up a stored, predetermined, pseudo-random schedule, and (D) computing a random output.

21. The method of claim 15 wherein the act of determining a uniform probability selection output is performed collectively by each of the plurality of input ports and each of the plurality of output ports.

22. The method of claim 15 wherein the act of determining a uniform probability selection output for each time slot is performed using a finite state machine as a function of the time slot.

23. The method of claim 15 wherein the act of determining a uniform probability selection output for each time slot is performed using a finite state machine as a function of the time slot at each of the plurality of input ports and at each of the plurality of output ports.

24. The method of claim 16 wherein the acts of serving and scheduling are pipelined such that scheduling and serving can occur in the same time slot.

25. The method of claim 24 wherein the alternative selection discipline can check multiple virtual output queues and multiple crosspoint buffers in a single time slot.

26. The method of claim 15 wherein the act of determining, for each input port, a difference value between the first variable and the queue length of the virtual output queue corresponding to the uniform probability selection output for the time slot, is performed locally by each of the plurality of input ports.

27. The method of claim 1 wherein the alternative selection discipline is one of (A) a round robin selection discipline, (B) selecting a most full virtual output queue, and (C) selecting a most full crosspoint buffer.

28. For use in a buffered crossbar switch having

a plurality of output ports,

a plurality of input ports, each of the plurality of input ports having a virtual output queue corresponding to each of the plurality of output ports, and

a switch fabric coupling each of the input ports with each of the output ports, defining crosspoints and including a buffer in the switch fabric at each input port-output port crosspoint,

a scheduling processor programmed to:

a) select, for each input port, either (A) the previously served virtual output queue, or (B) a virtual output queue corresponding to a uniform probability selection output for a time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output, for all of the plurality of input ports;

b) serve the selected virtual output queue if both (1) the selected virtual output queue is non-empty and (2) the corresponding crosspoint buffer is not full, otherwise serving another, non-empty, virtual output queue with a corresponding non-full crosspoint buffer, using an alternative selection discipline;

c) select, for each output port, either (A) the previously served crosspoint buffer, or (B) a crosspoint buffer corresponding to the uniform probability selection output for the time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output, for all of the plurality of input ports; and

d) serve the selected crosspoint buffer if the selected crosspoint buffer is non-empty, otherwise serving another, non-empty, crosspoint buffer using an alternative selection discipline.

29. The scheduler of claim 28 wherein each crosspoint buffer is a single cell buffer, and

wherein the act of selecting by the programmed scheduling processor, for each input port, either (A) the previously served virtual output queue, or (B) a virtual output queue corresponding to a uniform probability selection output for a time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output, for all of the plurality of input ports includes

1) tracking, for each input port, a queue length of a virtual output queue that was served in a last time slot and having a corresponding crosspoint buffer that was served in the last time slot,

2) setting a first variable to the queue length tracked if there is a virtual output queue that was served in the last time slot and having a corresponding crosspoint buffer that was served in the last time slot, otherwise setting the first variable to zero,

3) determining a uniform probability selection output for each time slot,

4) determining, for each input port, a queue length of a virtual output queue corresponding to the uniform probability selection output for the time slot,

5) determining, for each input port, a difference value between the first variable and the queue length of the virtual output queue corresponding to the uniform probability selection output for the time slot,

6) determining a binary value using a sum of the difference values determined by all of the input ports, and

7) selecting, for each input port, either (A) the previously served virtual output queue, or (B) the virtual output queue corresponding to the uniform probability selection output for the time slot based on the determined binary value.

30. The scheduler of claim 28 wherein each crosspoint buffer is a multi-cell buffer, and

wherein the act of selecting by the programmed scheduling processor, for each input port, either (A) the previously served virtual output queue, or (B) a virtual output queue corresponding to a uniform probability selection output for a time slot, as a function of queue lengths of the previously served virtual output queues of all of the plurality of input ports and queue lengths of the virtual output queue corresponding to the uniform probability selection output, for all of the plurality of input ports includes

1) tracking, for each input port, a queue length of a set of one or more virtual output queues having a corresponding non-empty crosspoint buffer that was served in the last time slot,

2) setting a first variable to a sum of the queue lengths tracked of the set of one or more virtual output queues if there is at least one virtual output queue having a corresponding non-empty crosspoint buffer that was served in the last time slot, otherwise setting the first variable to zero,

3) determining a uniform probability selection output for each time slot,

4) determining, for each input port, a queue length of a virtual output queue corresponding to the uniform probability selection output for the time slot,

5) determining, for each input port, a difference value between the first variable and the queue length of the virtual output queue corresponding to the uniform probability selection output for the time slot,

6) determining a binary value using a sum of the difference values determined by all of the input ports, and

7) selecting, for each input port, either (A) the previously served virtual output queue, or (B) the virtual output queue corresponding to the uniform probability selection output for the time slot based on the determined binary value.