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.
翻译:具有缓冲尺寸限制的线条网络的能力是一个开放但实际上重要的问题。 在本文中, 我们考虑由离散的无记忆通道组成的线条网络, 并研究分批编码的可实现速度, 其中包括在文献中研究的线条网络现有编码方案, 作为一种特殊情况。 分批编码有一个外码和一个内码。 外部编码将信息输入成批, 每个组都是一组编码符号, 而内码在发送批次的节点上对属于同一批次的符号进行重新编码。 条纹代码使我们能够通过调和编码参数, 施加各种区块长度和缓冲尺寸限制。 我们使用一种技术, 捕捉到线条网络的通信瓶颈, 将分批编码的可实现速度作为若干编码参数组的线网长度函数的上限。 我们还讨论具体的重新编码计划, 能达到这些编码参数组的线条长度的顺序。 我们的结果为我们如何在实际情景下设计大型多波纹网络通信提供了指导, 使用一个统一的编码框架, 而不是传统的层办法。