Broadcast throughput in radio networks: Routing vs. Network coding

Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian

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

7 Scopus citations

Abstract

The broadcast throughput in a network is defined as the average number of messages that can be transmitted per unit time from a given source to all other nodes when time goes to infinity. Classical broadcast algorithms treat messages as atomic tokens and route them from the source to the receivers by making intermediate nodes store and forward messages. The more recent network coding approach, in contrast, prompts intermediate nodes to mix and code together messages. It has been shown that certain wired networks have an asymptotic network coding gap, that is, they have asymptotically higher broadcast throughput when using network coding compared to routing. Whether such a gap exists for wireless networks has been an open question of great interest. We approach this question by studying the broadcast throughput of the radio network model which has been a standard mathematical model to study wireless communication. We show that there is a family of radio networks with a tight Θ(log log n) network coding gap, that is, networks in which the asymptotic throughput achievable via routing messages is a Θ (log log n) factor smaller than that of the optimal network coding algorithm. We also provide new tight upper and lower bounds showing that the asymptotic worst-case broadcast throughput over all networks with n nodes is Θ(1/log n)messages-per- round for both routing and network coding.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery
Pages1831-1843
Number of pages13
ISBN (Print)9781611973389
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
CountryUnited States
CityPortland, OR
Period1/5/141/7/14

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Broadcast throughput in radio networks: Routing vs. Network coding'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Ghaffari, M., Haeupler, B., & Khabbazian, M. (2014). Broadcast throughput in radio networks: Routing vs. Network coding. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 (pp. 1831-1843). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973402.132