On the Impact of a Single Edge on the Network Coding Capacity

Shirin Jalali, Michelle Effros, Tracey Ho

Abstract

In this paper, we study the effect of a single link on the capacity of a network of error-free bit pipes. More precisely, we study the change in network capacity that results when we remove a single link of capacity $\delta$. In a recent result, we proved that if all the sources are directly available to a single super-source node, then removing a link of capacity $\delta$ cannot change the capacity region of the network by more than $\delta$ in each dimension. In this paper, we extend this result to the case of multi-source, multi-sink networks for some special network topologies.

Introduction

Determining the exact capacity region of a general communication network remains a significant challenge in information theory. While network coding—allowing intermediate nodes to process data rather than just route it—can enhance throughput, calculating the precise set of achievable rates is often hindered by our limited understanding of entropy vectors.

Instead of seeking an absolute capacity value, this research investigates the sensitivity of the capacity region. Specifically, we ask: how does the overall network capacity degrade when a single edge $e$ has its capacity reduced by $\delta$? Does the network performance collapse catastrophically, or does it degrade gracefully? Previous work established that for networks with a single "super-source" node, the capacity region shrinks by at most $\delta$ in each dimension.

A network where all sources $M_1, \dots, M_k$ are available to a single super-source node $v_o$.

Methodology

The study employs a theoretical framework to compare an original network $\mathcal{N}$ with a degraded version $\mathcal{N}'$. The goal is to prove that if a rate vector $\mathbf{R}$ is achievable in $\mathcal{N}$, then a rate of $(\mathbf{R} - \delta \cdot \mathbf{1})^+$ is achievable in $\mathcal{N}'$. Two primary analytical paths are explored:

  1. Linear Network Coding Analysis: For networks restricted to linear codes, an algebraic proof demonstrates that sources can be coordinated to bypass the missing capacity. By restricting source messages such that the data on the degraded link is forced to zero, the loss is exactly bounded by $\delta$.
  2. Information-Theoretic Proof for General Codes: Since linear codes are not always optimal, a more rigorous proof is provided for general codes on specific topologies. The authors model the network as a combination of a $k$-user Multiple Access Channel (MAC) and a Deterministic Broadcast Channel (BC). Using Fano's inequality and entropy bounds, they demonstrate that reliable transmission is maintained at the reduced rate even with non-linear coding.

Key Results

The central contribution is Theorem 1, which applies to a $k$-unicast network topology featuring a central bottleneck. The theorem states that reducing a single link's capacity by $\delta$ reduces the achievable rate vector by at most $\delta$ per dimension.

Comparison between the original network $\mathcal{N}$ (a) and the degraded network $\mathcal{N}'$ (b) where link $\delta$ is removed.

This result allows for the derivation of computable outer bounds on the capacity region of such networks. By relating the complex $k$-unicast structure to the intersection of simpler, solvable multicast and single-source networks, the authors provide a tool for bounding performance in previously intractable scenarios.

Conclusion and Future Work

This work proves that for specific bottlenecked topologies, network capacity is robust to small link degradations. However, the proofs currently rely on specific structural assumptions, such as the presence of super-sources or the $k$-unicast bottleneck. The ultimate question—whether this $\delta$-reduction rule holds for all arbitrary multi-source, multi-sink networks—remains an open and compelling challenge for future research in network information theory.

Summary updated

Abstract

In this paper, we study the effect of a single link on the capacity of a network of error-free bit pipes. More precisely, we study the change in network capacity that results when we remove a single link of capacity $\delta$. In a recent result, we proved that if all the sources are directly available to a single super-source node, then removing a link of capacity $\delta$ cannot change the capacity region of the network by more than $\delta$ in each dimension. In this paper, we extend this result to the case of multi-source, multi-sink networks for some special network topologies.
BibTeX
@inproceedings{jalali2011impact,
  author = {Shirin Jalali and Michelle Effros and Tracey Ho},
  title = {{On the Impact of a Single Edge on the Network Coding Capacity}},
  booktitle = {ITA},
  year = {2011},
  url = {https://openreview.net/forum?id=xVGUhUZLpX},
}
Figure