Capacity Scalability of Line Networks with Batched Codes

Shenghao Yang, Jie Wang, Yanyan Dong, Yiheng Zhang

Abstract

The capacity of line networks with buffer size constraints is an open, but practically important problem. In this paper, we consider line networks formed by discrete memoryless channels, and study the achievable rate of batched codes, which include several existing coding schemes studied in literature for line networks as special cases. A batched code has an outer code and an inner code. The outer code encodes the information messages into batches, each of which is a group of coded symbols, while the inner code performs recoding on the symbols belonging to the same batch at all nodes that forwarding a batch. Batched codes enable us to impose various block-length and buffer size constraints by tuning coding parameters. Using a technique that captures the communication bottleneck of line networks, we derive upper bounds on the achievable rates of batched codes as functions of line network length for several coding parameter sets. We also discuss specific recoding schemes that can achieve rates of the same order of the line network length for these coding parameter sets. Our results shed light on how to design large multi-hop network communications in practical scenarios using a unified coding framework instead of the traditional layered approach.

Introduction

In long multi-hop "line networks"—such as underwater acoustic sensors, deep-space communication, or multi-hop wireless relays—achieving maximum data rates traditionally requires intermediate nodes to possess massive memory buffers and tolerate high latency. While the theoretical "min-cut" bound suggests the rate is limited only by the weakest link, practical constraints on buffer size and latency at relay nodes often make this bound unreachable as the network length ($L$) grows.

This paper investigates the fundamental trade-offs between network length, buffer size, and achievable data rate using a unified framework called Generalized Batched Network Coding (GBNC). By strictly constraining the buffer size at intermediate nodes, the authors establish the absolute maximum data rates achievable as the network scales.

Generalized Batched Network Coding (GBNC)

GBNC offers a flexible approach to multi-hop communication by decoupling the coding process into two layers:

  1. Outer Code: Encodes information messages into batches of size $M$.
  2. Inner Code: Performs recoding on symbols within the same batch at each intermediate node using an inner blocklength $N$.

By adjusting parameters $M$ and $N$, researchers can impose specific block-length and buffer size constraints, allowing for a more granular analysis of hardware requirements versus performance.

Table of notations used throughout the paper.

Methodology: The Bottleneck Status Technique

To derive upper bounds on capacity, the authors introduce the "Bottleneck Status" technique. This method identifies a probabilistic event where at least one link in the network produces a constant output regardless of the input. When this "bottleneck" occurs, information flow is effectively halted. By calculating the probability of this event across $L$ hops, the authors establish strict limits on the maximum achievable rate $C_L(M, N)$.

For lower bounds, the paper utilizes a channel reduction technique. This simplifies networks with heterogeneous noisy links into a model of identical links, facilitating the proof that specific rates are achievable with practical coding schemes like Random Linear Network Coding (RLNC).

Scaling Laws and Buffer Trade-offs

The core contribution of this work is the characterization of how data rates scale with network length under different buffer constraints. The findings reveal a sharp transition in performance based on how the inner blocklength $N$ scales with $L$.

Summary of upper and lower bounds for different coding parameters.

Key Findings:

  • Constant Buffer Constraints ($N = O(1)$): If the buffer size is strictly limited to a constant number of symbols, the achievable rate decays exponentially ($O(e^{-c'L})$) as the network length increases. There is no coding strategy that can circumvent this fundamental decay.
  • The Logarithmic Sweet Spot ($N = O(\ln L)$): By allowing the buffer size to grow logarithmically with the network length, the rate decay is significantly mitigated, scaling at $O(1/\ln L)$.
  • Efficiency of Simple Codes: Surprisingly, complex "decode-and-forward" schemes are not always necessary. The authors demonstrate that a simple repetition code can achieve the optimal $O(1/\ln L)$ scaling while requiring a buffer size of only $O(\ln \ln L)$, which is exponentially more efficient than standard methods.

Conclusion

This research provides a unified framework for designing large-scale multi-hop networks, proving that the traditional layered approach is not always optimal under strict memory constraints. Instead, simple batched coding schemes can achieve near-optimal rate scaling with drastically reduced hardware requirements. These results offer a roadmap for designing efficient communication protocols for resource-constrained relay devices in large-scale deployments.

Summary updated

Abstract

The capacity of line networks with buffer size constraints is an open, but practically important problem. In this paper, we consider line networks formed by discrete memoryless channels, and study the achievable rate of batched codes, which include several existing coding schemes studied in literature for line networks as special cases. A batched code has an outer code and an inner code. The outer code encodes the information messages into batches, each of which is a group of coded symbols, while the inner code performs recoding on the symbols belonging to the same batch at all nodes that forwarding a batch. Batched codes enable us to impose various block-length and buffer size constraints by tuning coding parameters. Using a technique that captures the communication bottleneck of line networks, we derive upper bounds on the achievable rates of batched codes as functions of line network length for several coding parameter sets. We also discuss specific recoding schemes that can achieve rates of the same order of the line network length for these coding parameter sets. Our results shed light on how to design large multi-hop network communications in practical scenarios using a unified coding framework instead of the traditional layered approach.
BibTeX
@article{yang2024capacity,
  author = {Shenghao Yang and Jie Wang and Yanyan Dong and Yiheng Zhang},
  title = {{Capacity Scalability of Line Networks with Batched Codes}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2024},
  doi = {10.1109/jsac.2024.3365900},
}
Figure