# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
### Aims and Objectives  
In this paper, we consider the use of \"reception status\" as a feedback for the previous node. As every recorded packet is a random linear combination of the existing packets, all recorded packets of the same batch have the same importance with respect to information carriage. In other words, the \"reception status\" is not the status for each individual packet but a piece of information that can represent the rank of the batch.  
From the reception status, the node can infer the number of \"innovative\" ranks that is still capable of providing the next node. Thus, the node may start another phase of transmission for sending these innovative ranks by recoding, where the number of recoded packets in this phase depends on the innovative ranks. The throughput can be enhanced because this approach can be regarded as \"partial\" hop-by-hop retransmission. Partial retransmission is emphasized in this context because in BNC, not all ranks (or packets) in a batch are necessary to be received for data recovery purposes. The \"retransmitted\" packets, which are recoded packets generated by random linear combinations, are likely to be different from what the node has previously sent. On the other hand, due to recoding, more packets apart from the innovative rank of a batch can be sent before receiving the feedback. These features of BNC make the concept of \"retransmission\" different from the conventional one.  
In general, one can perform more than two phases of recoding, i.e., multi-phase recoding. To understand the idea of \"phase\", we first illustrate in Figure 1 a three-phase recoding. To transmit a batch, the current node begins phase 1 and sends a few recoded packets. The number of recoded packets depends on the recoding scheme, which will be discussed in Section 3. The lost packets are marked by crosses in Figure 1. After the current node sends all phase 1 packets to the next node, the next node sends a feedback packet for phase 1, which describes the reception status of the batch. According to the feedback packet, the current node infers the number of \"ranks\" of the batch that can still be provided to the next node, i.e., the innovative rank of the batch; then, the transmission of phase 2 will begin. The number of recoded packets depends on the innovative rank inferred. After the current node has sent all phase 2 packets, the next node gives feedback for phase 2. Lastly, the current node starts phase 3 and discards the batch afterwards. Although the reception state after the last phase does not seem useful as it will not trigger a new phase, it can be used for synchronization in the protocol design. Details can be found in Section 3.4.  
Figure 1: An example of three-phase recoding. Each arrow corresponds to the flow of a packet. The crosses represent the lost packets.  
Although the idea looks simple, the main difficulty arises from the allocation of the expected number of packets to be sent in each phase. This problem does not exist in generation-based RLNC, as BNC does not require the next node to receive all the ranks. The optimization problem is a generalization of the adaptive recoding framework with high dependence between phases.