On the characteristics of queueing and scheduling at encoding nodes for network coding

Synchronization can greatly influence the performance of network coding. In this paper, we shall investigate the synchronization issue based on the use of queueing theory. We shall first propose a queueing model, referred to as the classic model, to investigate the characteristics of the encoding process. It will be proved that given the packet arrival processes are stationary, i.e. the distribution of the arrival processes does not depend on time, and obey independently and identically Poisson distribution and that the encoding time is exponentially distributed, the output flow will be an asymptotically Poisson flow with the same parameter. Through simulation we shall show that the network is sensitive to the arrival rate of input flows and becomes unstable with the input queue size increasing to infinity. This indicates that the classic coding scheme would impose strict requirements on synchronization over the whole network. In order to address this, we shall propose a combined opportunistic scheduling and encoding (COSE) strategy, in which the classic coding scheme and the traditional forwarding algorithm are well integrated. Theoretical analysis and simulation will demonstrate that the COSE strategy is able to control the input queue sizes and keep the network operating in a stable state while maintaining a relatively high throughput, low blocking probability and small waiting delay under various levels of traffic load.