The Taub Faculty of Computer Science Events and Talks

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 for the network coding gap for this natural problem. 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.

This talk is based on joint work with Bernhard Haeupler and Goran Zuzic.