Columbia University Joint CS/EE Networking Seminar Series


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

Dr. Philip Whiting

Bell Labs, Murray Hill, NJ

Tuesday, July 2, 2013, 11:00 am, CEPSR 414



Abstract: 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.

Bio: Phil Whiting received his BA degree from the University of Oxford, his MSc from the University of London and his Ph. D. was in queueing 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.