Document Open Access Logo

Congestion-Free Rerouting of Flows on DAGs

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.143.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Saeed Akhoondian Amiri
  • Max-Planck Institute of Informatics, Germany
Szymon Dudycz
  • University of Wroclaw, Poland
Stefan Schmid
  • University of Vienna, Austria
Sebastian Wiederrecht
  • TU Berlin, Germany

Funding

The research of Saeed Amiri and Sebastian Wiederrecht was partly supported by the ERC consolidator grant DISTRUCT, agreement No 648527. Stefan Schmid was supported by the Danish VILLUM foundation project ReNet.

Cite As Get BibTex

Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, and Sebastian Wiederrecht. Congestion-Free Rerouting of Flows on DAGs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 143:1-143:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.143

Abstract

Changing a given configuration in a graph into another one is known as a reconfiguration 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. 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.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
  • Theory of computation → Network flows
Keywords
  • Unsplittable Flows
  • Reconfiguration
  • DAGs
  • FPT
  • NP-Hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with congestion in acyclic digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS, pages 7:1-7:11, 2016. Google Scholar
  2. Saeed Akhoondian Amiri, Stephan Kreutzer, and Roman Rabinovich. Dag-width is pspace-complete. Theor. Comput. Sci., 655:78-89, 2016. Google Scholar
  3. Saeed Akhoondian Amiri, Arne Ludwig, Jan Marcinkowski, and Stefan Schmid. Transiently consistent sdn updates: Being greedy is hard. In 23rd International Colloquium on Structural Information and Communication Complexity, SIROCCO, 2016. Google Scholar
  4. D. Awduche, L. Berger, D. Gan, T. Li, V. Srinivasan, and G. Swallow. Rsvp-te: Extensions to rsvp for lsp tunnels. In RFC 3209, 2001. Google Scholar
  5. Jørgen Bang-Jensen and Gregory Gutin. Digraphs - theory, algorithms and applications. Springer, 2002. Google Scholar
  6. Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, and Jan Obdrzálek. The dag-width of directed graphs. J. Comb. Theory, Ser. B, 102(4):900-923, 2012. Google Scholar
  7. Paul Bonsma. The complexity of rerouting shortest paths. Theoretical computer science, 510:1-12, 2013. Google Scholar
  8. Sebastian Brandt, Klaus-Tycho Förster, and Roger Wattenhofer. On Consistent Migration of Flows in SDNs. In Proc. 36th IEEE International Conference on Computer Communications (INFOCOM), 2016. Google Scholar
  9. Luis Cereceda, Jan Van Den Heuvel, and Matthew Johnson. Finding paths between 3-colorings. Journal of graph theory, 67(1):69-82, 2011. Google Scholar
  10. Chandra Chekuri, Alina Ene, and Marcin Pilipczuk. Constant congestion routing of symmetric demands in planar directed graphs. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP, 2016. Google Scholar
  11. Chandra Chekuri, Sreeram Kannan, Adnan Raja, and Pramod Viswanath. Multicommodity flows and cuts in polymatroidal networks. SIAM J. Comput., 44(4):912-943, 2015. Google Scholar
  12. Shimon Even, Alon Itai, and Adi Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691-703, 1976. Google Scholar
  13. Klaus-Tycho Foerster, Stefan Schmid, and Stefano Vissicchio. Survey of consistent network updates. In ArXiv Technical Report, 2016. Google Scholar
  14. Klaus-Tycho Förster, Ratul Mahajan, and Roger Wattenhofer. Consistent Updates in Software Defined Networks: On Dependencies, Loop Freedom, and Blackholes. In Proc. 15th IFIP Networking, 2016. Google Scholar
  15. Parikshit Gopalan, Phokion G Kolaitis, Elitza Maneva, and Christos H Papadimitriou. The connectivity of boolean satisfiability: computational and structural dichotomies. SIAM Journal on Computing, 38(6):2330-2355, 2009. Google Scholar
  16. Robert A Hearn and Erik D Demaine. Pspace-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2):72-96, 2005. Google Scholar
  17. Takehiro Ito, Erik Demaine, Nicholas Harvey, Christos Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Algorithms and Computation, pages 28-39, 2008. Google Scholar
  18. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Stephan Kreutzer. An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In Proc. Symposium on Theory of Computing (STOC), pages 70-78, 2014. Google Scholar
  19. Jon M. Kleinberg. Decision algorithms for unsplittable flow and the half-disjoint paths problem. In Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), pages 530-539, 1998. Google Scholar
  20. Frank Thomson Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787-832, 1999. Google Scholar
  21. Arne Ludwig, Jan Marcinkowski, and Stefan Schmid. Scheduling loop-free network updates: It’s good to relax! In Proc. ACM PODC, 2015. Google Scholar
  22. Martin Skutella. Approximating the single source unsplittable min-cost flow problem. In Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 136-145, 2000. Google Scholar
  23. Aleksandrs Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM Journal on Discrete Mathematics, 24(1):146-157, 2010. Google Scholar
  24. Jan van den Heuvel. The complexity of change. Surveys in combinatorics, 409(2013):127-160, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact