Back to results
US 2008/0175259 A1Published application
Low complexity scheduling algorithm for a buffered crossbar switch with 100% throughput
AssigneePolytechnic Institute of New York Universiity
InventorsH. Jonathan CHAO, Shivendra S. Panwar, Yanming Shen
Life of this patent
Estimating the term…
Abstract
Scheduling techniques for use with buffered crossbar switches, without speedup, which can provide 100% throughput are described. Each input/output may keep track of the previously served VOQ/crosspoint buffer. The queue lengths of such VOQs and the queue lengths of VOQs corresponding to a uniform probability selection output (e.g., from a Hamiltonian walk schedule) are used to improve the schedule at each time slot.
Claims30
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.
6 more elements
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 scheduler comprising:
- a) means for 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;
- b) means for serving 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) means for selecting, 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) means for serving the selected crosspoint buffer if the selected crosspoint buffer is non-empty, otherwise serving another, non-empty, crosspoint buffer using an alternative selection discipline.
6 more elements
Dependencies are inferred from the claim text.