Windowed backoff algorithms for WiFi: theory and performance under batched arrivals

摘要

Binary exponential backoff (BEB) is a decades -old algorithm for coordinating access to a shared channel. In modern networks, BEB plays a crucial role in WiFi and other wireless communication standards. Despite this track record, well-known theoretical results indicate that under bursty traffic, BEB yields poor makespan, and superior algorithms are possible. To date, the degree to which these findings impact performance in wireless networks has not been examined. Here, we investigate a challenging case for BEB: a single burst (batch) of packets that simultaneously contend for access to a wireless channel. Using Network Simulator 3, we incorporate into IEEE 802.11g several newer algorithms that have theoretically-superior makespan guarantees. Surprisingly, we discover that these newer algorithms underperform BEB. Investigating further, we identify as the culprit a common abstraction regarding the cost of collisions. Our experimental results are complemented by analytical arguments that the number of collisions-and not solely makespan-is an important metric to optimize. We propose a new theoretical model that accounts for the cost of collisions, and derive new asymptotic bounds on the makespan for BEB and the newer backoff algorithms that align with our experimental findings. Finally, we argue that these findings have implications for the design of backoff algorithms in wireless networks.