The role of feedback in the choice between routing and coding for wireless unicast

Ramakrishna Gummadi, Laurent Massoulie, Ramavarapu S Sreenivas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the benefits of coding in wireless networks, specifically its role in exploiting the local broadcast property of the wireless medium. We first argue that for unicast, the throughput achieved with network coding is the same as that achieved without any coding. This argument highlights the role of a general max-flow min-cut duality and is more explicit than previous proofs. The maximum throughput can be achieved in multiple ways without any coding, for example, using backpressure routing, or using some centralized flow scheduler that is aware of the network topology. However, all such schemes, in order to take advantage of the local broadcast property, require dynamic routing decisions for choosing the next hop for each packet from among the nodes where it is successfully received. This choice seems to depend critically on feedback signalling information like queue lengths, or ARQ. In contrast, note that the use of network coding can achieve the same without such feedback, in exchange for decoding overhead. A key issue to be resolved in making a comparison between routing and coding would be how critical feedback signalling is, for the throughput of routing policies. With this motivation, we first explore how feedback at a given node affects its throughput, with arbitrary rates of its one hop neighbors to the destination. Static routing policies which are essentially feedback independent, are considered. An explicit characterization of the optimal policies under such a feedback constraint is obtained, which turns out to be a natural generalization of both flooding and traditional routing (which does not exploit local broadcast, because the next hop is fixed prior to the transmission). When losses at the receivers are independent (still allowing for dependencies on transmissions by two different nodes, to model interference), the reduction in capacity due to constraining the feedback is limited to a constant fraction (1 - e-1 = 63%) of the coding capacity, and gets arbitrarily close to optimal as the capacity itself is low. This result also extends to a more general version on feed forward networks without any assigned rates of the one hop neighbors to the destination. However, if there are dependencies in the losses seen by receivers from a single broadcast, the reduction could be arbitrarily bad, even with just two hops.

Original languageEnglish (US)
Title of host publication2010 IEEE International Symposium on Network Coding, NetCod 2010
Pages67-72
Number of pages6
DOIs
StatePublished - Oct 18 2010
Event2010 IEEE International Symposium on Network Coding, NetCod 2010 - Toronto, ON, Canada
Duration: Jun 9 2010Jun 11 2010

Publication series

Name2010 IEEE International Symposium on Network Coding, NetCod 2010

Other

Other2010 IEEE International Symposium on Network Coding, NetCod 2010
CountryCanada
CityToronto, ON
Period6/9/106/11/10

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'The role of feedback in the choice between routing and coding for wireless unicast'. Together they form a unique fingerprint.

Cite this