2026-07-26T17:23:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14147 2024-03-06T10:53:35Z ddc:004 open_access

Near-Optimal Schedules for Simultaneous Multicasts Haeupler, Bernhard Hershkowitz, D. Ellis Wajc, David Packet routing multicast scheduling algorithms 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bernhard Haeupler and D. Ellis Hershkowitz and David Wajc 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.78 urn:nbn:de:0030-drops-141471 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.78 eng https://creativecommons.org/licenses/by/4.0/legalcode