While operating communication networks adaptively may improve utilization and performance, frequent adjustments also introduce an algorithmic challenge: the re-optimization of traffic engineering solutions is time-consuming and may limit the granularity at which a network can be adjusted. This paper is motivated by question whether the reactivity of a network can be improved by re-optimizing solutions dynamically rather than from scratch, especially if inputs such as link weights do not change significantly. This paper explores to what extent dynamic algorithms can be used to speed up fundamental tasks in network operations. We specifically investigate optimizations related to traffic engineering (namely shortest paths and maximum flow computations), but also consider spanning tree and matching applications. While prior work on dynamic graph algorithms focuses on link insertions and deletions, we are interested in the practical problem of link weight changes. We revisit existing upper bounds in the weight-dynamic model, and present several novel lower bounds on the amortized runtime for recomputing solutions. In general, we find that the potential performance gains depend on the application, and there are also strict limitations on what can be achieved, even if link weights change only slightly.


翻译:在适应性地运作通信网络可以提高利用率和性能的同时,频繁调整也引入了算法上的挑战:交通工程解决方案的重新优化耗时,可能限制网络可调整的颗粒度。本文件的动机是质疑网络的回动性能否通过动态的重新优化解决方案而不是从零开始得到改进,特别是如果连接权重等投入不会发生重大变化。本文探讨了动态算法在多大程度上可以用于加快网络操作的基本任务。我们特别调查与交通工程(即最短路径和最大流量计算)有关的优化,但也考虑横跨树木和匹配应用程序。先前关于动态图表算法的工作侧重于链接插入和删除,但我们感兴趣的是连接权重变化的实际问题。我们重新审视了重力模型中的现有上层,并对摊销权重调整权重的时间提出了几个新的较低界限。一般来说,我们发现潜在的绩效增益取决于应用程序,而且对于能够实现的目标也有严格的限制,即使连接权重仅略有变化。

0
下载
关闭预览

相关内容

【斯坦福Jiaxuan You】图学习在金融网络中的应用,24页ppt
专知会员服务
43+阅读 · 2021年9月19日
专知会员服务
60+阅读 · 2020年3月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【综述笔记】Graph Neural Networks in Recommender Systems
图与推荐
5+阅读 · 2020年12月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2022年1月31日
Arxiv
0+阅读 · 2022年1月31日
Optimization for deep learning: theory and algorithms
Arxiv
104+阅读 · 2019年12月19日
dynnode2vec: Scalable Dynamic Network Embedding
Arxiv
14+阅读 · 2018年12月6日
VIP会员
相关VIP内容
【斯坦福Jiaxuan You】图学习在金融网络中的应用,24页ppt
专知会员服务
43+阅读 · 2021年9月19日
专知会员服务
60+阅读 · 2020年3月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
【综述笔记】Graph Neural Networks in Recommender Systems
图与推荐
5+阅读 · 2020年12月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员