Network Coding Gaps for Completion Times of Multiple Unicasts
share
Arguably the most common network communication problem is multiple-unicasts: Distinct packets at different nodes in a network need to be delivered to a destination specific to each packet as fast as possible. The famous multiple-unicast conjecture posits that, for this natural problem, there is no performance gap between routing and network coding, at least in terms of throughput. We study the same network coding gap but in terms of completion time. While throughput corresponds to the completion time for asymptotically-large transmissions, we look at completion times of multiple unicasts for arbitrary amounts of data. We develop nearly-matching upper and lower bounds. In particular, we prove that the network coding gap for the completion time of k unicasts is at most polylogarithmic in k, and there exist instances of k unicasts for which this coding gap is polylogarithmic in k.
READ FULL TEXT