|
We describe a novel method for scheduling high-speed network switches. The
targeted architecture is an input-buffered switch with a non-blocking switch
fabric. The input buffers are organized as virtual output queues to avoid
head-of-line blocking. The task of the scheduler is to decide when the input
ports can forward packets from the virtual output queues to the corresponding
output ports. Our Least Choice First (LCF) scheduling method selects the input
and output ports to be matched by prioritizing the input ports according to the
number of virtual output queues that contain packets: The fewer virtual output
queues with packets, the higher the scheduling priority of the input port. This
way, the number of switch connections and, with it, switch throughput is
maximized. Fairness is provided through the addition of a round-robin
algorithm.
We present two alternative implementations: A central implementation intended
for narrow switches and a distributed implementation based on an iterative
algorithm intended for wide switches.
The simulation results show that the LCF scheduler outperforms other scheduling
methods such as the parallel iterative matcher [1], iSLIP [12], and the wave
front arbiter [16].
This report is an extended version of a paper presented at IPDPS 2002, Fort
Lauderdale, Florida, April 2002.
|
