# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 3 Multi-Phase Adaptive Recoding
### Protocol Design  
To evaluate the decoding time, we need a workable protocol that supports multi-phase recoding. The purpose of the following discussion is to give a preliminary idea on a workable protocol and also to construct such a protocol for our numerical evaluation. Note that advanced protocol design may affect the performance and decoding time in practice. We leave such an optimal design as an open problem. In a fire-and-forget recoding approach, i.e., one-phase recoding, the minimal protocol is very simple. Every BNC packet consists of a batch ID (BID), a coefficient vector, and a payload [72, 85, 86]. Besides acting as a batch identifier, the BID is also used as a seed for the pseudorandom generator so that the encoder and the decoder can agree with the same random sequence. Depending on the BNC design, this random sequence may be used for describing how a batch is being generated. The coefficient vector records the network coding operations--that is, it describes how a recoded packet is being mixed by random linear combination. At last, the payload is the data carried by the packet. To travel through the existing network infrastructure, the BNC packet is encapsulated by other network protocols for transmission [85, 86, 106]. In more complicated designs, there are control packets and control mechanisms besides the data packets [124], but they are beyond the scope of this paper. We can see that there is no feedback packet required in the minimal protocol. To maximize the information carried by each recoded packet in a batch, recoding is performed when no packet of this batch will be received anymore. In order to identify that the previous node has transmitted all recoded packets of a batch without using feedback, the minimal protocol assumes that the batches are transmitted sequentially and there is no out-of-order packet across batches, so that when a node receives a packet from a new batch (with a new BID), we can start recoding the original batch. In case there are out-of-order packets across batches, a simple way to handle this is to assume an ascending order of BID so that we can detect and discard the out-of-order packets. This way, the protocol does not rely on feedback. However, to support multi-phase recoding, we need to know the reception state of the batches at the next node; thus, we must introduce feedback packets in the protocol. We modify from the minimal protocol this way. For the BNC packets (data packets), we also attach a list of BID-phase pairs when the node has finished sending all recoded packets of the corresponding phases of these batches. That is, the next node can start recoding the corresponding phase and send a feedback packet back to the current node. The number of recoded packets depends on the innovative rank of the batch, which is determined by the multi-phase recoding optimization problems. The BID-phase pair will be removed from the list when the next node notifies the reception state of this information. The feedback packet consists of a list of BID-phase-rank triples. When the node receives a BID-phase pair, it sends an acknowledgment of receiving this BID-phase pair together with the rank of the batch with this BID at this node, i.e., a BID-phase-rank triple. A triple will be removed from the list when the corresponding BID-phase pair no longer appears in the incoming BNC packets, i.e., the previous node has received the acknowledgment. The feedback packet is constantly sent from a node like a heartbeat message to combat against feedback packet loss. For a bidirectional transmission scenario, this list of triples can be sent together with the BNC packets. Certainly, we can separate these lists from the data packets and send them as control messages. This way, we can have a better flexibility on the length of the payload, as the length of a BNC packet is usually limited by the protocols that encapsulate it, e.g., 65,507 bytes for UDP over IPv4.