Routing versus Network Coding in Erasure Networks with Broadcast and Interference Constraints

This paper determines upper and lower bounds on the scaling of the system throughput with the number of nodes in an erasure network with transmit and receive-side constraints. This model is a useful abstraction of the network-layer behavior of a wireless network. An upper bound on throughput is determined for such a network, which is found to be achievable by routing within a polylog factor if the parameter that determines the decay of channel quality with distance is greater than a critical value. In other words, network coding can provide no more than a polylog factor improvement in performance in such networks.