Broadcast Throughput in Radio Networks: Routing vs. Network Coding

Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, Majid KhabbazianSODA 2014 · DOI

Abstract

The efficiency of broadcasting in networks is a fundamental problem in distributed computing. While network coding is known to offer significant throughput advantages over traditional routing in wired networks, its benefit in wireless environments—specifically under the radio network model—has remained an open question. This paper establishes that the asymptotic network coding gap in radio networks is $\Theta(\log \log n)$. Furthermore, it demonstrates that the worst-case broadcast throughput for both routing and network coding is $\Theta(1/\log n)$ messages per round.

Introduction

Broadcasting—the process of disseminating information from a single source to all other nodes in a network—is a cornerstone of communication theory. Traditionally, this is achieved via routing, where intermediate nodes act as relays, storing and forwarding atomic messages. A more recent paradigm, network coding, allows nodes to perform algebraic operations on incoming messages (e.g., XORing packets) before transmission.

In wired networks, it has been shown that network coding can provide an asymptotic throughput advantage over routing. However, wireless networks introduce the challenge of interference. In the standard radio network model, a transmission is successful only if a receiver has exactly one transmitting neighbor. If multiple neighbors transmit simultaneously, a collision occurs, and no information is received. This paper investigates whether the flexibility of network coding provides a significant advantage over routing in this interference-limited setting.

Methodological Framework

To analyze this problem, the authors introduce several theoretical innovations that simplify the complexity of multi-hop wireless communication.

The Bipartite Simplification

A key contribution is the proof that the worst-case broadcast throughput of any general network can be characterized by studying bipartite networks. By reducing complex topologies to a two-layer model consisting of "senders" and "receivers," the authors could isolate the effects of interference and node degree without loss of generality.

Solitude Transmission Schedules (STS)

Analyzing routing is notoriously difficult when multiple messages are pipelined through a network. To address this, the authors developed the Solitude Transmission Schedule (STS). This abstraction focuses on the successful delivery of a single "message of interest" while treating concurrent transmissions as potential noise. The authors proved a fundamental link: if a low-weight STS exists for a network, a high-throughput routing schedule can be constructed.

The Network Coding Gap

The central finding of this research is the existence of a tight $\Theta(\log \log n)$ network coding gap. Through a probabilistic construction of a specific family of random bipartite networks, the authors demonstrate that there are instances where routing is mathematically constrained to be slower than coding by this factor.

This gap arises from a "degree dichotomy." In a wireless environment:

  1. To reach nodes with high degrees (many neighbors), very few senders should transmit to avoid collisions.
  2. To reach nodes with low degrees (few neighbors), many senders should transmit to ensure at least one signal reaches the receiver.

While network coding can effectively "mask" these conflicting requirements by mixing messages, routing algorithms struggle to balance these needs simultaneously across the entire network. However, the $\Theta(\log \log n)$ factor is surprisingly small; for a network of one billion nodes, network coding might only offer a five-fold speedup over the optimal routing strategy.

Universal Throughput Bounds

Beyond the gap between the two methods, the paper establishes the absolute limits of broadcasting in radio networks. The authors prove that for any network with $n$ nodes, the worst-case broadcast throughput is $\Theta(1/\log n)$ messages per round.

Crucially, this bound applies to both routing and network coding. The authors provide a routing scheme that achieves $\Omega(1/\log n)$ throughput for any arbitrary network, demonstrating that routing is asymptotically almost as robust as the most sophisticated coding schemes. They also provide a simplified proof for the $O(1/\log n)$ upper bound, showing that no algorithm, regardless of its complexity, can surpass this limit in the worst case.

Conclusion and Future Directions

This work settles the question of the network coding gap in the asymptotic regime where the number of messages ($k$) and nodes ($n$) are large. It reveals that while network coding provides a measurable benefit, the advantage is limited in the face of wireless interference.

A significant remaining question involves the "small $k$" regime. The routing algorithms presented here require a large number of messages to reach peak efficiency. If only a few messages (e.g., $k = \log n$) are being broadcast, the gap between routing and coding might be as large as $\Theta(\log n)$. Future research into these transient states will be essential for practical applications in dynamic wireless networks.

Summary updated

BibTeX
@inproceedings{alon2014broadcast,
  author = {Noga Alon and Mohsen Ghaffari and Bernhard Haeupler and Majid Khabbazian},
  title = {{Broadcast Throughput in Radio Networks: Routing vs. Network Coding}},
  booktitle = {SODA},
  year = {2014},
  doi = {10.1137/1.9781611973402.132},
}
Figure