The Cost of Mitigating Power Law Delay in Random Access Networks
Exponential Backoff (EB) is a widely adopted collision resolution mechanism in many popular random-access networks including Ethernet and WLAN. The prominence of EB is primarily attributed to its asymptotic throughput stability, which ensures a non-zero throughput even when the number of users in the network goes to infinity. Recent studies, however, show that EB is fundamentally unsuitable for applications that are sensitive to large delay and delay jitters, as it induces divergent second- and higher-order moments of medium access delay. Essentially, the medium access delay follows a power law distribution, a subclass of heavy-tailed distribution.