论文标题
滑动窗口QPS（SW-QPS）：用于输入气的开关的完美平行迭代开关算法
Sliding-Window QPS (SW-QPS): A Perfect Parallel Iterative Switching Algorithm for Input-Queued Switches
论文作者
论文摘要
在这项工作中，我们首先提出了一种称为小批次队列育育星采样（SB-QP）的并行批处理开关算法。与其他批处理开关算法相比，SB-QP大大降低了批量的大小而不牺牲吞吐量性能，因此当交通负荷轻到中等时，延迟的延迟要较低。通过并行化，它还达到了每个端口每个匹配计算的$ O（1）$的最低时间复杂性。然后，我们提出了另一种称为滑动窗口QPS（SW-QP）的算法。 SW-QP保留并增强了SB-QP的所有好处，并通过新的称为滑动窗口开关的新型切换框架将批处理延迟减少到零。此外，与QPS-1相比，SW-QP计算出更高质量的匹配，该匹配是由最终的定期开关算法QPS-1衡量的，该算法是在相同基础的双分部分匹配算法上构建的。
In this work, we first propose a parallel batch switching algorithm called Small-Batch Queue-Proportional Sampling (SB-QPS). Compared to other batch switching algorithms, SB-QPS significantly reduces the batch size without sacrificing the throughput performance and hence has much lower delay when traffic load is light to moderate. It also achieves the lowest possible time complexity of $O(1)$ per matching computation per port, via parallelization. We then propose another algorithm called Sliding-Window QPS (SW-QPS). SW-QPS retains and enhances all benefits of SB-QPS, and reduces the batching delay to zero via a novel switching framework called sliding-window switching. In addition, SW-QPS computes matchings of much higher qualities, as measured by the resulting throughput and delay performances, than QPS-1, the state-of-the-art regular switching algorithm that builds upon the same underlying bipartite matching algorithm.
