Scheduling policies for CIOQ switches

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 is responsible for 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 sent packets.We derive a number of scheduling policies for CIOQ switches and analyze their throughput using competitive analysis. We thus give for these policies a uniform throughput guarantee, regardless of specific traffic patterns. 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 switch policies. One achieves a competitive ratio of 4S, and the other achieves a competitive ratio of 8min(k,2⌈logα⌉), where k is the number of distinct packet values and α is the ratio between the largest and the smallest value.