Capacity of multiple unicast in wireless networks: A polymatroidal approach

Sreeram Kannan, Pramod Viswanath

Research output: Contribution to journalArticlepeer-review


A classical result in undirected wireline networks is the near optimality of routing (flow) for multiple-unicast traffic (multiple sources communicating independent messages to multiple destinations): the min cut upper bound is within a logarithmic factor of the number of sources of the max flow. In this paper, we extend the wireline result to the wireless context. In particular, we show the following meta-theorem: if for a given channel and its reciprocal channel, the cut-set bound is (approximately) achievable, then for multiple-unicast in a bidirected network comprised of such channels, the cut-set bound is (approximately) achievable within a logarithmic factor of the number of sources. The achievable scheme can be viewed as an instantiation of a simple layering principle: local physical-layer schemes combined with global routing. We use the reciprocity of the wireless channel critically in this result. We prove this result formally as a capacity approximation result for a variety of channel models, including general Gaussian networks under fast fading, networks comprised only of broadcast and MAC channels, and networks comprised of broadcast erasure channels with feedback. The capacity approximations we prove tend to have both an additive gap (power loss) and a multiplicative gap (degrees of freedom loss). The key engineering insight is that layered architectures, common in the engineering-design of wireless networks, can have near-optimal performance if the locality over which physical-layer schemes should operate is carefully designed. Feedback is shown to play a critical role in enabling the separation between the physical and the network layers. The main technical contribution is the usage of polymatroidal network as a graphical model for analyzing the performance of complex wireless networks.

Original languageEnglish (US)
Article number6877730
Pages (from-to)6303-6328
Number of pages26
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - Oct 1 2014


  • Multiple unicast
  • ad hoc networks
  • deterministic networks
  • layering
  • network capacity
  • network information theory
  • polymatroidal networks
  • submodular networks
  • wireless networks

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Capacity of multiple unicast in wireless networks: A polymatroidal approach'. Together they form a unique fingerprint.

Cite this