论文标题
同时多播的几乎最佳时间表
Near-Optimal Schedules for Simultaneous Multicasts
论文作者
论文摘要
我们研究了同时多播的商店和前向数据包路由问题，其中必须尽快沿着给定的树木转发多个数据包。 这是对Leighton，Maggs和Rao的开创性工作的自然概括，它解决了单播这个问题，即所有树木都是路径的情况。他们展示了渐近最佳$ O（C + D）$长度时间表的存在，其中充血$ C $是发送到边缘上的最大数据包数，而扩张$ D $是树的最大深度。这改进了微不足道的$ O（CD）$长度时间表。 我们证明了用于多播的下限，这表明并不总是存在非平凡长度的时间表，即$ O（CD）$。在积极方面，我们在任何$ n $ node网络中构造$ o（C+D+\ log^2 N）$长度时间表。这些时间表几乎是最佳的，因为我们的下限表明该长度不能提高到$ O（C + D） + O（\ log n）$。
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^2 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)$.
