# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 3 Multi-Phase Adaptive Recoding
### Multi-Phase Systematic Adaptive Recoding Problem (SAP)  
We now investigate a constrained version of GAP. In systematic recoding, we forward the received, linearly independent packets of a batch to the next node--that is, the number of packets we forwarded is the rank of the batch. As a multi-phase analogue of systematic recoding, in each phase, the number of packets we \"forwarded\" is the innovative rank of the batch of that phase. However, except the first phase, the so-called \"forwarded\" packetsare generated by RLNC so that we do not need to learn and detect which packets sent by the previous phases are lost during the transmission process. We now formulate the \(S\)-phase Systematic Adaptive recoding Problem (SAP), where for each batch, the node sends the innovative packets to the next node in all phases except the last one. That is, except the last phase, we have \(t_{i,r}=r\) for all \(r\), where these phases are called the systematic phases. For the last phase, we perform adaptive recoding on the phase \(S\) innovative rank with the remaining resource. By imposing the systematic phases as constraints to (3), we obtain  
\[ \begin{split}\max_{T_{S}}&\sum_{r_{S}}\Pr(r_{S})E( r_{S},t_{S,r_{S}})+\sum_{i=1}^{S-1}\sum_{r_{i}}\Pr(r_{i})E(r_{i},r_{i})\\ \text{s.t.}&\sum_{r_{S}}\Pr(r_{S})t_{S,r_{S}}+\sum_ {i=1}^{S-1}\sum_{r_{i}}\Pr(r_{i})r_{i}=t_{\text{avg}}.\end{split}  \tag{5}\]  
When \(\sum_{i=1}^{S-1}\sum_{r_{i}}\Pr(r_{i})r_{i}>t_{\text{avg}}\), i.e., there is insufficient resources to perform the first \((S-1)\) phases, (5) has no feasible solution. Thus, we need to choose a suitable \(S\) in practice. On the other hand, as the variables are all for the last phase, we can regard SAP as a single-phase problem; thus, it has the same form as TAP. That is, SAP can be solved by Algorithm 1. When (5) has a feasible solution, then the optimal solution of (5) is a feasible solution of (3). As SAP is easier to solve compared to RAP, by investigating higher-phase SAP, we can obtain a lower bound on the performance of higher-phase GAP. Let \(\tilde{R}_{i}\) be the random variable of the phase \(i\) innovative rank where all the previous phases are systematic phases. For the first phase, define \(\tilde{R}_{1}=R_{1}\). Then, \(\tilde{R}_{1}\rightarrow\tilde{R}_{2}\rightarrow\ldots\rightarrow\tilde{R}_ {S}\) forms a Markov chain. For any \(k\in\mathbb{Z}^{+}\), systematic recoding uses \(t_{k,r_{k}}=r_{k}\). That is, we have \(\underset{t\sim}{\text{Bin}}(r_{k},p,r_{k};\cdot)=\text{Bin}(r_{k},p;\cdot)\). The following lemma and theorem give the formulae on the performance of SAP. **Lemma 2**. : _Assume \(\sum_{i=1}^{k-1}\sum_{r_{i}}\Pr(r_{i})r_{i}\leq t_{\text{avg}}\), i.e., there are enough resources to perform \((k-1)\) systematic phases, then \(\mathbb{E}[\tilde{R}_{k}]=p^{k-1}\mathbb{E}[R_{1}]\)._  
Proof. : By using (2), we have  
\[\mathbb{E}[\tilde{R}_{k}]=\sum_{r_{k}}r_{k}\Pr(r_{k})=\sum_{r_{1},r_{2},\ldots r _{k}}r_{k}\Pr(r_{1})\prod_{j=1}^{k-1}\text{Bin}(r_{j},p;r_{j}-r_{j+1}).\]  
We prove this lemma by induction. When \(k=1\), we have \(\mathbb{E}[\tilde{R}_{1}]=\mathbb{E}[R_{1}]=p^{(1)-1}\mathbb{E}[R_{1}]\). Assume \(\mathbb{E}[\tilde{R}_{k}]=p^{k-1}\mathbb{E}[R_{1}]\) for some \(k\in\mathbb{Z}^{+}\). For the case of \(k+1\), we have  
\[\mathbb{E}[\tilde{R}_{k+1}] =\sum_{r_{1},r_{2},\ldots,r_{k+1}}r_{k+1}\Pr(r_{1})\prod_{j=1}^{k }\text{Bin}(r_{j},p;r_{j}-r_{j+1})\] \[=\sum_{r_{1},r_{2},\ldots,r_{k}}\Pr(r_{1})\left(\sum_{r_{k+1}}r_{ k+1}\text{Bin}(r_{k},p;r_{k}-r_{k+1})\right)\prod_{j=1}^{k-1}\text{Bin}(r_{j},p;r_{j }-r_{j+1})\] \[=p\sum_{r_{1},r_{2},\ldots,r_{k}}r_{k}\Pr(r_{1})\prod_{j=1}^{k-1} \text{Bin}(r_{j},p;r_{j}-r_{j+1})\] \[=p^{(k+1)-1}\mathbb{E}[R_{1}].\qed\]  
**Theorem 3**. : _Assume \(\sum_{i=1}^{k}\sum_{r_{i}}\Pr(r_{i})r_{i}\leq t_{\text{avg}}\), i.e., there are enough resources to perform \(k\) systematic phases; then, the resources consumed by these \(k\) phases are \(\frac{1-p^{k}}{1-p}\mathbb{E}[R_{1}]\) and the average expected rank at the next node is \((1-p^{k})\mathbb{E}[R_{1}]\)._Proof.