On queueing in coded networks - queue size follows degrees of freedom

We propose a new queueing mechanism for coded networks with stochastic arrivals and/or lossy links. In this context, earlier work introduced the notion of "virtual queues" which represent the backlog in degrees of freedom. For instance, the work by Ho and Viswanathan defined the achievable rate region for which the virtual queue size is stabilized, using intra-session coding. The queueing scheme that we propose here forms a natural bridge between the virtual queue size and the physical queue size, and thus extends their result to the stability of the physical queues as well. Specifically, we show that the amount of memory used at the transmit buffer in our scheme is upper bounded by the total backlog in the number of linearly independent degrees of freedom. Moreover, our scheme gives an online algorithm for queue update and coding, in the sense that the coding does not happen block by block, but in a streaming manner. The main idea in our scheme is to ensure that the information stored at the sender excludes any knowledge that is common to all receivers. This requires the transmitting node to track the states of knowledge of its receivers. Therefore, if the links are lossy, some form of feedback may be necessary.