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.
, Kwak, B.
and Miller, L.
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 December 3, 2023)