Performance analysis of general backoff protocols
Abstract
In this paper, we analyze backoff protocols, such as the one used in Ethernet. We examine a general backoff function (GBF) rather than just the binary exponential backoff (BEB) used by Ethernet. Under some mild assumptions we find stability and optimality conditions for a wide class of backoff protocols with GBF. In particular, it is proved that the maximal throughput rate over the class of backoff protocols is a fixed function of the number of stations (N) and the optimal average service time is about Ne for large N. The reasons of the instability of the BEB protocol (for a big enough input rate) are explained. Additionally, the paper introduces novel procedure for analyzing bounded backoff protocols, which is useful for creating new protocols or improving existing, as no protocol can use unbounded counters.
Keywords
Ethernet, backoff protocol, contention resolution, stability, optimality, queuing theory
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
A. Gurtov, "Performance analysis of general backoff protocols," in Journal of Communications Software and Systems, vol. 4, no. 1, pp. 13-21, March 2008, doi: 10.24138/jcomss.v4i1.233
@article{gurtov2008performanceanalysis,
author = {Andrei Gurtov},
title = {Performance analysis of general backoff protocols},
journal = {Journal of Communications Software and Systems},
month = {3},
year = {2008},
volume = {4},
number = {1},
pages = {13--21},
doi = {10.24138/jcomss.v4i1.233},
url = {https://doi.org/10.24138/jcomss.v4i1.233}
}