# ARQ for Network Coding - Computer Science > Information Theory

Abstract: A new coding and queue management algorithm is proposed for communicationnetworks that employ linear network coding. The algorithm has the feature thatthe encoding process is truly online, as opposed to a block-by-block approach.The setup assumes a packet erasure broadcast channel with stochastic arrivalsand full feedback, but the proposed scheme is potentially applicable to moregeneral lossy networks with link-by-link feedback. The algorithm guaranteesthat the physical queue size at the sender tracks the backlog in degrees offreedom also called the virtual queue size. The new notion of a node -seeing-a packet is introduced. In terms of this idea, our algorithm may be viewed as anatural extension of ARQ schemes to coded networks. Our approach, known as thedrop-when-seen algorithm, is compared with a baseline queuing approach calleddrop-when-decoded. It is shown that the expected queue size for our approach is$O\frac1{1- ho}$ as opposed to $\Omega\frac1{1- ho^2}$ for the baselineapproach, where $ho$ is the load factor.

Author: Jay Kumar Sundararajan, Devavrat Shah, Muriel Médard

Source: https://arxiv.org/