On the Scaling Law of Network Coding Gains in Wireless Networks

We study the scaling law governing the delay gains of network coding as compared to traditional transmission strategies in unreliable wireless networks. We distinguish between two types of traffic, namely elastic and inelastic, where the elasticity of a flow is based on the delay constraints associated with it. This novel formulation is useful in that it allows for the modeling of real-time traffic more accurately. Considering the limited availability of feedback in such systems, we focus on strategies with minimal acknowledgement requirements. Under both traffic types, we provide an extensive analysis of the gains of network coding as compared to traditional transmission strategies in a single-hop setting, and show that the gains are significant in general and can be considerably large in some cases. We further provide a method for realizing these gains in multi-hop networks with general topologies using the analysis of the single hop scenario.