Network capacity under traffic symmetry: Wireline and wireless networks

Sudeep Kamath, Sreeram Kannan, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

The problem of designing near optimal strategies for multiple unicast traffic in wireline networks is wide open; however, channel symmetry or traffic symmetry can be leveraged to show that routing can achieve with a polylogarithmic approximation factor of the edge-cut bound. For the same problem, the edge-cut bound is known to only upper bound rates of routing flows and unlike the information theoretic cut-set bound, it does not upper bound (capacity-achieving) information rates with general strategies. In this paper, we demonstrate that under channel or traffic symmetry, the edge-cut bound upper-bounds general information rates, thus providing a capacity approximation result. The key technique is a combinatorial result relating edge-cut bounds to generalized network sharing bounds. Finally, we generalize the results to wireless networks via an intermediary class of combinatorial graphs known as polymatroidal networks - our main result is that a natural architecture separating the physical and networking layers is near optimal when the traffic is symmetric among source-destination pairs, even when the channel is asymmetric (due to asymmetric power constraints, or prior frequency allocation like frequency division duplexing). This result is complementary to an earlier work of two of the authors proving a similar result under channel symmetry.

Original languageEnglish (US)
Article number6847686
Pages (from-to)5457-5469
Number of pages13
JournalIEEE Transactions on Information Theory
Volume60
Issue number9
DOIs
StatePublished - Sep 2014

Fingerprint

Frequency allocation
Channel capacity
Wireless networks
traffic
networking

Keywords

  • Network coding
  • wireless networks

ASJC Scopus subject areas

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

Cite this

Network capacity under traffic symmetry : Wireline and wireless networks. / Kamath, Sudeep; Kannan, Sreeram; Viswanath, Pramod.

In: IEEE Transactions on Information Theory, Vol. 60, No. 9, 6847686, 09.2014, p. 5457-5469.

Research output: Contribution to journalArticle

@article{73d93db478ea40f5ba7922f0d8121c1d,
title = "Network capacity under traffic symmetry: Wireline and wireless networks",
abstract = "The problem of designing near optimal strategies for multiple unicast traffic in wireline networks is wide open; however, channel symmetry or traffic symmetry can be leveraged to show that routing can achieve with a polylogarithmic approximation factor of the edge-cut bound. For the same problem, the edge-cut bound is known to only upper bound rates of routing flows and unlike the information theoretic cut-set bound, it does not upper bound (capacity-achieving) information rates with general strategies. In this paper, we demonstrate that under channel or traffic symmetry, the edge-cut bound upper-bounds general information rates, thus providing a capacity approximation result. The key technique is a combinatorial result relating edge-cut bounds to generalized network sharing bounds. Finally, we generalize the results to wireless networks via an intermediary class of combinatorial graphs known as polymatroidal networks - our main result is that a natural architecture separating the physical and networking layers is near optimal when the traffic is symmetric among source-destination pairs, even when the channel is asymmetric (due to asymmetric power constraints, or prior frequency allocation like frequency division duplexing). This result is complementary to an earlier work of two of the authors proving a similar result under channel symmetry.",
keywords = "Network coding, wireless networks",
author = "Sudeep Kamath and Sreeram Kannan and Pramod Viswanath",
year = "2014",
month = "9",
doi = "10.1109/TIT.2014.2335205",
language = "English (US)",
volume = "60",
pages = "5457--5469",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "9",

}

TY - JOUR

T1 - Network capacity under traffic symmetry

T2 - Wireline and wireless networks

AU - Kamath, Sudeep

AU - Kannan, Sreeram

AU - Viswanath, Pramod

PY - 2014/9

Y1 - 2014/9

N2 - The problem of designing near optimal strategies for multiple unicast traffic in wireline networks is wide open; however, channel symmetry or traffic symmetry can be leveraged to show that routing can achieve with a polylogarithmic approximation factor of the edge-cut bound. For the same problem, the edge-cut bound is known to only upper bound rates of routing flows and unlike the information theoretic cut-set bound, it does not upper bound (capacity-achieving) information rates with general strategies. In this paper, we demonstrate that under channel or traffic symmetry, the edge-cut bound upper-bounds general information rates, thus providing a capacity approximation result. The key technique is a combinatorial result relating edge-cut bounds to generalized network sharing bounds. Finally, we generalize the results to wireless networks via an intermediary class of combinatorial graphs known as polymatroidal networks - our main result is that a natural architecture separating the physical and networking layers is near optimal when the traffic is symmetric among source-destination pairs, even when the channel is asymmetric (due to asymmetric power constraints, or prior frequency allocation like frequency division duplexing). This result is complementary to an earlier work of two of the authors proving a similar result under channel symmetry.

AB - The problem of designing near optimal strategies for multiple unicast traffic in wireline networks is wide open; however, channel symmetry or traffic symmetry can be leveraged to show that routing can achieve with a polylogarithmic approximation factor of the edge-cut bound. For the same problem, the edge-cut bound is known to only upper bound rates of routing flows and unlike the information theoretic cut-set bound, it does not upper bound (capacity-achieving) information rates with general strategies. In this paper, we demonstrate that under channel or traffic symmetry, the edge-cut bound upper-bounds general information rates, thus providing a capacity approximation result. The key technique is a combinatorial result relating edge-cut bounds to generalized network sharing bounds. Finally, we generalize the results to wireless networks via an intermediary class of combinatorial graphs known as polymatroidal networks - our main result is that a natural architecture separating the physical and networking layers is near optimal when the traffic is symmetric among source-destination pairs, even when the channel is asymmetric (due to asymmetric power constraints, or prior frequency allocation like frequency division duplexing). This result is complementary to an earlier work of two of the authors proving a similar result under channel symmetry.

KW - Network coding

KW - wireless networks

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

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

U2 - 10.1109/TIT.2014.2335205

DO - 10.1109/TIT.2014.2335205

M3 - Article

AN - SCOPUS:84906674860

VL - 60

SP - 5457

EP - 5469

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 9

M1 - 6847686

ER -