On the Stability of Exponential Backoff

Published

August 1, 2003

Author(s)

N-O Song, B-J Kwak, Leonard E. Miller

Abstract

New analytical results are given for the stability and performance of the exponential backoff (EB) algorithm. Previous studies on the stability of the (binary) EB have produced contradictory results instead of a consensus: some proved instability, others showed stability under certain conditions. In these studies, simplified and/or modified models of the backoff algorithm were used to make analysis more tractable. In this paper, care is taken to use a model that reflects the actual behavior of backoff algorithms. We show that EB is stable under a throughput definition of stability; the throughput of the network converges to a non-zero constant as the offered load N goes to infinity. We also obtain the analytical expressions for the saturation throughput for a given number of nodes, N. The analysis considers the general case of EB with backoff factor r, where BEB is the special ease with r = 2. We show that r = 1/(1 - e-1) is the optimum backoff factor that maximizes the throughput. The accuracy of the analysis is checked against simulation results.

Citation

Journal of Research (NIST JRES) - of

Report Number

of

Volume

108 No. 4

NIST Pub Series

Journal of Research (NIST JRES)

Pub Type

NIST Pubs

Download Paper

Local Download

Keywords

exponential backoff algorithm, medium access control, stability

Citation

Song, N. , Kwak, B. and Miller, L. (2003), On the Stability of Exponential Backoff, Journal of Research (NIST JRES), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=50731 (Accessed January 22, 2025)