On iterative scheduling for input-queued switches with a speedup of 2amp;#x2212;1/N

摘要

An efficient iterative scheduling algorithm for input-queued switches, called Round Robin with Longest Queue First (RR/LQF), is proposed in this paper. RR/LQF only needs a single bit for request, grant and accept messages respectively. The scheduling priority is given to the preferred input/output pairs first. Each single-bit request is actually an indication of a new packet arrival at the specific VOQ. Based on them, each output keeps track of the size of N VOQs destined to it. In the granting phase, if the preferred input's VOQ is empty, an output port j grants the (non-preferred) input that has the longest VOQ (among N VOQs destined to output j). In the accepting phase, if the preferred VOQ is not empty, input port accepts it directly. Otherwise, an input port i accepts the grant received by the long VOQ (among input i). When RR/LQF is executed for a single iteration, we show that RR/LQF outperforms SRR [15] in all simulations conducted. When RR/LQF is executed (up to N iterations) until finding the maximal size matching in input-queued switches, we prove that RR/LQF is stable with a speedup of 2−1/N, where N is the switch size. To the best of our knowledge, this is the first work showing that an iterative scheduling algorithm for input-queued switches can achieve a speedup requirement less than 2. Though the improvement is just 1/N we successfully tighten the speedup bound.