Capacity of multiple unicast in wireless networks: A polymatroidal approach

Sreeram Kannan, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

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
Volume60
Issue number10
DOIs
StatePublished - Oct 1 2014

Fingerprint

Wireless networks
Feedback
Network layers
Complex networks
broadcast
engineering
reciprocity
performance
traffic

Keywords

  • 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

Cite this

Capacity of multiple unicast in wireless networks : A polymatroidal approach. / Kannan, Sreeram; Viswanath, Pramod.

In: IEEE Transactions on Information Theory, Vol. 60, No. 10, 6877730, 01.10.2014, p. 6303-6328.

Research output: Contribution to journalArticle

@article{8a297ec07d1848f4a7d774b462a55797,
title = "Capacity of multiple unicast in wireless networks: A polymatroidal approach",
abstract = "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.",
keywords = "Multiple unicast, ad hoc networks, deterministic networks, layering, network capacity, network information theory, polymatroidal networks, submodular networks, wireless networks",
author = "Sreeram Kannan and Pramod Viswanath",
year = "2014",
month = "10",
day = "1",
doi = "10.1109/TIT.2014.2347277",
language = "English (US)",
volume = "60",
pages = "6303--6328",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "10",

}

TY - JOUR

T1 - Capacity of multiple unicast in wireless networks

T2 - A polymatroidal approach

AU - Kannan, Sreeram

AU - Viswanath, Pramod

PY - 2014/10/1

Y1 - 2014/10/1

N2 - 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.

AB - 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.

KW - Multiple unicast

KW - ad hoc networks

KW - deterministic networks

KW - layering

KW - network capacity

KW - network information theory

KW - polymatroidal networks

KW - submodular networks

KW - wireless networks

UR - http://www.scopus.com/inward/record.url?scp=84906563896&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84906563896&partnerID=8YFLogxK

U2 - 10.1109/TIT.2014.2347277

DO - 10.1109/TIT.2014.2347277

M3 - Article

AN - SCOPUS:84906563896

VL - 60

SP - 6303

EP - 6328

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 10

M1 - 6877730

ER -