STOC Conference 1985 Conference Paper
On the Stability of the Ethernet
- Jonathan Goodman
- Albert G. Greenberg
- Neal Madras
- Peter March
We consider the stochastic behavior of binary exponential backoff, a probabilistic algorithm for regulating transmissions on a multiple access channel. Ethernet, a local area network, is built upon this algorithm. The fundamental theoretical issue is stability: does the backlog of packets awaiting transmission remain bounded in time, provided the rates of new packet arrivals are small enough? We present a realistic model of n ≥ 2 stations communicating over the channel. Our main result is to establish that the algorithm is stable if the sum of the arrival rates is sufficiently small. We report detailed results on which rates lead to stability when n = 2 stations share the channel. In passing we derive several other results bearing on the efficiency of the conflict resolution process. Lastly, we report results from a simulation study, which, in particular, indicate alternative retransmission strategies can significantly improve performance.