On the Optimality and the Stability of Backoff Protocols

摘要

In this paper, we analyze backoff protocols, such as 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 with N stations is (1-(1/N))~(1/(N-1)) and the optimal average service time for any station is ES = N/(1-(1/N))~(1/(N-1)) or about Ne for large N. The reasons of the instability of the BEB protocol (for a big enough input rate) is explained.