Analysis of backoff protocols for multiple access channels

ABSTRACT

In the paper, we analyze the stochastic behavior of backoff protocols for multiple access channels such as the Ethernet. In particular, we prove that binary exponential backoff is unstable if the arrival rate of new messages at each station is &lgr;/N for any number of stations N exceeding 1 and any overall arrival rate &lgr; exceeding .567 + 1/4N - 2. More importantly, we also prove that any superlinear polynomial backoff protocol (e.g., quadratic backoff) is stable for any set of arrival rates that sum to less than one, and any number of stations. The results significantly extend the previous work in the area, and provide the first examples of acknowledgement based protocols known to be stable for a nonnegligible overall arrival rate distributed over an arbitrarily large number of stations. The results also disprove a popular assumption that exponential backoff is the best choice among acknowledgement based protocols for systems with large overall arrival rates. Finally, we prove that any linear or sublinear backoff protocol is unstable if the arrival rate at each station is &lgr;/N for any fixed &lgr; and sufficiently large N.

REFERENCES

• 1: 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]
• 2: J Goodman , A G Greenberg , N Madras , P March, On the stability of the Ethernet, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.379-387, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22187]
• 3: B. Hajek and T. van Loon, "Decentralized dynamic control of ~ multiaccess broadcast channel," IEEE Trans. on Automatic Control, Vol. AC-27, No. 3, June 1982, pp. 559-569.
• 4: IEEE Trans. on Inform. Theory, Vol. IT-31, March 1985.
• 5: F.P. Kelley, "Stochastic models of computer communications systems," Journal of the Royal Statistical Society (B) Vol. 47. No. 1, 1985.
• 6: R. Ladner, personal communication, 1986.
• 7: 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]
• 8: Ronald L. Rivest, Network control by bayesian broadcast, IEEE Transactions on Information Theory, v.33 n.3, p.323-328, May 1, 1987 [doi>10.1109/TIT.1987.1057315]
• 9: 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
• 10: 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]
• 11: Stidham, "The last word on the L '- ,~W,' Operations Research.
• 12: Wojceich Szpankowski, Stability conditions for multidimensional queueing systems with computer applications, Operations Research, v.36 n.6, p.944-957, Nov./Dec. 1988 [doi>10.1287/opre.36.6.944]
• 13: Andrew S. Tanenbaum, Network Protocols, ACM Computing Surveys (CSUR), v.13 n.4, p.453-489, Dec. 1981 [doi>10.1145/356859.356864]
• 14: B. Tsybakov and V. Mikha/lov, "Ergodlcity of a slotted Aloha system," ProblEms of information Transmission, Vol. 15, No. 4, April 1980 (translated version).

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

  K. Computing Milieux
  K.1 THE COMPUTER INDUSTRY
      Subjects: Standards

General Terms:
Standardization, Theory, Verification