# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 3 Multi-Phase Adaptive Recoding
### Protocol Design
To reduce the computational overhead due to the reassembling of IP fragments at every node for recoding, the length may further be limited within the size of a data-link frame. With these modifications, the timing for recoding is no longer dependent on the sequential order of BIDs. To demonstrate how the protocol works, we consider a two-hop network (a source node, an intermediate node, and a destination node) with the following settings. We divide the timeline into synchronized timeslots. Each node can send one BNC packet to the next node at each individual timeslot. At the same time, each node can send one feedback packet to the previous node. A transmission will be received at the next timeslot. Assume a node can react to the received BID-phase pairs and BID-phase-rank triples immediately. Also, assume that a feedback packet is sent at every timeslot when acknowledgment is needed. Each BNC packet and feedback packet have independent probability to be lost during transmission. The batch size and the average number recoded packets for all phases at each node are both four, i.e., \(M=t_{\text{avg}}=4\). We consider the flow of the packets until the destination node receives a total rank of 10, so that the flow is long enough to reach the second phase of some batches while it is short enough to be illustrated in a single page. The computational time for recoding is omitted here, as it only consists of a small amount of operations, which can be further accelerated by multi-threading, intrinsic instructions for single instruction/multiple data (SIMD), or hardware implementation. The solution of the adaptive recoding problem can be reused if the configuration is not changed. In practice, the bottleneck is the transmission rate of the channel. Figure 4 illustrates an example flow of the protocol without adopting multi-phase systematic recoding. Consider two-phase recoding: At the beginning, the BNC packets sent by the source node do not include the list of BID-phase pairs. After finishing phase 1 of the first batch, the BID-phase pair \((1,1)\) is attached to the next BNC packet. The intermediate node gives feedback about the rank of the batch it received. When the source node receives  
the feedback for BID 1 phase 1, it will not attach this information again in the upcoming BNC packets. This way, the intermediate node can make use of the BID-phase pairs attached to the received BNC packets to identify whether the source node has received the feedback message or not. As the feedback packet can also be lost, the intermediate node constantly sends feedback messages to the source node. A similar process is conducted between the intermediate node and the destination node. We can see in the figure that the intermediate node did not start phase 2 of the second batch (BID 2). This is because the innovative rank of the batch at the intermediate node after phase 1 is 0. The destination node cannot gain any rank by receiving more recorded packets of this batch. Right after that, the intermediate node has nothing to be transmitted; thus, an idle timeslot is induced. Figure 4: An example flow of the protocol without adopting multi-phase systematic recoding. The hyphen in the feedback BID–phase–rank triple means that the value will not be used by the previous node. We illustrate another example in Figure 5. This time we adopt two-phase SAP: The source node sends four packets per batch in phase 1. As the average number of recoded packets \(t_{\text{avg}}=4\), the source node sends nothing in phase 2. Therefore, we can see that once the source node receives the feedback of BID 1 phase 1 from the intermediate node, it sends the BID-phase pair \((1,2)\) directly, which indicates the end of BID 1 phase 2. Notice that if we configure with a larger value of \(t_{\text{avg}}\), the source node will send packets in phase 2 if some of the phase 1 packets are lost. These extra packets will be regarded as phase 1 systematic packets sent from the intermediate node.