Compressing backoff in CSMA networks

Randomized backoff is a well-established approach for avoiding collisions in CSMA networks. Today's backoff operation, such as in WiFi, attempts to create a total ordering among all the nodes contending for the channel. Total ordering requires assigning a unique backoff to each node, which is achieved by having nodes choose their back-offs from a large range, ultimately leading to channel wastage. This paper observes that total ordering can be achieved more efficiently. We propose 'hierarchical backoff' in which nodes pick random numbers from a smaller range, resulting in groups of nodes picking the same number (i.e., partial order). Now, the group of nodes that picks the smallest number is advanced to a second round, where they again perform the same operation. This results in more efficient backoff because the time for partially ordering all nodes plus totally ordering each small groups is actually less than the time needed to totally order all nodes. Realizing the above intuition requires addressing new protocol challenges in group signaling, the feasibility of which is demonstrated on a USRP/GNUradio prototype. Large scale simulations also show consistent throughput gains by incorporating the proposed backoff approach into two CSMA protocols - WiFi and oCSMA. We also show that the proposed approach can be complementary to and even outperform existing backoff optimization schemes.