arXiv (Cornell University) · 2016 · 13 citations · 24 references
ComputingComputer ScienceAlgorithmsCombinatoricsSchedulingCombinatorial OptimizationGraph AlgorithmsNetwork FlowsNetwork OptimizationRoutingRouting AlgorithmsAlgorithmic Graph TheoryMulti-commodity FlowMulti-commodity Flow ModelsMulti-commodity Flow ProblemNetwork Flow ProblemsNp-hardnessReconfigurationTraffic Rerouting
Changing a given configuration in a graph into another one is known as a re- configuration problem. Such problems have recently received much interest in the context of algorithmic graph theory. We initiate the theoretical study of the following reconfiguration problem: How to reroute $k$ unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NP-hard already for $k = 2$ flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general $k$, deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Both NP-hardness proofs are non-trivial. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows.
24
Achieving high utilization with software-driven WAN
Chi-Yao Hong, Srikanth Kandula, Ratul Mahajan et al. · 2013 · 1.1K citations · Full text
Nick Feamster, Jennifer Rexford, Ellen Zegura · ACM SIGCOMM Computer Communication Review · 2014 · 891 citations
Abstractions for network update
Mark Reitblatt, Nate Foster, Jennifer Rexford et al. · 2012 · 580 citations · Full text
Dynamic scheduling of network updates
Xin Jin, Hongqiang Harry Liu, Rohan Gandhi et al. · 2014 · 333 citations · Full text