Distributed random access algorithms

Prof. F.P. Kelly

This essay concerns networks of conflicting queues. These models are motivated by emerging communication networks, for example wireless devices that can communicate directly when they are close enough to each other.

A scheduling algorithm is throughput-optimal if it can stabilize the network queues for all feasible arrival rates. An early breakthrough was the Maximum Weight algorithm of Tassiulas and Ephremides, but this algorithm is computationally expensive and centralized.

There is considerable current interest in whether throughput-optimal algorithms can be implemented in a simple and distributed manner, using only local information. Random access algorithms in particular have been the focus of several recent papers. The delay properties of these algorithms are not well understood.

This essay will review recent progress in this area.

Relevant courses

Essential: Stochastic Networks

References

Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
L. Tassiulas and A. Ephremides
IEEE Trans. Autom. Control 37 (1992), 1936-1948.

Distributed random access algorithm: scheduling and congestion control
Jiang, L., Shah, D., Shin, J. and Walrand, J.
IEEE Trans. Inform. Theory 56 (2010), 6182-6207.

Randomized scheduling algorithm for queueing networks
Shah, D. and Shin, J.
Ann. Appl. Probab. 22 (2012), 128-171.

Stability and delay of distributed scheduling algorithms for networks of conflicting queues
L Jiang and J Walrand
Queueing Systems 72 (2012), 161-187