Distributed throughput optimal scheduling in the presence of heavy-tailed traffic

Abstract

The heavy tailed traffic in wireless networks fundamentally challenges the applicability of conventional throughput optimal scheduling algorithms. To encounter this, the stability performance of distributed maximum weight scheduling algorithms (DMWS), which are known to be throughput optimal under light tailed environment, is first analyzed. More specifically, it is shown that heavy tailed traffic can significantly degrade the stability performance of DMWS. In particular, it is proven that if a user with light-tailed traffic arrivals has the average traffic rate lambda below a threshold lambda*, it will experience bounded queueing delay. Otherwise, if lambda is larger than a threshold. lambda', its queueing delay is necessarily of infinite mean. To address this problem, the distributed maximum weight-alpha scheduling (DMWS-alpha) algorithm is proposed, which makes the scheduling decision based on the queue lengths raised to the alpha-th power. It is demonstrated that DMWS-alpha is throughput optimal with respect to moment stability in the sense that if the traffic arrivals rates are within the network stability region, all network users with light-tailed traffic arrivals always have bounded queueing delay with finite mean and variance.