This paper initiates the study of online algorithms for the maximum weight $b$-matching problem, a generalization of maximum weight matching where each node has at most $b \geq 1$ adjacent matching edges. The problem is motivated by emerging optical technologies which allow to enhance datacenter networks with reconfigurable matchings, providing direct connectivity between frequently communicating racks. These additional links may improve network performance, by leveraging spatial and temporal structure in the workload. We show that the underlying algorithmic problem features an intriguing connection to online paging (a.k.a. caching), but introduces a novel challenge. Our main contribution is an online algorithm which is $O(b)$-competitive; we also prove that this is asymptotically optimal. We complement our theoretical results with extensive trace-driven simulations, based on real-world datacenter workloads as well as synthetic traffic traces.


翻译:本文开始研究最大重量($b$)匹配问题的在线算法, 在每个节点最多拥有$b \geq 1美元相邻匹配边缘的地方, 将最大重量匹配的普及化。 问题的起因是新兴的光学技术, 能够通过重新配置匹配加强数据中心网络, 提供经常沟通的架子之间的直接连接。 这些额外的链接可以提高网络的性能, 在工作量中利用空间和时间结构。 我们显示, 根本的算法问题具有与在线调试( a.k.a.caching) 连接的吸引力, 但却带来了新的挑战。 我们的主要贡献是在线算法, 它具有O(b)$- 竞争性; 我们还证明, 这是一种微量的最佳方法。 我们用基于真实世界数据中心工作量和合成交通轨迹的广泛的微动模拟来补充我们的理论结果。

0
下载
关闭预览

相关内容

Networking:IFIP International Conferences on Networking。 Explanation:国际网络会议。 Publisher:IFIP。 SIT: http://dblp.uni-trier.de/db/conf/networking/index.html
专知会员服务
44+阅读 · 2020年10月31日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
人工智能 | ACCV 2020等国际会议信息5条
Call4Papers
6+阅读 · 2019年6月21日
CCF推荐 | 国际会议信息8条
Call4Papers
9+阅读 · 2019年5月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能 | NIPS 2019等国际会议信息8条
Call4Papers
7+阅读 · 2019年3月21日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
37+阅读 · 2021年2月10日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Arxiv
15+阅读 · 2019年4月4日
Arxiv
8+阅读 · 2018年3月20日
VIP会员
相关VIP内容
专知会员服务
44+阅读 · 2020年10月31日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
人工智能 | ACCV 2020等国际会议信息5条
Call4Papers
6+阅读 · 2019年6月21日
CCF推荐 | 国际会议信息8条
Call4Papers
9+阅读 · 2019年5月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能 | NIPS 2019等国际会议信息8条
Call4Papers
7+阅读 · 2019年3月21日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员