Queueing analysis of a butterfly network

Abstract—Network coding has gained significant attention in recent years as a means to improve throughput, especially in multicast scenarios. These capacity gains are achieved by combining packets algebraically at various points in the network, thereby alleviating local congestion at the nodes. The benefits of network coding are greatest when the network is heavily utilized or, equivalently, when the sources have infinite backlogs. However, if a network supports delay-sensitive applications, traffic is often sparse and congestion becomes undesirable. The lighter loads typical of real-time traffic with variable sources tend to reduce the returns of network coding. This work seeks to identify the potential benefits of network coding in the context of delay-sensitive applications. As a secondary objective, this paper also studies the cost of establishing network coding in wireless environments. For a network topology to be suitable for coding, links need to possess a proper structure. The cost of establishing this structure may require excessive wireless resources in terms of bandwidth and transmit power. Together, these effects decrease the potential benefits of network coding. For real-time applications over wireless networks, it may be best not to combine information at the nodes. I