Stability and delay of distributed scheduling algorithms for networks of conflicting queues

Abstract

This paper explains recent results on distributed algorithms for networks of conflicting queues. At any given time, only specific subsets of queues can be served simultaneously. The challenge is to select the subsets in a distributed way to stabilize the queues whenever the arrival rates are feasible. One key idea is to formulate the subset selection as an optimization problem where the objective function includes the entropy of the distribution of the selected subsets. The dual algorithm for solving this optimization problem provides a distributed scheduling algorithm that requires only local queue-length information. The algorithm is based on the CSMA (Carrier Sense Multiple Access) protocol in wireless networks. We also explain recent results, some of them unpublished so far, on the delay properties of these algorithms. In particular, we present a framework for queuing stability under bounded CSMA parameters, and show how the expected queue lengths depend on the throughput region to be supported. When the arrival rates are within a fraction of the capacity region, queue lengths that are polynomial (or even logarithmic) in the number of queues can be achieved.

Additional details