On iterative scheduling for input-queued switches with a speedup of 2−1/N
On iterative scheduling for input-queued switches with a speedup of 2−1/N
复制标题
DOI：
10.1109/hpsr.2014.6900877
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Bing Hu;K. Yeung;Chunzhi He
中科院分区：
文献类型：
--
作者：
Bing Hu;K. Yeung;Chunzhi He
本文提出了一种用于输入排队交换机的高效迭代调度算法，称为最长队列优先轮询算法（RR/LQF）。 RR/LQF 分别只需要一个比特来表示请求、授予和接受消息。首先将调度优先级赋予优选的输入/输出对。每个单位请求实际上是新数据包到达特定 VOQ 的指示。基于它们，每个输出都会跟踪发往它的 N 个 VOQ 的大小。在授予阶段，如果优选输入的VOQ为空，则输出端口j授予具有最长VOQ（在指定为输出j的N个VOQ中）的（非优选）输入。在接受阶段，如果首选VOQ不为空，则输入端口直接接受。否则，输入端口 i 接受长 VOQ（输入 i 中）接收的授权。当 RR/LQF 执行单次迭代时，我们表明 RR/LQF 在所有进行的模拟中均优于 SRR [15]。当执行 RR/LQF（最多 N 次迭代）直到找到输入排队交换机中的最大大小匹配时，我们证明 RR/LQF 是稳定的，加速比为 2-1/N，其中 N 是交换机大小。据我们所知，这是第一个表明输入排队交换机的迭代调度算法可以实现小于 2 的加速比要求的工作。尽管改进仅为 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.