Upper Bound Scalability on Achievable Rates of
Batched Codes for Line Networks

The communication in a network from a source node to a destination node may go through multiple hops, each of which introduces errors. In this paper, we are interested in the problem that when the intermediate nodes have buffer size constraints, how the communication rate scales with the number of hops.

In particular, we consider a line network of $L$ hops formed by a sequence of nodes, where discrete memoryless channels (DMCs) exist only between two adjacent nodes. We call the first node source node and the last node destination node. Except for the source and destination nodes, all the other nodes, called intermediate nodes, have one incoming channel and one outgoing channel. Each intermediate node has a buffer of $B$ bits to keep the content used between different intermediate processing steps. There are no other storage and computation constraints on the network nodes.

For some cases of the problem, the answers are known. When the buffer size $B$ is allowed to increase with the block length at the source node, the min-cut capacity can be achieved using hop-by-hop decoding and re-encoding [1]. When the zero-error capacity of each channel is nonzero, using a constant buffer size $B$ can achieve the zero-error capacity for any value of $L$ [2].

In this paper, we focus on the DMCs in the line network with finite input and output alphabets and $0$ zero-error capacity. Note that for most common channel models, e.g., binary symmetric channels and erasure channels, the zero-error capacities are zero. When all cascaded channels are identical, Niesen, Fragouli, and Tuninetti [2] showed that a class of codes with a constant buffer size $B$ can achieve rates $\Omega(e^{-cL})$, where $c$ is a constant. They also showed that if the buffer size $B$ is of order $\ln L$, any rate below the capacity of the channel $Q$ can be achieved. Recently, Yang et al. [3, 4] showed that the end-to-end throughput can be lower bounded by $\Omega(1/\ln L)$ using an intermediate node buffer size $O(\ln\ln L)$. ¹¹1In this paper, we say that $f(n)=\Omega(g(n))$ if there exists a real constant $c>0$ and there exists an integer constant $n_{0}\geq 1$ such that $f(n)\geq c\cdot g(n)$ for every integer $n\geq n_{0}$; $f(n)=O(g(n))$ if there exists a real constant $c>0$ and there exists an integer constant $n_{0}\geq 1$ such that $f(n)\leq c\cdot g(n)$ for every integer $n\geq n_{0}$; and $f(n)=\Theta(g(n))$ if both $f(n)=\Omega(g(n))$ and $f(n)=O(g(n))$ are satisfied.

In contrast to these achievability results, min-cut is still the best upper bound. Characterizing a non-trivial, general upper bound for a line network with buffer size constraints could be difficult as hinted in [5]. We relax the difficulty of the problem by asking the scalability of the upper bound with the network length $L$ for a class of codes, called batched codes.

Batched codes provide a general coding framework for line networks with buffer size constraints, and include the codes studied in the previous works [2, 3, 4] to show the achievability results 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 sequence of coded symbols, while the inner code performs a general network coding for the symbols belonging to the same batch. The inner code, comprising of recoding at network nodes on each batch separately, should be designed for specific channels. Batched codes have been studied for designing efficient network coding for packet erasure channels (see, for example, [6, 7]), and practical designs have been provided [8, 9].

The upper bound scalability on the achievable rates of batched codes provides important guidance for us to design batched codes for large networks. For example, we want to know whether the exponential decade of the achievable rate with $L$ is necessary for $B=O(1)$, and whether we can do better than $\Omega(1/\ln L)$ when $B=O(\ln\ln L)$. These questions are answered in this paper (see Table I). In particular, we show that when $N=O(1)$, which implies $M,B=O(1)$, the achievable rates must be exponential decade with $L$. When $N=O(1/\ln L)$ and $M=O(1)$, which implies $B=O(1/\ln L)$, the achievable rate is $O(1/\ln L)$. These upper bounds have the same order of $L$ as the previous achievability results, and hence, together, provide tight capacity scalability results of batched codes for these parameter sets.

Our results are proved in a general setting of line networks where the DMC channels in the line network can be arbitrarily different except for a mild technical condition. The main technique of our converse is to separate the end-to-end transition matrix induced by the inner code as the linear combination of two parts, where one part captures the communication bottleneck in the line network and the other part can be simply upper bounded.

After introducing batched codes, we first use line networks of packet erasure channels to illustrate our main technique (Sec III). We then generalize the results to a broad class of channels called canonical channels, which include BSCs and BECs (Sec IV-A). Finally, we present a technique to solve line networks of general DMCs with zero-error capacity zero (Sec IV-B).

In this section, we describe a general line network model and introduce batched codes, which form a general coding framework for line networks with buffer size constraints.

We first discuss a special case that the channels $\{Q_{\ell}\}$ are identical packet erasure channels with transition matrix $Q_{\text{erasure}}$. Fix an alphabet $\mathcal{Q}^{*}$ with $|\mathcal{Q}^{*}|\geq 2$. Suppose that the input alphabet $\mathcal{Q}_{\mathrm{in}}$ and the output alphabet $\mathcal{Q}_{\mathrm{out}}$ are both $\mathcal{Q}^{*}\cup\{0\}$ where $0\notin\mathcal{Q}^{*}$ is called the erasure. For each $x\in\mathcal{Q}^{*}$,

where $\epsilon$ is a constant value in $(0,1)$ called the erasure probability. The input $0$ can be used to model the input when the channel is not used for transmission and we define $Q(0|0)=1$.

The relation between the input $X$ and output $Y$ of a packet erasure channel can be written as a function $Y=XZ$, where $Z$ is a binary random variable independent of $X$ with $\Pr\{Z=0\}=1-\Pr\{Z=1\}=\epsilon$. In other words, $Z$ indicates whether the channel output is the erasure or not. With this formulation, we can write for $\ell=1,\ldots,L$ and $i=1,\ldots,N$,

where $\mathbf{Z}_{\ell}[i]$ are independent binary random variables with $\Pr\{\mathbf{Z}_{\ell}[i]=0\}=\epsilon$.

The main idea of our converse is that the worst link in a line network restricts the capacity. We define the event $E_{0}$ to capture the communication bottleneck

where $\mathbf{Z}_{\ell}=0$ means $\mathbf{Z}_{\ell}[i]=0$ for all $i$. In other words, $E_{0}$ is the event that for at least one link, all the $N$ uses of the channel for a batch are erasures. Define $W_{L}^{(0)}$ and $W_{L}^{(1)}$ as the transition matrix from $\mathcal{A}^{M}$ to $\mathcal{Q}_{\mathrm{out}}^{N}$ such that

where $\overline{E_{0}}=\left\{\land_{\ell=1}^{L}(\mathbf{Z}_{\ell}\neq 0)\right\}$. As $\mathbf{X}$ and $\mathbf{Z}_{\ell}$, $\ell=1,\ldots,L$ are independent, we have

where $p_{0}=\Pr\{E_{0}\}$ and $p_{1}=1-p_{0}$. As $I(p_{\mathbf{X}},W_{L})$ is a convex function of $W_{L}$ when $p_{\mathbf{X}}$ is fixed, we obtain

As $p_{1}=(1-\epsilon^{N})^{L}$ and

we have

Consider a generic channel $Q:\mathcal{Q}_{\mathrm{in}}\to\mathcal{Q}_{\mathrm{out}}$. The relation between the input $X$ and output $Y$ of $Q$ can be modeled as a function $\alpha$ (see [10, Section 7.1]):

where $\bm{1}$ denotes the indicator function, and $Z_{x},x\in\mathcal{Q}_{\mathrm{in}}$ are independent random variables with alphabet $\mathcal{Q}_{\mathrm{out}}$ define as

For $N$ uses of the channel $Q$, we can write

where $\mathbf{Y}[i]=\alpha(\mathbf{U}[i],\mathbf{Z}[i])$.

In this section, we consider general DMCs $Q_{\ell}$ for all $\ell$, which can be modeled as the function $\alpha_{\ell}$. With the above formulation, we can write for $\ell=1,\ldots,L$,

This paper characterized the tight capacity upper bound of batched codes for line networks when the channels have finite alphabets and $0$ zero-error capacities.

Generalization of our analysis for channels with infinite alphabets and continuous channels is of research interests. The study of batched code design for a line network of channels like BSC is also desirable.

Last, we are curious whether our outer bound holds without the batched code constraint.