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.
(Publisher abstract provided.)
Downloads
Related Datasets
Similar Publications
- Men Do Matter: Ethnographic Insights on the Socially Supportive Role of the African American Uncle in the Lives of Inner-City African American Male Youth
- Spectroscopic Differentiation and Regioisomeric Indole Aldehydes: Synthetic Cannabinoids Precursors
- When the Management of Grief Becomes Everyday Life: The Aftermath of Murder