Document Open Access Logo

Near-Optimal Schedules for Simultaneous Multicasts

Authors Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.78.pdf
  • Filesize: 0.8 MB
  • 19 pages

Document Identifiers

Author Details

Bernhard Haeupler
  • Carnegie Mellon University, Pittsburgh, PA, USA
  • ETH Zürich, Switzerland
D. Ellis Hershkowitz
  • Carnegie Mellon University, Pittsburgh, PA, USA
David Wajc
  • Stanford University, CA, USA

Funding

Supported in part by NSF grants CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808, a Sloan Research Fellowship, and funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (ERC grant agreement 949272).
  • Hershkowitz, D. Ellis: Supported by the Air Force Office of Scientific Research under award number FA9550-20-1-0080.
  • Wajc, David: Supported by NSF award 1812919, ONR award N000141912550, and a gift from Cisco Research.

Cite AsGet BibTex

Bernhard Haeupler, D. Ellis Hershkowitz, and David Wajc. Near-Optimal Schedules for Simultaneous Multicasts. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 78:1-78:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.78

Abstract

We study the store-and-forward packet routing problem for simultaneous multicasts, in which multiple packets have to be forwarded along given trees as fast as possible. This is a natural generalization of the seminal work of Leighton, Maggs and Rao, which solved this problem for unicasts, i.e. the case where all trees are paths. They showed the existence of asymptotically optimal O(C + D)-length schedules, where the congestion C is the maximum number of packets sent over an edge and the dilation D is the maximum depth of a tree. This improves over the trivial O(CD) length schedules. We prove a lower bound for multicasts, which shows that there do not always exist schedules of non-trivial length, o(CD). On the positive side, we construct O(C+D+log² n)-length schedules in any n-node network. These schedules are near-optimal, since our lower bound shows that this length cannot be improved to O(C+D) + o(log n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Routing and network design problems
Keywords
  • Packet routing
  • multicast
  • scheduling algorithms

Metrics

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

Related Versions

References

  1. Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016. Google Scholar
  2. Friedhelm Meyer auf der Heide and Berthold Vöcking. Shortest-path routing in arbitrary networks. Journal of Algorithms, 31(1):105-131, 1999. Google Scholar
  3. Baruch Awerbuch, Oded Goldreich, Ronen Vainish, and David Peleg. A trade-off between information and communication in broadcast protocols. Journal of the ACM (JACM), 37(2):238-256, 1990. Google Scholar
  4. Amotz Bar-Noy, Sudipto Guha, Joseph Naor, and Baruch Schieber. Message multicasting in heterogeneous networks. SIAM Journal on Computing (SICOMP), 30(2):347-358, 2000. Google Scholar
  5. Dimitris Bertsimas and David Gamarnik. Asymptotically optimal algorithms for job shop scheduling and packet routing. Journal of Algorithms, 33(2):296-318, 1999. Google Scholar
  6. Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, and Paul Spirakis. Direct routing: Algorithms and complexity. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA), pages 134-145, 2004. Google Scholar
  7. Robert Carr and Santosh Vempala. Randomized metarounding. Random Structures & Algorithms, 20(3):343-352, 2002. Google Scholar
  8. Yang Chu, Sanjay Rao, Srinivasan Seshan, and Hui Zhang. Enabling conferencing applications on the internet using an overlay muilticast architecture. ACM SIGCOMM computer communication review, 31(4):55-67, 2001. Google Scholar
  9. Michal Dory and Mohsen Ghaffari. Improved distributed approximations for minimum-weight two-edge-connected spanning subgraph. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pages 521-530, 2019. Google Scholar
  10. Michael Elkin and Guy Kortsarz. Sublogarithmic approximation for telephone multicast: path out of jungle. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 76-85, 2003. Google Scholar
  11. Mohsen Ghaffari. Distributed broadcast revisited: Towards universal optimality. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), pages 638-649. Springer, 2015. Google Scholar
  12. Mohsen Ghaffari. Near-optimal scheduling of distributed algorithms. In Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), pages 3-12, 2015. Google Scholar
  13. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks I: Planar embedding. In Proceedings of the 35th ACM Symposium on Principles of Distributed Computing (PODC), pages 29-38, 2016. Google Scholar
  14. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks II: Low-congestion shortcuts, mst, and min-cut. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 202-219, 2016. Google Scholar
  15. Mohsen Ghaffari and Bernhard Haeupler. Low-congestion shortcuts for graphs excluding dense minors. arXiv preprint, 2020. URL: http://arxiv.org/abs/2008.03091.
  16. Mohsen Ghaffari and Jason Li. New distributed algorithms in almost mixing time via transformations from parallel algorithms. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pages 31:1-31:16, 2018. Google Scholar
  17. Bernhard Haeupler, D Ellis Hershkowitz, and David Wajc. Round-and message-optimal distributed graph algorithms. In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC), pages 119-128, 2018. Google Scholar
  18. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. In Proceedings of the 35th ACM Symposium on Principles of Distributed Computing (PODC), pages 451-460, 2016. Google Scholar
  19. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-optimal low-congestion shortcuts on bounded parameter graphs. In Proceedings of the 30th International Symposium on Distributed Computing (DISC), pages 158-172, 2016. Google Scholar
  20. Bernhard Haeupler, Jason Li, and Goran Zuzic. Minor excluded network families admit fast distributed algorithms. In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC), pages 465-474, 2018. Google Scholar
  21. Bernhard Haeupler, David Wajc, and Goran Zuzic. Universally-optimal distributed algorithms for known topologies. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), 2021. To appear. Google Scholar
  22. Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In Proceedings of the 31st ACM Symposium on Principles of Distributed Computing (PODC), pages 355-364, 2012. Google Scholar
  23. Jennifer Iglesias, Rajmohan Rajaraman, R Ravi, and Ravi Sundaram. Rumors across radio, wireless, telephone. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2015. Google Scholar
  24. Jennifer Iglesias, Rajmohan Rajaraman, R Ravi, and Ravi Sundaram. Plane gossip: Approximating rumor spread in planar graphs. In Proceedings of the 13th Latin American Theoretical Informatics Symposium (LATIN), pages 611-624, 2018. Google Scholar
  25. John Jannotti, David K Gifford, Kirk L Johnson, M Frans Kaashoek, et al. Overcast: reliable multicasting with on overlay network. In Proceedings of the 4th USENIX Symposium on Operating Systems Design and Implementation (OSDI), page 14, 2000. Google Scholar
  26. K Jansen and H Zhang. An approximation algorithm for the multicast congestion problem via minimum steiner trees. In Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 77-90, 2002. Google Scholar
  27. Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, and Taisuke Izumi. Low-congestion shortcut and graph parameters. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC), pages 25:1-25:17, 2019. Google Scholar
  28. Ronald Koch, Britta Peis, Martin Skutella, and Andreas Wiese. Real-time message routing and scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 217-230. Springer, 2009. Google Scholar
  29. Shimon Kogan and Merav Parter. Low-congestion shortcuts in constant diameter graphs. In Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC), 2021. To appear. Google Scholar
  30. Thomson Leighton, Bruce M Maggs, and Satish B Rao. Packet routing and job-shop scheduling in O(congestion+ dilation) steps. Combinatorica, 14(2):167-186, 1994. Google Scholar
  31. Tom Leighton, Bruce Maggs, and Andrea W Richa. Fast algorithms for finding o (congestion+ dilation) packet routing schedules. Combinatorica, 19(3):375-401, 1999. Google Scholar
  32. Christoph Lenzen and David Peleg. Efficient distributed source detection with limited bandwidth. In Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC), pages 375-382, 2013. Google Scholar
  33. Friedhelm Meyer and Berthold Vöcking. A packet routing protocol for arbitrary networks. In Proceedings of the 12th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 291-302. Springer, 1995. Google Scholar
  34. Rafail Ostrovsky and Yuval Rabani. Universal O (congestion+ dilation+ log^1+εn) local control packet switching algorithms. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), volume 29, pages 644-653, 1997. Google Scholar
  35. Britta Peis, Martin Skutella, and Andreas Wiese. Packet routing: Complexity and algorithms. In Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA), pages 217-228, 2009. Google Scholar
  36. Britta Peis and Andreas Wiese. Universal packet routing with arbitrary bandwidths and transit times. In Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 362-375, 2011. Google Scholar
  37. David Peleg. Distributed computing. SIAM Monographs on discrete mathematics and applications, 5:1-1, 2000. Google Scholar
  38. Yuval Rabani and Éva Tardos. Distributed packet switching in arbitrary networks. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), volume 96, pages 366-375, 1996. Google Scholar
  39. Thomas Rothvoß. A simpler proof for O (Congestion + Dilation) packet routing. In Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 336-348, 2013. Google Scholar
  40. Christian Scheideler. Universal routing strategies for interconnection networks, volume 1390. Springer, 2006. Google Scholar
  41. Jeanette P Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223-250, 1995. Google Scholar
  42. Daniel D Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983. Google Scholar
  43. Aravind Srinivasan and Chung-Piaw Teo. A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria. SIAM Journal on Computing (SICOMP), 30(6):2051-2068, 2001. Google Scholar
  44. Donald M. Topkis. Concurrent broadcast for information dissemination. IEEE Transactions on Software Engineering, SE-11(10):1107-1112, 1985. Google Scholar
  45. Santosh Vempala and Berthold Vöcking. Approximating multicast congestion. In Proceedings of the 10th Annual International Symposium on Algorithms and Computation (ISAAC), pages 367-372, 1999. 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