Delay Stability of Back-Pressure Policies in the presence of Heavy-Tailed Traffic

Abstract—We study scheduling and routing problems that arise in multi-hop wireline networks with a mix of heavy-tailed and light-tailed traffic. We analyze the delay performance of the widely studied class of Back-Pressure policies, known for their throughput optimality property, using as a performance criterion the notion of delay stability, i.e., whether the expected end-to-end delay in steady state is finite. First, by means of simple examples, we provide insights into how the network topology, the routing constraints, and the link capacities (relative to the arrival rates) may affect the delay stability of the Back-Pressure policy in the presence of heavy-tailed traffic. Next, we illustrate how fluid approximations facilitate the delay-stability analysis of multi-hop networks with heavy-tailed traffic. This approach allows us to derive analytical results that would have been hard to obtain otherwise, and also to build a Bottleneck Identification algorithm, which identifies (some) delay unstable queues by solving the fluid model of the network from certain initial conditions. Finally, we show how one can achieve optimal performance, with respect to the delay stability criterion, by using a parameterized version of the Back-Pressure policy. I