On the Efficiency of Random Access Scheduling for Wireless Multi-Hop Networks

Speaker: Apoorva Jindal, USCAbstract: We formally establish that random access scheduling with carrier sense yields exceptionally good performance in the context of wireless multi-hop networks. A common misconception is that existing random access schemes, like CSMA-CA, yield unfair and inefficient rates in these networks. This misconception is based on works which study CSMA-CA scheduled multi-hop networks either with TCP or in saturation conditions both of which grossly underutilize the available capacity that CSMA-CA provides, or use topologies which cannot occur in practice due to physical layer limitations.To formally establish our thesis, we derive worst case performance bounds on CSMA-CA scheduling in multi-hop networks. We first derive a methodology to characterize the capacity region for any CSMA-CA-scheduled multi-hop network, thus addressing a long standing fundamental open problem in the research community. We then use this characterization to compare the max-min rate allocation achieved by CSMA-CA and optimal scheduling, and find that: (i) in any realistic topology with geometric constraints due to the physical layer, CSMA-CA is never worse than 30% of the optimal, and (ii) in typical topologies, CSMA-CA attains more than 55% of the optimal throughput. Considering that the state-of-the-art distributed collision-free approximations to optimal scheduling achieve lower worst case bounds than the above, CSMA-CA is surprisingly efficient. To ensure that this good performance is achievable with a distributed rate controller, we design and implement two rate control schemes, WCP and WCP-CAP, which achieve close to optimal performance.Biography: Apoorva Jindal is currently with the Networked Systems Performance and Design Lab at University of Southern California. He received his B.Tech degree in EE from IIT Kanpur in 2002, and then received his PhD degree in EE from USC in January 2009. His research primarily focusses on protocol design, implementation and performance analysis for wireless networks. The research he has been involved with during his thesis has received grants from NSF and Cisco as well as the "Best and Most Compelling Presentation and Demonstration Award" at the networking workshop "Future of TCP: Train-wreck or Evolution" held at the Stanford University and sponsored by Cisco systems. He has been a recipient of the Best Graduate Teaching Assistant award from the Electrical Engineering Department at USC and the best undergraduate research project award at IIT Kanpur from Tata Consultancy Services.Host: Michael Neely, mjneely@usc.edu, EEB 520, x03505

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos