# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 3 Multi-Phase Adaptive Recoding
### Multi-Phase Relaxed Adaptive Recoding Problem (RAP)
Up to this point, we know that the hardness of RAP is raised from the selection of \(\alpha_{i}\). Our simulation shows that two-phase RAP already has a significant throughput gain; therefore, we propose an efficient bisection-like heuristic for two-phase RAP in Algorithm 2 for practical deployment. The heuristic is based on our observations that the objective of RAP looks unimodal with respect to \(\alpha_{1}\). Note that although we solve TAP multiple times in the algorithm, we can reuse the previous output of TAP by applying the tuning scheme in [73] so that we do not need to repeatedly run the full Algorithm 1. ```
Data: Total available resource \(t_{\text{avg}}\), rank distribution \(\{\Pr(R_{1}=r)\}_{r=0}^{M}\), loss rate \(p\), threshold \(\epsilon\). Result: Approximate solution \((t_{1},r)_{r=0}^{M}\), \((t_{2},r)_{r=0}^{M}\) for RAP. \(\alpha_{\min}\gets 0\) ; \(\alpha_{\max}\gets t_{\text{avg}}\) ; while\(\alpha_{\max}-\alpha_{\min}>\epsilon\)do \(\alpha\leftarrow(\alpha_{\min}+\alpha_{\max})/2\) ; for\(i=1,2,3\)do \(e^{\prime}\leftarrow(i-2)\epsilon\) ;  Run TAP on \(R_{1}\) and resource \(\alpha+\epsilon^{\prime}\) to obtain \(T_{1}^{(i)}\) and objective \(E_{1}^{(i)}\) ;  Calculate \(R_{2}\) ;  Run TAP on \(R_{2}\) and resource \(t_{\text{avg}}-(\alpha+\epsilon^{\prime})\) to obtain \(T_{2}^{(i)}\) and objective \(E_{2}^{(i)}\) ; \(E^{(i)}\gets E_{1}^{(i)}+E_{2}^{(i)}\) ; if\(E^{(1)}\leq E^{(2)}\leq E^{(3)}\)then\(\alpha_{\min}\leftarrow\alpha\) ; else\(\alpha_{\max}\leftarrow\alpha\) ; return\(T_{1}^{(2)}\), \(T_{2}^{(2)}\) ;
```  
**Algorithm 2**Heuristic for two-phase RAP. Before we continue, we discuss a subtle issue in adaptive recoding here. Consider \(\alpha_{i}<\mathbb{E}[R_{i}]=\sum_{r_{i}}\Pr(r_{i})r_{i}\). That is, the amount of resource is too little, so it is insufficient to send a basis of the innovative rank space. For simplicity, we call the packets in this basis the innovative packets. Recall that any feasible solution is where \(t_{ir}\leq r\) is an optimal solution for this phase. However, different optimal solutions can lead to different innovative rank distributions in the next phase. This issue actually also occurs when there are more than one \(r\) having the same value of \(\Delta_{r,t_{r}}\) in the general case, but it was ignored in previous works. In this paper, we consider the following heuristic. First, we obtain the set of candidates of \(r\), i.e., \(\operatorname*{arg\,max}_{r\in\{0,1,2,\ldots,M\}}\Delta_{r,t_{r}}\). If it is the case discussed above where the amount of resource is too little, then this set would be \(\{1,2,3,\ldots,M\}\). Next, our intuition is that we should let those with smaller \(t_{r}\) send more recorded packets. Although they have the same importance in terms of expected rank, their packets on average--i.e., the expected rank of the batch (at the next node) divided by \(t_{r}\)--possess a different importance. This means that it is more risky for us to lose a packet of that batch with smaller \(t_{r}\). At last, another intuition is that, among the \(r\)'s with the same \(t_{r}\), we should let the higher rank one send more recoded packets so that the shape of the rank distribution at the next node is skewed towards the higher rank side, i.e., potentially more information (rank) is retained. To conclude, we have \(r=\max\operatorname*{arg\,min}_{r^{\prime}\in\operatorname*{arg\,max}_{r^{ \prime}\in\{0,1,2,\ldots,M\}}\Delta_{r^{\prime},t_{r^{\prime}}}}t_{r^{\prime \prime}}\).