Cargando…

On the Stability of Exponential Backoff

Random access schemes for packet networks featuring distributed control require algorithms and protocols for resolving packet collisions that occur as the uncoordinated terminals contend for the channel. A widely used collision resolution protocol is the exponential backoff (EB). New analytical resu...

Descripción completa

Detalles Bibliográficos
Autores principales: Song, Nah-Oak, Kwak, Byung-Jae, Miller, Leonard E.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: [Gaithersburg, MD] : U.S. Dept. of Commerce, National Institute of Standards and Technology 2003
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4846233/
https://www.ncbi.nlm.nih.gov/pubmed/27413612
http://dx.doi.org/10.6028/jres.108.027
_version_ 1782429045829402624
author Song, Nah-Oak
Kwak, Byung-Jae
Miller, Leonard E.
author_facet Song, Nah-Oak
Kwak, Byung-Jae
Miller, Leonard E.
author_sort Song, Nah-Oak
collection PubMed
description Random access schemes for packet networks featuring distributed control require algorithms and protocols for resolving packet collisions that occur as the uncoordinated terminals contend for the channel. A widely used collision resolution protocol is the exponential backoff (EB). New analytical results for the stability of the (binary) EB are given. 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. 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 case 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.
format Online
Article
Text
id pubmed-4846233
institution National Center for Biotechnology Information
language English
publishDate 2003
publisher [Gaithersburg, MD] : U.S. Dept. of Commerce, National Institute of Standards and Technology
record_format MEDLINE/PubMed
spelling pubmed-48462332016-07-13 On the Stability of Exponential Backoff Song, Nah-Oak Kwak, Byung-Jae Miller, Leonard E. J Res Natl Inst Stand Technol Article Random access schemes for packet networks featuring distributed control require algorithms and protocols for resolving packet collisions that occur as the uncoordinated terminals contend for the channel. A widely used collision resolution protocol is the exponential backoff (EB). New analytical results for the stability of the (binary) EB are given. 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. 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 case 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. [Gaithersburg, MD] : U.S. Dept. of Commerce, National Institute of Standards and Technology 2003 2003-08-01 /pmc/articles/PMC4846233/ /pubmed/27413612 http://dx.doi.org/10.6028/jres.108.027 Text en https://creativecommons.org/publicdomain/zero/1.0/ The Journal of Research of the National Institute of Standards and Technology is a publication of the U.S. Government. The papers are in the public domain and are not subject to copyright in the United States. Articles from J Res may contain photographs or illustrations copyrighted by other commercial organizations or individuals that may not be used without obtaining prior approval from the holder of the copyright.
spellingShingle Article
Song, Nah-Oak
Kwak, Byung-Jae
Miller, Leonard E.
On the Stability of Exponential Backoff
title On the Stability of Exponential Backoff
title_full On the Stability of Exponential Backoff
title_fullStr On the Stability of Exponential Backoff
title_full_unstemmed On the Stability of Exponential Backoff
title_short On the Stability of Exponential Backoff
title_sort on the stability of exponential backoff
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4846233/
https://www.ncbi.nlm.nih.gov/pubmed/27413612
http://dx.doi.org/10.6028/jres.108.027
work_keys_str_mv AT songnahoak onthestabilityofexponentialbackoff
AT kwakbyungjae onthestabilityofexponentialbackoff
AT millerleonarde onthestabilityofexponentialbackoff