Backlog-Based Random Access Algorithms: Stability Issues via Fluid Limits

July 2, 2013
Hosted by: Columbia Joint CS/EE Networking Seminar Series
Speaker: Dr. Philip Whiting (Bell Labs)


We use fluid limits to explore the (in)stability properties of wireless networks with backlog-based random-access algorithms. While relatively simple and inherently distributed in nature, suitably designed backlog-based access schemes provide the striking capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. The type of activation rules for which throughput optimality has been established, may however yield excessive backlogs and delays. More aggressive/persistent access schemes have the potential to improve the delay performance, but do not offer any universal maximum-stability guarantees.

In order to gain qualitative insight and investigate the (in)stability properties of more aggressive/persistent activation rules, we examine fluid limits where the system dynamics are scaled in space and time. In some situations, the fluid limits have smooth deterministic features and maximum stability is maintained, while in other scenarios they exhibit rather erratic random characteristics. In the latter regime, more aggressive access schemes continue to provide maximum stability in some networks, but may persistently drive the system into inefficient states and cause instability in others. Simulation experiments are conducted to illustrate and validate the analytical results.

Speaker Biography

Phil Whiting received his BA degree from the University of Oxford, his MSc from the University of London and his Ph. D. was in queuing theory from the University of Strathclyde. After a post-doc at the University of Cambridge, Phil's interests centered on wireless. In 1993 Phil participated in the Telstra trial of Qualcomm CDMA in South Eastern Australia. He then joined the Mobile research Centre at the University of South Australia Adelaide. He was a Member of Technical Staff at Bell Labs from January 1997 to June 2013. He is now a research fellow at MacQuarie University, Sydney Australia.

His main interests are the mathematics of wireless networks, particularly stochastic models for resource allocation, information and coding theory. Phil's current research includes lazy maxweight scheduling, CSMA networks, HetNets and the theory of random matrices.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University