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