Backing out of linear backoff in wireless networks

This paper revisits the randomized backoff problem in CSMA networks and identifies opportunities of improvement. The key observation is that today's backoff operation, such as in WiFi, attempts to create a total ordering among all nodes contending for the channel. Total ordering indeed assigns a unique backoff to each node (thus avoiding collisions), but pays the penalty of choosing the random back-offs from a large range, ultimately translating to channel wastage. We envision breaking away from total ordering. Briefly, we force nodes to pick random numbers from a smaller range, so that groups of nodes pick the same random number (i.e., partial order). Now, the group that picks the smallest number - the winners - is advanced to a second round, where they again perform the same operation. We show that narrowing down the contenders through multiple rounds improves channel utilization. The intuition is that time for partially ordering all nodes plus totally ordering each small group is actually less than the time needed to totally order all nodes. We instantiate the idea with two well known CSMA protocols - WiFi and oCSMA. We resolve new challenges regarding multi domain contentions and group signaling. USRP and simulation based microbenchmarks are promising. We believe the idea of "hierarchical backoff" applies to other CSMA systems as well, exploration of which is left to future work.