On the Capacity of Noncoherent Network Coding

Mahdi Jafari Siavoshani, Soheil Mohajer, Christina Fragouli, Suhas N. Diggavi

TL;DR

This paper investigates the theoretical limits of network coding in scenarios where neither the sender nor the receiver has knowledge of the network's internal operations (non-coherent communication). The authors introduce a new channel model and demonstrate that using subspace coding is optimal for achieving the maximum information rate, especially in networks with packet erasures.

What Problem Does This Paper Address?

Traditional network coding relies on receivers knowing the exact operations performed by intermediate nodes. However, in dynamic or large-scale networks, this "coherent" knowledge is often impractical or costly to obtain. This paper addresses the challenge of non-coherent network coding, where the network's internal workings are unknown. Specifically, it aims to:

  1. Determine the fundamental limits (capacity) of information transmission in such non-coherent networks.
  2. Identify optimal coding strategies that can achieve these limits.
  3. Compare the performance of these strategies against existing methods, like using coding vectors.

The authors focus on a probabilistic model where channel transfer matrices are randomly drawn, and they extend their analysis to multi-source scenarios, which are common in applications like sensor networks.

Methods

The core of this paper lies in developing a novel probabilistic channel model for non-coherent network coding. Key methodological aspects include:

  • Random Matrix Channel Model: The channel is modeled using random matrices that change over time, reflecting the unknown and dynamic nature of the network.
  • Subspace Coding: The authors propose and analyze the use of subspace coding, where information is encoded into subspaces of a vector space. This is a departure from traditional linear coding where information is encoded into specific vectors.
  • Capacity Calculation: They derive the channel capacity as a function of network parameters like packet length and field size.
  • Equivalence of Channels: A crucial step is showing the equivalence between a matrix channel (operating on matrices) and a subspace channel (operating on subspaces) for capacity calculation. This simplifies the analysis.
  • Convex Optimization: For finding optimal input distributions, the authors leverage convex optimization techniques and the Kuhn-Tucker theorem.
  • Extension to Multi-Source MAC: The framework is extended to model multiple sources transmitting to a single receiver, forming a non-coherent multiple access channel (MAC).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Subspace Coding is Optimal: The paper definitively shows that subspace coding is the optimal strategy for achieving capacity in non-coherent network coding scenarios, outperforming traditional coding vector approaches in certain regimes.
  • Packet Length Matters: The optimal choice of subspace dimensions for encoding is shown to be dependent on the packet length. For shorter packets, a wider range of subspace dimensions might be optimal, while for longer packets, fewer, larger dimensions suffice.
  • Non-Coherence is Manageable: Despite the lack of channel state information, the paper demonstrates that high communication rates are still achievable by leveraging probabilistic models and subspace coding.
  • Erasures Don't Kill Capacity: The analysis extends to packet erasure networks, showing that capacity can still be bounded and achieved even when packets are lost.
  • Coding Vectors vs. Subspace Coding: The paper provides guidelines on when subspace coding offers significant advantages over coding vectors, particularly for shorter packet lengths. For large field sizes and long packets, the performance gap diminishes.

Key Results

  • Capacity Formulae: The paper provides explicit formulae for the channel capacity in both asymptotic (large field size) and finite field size regimes for single-source non-coherent network coding. For example, Theorem 2 states the asymptotic capacity is $i^*(T – i^*) \log_2 q + o(1)$, where $i^* = \min[m, n, \lfloor T/2 \rfloor]$.
  • Optimal Input Distribution: Theorem 3 characterizes the optimal input distribution, showing it's non-zero only for matrices of specific ranks, and Theorem 8 reveals that for the subspace channel, the optimal input distribution is uniform over subspaces of the same dimension.
  • Multi-Source MAC Capacity Region: Theorem 7 provides the asymptotic capacity region for a two-user non-coherent multiple access channel, showing that for certain conditions, coding vectors are asymptotically optimal.
  • Packet Erasure Bounds: Theorem 5 provides upper and lower bounds on the capacity in the presence of packet erasures, showing it scales with $\mu_1 (T – m) \log_2 q$, where $\mu_1$ is the expected number of received packets.

Limitations and Future Work

  • Generalization to Ns Sources: While the paper extends to two sources for the MAC, the authors believe the technique can be generalized to more than two sources.
  • Exact qo Characterization: Theorem 3 provides a non-asymptotic result, but analytically finding the exact minimum field size $q_0$ for which the theorem holds is noted as difficult. Theorem 4 offers a way to characterize $q_0$ under certain conditions.
  • Practical Implementation: The paper focuses on theoretical capacity. Future work could explore practical implementations of subspace coding in non-coherent network settings.
  • Other Error Models: The paper primarily considers packet erasures. Extending the analysis to other error models (e.g., additive errors) could be valuable.

Summary updated

Abstract

We consider the problem of multicasting information from a source to a set of receivers over a network where intermediate network nodes perform randomized linear network coding operations on the source packets. We propose a channel model for the noncoherent network coding introduced by Koetter and Kschischang in , that captures the essence of such a network operation, and calculate the capacity as a function of network parameters. We prove that use of subspace coding is optimal, and show that, in some cases, the capacity-achieving distribution uses subspaces of several dimensions, where the employed dimensions depend on the packet length. This model and the results also allow us to give guidelines on when subspace coding is beneficial for the proposed model and by how much, in comparison to a coding vector approach, from a capacity viewpoint. We extend our results to the case of multiple source multicast that creates a virtual multiple access channel.
BibTeX
@article{siavoshani2011capacity,
  author = {Mahdi Jafari Siavoshani and Soheil Mohajer and Christina Fragouli and Suhas N. Diggavi},
  title = {{On the Capacity of Noncoherent Network Coding}},
  journal = {IEEE Trans. Information Theory},
  year = {2011},
  url = {https://openreview.net/forum?id=nECEpYlisf},
}
Figure