On the stability of the Ethernet

ABSTRACT

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.

REFERENCES

• 1: Capetanakis, J.I., "Tree algorithms for packet broadcast channels", IEER Transactions on Information Theory, IT- 25, 5 (Sept. 1979), 505-515.
• 2: Gallager, R.G., "Conflict resolution in random access broadcast networks", Proceedings of the AFOSR Workshop in Communication Theoey and Applications, Provincetown, Mass. (Sept. 1978), 74-76.
• 3: Greenberg, A.G., Flajolet, P., and Ladner, R.F., "Improved algorithms for estimating the multiplicities of conflicts and for resolving conflicts in multiple access channels", (Sept. 1984) preprint.
• 4: Hajek, B. and van Loon, T. Decentralized dynamic control of a multiaccess broadcast channel", IEEE Transactions on Aaromatic Control, AC-27, 3 (June 1982), 559-569.
• 5: Hayes, J.F., "An adaptive technique for local distribution", IEEE Transactions on Communications, COM-29, 6 (June 1978), 1178-1186.
• 6: Karlin, S. and Taylor, H.M., A First Course in Stochastic Processes, second edition, Academic Press, New York, 1975.
• 7: Kelly, F.P., "Stochastic models of computer communication systems, preprint (September 1984).
• 8: Lam, S., "A carrier sense multiple access protocol for local networks", Computer Networks, 4 (Feb. 1980), 21- 32.
• 9: Mathys, P., "A comparsion of q-ary tree algorthims for collision resolution", Memo of AFIP, ETH Zurich, Switzerland (Nov. 1980).
• 10: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 11: Mikhailov, V.A., "A random access algorithm for a broadcast channel, (abstract in Russian), in 5-th Int. Symposium on Information Theory, 3, Tbilbi, Moscow (1979), 83-86.
• 12: Walter A. Rosenkrantz, Some Theorems on the Instability of the Exponential Back-Off Protocol, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.199-205, December 19-21, 1984
• 13: John F. Shoch , Jon A. Hupp, Measured performance of an Ethernet local network, Communications of the ACM, v.23 n.12, p.711-721, Dec. 1980 [doi>10.1145/359038.359044]
• 14: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 15: Tsybakov, B.S. and Mikhailov, V.A., "Free synchronous packet access in a broadcast channel with feedback", Probtems of Information Transmission, 14, 4 (April 1979), 259-280, (translated from Russian original in Problemy Peredachi Informatsii, 14, 4 (Oct.-Dec 1978), 32-59).
• 16: Tsybakov, B.S. and Mikhailov, V.A., "Ergodicity of a slotted Aloha system", Problems of Information Transmission, 15, 4 (April 1980), (translated from Russian original in Problemy Peredachi Informatsii, 15, 4 (oct.-Dec. 1979) 72.87).
• 17: Tsybakov, B.S. and Vvendenskaya, N.D., "Random multiple-access stack algorithm", Problems of Information Transmission, 16, 3 (Jan. 1982), 230-243, (translated from Russian original in Problemy Peredachi Informatsii 16, 3 (July-Sept. 1980) 80-94.

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: Ethernet

General Terms:
Algorithms, Theory, Verification