Routing is Order-optimal in Broadcast Erasure Networks with Interference

The transport capacity of a class of erasure networks with broadcast and interference constraints is studied in this paper. A memoryless network model is considered, with transmitted symbols constrained to belong to a finite field. Connections between nodes are modeled to be independent erasures, with the probability of the existence of a "link" between any two nodes decaying exponentially with increasing geographic distance between those two nodes. Each node obeys a broadcast requirement. In addition, each receiver obtains the finite-field sum of the unerased symbols sent along all the edges connecting to it (an interference condition). In this setting, the transport capacity is bounded above by a linear growth term in the number of nodes, for any network which obeys a minimum node separation constraint. Finally, we show that this linear growth is achievable in random networks by employing routing. The main thrust of this paper is its conclusion: Routing is order-optimal in a random broadcast erasure network. Thus, network coding can only provide a constant gain in performance.