Network Coding Gaps for Completion Times of Multiple Unicasts
Network Coding Gaps for Completion Times of Multiple Unicasts
复制标题
DOI：
10.1109/focs46700.2020.00053
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Bernhard Haeupler;David Wajc;Goran Zuzic
中科院分区：
文献类型：
--
作者：
Bernhard Haeupler;David Wajc;Goran Zuzic
我们研究网络编码间隙问题，以最小化多个单播的完工时间。在这个问题中，网络中不同节点上的不同分组需要尽可能快地被递送到特定于每个分组的目的地。网络编码差距规定了与更自然的路由方法相比，在网络中一起编码数据包可以提供多少帮助。虽然使用路由的最小完工时间对于多播问题已经有了深入的研究，但是对于这个问题的网络编码间隔的限制是未知的。我们开发了新的技术，允许我们为$k$单播的完成时间上限网络编码差距，证明了这个差距在$k$中至多是多对数的。作为对这一结果的补充，我们证明了存在$k$单播实例，其编码差距在$k$中是多对数的。我们的结果也适用于平均完成时间，更一般地，也适用于任何完成时间的$\ell_{p}范数。
We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The network coding gap specifies how much coding packets together in a network can help compared to the more natural approach of routing. While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of $k$ unicasts, proving this gap is at most polylogarithmic in $k$. Complementing this result, we show there exist instances of $k$ unicasts for which this coding gap is polylogarithmic in $k$. Our results also hold for average completion time, and more generally any $\ell_{p}$ norm of completion times.