The cost of mitigating power law delay in random access networks
Publication in refereed journal

Times Cited
Altmetrics Information

Other information
AbstractExponential backoff (EB) is a widely adopted collision resolution mechanism in many popular random-access networks including Ethernet and wireless LAN (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 fundamentallyunsuitable 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. To understand and alleviate the issue, this paper systematically analyzes the tail delay distribution of general backoff functions, with EB being a special case. In particular, we establish a tradeoff between the tail decaying rate of medium access delay distribution and the stability of throughput. To be more specific, convergent delay moments are attainable only when the backoff functions g(k) grow slower than exponential functions, i.e., when g(k) o(r^k) for all r>1. On the other hand, non-zero asymptotic throughput is attainable only when backoff functions grow at least as fast as an exponential function, i.e., g(k)Ω(r^k) for some r>1. This implies that bounded delay moments and stable throughput cannot be achieved at the same time. For practical implementation, we show that polynomial backoff (PB), where g(k) is a polynomial that grows slower than exponential functions, obtains finite delay moments and good throughput performance at the same time within a practical range of user population. This makes PB a better alternative than EB for multimedia applications with stringent delay requirements. © 2013 IEEE.
All Author(s) ListBi S., Zhang Y.J.A.
Journal nameIEEE Transactions on Wireless Communications
Volume Number12
Issue Number9
PublisherInstitute of Electrical and Electronics Engineers
Place of PublicationUnited States
Pages4612 - 4626
LanguagesEnglish-United Kingdom
Keywordsbackoff algorithms, Medium access control, power law delay, wireless LAN (WLAN)

Last updated on 2021-16-01 at 00:42