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 和在统一交通中的重交运的动作。 我们随后专注于非统一运算运算的超重运算, 我们的大幅的算算算法, 也最终的大幅的压级演算得相当重的重的重。

0
下载
关闭预览

相关内容

Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
车辆目标检测
数据挖掘入门与实战
30+阅读 · 2018年3月30日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】树莓派/OpenCV/dlib人脸定位/瞌睡检测
机器学习研究会
9+阅读 · 2017年10月24日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
VIP会员
相关资讯
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
车辆目标检测
数据挖掘入门与实战
30+阅读 · 2018年3月30日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】树莓派/OpenCV/dlib人脸定位/瞌睡检测
机器学习研究会
9+阅读 · 2017年10月24日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员