# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 2 Preliminary
### Traditional Adaptive Recoding Problem (TAP)  
We now discuss the adaptive recoding framework, which we call the Traditional Adaptive recoding Problem (TAP) in this paper. The formulation of our multi-phase recoding models is a generalization of this TAP framework. After that, we reduce our models into instances of TAPs so that we can solve them efficiently.  
Let \(R\) be the random variable of the (innovative) rank of a batch. When the node receives an (innovative) rank-\(r\) batch, it sends \(t_{r}\) recoded packets to the next node. As we cannot use the outgoing link indefinitely for a batch, there is a \"resource\" limitation for the transmission. This resource, denoted by \(t_{\text{avg}}\), is the average number of recoded packets per batch, which is an input to the adaptive recoding framework. Depending on the scenario, this value may be jointly optimized with other objectives [122].  
From [73], we know that if the packet loss pattern is a stationary stochastic process, e.g., the Bernoulli process we used in this paper for independent packet loss, then the expected rank function \(E(r,t)\) is concave with respect to \(t\). Further, under this concavity condition, the adaptive recoding problem that maximizes the average expected rank at the next node can be written as  
\[\max_{\{t_{i}\}_{i=0}^{M}} \sum_{r=0}^{M}\Pr(R=r)E(r,t_{r})\] (1) s.t. \[\sum_{r=0}^{M}\Pr(R=r)t_{r}=t_{\text{avg}}.\]  
Our multi-phase recoding formulations in the remaining text of this paper are constructed based on (1). For ease of reference, we reproduce in Algorithm 1 the greedy algorithm for solving TAP [73] with the initial condition embedded. In the algorithm, \(\Delta_{r,t}\)is defined to be \(E(r,t+1)-E(r,t)\), which can be calculated via dynamic programming or regularized incomplete beta functions [74].  
```
Data: Available resource \(u\), innovative rank distribution \(\{\Pr(R=r)\}_{r=0}^{M}\). Result: Optimal solution \((t_{r})_{r=0}^{M}\) of TAP. \(t_{r}\gets 0,\forall r=0,1,2,\ldots,M\); while\(u>0\)do \(r\leftarrow\) an element in \(\arg\max_{r\in[0,1,2,\ldots,M]}\Delta_{r,\lfloor t_{r}\rfloor}\); if\(\Pr(R=r)(1-(t_{r}-\lfloor t_{r}\rfloor))\leq u\)then \(u\gets u-\Pr(R=r)(1-(t_{r}-\lfloor t_{r}\rfloor))\); \(t_{r}\leftarrow\lfloor t_{r}\rfloor+1\); else \(t_{r}\gets t_{r}+u/\Pr(R=r)\); \(u\gets 0\); return\((t_{r})_{r=0}^{M}\);
```  
**Algorithm 1**Greedy Algorithm for Solving TAP.  
As a remark, when there is insufficient resource for forwarding, i.e., \(\mathbb{E}[R]\geq t_{\mathrm{avg}}\), any feasible solution satisfying \(t_{r}\leq r\) is an optimal solution of (1), and the optimal objective value is \((1-p)t_{\mathrm{avg}}\). This is stated in the following lemma, which is a continuous analogue of [123], Lemma 2.  
**Lemma 1**: _When \(\mathbb{E}[R]\geq t_{\mathrm{avg}}\), any feasible solution satisfying \(t_{r}\leq r\) is an optimal solution of (1), and the optimal objective value is \((1-p)t_{\mathrm{avg}}\)._  
According to [73], Corollary 2, all \(\Delta_{r,t}\) have the same value when \(t<r\) for all \(r\). On the other hand, we know that \(\Delta_{r+1,t_{r}}>\Delta_{r,t}\) for all \(t\geq r>0\) from [73], Theorem 1. In other words, as Algorithm 1 selects those largest \(\Delta_{\cdot\cdot}\) until the resources deplete, we conclude that it will terminate with \(t_{r}\leq r\) for all \(r\). As \(\hat{E}(r,t_{r})=(1-p)t_{r}\) for \(t_{r}\leq r\), the objective value is \(\sum_{r=0}^{M}\Pr(R=r)(1-p)t_{r}=(1-p)t_{\mathrm{avg}}\).