Scheduling policies for CIOQ switches
Alex Kesselman, Adi Rosén · 2003
Combined input and output queued (CIOQ) architectures with a moderate fabric speedup S>1 have come to play a major role in the design of high performance switches. The switch policy that controls such switches must consist of two components. A buffer management policy that controls admission to buffers, and a scheduling policy that schedules the transfer of packets from input buffers to output buffers. The goal of the switch policy is to maximize the throughput of the switch. When all packets have a uniform value (or importance), this corresponds to the number of packets sent from the switch. When packets have variable values, this corresponds to the total value of the packets sent.We mainly consider switches with virtual output queuing (VOQ) at the inputs. For the case of packets with uniform values we present a switch policy that is 3-competitive for any speedup. For the case of packets with variable values we propose two preemptive switch policies. One achieves a competitive ratio of 4S, and the other achieves a competitive ratio of 8min(k, 2log α), where k is the number of distinct packet values and α is the ratio between the largest and smallest values.