University of Illinois Urbana-Champaign

An Analysis of the Binary Exponential Backoff Algorithm in Distributed MAC Protocols

Hu, Chunyu; Kim, Hwangnam; Hou, Jennifer C.

Content Files
An Analysis of the Binary Exponential Backoff Algorithm in Distributed MAC Protocols.pdf

Permalink

https://hdl.handle.net/2142/11066

Description

Title
An Analysis of the Binary Exponential Backoff Algorithm in Distributed MAC Protocols
Author(s)
  • Hu, Chunyu
  • Kim, Hwangnam
  • Hou, Jennifer C.
Issue Date
2005-07
Keyword(s)
algorithms
Date of Ingest
2009-04-20T15:12:20Z
Abstract
In the paper, we perform an in-depth analytic study of the binary exponential algorithm (BEBA) that is widely used in distributed MAC protocols, for example, IEEE 802.11 DCF. We begin with a generalized framework of modeling BEBA. Then we identify a key difference between BEBA and the commonly-assumed p-persistent model: due to the characteristics of BEBA, the slot succeeding a busy period has a different contention rate from the other slots. This causes access to a slot to be non-uniform and dependent on whether or not the slot immediately follows a busy period. We propose a detailed model with the use of a Markov chain to faithfully describe the channel activities governed by BEBA. To reduce the computational complexity, we simplify the model to an approximate one, and conduct an extensive simulation study. The analytical results derived in the proposed model are compared against those obtained from two other representative models. It is demonstrated that the proposed model is an accurate characterization of the BEBA algorithm in a broader range of system configuration. We further investigate the impact of the stochastic property of the backoff time, r, on the performance. It is revealed that in certain circumstances it becomes an important factor that affects the performance. A case study shows that by shifting the distribution range of r merely by 1 slot, substantial degradation in the system throughput may result.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/11066
Copyright and License Information
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections

Research and Tech Reports - Computer Science PRIMARY