Congestion Minimization for Multipath Routing via Multiroute Flows

Authors Chandra Chekuri, Mark Idleman



PDF
Thumbnail PDF

File

OASIcs.SOSA.2018.3.pdf
  • Filesize: 485 kB
  • 12 pages

Document Identifiers

Author Details

Chandra Chekuri
Mark Idleman

Cite AsGet BibTex

Chandra Chekuri and Mark Idleman. Congestion Minimization for Multipath Routing via Multiroute Flows. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.SOSA.2018.3

Abstract

Congestion minimization is a well-known routing problem for which there is an O(log n/loglog n)-approximation via randomized rounding due to Raghavan and Thompson. Srinivasan formally introduced the low-congestion multi-path routing problem as a generalization of the (single-path) congestion minimization problem. The goal is to route multiple disjoint paths for each pair, for the sake of fault tolerance. Srinivasan developed a dependent randomized scheme for a special case of the multi-path problem when the input consists of a given set of disjoint paths for each pair and the goal is to select a given subset of them. Subsequently Doerr gave a different dependentrounding scheme and derandomization. Doerr et al. considered the problem where the paths have to be chosen, and applied the dependent rounding technique and evaluated it experimentally. However, their algorithm does not maintain the required disjointness property without which the problem easily reduces to the standard congestion minimization problem. In this note we show a simple algorithm that solves the problem correctly without the need for dependent rounding --- standard independent rounding suffices. This is made possible via the notion of multiroute flows originally suggested by Kishimoto et al. One advantage of the simpler rounding is an improved bound on the congestion when the path lengths are short.
Keywords
  • multipath routing
  • congestion minimization
  • multiroute flows

Metrics

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

References

  1. Charu C. Aggarwal and James B. Orlin. On multiroute maximum flows in networks. Networks, 39(1):43-52, 2002. URL: http://dx.doi.org/10.1002/net.10008.
  2. Stephen Baum and Leslie E Trotter Jr. Integer rounding and polyhedral decomposition for totally unimodular systems. Optimization and Operations Research, 157:15-23, 1978. Google Scholar
  3. Graham Brightwell, Gianpaolo Oriolo, and F Bruce Shepherd. Reserving resilient capacity in a network. SIAM journal on discrete mathematics, 14(4):524-539, 2001. Google Scholar
  4. Chandra Chekuri, Alina Ene, and Ali Vakilian. Prize-collecting survivable network design in node-weighted graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 98-109, 2012. Google Scholar
  5. Chandra Chekuri, Jan Vondrak, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 575-584. IEEE, 2010. Google Scholar
  6. Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, and Kunal Talwar. Hardness of routing with congestion in directed graphs. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 165-178. ACM, 2007. Google Scholar
  7. Benjamin Doerr. Randomly rounding rationals with cardinality constraints and derandomizations. STACS 2007, pages 441-452, 2007. Google Scholar
  8. Benjamin Doerr, Marvin Künnemann, and Magnus Wahlström. Randomized rounding for routing and covering problems: Experiments and improvements. In Proceedings of the 9th International Conference on Experimental Algorithms, SEA'10, pages 190-201, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-13193-61_7.
  9. Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM (JACM), 53(3):324-360, 2006. Google Scholar
  10. Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. New constructive aspects of the lovász local lemma. Journal of the ACM (JACM), 58(6):28, 2011. Google Scholar
  11. Mark Idleman. Approximation algorithms for the minimum congestion routing problem via k-route flows. Master’s thesis, University of Illinois, July 2017. Google Scholar
  12. Wataru Kishimoto. A method for obtaining the maximum multiroute flows in a network. Networks, 27(4):279-291, 1996. URL: http://dx.doi.org/10.1002/(SICI)1097-0037(199607)27:4<279::AID-NET3>3.0.CO;2-D.
  13. Wataru Kishimoto and Masashi Takeuchi. m-route flows in a network. Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 77(5):1-18, 1994. URL: http://dx.doi.org/10.1002/ecjc.4430770501.
  14. Andrew McGregor and F. Bruce Shepherd. Island hopping and path colouring with applications to WDM network design. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 864-873. SIAM, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283476.
  15. Robin A Moser and Gábor Tardos. A constructive proof of the general lovász local lemma. Journal of the ACM (JACM), 57(2):11, 2010. Google Scholar
  16. Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Chapman &Hall/CRC, 2010. Google Scholar
  17. Prabhakar Raghavan and Clark D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987. URL: http://dx.doi.org/10.1007/BF02579324.
  18. Aravind Srinivasan. Distributions on level-sets with applications to approximation algorithms. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 588-597. IEEE Computer Society, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959935.
  19. Aravind Srinivasan. An extension of the lovász local lemma, and its applications to integer programming. SIAM Journal on Computing, 36(3):609-634, 2006. 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