Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

On the Stability of Exponential Backoff

Published

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

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 June 15, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created August 1, 2003, Updated February 19, 2017