# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 2 Preliminary
### Batched Network Coding  
Denote by \(\mathbb{Z}\) and \(\mathbb{Z}^{+}\) the sets of integers and positive integers, respectively. Suppose we want to send a file from a source node to a destination node via a multi-hop line network. The data to be transmitted are divided into a set of input packets of the same length. Each input packet is regarded as a column vector over a finite field. An unsuitable choice of input packet size has significant implications as we need to pad useless symbols to the file [46, 90]. A similar issue also occurs in the ordinary RLNC, and there are various schemes to reduce this overhead [46, 47, 48, 49, 50]. For BNC, there are other types of padding overheads due to the finite size of batches. To select a good input packet size, one solution is to apply the heuristic in [91]. We consider a sufficiently large field size so that we can make an approximate assumption that two random vectors over this field are linearly independent of each other. This assumption is common in network coding literature such as [70, 75, 89, 92, 93]. This way, any \(n\) random vectors in an \(r\)-dimensional vector space can span a \(\min\{n,r\}\)-dimensional vector space with high probability. The source node runs a BNC encoder to generate batches. Each generated batch consists of \(M\in\mathbb{Z}^{+}\) coded packets, where \(M\) is known as the batch size. Each coded packet is a linear combination of a subset of the input packets. The formation of the subset depends on the design of the BNC. The choice of batch size is a trade-off between the advantages and disadvantages of RLNC. A large batch size can achieve a higher rate, but this reintroduces the drawback of the ordinary RLNC. A small batch size leads to a lower rate, but it allows practical deployments of BNC. Common choices of batch sizes are \(M=4,8,\) and \(16\). Take BATS codes [63, 77] as an example, where BATS coding is a matrix generalization of fountain codes such as Luby transform codes [94], Raptor codes [95, 96], and online codes [97]. The encoder samples a predefined degree distribution to obtain a degree, where the degree is the number of input packets contributed to the batch, and this set of packets is randomly chosen from the input packets. Depending on the application, there are various ways to formulate the degree distribution based on differential equation analysis [63] or tree analysis [98]. Examples of applications include streaming via sliding windows [99; 100] or expanding windows [101; 102], finite-length data transmission [103], unequal data protection [104], and multicast communication [105]. The throughput degradation issue due to unmatched degree distribution was investigated and mitigated in [77; 105; 106], and was resolved with a close-to-optimal throughput via a Wasserstein distributionally robust optimization framework in [107]. The encoding and decoding of batches form the outer code of BNC. As a general description, let \(\mathbf{S}\) be a matrix formed by juxtaposing the input packets and \(\mathbf{G}\) be a width-\(M\) generator matrix of a batch. Each column in the product of \(\mathbf{S}\) and \(\mathbf{G}\) corresponds to a packet of the batch. A coefficient vector is attached to each of the coded packets. The juxtaposition of the coefficient vectors in a freshly generated batch is an \(M\times M\) full-rank matrix, e.g., an identity matrix [85; 86]. The rank of a batch at a node is defined as the dimension of the vector space spanned by the coefficient vectors of the packets of the batch at the node. In order words, by juxtaposing the coefficient vectors of the packets of a batch at the node to form a matrix \(\mathbf{H}\), the matrix rank of \(\mathbf{H}\) is the rank of the batch at this node. At the source node, every batch has rank \(M\). Recoding is performed at any non-destination node, which is known as the inner code of BNC--that is, we can also apply recoding to generate more packets at the source node before transmitting them to the next node.