  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.
