Document Open Access Logo

Compact Oblivious Routing

Authors Harald Räcke, Stefan Schmid

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.75.pdf
  • Filesize: 442 kB
  • 14 pages

Document Identifiers

Author Details

Harald Räcke
  • Department of Informatics, TU München, Germany
Stefan Schmid
  • Faculty of Computer Science, University of Vienna, Austria

Cite As Get BibTex

Harald Räcke and Stefan Schmid. Compact Oblivious Routing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 75:1-75:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.75

Abstract

Oblivious routing is an attractive paradigm for large distributed systems in which centralized control and frequent reconfigurations are infeasible or undesired (e.g., costly). Over the last almost 20 years, much progress has been made in devising oblivious routing schemes that guarantee close to optimal load and also algorithms for constructing such schemes efficiently have been designed. However, a common drawback of existing oblivious routing schemes is that they are not compact: they require large routing tables (of polynomial size), which does not scale.
This paper presents the first oblivious routing scheme which guarantees close to optimal load and is compact at the same time - requiring routing tables of polylogarithmic size. Our algorithm maintains the polylogarithmic competitive ratio of existing algorithms, and is hence particularly well-suited for emerging large-scale networks.

Subject Classification

ACM Subject Classification
  • Networks → Routing protocols
  • Theory of computation → Routing and network design problems
  • Networks → Network algorithms
Keywords
  • Oblivious Routing
  • Compact Routing
  • Competitive Analysis

Metrics

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

References

  1. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On Space-stretch Trade-offs: Upper Bounds. In Proc. 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 217-224, 2006. Google Scholar
  2. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Seffi Naor. A general approach to online network optimization problems. ACM Transactions on Algorithms (TALG), 2(4):640-660, 2006. Google Scholar
  3. Konstantin Andreev, Charles Garrod, Daniel Golovin, Bruce Maggs, and Adam Meyerson. Simultaneous source location. ACM Transactions on Algorithms (TALG), 6(1):16, 2009. Google Scholar
  4. Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, and Harald Räcke. Optimal oblivious routing in polynomial time. Journal of Computer and System Sciences, 69(3):383-394, 2004. Google Scholar
  5. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, and Roy Schwartz. Min-max graph partitioning and small set expansion. In Proc. IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 17-26. IEEE, 2011. Google Scholar
  6. Yair Bartal and Stefano Leonardi. On-line routing in all-optical networks. In Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 516-526. Springer, 1997. Google Scholar
  7. Marcin Bienkowski, Miroslaw Korzeniowski, and Harald Räcke. A practical algorithm for constructing oblivious routing schemes. In Proc. 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 24-33. ACM, 2003. Google Scholar
  8. Allan Borodin and John E. Hopcroft. Routing, merging, and sorting on parallel models of computation. Journal of computer and system sciences, 30(1):130-145, 1985. Google Scholar
  9. Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin. Approximating a finite metric by a small number of tree metrics. In Proc. 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 379-388. IEEE, 1998. Google Scholar
  10. Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. The all-or-nothing multicommodity flow problem. In Proc. 36th Annual ACM Symposium on Theory of Computing (STOC), pages 156-165. ACM, 2004. Google Scholar
  11. Marco Chiesa, Gábor Rétvári, and Michael Schapira. Lying Your Way to Better Traffic Engineering. In Proc. ACM 12th International on Conference on Emerging Networking EXperiments and Technologies (CoNEXT), pages 391-398, 2016. Google Scholar
  12. Marco Chiesa, Gábor Rétvári, and Michael Schapira. Oblivious Routing in IP Networks. IEEE/ACM Transactions on Networking (TON), 26(3):1292-1305, 2018. Google Scholar
  13. Lenore J Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38(1):170-183, 2001. Google Scholar
  14. Roee Engelberg, Jochen Könemann, Stefano Leonardi, and Joseph Seffi Naor. Cut problems in graphs with a budget constraint. In Proc. Latin American Symposium on Theoretical Informatics (LATIN), pages 435-446. Springer, 2006. Google Scholar
  15. Klaus-Tycho Foerster, Stefan Schmid, and Stefano Vissicchio. Survey of Consistent Software-Defined Network Updates. In IEEE Communications Surveys and Tutorials (COMST), 2018. Google Scholar
  16. Pierre Fraigniaud and Cyril Gavoille. Memory requirement for universal routing schemes. In Proc. 14th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 223-230. ACM, 1995. Google Scholar
  17. Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 757-772. Springer, 2001. Google Scholar
  18. Greg N Frederickson and Ravi Janardan. Designing networks with compact routing tables. Algorithmica, 3(1-4):171-190, 1988. Google Scholar
  19. Cyril Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News, 32(1):36-52, 2001. Google Scholar
  20. Cyril Gavoille and Stéphane Pérennès. Memory requirement for routing in distributed networks. In Proc. 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 125-133. ACM, 1996. Google Scholar
  21. Chris Harrelson, Kirsten Hildrum, and Satish Rao. A polynomial-time tree decomposition to minimize congestion. In Proc. 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 34-43, 2003. Google Scholar
  22. Christos Kaklamanis, Danny Krizanc, and Thanasis Tsantilas. Tight bounds for oblivious routing in the hypercube. Mathematical Systems Theory, 24(1):223-232, 1991. Google Scholar
  23. Rohit Khandekar, Guy Kortsarz, and Vahab Mirrokni. On the advantage of overlapping clusters for minimizing conductance. Algorithmica, 69(4):844-863, 2014. Google Scholar
  24. Rohit Khandekar, Satish Rao, and Umesh Vazirani. Graph partitioning using single commodity flows. Journal of the ACM (JACM), 56(4):19, 2009. Google Scholar
  25. Petr Kolman and Christian Scheideler. Improved bounds for the unsplittable flow problem. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 184-193. Society for Industrial and Applied Mathematics, 2002. Google Scholar
  26. Jochen Könemann, Ojas Parekh, and Danny Segev. A unified approach to approximating partial covering problems. In Proc. European Symposium on Algorithms (ESA), pages 468-479. Springer, 2006. Google Scholar
  27. Dmitri Krioukov, Kevin Fall, Arthur Brady, et al. On compact routing for the internet. ACM SIGCOMM Computer Communication Review (CCR), 37(3):41-52, 2007. Google Scholar
  28. Dmitri Krioukov, Kevin Fall, and Xiaowei Yang. Compact routing on Internet-like graphs. In Proc. IEEE INFOCOM. IEEE, 2004. Google Scholar
  29. Aleksander Madry. Fast approximation algorithms for cut-based problems in undirected graphs. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 245-254. IEEE, 2010. Google Scholar
  30. Bruce M Maggs, F Meyer auf der Heide, Berthold Vocking, and Matthias Westermann. Exploiting locality for data management in systems of limited bandwidth. In Proc. 38th Annual Symposium on Foundations of Computer Science (FOCS), pages 284-293. IEEE, 1997. Google Scholar
  31. Richard Peng. Approximate undirected maximum flows in o(m polylog (n)) time. In Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1862-1867. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  32. Harald Räcke. Minimizing Congestion in General Networks. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 43-52, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181881.
  33. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC), pages 255-264. ACM, 2008. Google Scholar
  34. Harald Räcke. Survey on Oblivious Routing Strategies. In Proc. 5th Conference on Computability in Europe: Mathematical Theory and Computational Practice (CiE), pages 419-429, 2009. Google Scholar
  35. Harald Räcke, Chintan Shah, and Hanjo Täubig. Computing cut-based hierarchical decompositions in almost linear time. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 227-238. Society for Industrial and Applied Mathematics, 2014. Google Scholar
  36. Gábor Rétvári, András Gulyás, Zalán Heszberger, Márton Csernai, and József J Bíró. Compact policy routing. Distributed computing, 26(5-6):309-320, 2013. Google Scholar
  37. Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proc. 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). ACM, 2001. Google Scholar
  38. Leslie G. Valiant and Gordon J. Brebner. Universal Schemes for Parallel Communication. In Proceedings of the 13th ACM Symposium on Theory of Computing (STOC), pages 263-277, 1981. URL: https://doi.org/10.1145/800076.802479.
  39. Jan van Leeuwen and Richard B Tan. Compact routing methods: A survey. In Proc. Colloquium on Structural Information and Communication Complexity (SICC), pages 99-109, 1995. 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