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...
Autores principales: | , , |
---|---|
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 |