Queueing Analysis of a Butterfly Network for Comparing Network Coding to Classical Routing

Abstract—Network coding has gained significant attention in re-cent years as a means to improve throughput, especially in mul-ticast scenarios. These capacity gains are achieved by combining packets algebraically at various points in the network, thereby al-leviating local congestion at the nodes. The benefits of network coding are greatest when the network is heavily utilized or, equiva-lently, when the sources are saturated so that there is data to send at every scheduling opportunity. Yet, when a network supports delay-sensitive applications, traffic is often bursty 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 objec-tive, 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 es-tablishing this structure may require excessive radio resources in terms of bandwidth and transmit power. Bursty traffic together with structural cost tend to decrease the potential benefits of net-work coding. This paper describes how, for real-time applications over wireless networks, there exist network topologies for which it may be best not to establish a network structure tailored to net-work coding. Index Terms—Butterfly network, communication system, delay, quality of service (QoS), network coding, routing, tail asymptotics, tandem queues, wireless networks, wireless systems. I