Motivated by applications in data center networks, in this paper, we study the problem of scheduling in an input queued switch. While throughput maximizing algorithms in a switch are well-understood, delay analysis was developed only recently. It was recently shown that the well-known MaxWeight algorithm achieves optimal scaling of mean queue lengths in steady state in the heavy-traffic regime, and is within a factor less than $2$ of a universal lower bound. However, MaxWeight is not used in practice because of its high time complexity. In this paper, we study several low complexity algorithms and show that their heavy-traffic performance is identical to that of MaxWeight. We first present a negative result that picking a random schedule does not have optimal heavy-traffic scaling of queue lengths even under uniform traffic. We then show that if one picks the best among two matchings or modifies a random matching even a little, using the so-called flip operation, it leads to MaxWeight like heavy-traffic performance under uniform traffic. We then focus on the case of non-uniform traffic and show that a large class of low time complexity algorithms have the same heavy-traffic performance as MaxWeight, as long as it is ensured that a MaxWeight matching is picked often enough. We also briefly discuss the performance of these algorithms in the large scale heavy-traffic regime when the size of the switch increases simultaneously with the load. Finally, we perform empirical study on a new algorithm to compare its performance with some existing algorithms.
翻译:根据数据中心网络的应用,本文中我们研究了输入队列开关的排程问题。 虽然对开关的排量最大化算法非常了解, 但延迟分析只是最近才开发出来。 最近显示, 众所周知的 MaxWeight 算法在重交通制度下以稳定状态实现了平均队列长度的最佳缩放比例, 在重交通制度下, 并且处于一个小于2美元的普遍较低约束范围内。 但是, MaxWeight 并没有在实际中被使用, 因为它的时间复杂度很高。 在本文中, 我们研究了若干低复杂度算法, 并显示其重交通的超重性能与MaxWeight的相同。 我们首先提出一个负面结果, 随机的排程并不具有最佳的超重排长排长的排队列长度缩放比例。 然后我们展示, 如果一个人在两次匹配中选取最好的或稍小的随机匹配一个系数, 使用所谓的翻转操作, 它就会在实际操作中被使用, MaxWeight 和在统一交通中的重交运的动作。 我们随后专注于非统一运算运算的超重运算, 我们的大幅的算算算法, 也最终的大幅的压级演算得相当重的重的重。