Backing out of linear backoff in wireless networks
Mahanth Gowda, Nirupam Roy, Romit Roy Choudhury, Srihari Nelakuditi · 2014
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.