On the queueing behavior of inter-flow asynchronous network coding

Despite the substantial research efforts on network coding, its real-world implementation is mainly over wireless networks or peer-to-peer networks. The deployment of network coding in the Internet core still largely lags behind. Among the many challenges, one difficulty is the selection of routers to perform network coding, which relies on the understanding of the queueing behavior of network coding. Unfortunately, the intricate queueing behavior of network coding, even for a single node case, is still unclear. In this paper, we build a generic queueing model to answer many fundamental questions, including for example, under what condition is the system stable? How many packets could be possibly coded when multiple stochastic traffic flows pass through a coding node? What is the quantitative relationship among the traffic arrival rate, the service rate, and the coding opportunities under a general network configuration? Based on our analytical results, we propose a self-adjustable delay-based coding mechanism for better congestion control. Our work provides network researchers and engineers with insights on the queueing behavior of network coding, which are helpful in future applications of network coding in the Internet core.