Document Open Access Logo

Compact Oblivious Routing in Weighted Graphs

Authors Philipp Czerner , Harald Räcke

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.36.pdf
  • Filesize: 0.55 MB
  • 23 pages

Document Identifiers

Author Details

Philipp Czerner
  • Department of Informatics, TU München, Germany
Harald Räcke
  • Department of Informatics, TU München, Germany

Cite AsGet BibTex

Philipp Czerner and Harald Räcke. Compact Oblivious Routing in Weighted Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 36:1-36:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.36

Abstract

The space-requirement for routing-tables is an important characteristic of routing schemes. For the cost-measure of minimizing the total network load there exist a variety of results that show tradeoffs between stretch and required size for the routing tables. This paper designs compact routing schemes for the cost-measure congestion, where the goal is to minimize the maximum relative load of a link in the network (the relative load of a link is its traffic divided by its bandwidth). We show that for arbitrary undirected graphs we can obtain oblivious routing strategies with competitive ratio 𝒪̃(1) that have header length 𝒪̃(1), label size 𝒪̃(1), and require routing-tables of size 𝒪̃(deg(v)) at each vertex v in the graph. This improves a result of Räcke and Schmid who proved a similar result in unweighted graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Network flows
  • 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

Related Versions

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. URL: https://doi.org/10.1145/1148109.1148144.
  2. 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. URL: https://doi.org/10.1145/780542.780599.
  3. 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
  4. Marcin Bienkowski, Miroslaw Korzeniowski, and Harald Räcke. A practical algorithm for constructing oblivious routing schemes. In Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 24-33, 2003. URL: https://doi.org/10.1145/777412.777418.
  5. 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. URL: https://doi.org/10.1145/800070.802209.
  6. 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. URL: https://doi.org/10.1109/TNET.2018.2832020.
  7. Lenore J Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38(1):170-183, 2001. URL: https://doi.org/10.1006/jagm.2000.1134.
  8. Paul Erdős. Extremal problems in graph theory. In Proceedings of the Symposium on Theory of Graphs and its Applications, pages 29-36, 1963. URL: https://doi.org/10.1002/jgt.3190010206.
  9. 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. URL: https://doi.org/10.1145/224964.224989.
  10. Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 757-772. Springer, 2001. URL: https://doi.org/10.1007/3-540-48224-5_62.
  11. Greg N Frederickson and Ravi Janardan. Designing networks with compact routing tables. Algorithmica, 3(1-4):171-190, 1988. URL: https://doi.org/10.1007/BF01762113.
  12. Cyril Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News, 32(1):36-52, 2001. URL: https://doi.org/10.1145/568438.568451.
  13. 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. URL: https://doi.org/10.1145/248052.248075.
  14. 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. URL: https://doi.org/10.1145/777412.777419.
  15. Christos Kaklamanis, Danny Krizanc, and Thanasis Tsantilas. Tight bounds for oblivious routing in the hypercube. Mathematical Systems Theory, 24(1):223-232, 1991. URL: https://doi.org/10.1145/97444.97453.
  16. Rohit Khandekar, Satish Rao, and Umesh Vazirani. Graph partitioning using single commodity flows. Journal of the ACM (JACM), 56(4):19, 2009. URL: https://doi.org/10.1145/1538902.1538903.
  17. M. Kodialam, T.V. Lakshman, J.B. Orlin, and S. Sengupta. Oblivious routing of highly variable traffic in service overlays and ip backbones. IEEE/ACM Transactions on Networking (TON), 17(2):459-472, 2009. URL: https://doi.org/10.1109/TNET.2008.927257.
  18. Dmitri Krioukov, Kevin Fall, and Xiaowei Yang. Compact routing on internet-like graphs. In Proc. IEEE INFOCOM. IEEE, 2004. URL: https://doi.org/10.1109/INFCOM.2004.1354495.
  19. Praveen Kumar, Yang Yuan, Chris Yu, Nate Foster, Robert Kleinberg, Petr Lapukhov, Chiun Lin Lim, and Robert Soulé. Semi-oblivious traffic engineering: The road not taken. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18), pages 157-170, Renton, WA, April 2018. USENIX Association. URL: https://www.usenix.org/conference/nsdi18/presentation/kumar.
  20. Harald Racke. Minimizing congestion in general networks. In Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 43-52. IEEE, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181881.
  21. 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. URL: https://doi.org/10.1145/1374376.1374415.
  22. Harald Räcke and Stefan Schmid. Compact oblivious routing. In Proceedings of the 27th European Symposium on Algorithms (ESA), 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.75.
  23. 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. URL: https://doi.org/10.1137/1.9781611973402.17.
  24. 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. URL: https://doi.org/10.1007/s00446-012-0181-9.
  25. Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proceedings of the 13th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), SPAA 01, pages 1-10, New York, NY, USA, 2001. Association for Computing Machinery. URL: https://doi.org/10.1145/378580.378581.
  26. Brian Towles and William J Dally. Worst-case traffic for oblivious routing functions. In Proc. 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). ACM, 2002. URL: https://doi.org/10.1109/L-CA.2002.12.
  27. Leslie G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350-361, 1982. URL: https://doi.org/10.1137/0211027.
  28. 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.
  29. 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 Imprint Privacy Contact