# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
### Paper Organization and Our Contributions  
The organization of this paper is as follows: The background of BNC and the formulation of the adaptive recoding framework are described in Section 2. This formulation aims for a fire-and-forget strategy, i.e., a one-phase adaptive recoding scheme. Next, the optimization model of multi-phase adaptive recoding is described in Section 3. The general problem in Section 3.1 is complex and hard to solve due to the high dependency between phases. Therefore, a relaxed model is formulated in Section 3.2 and a heuristic to efficiently solve the two-phase problem is proposed. After that, the mixed use of systematic recoding and multi-phase recoding is investigated in Section 3.3. This version is easy to be solved and gives a lower bound on the other multi-phase recoding models. Next, the design of a protocol that supports multi-phase recoding is described in Section 3.4, which allows the evaluation of the decoding time. At last, the numerical evaluations of the throughput and the decoding time are presented in Section 4, and the study is concluded in Section 5. The flow of this research is highlighted in the flowchart illustrated in Figure 2.  
The first contribution of this study lies on the formulation and investigation of the throughput of multi-phase recoding. As a tradition in BNC literature, the throughput is defined as the expected value of the rank distribution of the batches arriving at the destination node, i.e., the theoretical upper-bound of the achievable rate [68]. This is because there exists BNC (e.g., BATS codes [63]) that can achieve a close-to-optimal rate. The throughput is the objective to be maximized in the framework of adaptive recoding. However, the full multi-phase problem is hard to optimize in general; thus, we formulate a  
Figure 2: The flowchart highlighting the flow of this research. relaxed problem as a baseline for comparison. For the two-phase relaxed problem, we also propose a heuristic so that we can approximate the solution efficiently. The throughput defined for BNC does not consider the time needed for decoding. It is a measurement of the amount of information carried by the transmissions. Yet, decoding time is a crucial factor in Internet of Things and real-time applications. When the previous node has finished sending all recoded packets of the current batch, it will be an appropriate time to start recoding a batch in traditional BNC, as this arrangement can maximize the throughput (i.e., expected rank) [84, 85]. With systematic recoding, the received linearly independent recoded packets are directly forwarded to the next node; thus, the number of recoded packets to be generated at later stages is reduced. Although this approach can potentially reduce the decoding time, its generalization into a multi-phase variation to become aligned with the multi-phase recoding scheme is necessary, which lays down the second contribution of this study. An example of two-phase variation of systematic recoding is illustrated in Figure 3. The flow of the phases between the previous and the current nodes is the same as that shown in Figure 1. When the current node receives a linearly independent recoded packet, it forwards the packet to the next node directly. Starting from phase 2, the nodes (both the previous and the current nodes) generate new recoded packets by RLNC to avoid (with high probability) having the same packet arriving at the next node again. Except the last phase, the number of recoded packets is the same as the innovative rank in this phase; thus, the idea is similar to the original systematic recoding. In the last phase, a fire-and-forget adaptive recoding is applied to complete the batch transmission process. There might be many idling time intervals between the current and the next nodes in the figure, but this can be attributed to the consideration of a single batch (as shown in the figure). During these time intervals, packets of other batches can be sent to utilize the link, and a more detailed discussion can be found in Section 3.4.