Delay optimal queue-based CSMA

In the past year or so, an exciting progress has led to throughput optimal design of CSMA-based algorithms for wireless networks. However, such an algorithm suffers from very poor delay performance. A recent work suggests that it is impossible to design a CSMA-like simple algorithm that is throughput optimal and induces low delay for any wireless network. However, wireless networks arising in practice are formed by nodes placed, possibly arbitrarily, in some geographic area.

In this paper, we propose a CSMA algorithm with per-node average-delay bounded by a constant, independent of the network size, when the network has geometry (precisely, polynomial growth structure) that is present in any practical wireless network. Two novel features of our algorithm, crucial for its performance, are (a) choice of access probabilities as an appropriate function of queue-sizes, and (b) use of local network topological structures. Essentially, our algorithm is a queue-based CSMA with a minor difference that at each time instance a very small fraction of frozen nodes do not execute CSMA. Somewhat surprisingly, appropriate selection of such frozen nodes, in a distributed manner, lead to the delay optimal performance.