On Iterative Scheduling for Input-Queued Switches With a Speedup of $2-1/N$
Bing Hu, Kwan Lawrence Yeung, Qian Zhou, Chunzhi He · IEEE/ACM Transactions on Networking · 2016
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 consists of three phases: report, grant, and accept. In each phase, only a single-bit message per port is sent for reporting a packet arrival, granting an input for packet sending, or accepting a grant. In both the grant and accept phases, scheduling priority is given to the preferred input-output pairs first and the longest virtual output queuing (VOQ) next. The notion of the preferred input-output pair is to keep a global RR schedule among all the inputs and the outputs. By serving the preferred input-output pairs first, the match size tends to be maximized. By serving the longest VOQ next, the match weight is also boosted. When RR/LQF is executed for a single iteration (i.e., RR/LQF-1), we show by simulations that RR/LQF-1 outperforms all the existing single-bit-single-iteration scheduling algorithms. When RR/LQF is executed up to N iterations (i.e., RR/LQF-N), we prove that under any admissible traffic pattern, RR/LQF-N 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 is stable with a speedup less than 2. We then generalize RR/LQF to become a class of algorithms that have the same speedup bound of 2-1/N. Efforts are then made to further reduce the implementation complexity of RR/LQF. To this end, the pipelined RR/LQF and RR/RR, a simpler variant of RR/LQF, are proposed.