Control procedures for slotted Aloha systems that achieve stability

ABSTRACT

A class of slotted ALOHA dynamic control strategies is considered. These strategies are simple to implement and can yield lossless and stable operation for arbitrarily large user populations with aggregate arrival rates below e-1 packets/slot. An ergodicity analysis is given that provides conditions on the system parameters, such that any specified set of control parameters that satisfies the given conditions is guaranteed to yield stable performance. The system state is modelled as a two-dimensional Markov chain that incorporates the backlog (the number of packets awaiting retransmission) and the estimate of the backlog. The geometrical concepts are illustrated by figures corresponding to an example case. Simulation results are presented that compare alternative control schemes.

REFERENCES

• 1: S. S. Lam and L. Kleinrock, "Packet switching in a multiaccess broadcast channel: Dynamic control procedures,'' IEEE Trans. Commun., vol. COM-23, pp. 891- 904, September 1975.
• 2: A. Segall, "Recursive estimation from discrete-time point processes," IEEE Trans. Inform. Theory, vol. IT- 22, no. 4, pp. 422-431, July 1976.
• 3: Mario Gerla , Leonard Kleinrock, Closed loop stability controls for s-aloha satellite communications, Proceedings of the fifth symposium on Data communications, p.2.10-2.19, September 27-29, 1977, Snowbird, Utah, United States [doi>10.1145/800103.803330]
• 4: N. B. Meisner, J. L. Segal, and M. Y. Tanigawa, "An adaptive retransmission technique for use in a slotted- ALOHA channel," IEEE Trans. Commun., vol. COM- 28, pp. 1776-1778, September 1980.
• 5: B. Hajek and T. van Loon, "Decentralized dynamic control of a multiaccess broadcast channel," IEEE Trans. Automat. Control, vol. AC-27, no. 3, pp. 559- 569, June 1982.
• 6: B. Hajek, "Hitting-time and occupation-time bounds implied by drift analysis with applications," Adv. Appl. Prob., vol. 14, pp. 502-525, September 1982.
• 7: L. P. Clare, "Delay analysis of stable slotted ALOHA systems," Proc. IEEE INFOCOM 86, Miami, Florida, April 1986.
• 8: A. B. Carleial and M. E. Hellman, "Bistable behavior of ALOHA-type systems," IEEE Trans. Commun., vol. COM-23, pp. 401-410, April 1975.
• 9: L. Kleinrock and S. S. Lam, "P;~cket switching in a multiaccess broadcast channel: Performance evaluation,'' IEEE Trans. Commun., vol. COM-23, pp. 410- 423, April 1975.
• 10: G. Fayolle, E. Celenbe, and J. Labetoulle, "The stability problem of broadcast packet switching computer networks," Acta In~ormatica, vol. 4, pp. 49-53, 1974.
• 11: M. Kaplan, "A sufficient condition for nonergodicity of a Markov chain," IEEE Trans. Inform. Theory, vol. IT-25, no. 4, pp. 470-471, July 1979.
• 12: W. A. Rosenkrantz and D. Towsley, "On the instability of the slotted ALOHA multiaccess algorithm," IEEE Trans. Automat. Control, vol. AC-28, pp. 994- 996, October 1983.
• 13: Guy Fayolle , Erol Gelenbe , Jacques Labetoulle, Stability and Optimal Control of the Packet Switching Broadcast Channel, Journal of the ACM (JACM), v.24 n.3, p.375-386, July 1977 [doi>10.1145/322017.322019]
• 14: A. G. Pakes, "Some conditions for ergodicity and recurrence of Markov chains," Opel'. Res., vol. 17, pp. 1059-1061, 1969.
• 15: S. C. A. Thomopoulos, "Decentralized estimation and control in random access communication networks: Stability and performance analysis," Proc. IEEE INPOCOM ~$$, Washington, D.C., pp. 246-254, March 1985.
• 16: S. C. A. Thomopoulos, "A certainty equivalence nonlinear separation control rule for random access channels: Delay analysis," Conference Record, IEEE GLOBECOM~8$, pp.5.2.1-5.2.5, Dec. 2-5, 1985.
• 17: S. C. A. Thomopoulos, "Decentralized control for random access channels: Stability analysis and performance evaluation," Proc. AOC'$5, Boston, pp. 580- 585, June 19-21, 1985.
• 18: R. L. Tweedie, "Criteria for classifying general Markov chains," Adv. Appl. Prob., vol. 8, pp. 737-771, 1976.
• 19: John Lamperti, "Criteria for the recurrence or transience of stochastic process. I," J. Math. Anal. and Appl., vol. 1, pp. 314-330, 1960.
• 20: J. F. C. Kingman, "The ergodic behaviour of random walks," Biometrica, vol. 48, no. 3 and 4, pp. 391-396, 1961.
• 21: V. A. Maly~ev, "Classification of two-dimensional positive random walks and almost linear semimartingales," $ovSet Math. Dokl., vol. lS, no. l, pp. 136-139, 1972.
• 22: Michael A. Crane , Donald L. Iglehart, Simulating Stable Stochastic Systems, II: Markov Chains, Journal of the ACM (JACM), v.21 n.1, p.114-123, Jan. 1974 [doi>10.1145/321796.321806]

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

          Nouns: ALOHA

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

General Terms:
Performance, Security, Standardization, Verification