A Unified Adaptive Recoding Framework for Batched Network Coding

Batched network coding is a variation of random linear network coding which has low computational and storage costs. In order to adapt random fluctuations in the number of erasures in individual batches, it is not optimal to recode and transmit the same number of packets for all batches. Different distributed optimization models, which are called adaptive recoding schemes, were formulated for this purpose. The key component of these optimization problems is the expected value of the rank distribution of a batch at the next network node, which is also known as the expected rank. In this paper, we put forth a unified adaptive recoding framework. We show that the expected rank functions are concave when the packet loss pattern is a stationary stochastic process regardless of the field size, which covers but not limited to independent packet loss and burst packet loss. Under this concavity assumption, we show that there always exists a solution which not only can minimize the randomness on the number of recoded packets but also can tolerate rank distribution errors due to inaccurate measurements or limited precision of the machine. To obtain such an optimal solution, we propose tuning schemes that can turn any feasible solution into a desired optimal solution.