On stability and maximum throughput of exponential backoff mechanisms with two users

ABSTRACT

The Binary Exponential Backoff (BEB) mechanism plays a key role in determining stability and efficiency of popular MAC protocols, such as IEEE 802.3 and IEEE 802.11. Unfortunately, the maximum throughput allowed by this protocol under different system parameters and user's multiplicity is largely unknown. In this paper we evaluate the capacity of a two-station system under Bernoulli arrivals, which is proved in the literature to be lower bounded by 0:3 under balanced arrivals. We refer to the general exponential backoff law b^-i and show that, when close to capacity, the system behaves in a simple manner, which allows us to assess capacity without resorting to the general Markov Chain approach. Our approach shows that the capacity of BEB under balanced load is equal to 0.6096. We also provide the stability region when arrivals are unbalanced in the two queues. Simulation results support our finding.

REFERENCES

• 1: H. Al-Ammal, L. A. Goldberg, and P. MacKenzie. An improved stability bound for binary exponential backoff. Theory Comput. Syst., 30(3):229--244, Dec. 2001.
• 2: D.J. Aldous, Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels, IEEE Transactions on Information Theory, v.33 n.2, p.219-223, March 1987 [doi>10.1109/TIT.1987.1057295]
• 3: G. Bianchi. Performance analysis of the ieee 802.11 distributed coordination function. Journ. on Select. Areas Commun., 18(3):535--547, March 2000.
• 4: Johan Håstad , Tom Leighton , Brian Rogoff, Analysis of Backoff Protocols for Mulitiple AccessChannels, SIAM Journal on Computing, v.25 n.4, p.740-774, Aug. 1996 [doi>10.1137/S0097539792233828]
• 5: Jonathan Goodman , Albert G. Greenberg , Neal Madras , Peter March, Stability of binary exponential backoff, Journal of the ACM (JACM), v.35 n.3, p.579-602, July 1988 [doi>10.1145/44483.44488]
• 6: Byung-Jae Kwak , Nah-Oak Song , Leonard E. Miller, Performance analysis of exponential backoff, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.343-355, April 2005 [doi>10.1109/TNET.2005.845533]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

General Terms:
Performance, Theory

Keywords:
Markov Chain, binary exponential backoff, throughput