Congestion-Free Rerouting of Flows on DAGs

Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, Sebastian Wiederrecht

arXiv (Cornell University) · 2016 · 13 citations · 24 references

DOIFull text

Open access

Concepts

Abstract

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.

References

24