QPS-r: A cost-effective iterative switching algorithm for input-queued switches
QPS-r: A cost-effective iterative switching algorithm for input-queued switches
复制标题
QPS-r：一种用于输入队列交换机的经济高效的迭代切换算法
DOI：
10.1016/j.peva.2021.102197
复制
发表时间：
2021
影响因子：
2.2
通讯作者：
Maguluri, Siva Theja
中科院分区：
文献类型：
--
作者：
Gong, Long;Xu, Jun;Liu, Liang;Maguluri, Siva Theja
在输入排队交换机中，需要为每个交换周期或时隙计算交叉开关调度或输入端口与输出端口之间的匹配。当交换机具有大量的端口时，如何设计能够产生高质量匹配的交换算法而又具有很低的计算复杂度是一个具有挑战性的研究问题。实际上，在切换算法的计算复杂度和计算匹配的质量之间似乎存在一个基本的折衷。并行最大匹配算法（适用于切换）似乎是这方面的一个甜蜜的折衷点。一方面，它们提供了以下性能保证：使用最大匹配作为交叉开关调度导致至少50%的交换机吞吐量和顺序最优（即，独立于交换机大小N）各种业务到达过程的平均延迟界限。另一方面，它们的计算复杂度可以低至O（log 2 N）每端口/处理器，这是远远低于那些寻找更高质量的匹配，如最大加权matching.In这项工作中，我们提出了QPS-r，并行迭代切换算法，具有最低的计算复杂度：O（1）每端口。然而，QPS-r计算的匹配在以下意义上具有与最大匹配相同的质量：使用这种匹配作为交叉杆调度，与使用最大匹配完全相同的上述可证明的吞吐量和延迟保证，正如我们使用李雅普诺夫稳定性分析所示。虽然QPS-r建立在一个现有的附加技术称为比例采样（QPS），我们是第一个发现和证明这种匹配的好属性。我们还表明，QPS-3（运行3次迭代）具有可比的经验吞吐量和延迟性能iSLIP（运行log 2 N迭代），一个完善和优化的代表性最大匹配算法适用于切换。
In an input-queued switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed for each switching cycle, or time slot. It is a challenging research problem to design switching algorithms that produce high-quality matchings yet have a very low computational complexity when the switch has a large number of ports. Indeed, there appears to be a fundamental tradeoff between the computational complexity of the switching algorithm and the quality of the computed matchings.Parallel maximal matching algorithms (adapted for switching) appear to be a sweet tradeoff point in this regard. On one hand, they provide the following performance guarantees: Using maximal matchings as crossbar schedules results in at least 50% switch throughput and order-optimal (i.e., independent of the switch size N) average delay bounds for various traffic arrival processes. On the other hand, their computational complexities can be as low as O(log2 N) per port/processor, which is much lower than those of the algorithms for finding matchings of higher qualities such as maximum weighted matching.In this work, we propose QPS-r, a parallel iterative switching algorithm that has the lowest possible computational complexity: O(1) per port. Yet, the matchings that QPS-r computes have the same quality as maximal matchings in the following sense: Using such matchings as crossbar schedules results in exactly the same aforementioned provable throughput and delay guarantees as using maximal matchings, as we show using Lyapunov stability analysis. Although QPS-r builds upon an existing add-on technique called Queue-Proportional Sampling (QPS), we are the first to discover and prove this nice property of such matchings. We also demonstrate that QPS-3 (running 3 iterations) has comparable empirical throughput and delay performances as iSLIP (running log2 N iterations), a refined and optimized representative maximal matching algorithm adapted for switching.