An analysis of generalized slotted-Aloha protocols

ABSTRACT

Aloha and its slotted variation are commonly deployed Medium Access Control (MAC) protocols in environments where multiple transmitting devices compete for a medium, yet may have difficulty sensing each other's presence (the "hidden terminal problem"). Competing 802.11 gateways, as well as most modern digital cellular systems, like GSM, are examples. This paper models and evaluates the throughput that can be achieved in a system where nodes compete for bandwidth using a generalized version of slotted-Aloha protocols. The protocol is implemented as a two-state system, where the probability that a node transmits in a given slot depends on whether the node's prior transmission attempt was successful. Using Markov Models, we evaluate the channel utilization and fairness of this class of protocols for a variety of node objectives, including maximizing aggregate throughput of the channel, each node selfishly maximizing its own throughput, and attacker nodes attempting to jam the channel. If all nodes are selfish and strategically attempt to maximize their own throughput, a situation similar to the traditional Prisoner's Dilemma arises. Our results reveal that under heavy loads, a greedy strategy reduces the utilization, and that attackers cannot do much better than attacking during randomly selected slots.

REFERENCES

• 1: Ethernet, a Local Area Network: Data Link Layer and Physical Layer Specifications (Version 1.0). Digital Equipment Corporation, Intel, Xerox.
• 2: 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]
• 3: L. Kleinrock and F. A. Tobagi, "Packet switching in radio channels: Part I-carrier sense multiple-access modes and their throughput-delay characteristics," IEEE Trans. Commun., vol. COM-23, no. 12, pp. 1400-1416, 1975.
• 4: Norman Abramson, THE ALOHA SYSTEM: another alternative for computer communications, Proceedings of the November 17-19, 1970, fall joint computer conference, November 17-19, 1970, Houston, Texas [doi>10.1145/1478462.1478502]
• 5: Lawrence G. Roberts, ALOHA packet system with and without slots and capture, ACM SIGCOMM Computer Communication Review, v.5 n.2, p.28-42, April 1975 [doi>10.1145/1024916.1024920]
• 6: M. J. Osborne and A. Rubinstein, A Course in Game Theory. Cambridge, MA: The MIT Press, 1994.
• 7: Raphael Rom , Moshe Sidi, Multiple access protocols: performance and analysis, Springer-Verlag New York, Inc., New York, NY, 1990
• 8: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 9: Y. Yu, X. Cai, and G. B. Giannakis, "On the instability of slotted Aloha with capture," presented at the IEEE WCNC, Atlanta, GA, 2004.
• 10: L. Kleinrock and S. Lam, "Packet switching in a multi access broadcast channel: Performance evaluation," IEEE Trans. Commun., vol. COM-23, pp. 410-422, 1975.
• 11: A. Carleial and M. Hellman, "Bistable behavior of Aloha-type systems," IEEE Trans. Commun., vol. COM-23, pp. 401-410, 1975.
• 12: S. Ghez, S. Verd, and S. Schwartz, "Stability properties of slotted-Aloha with multipacket reception capability," IEEE Trans. Autom. Contr., vol. AC-33, no. 7, pp. 640-649, Jul. 1988.
• 13: 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]
• 14: S. Lam and L. Kleinrock, "Packet switching in a multi access broadcast channel: Dynamic control procedures," IEEE Trans. Commun., vol. COM-23, pp. 891-904, 1975.
• 15: Jerzy Konorski, A game-theoretic study of CSMA/CA under a backoff attack, IEEE/ACM Transactions on Networking (TON), v.14 n.6, p.1167-1178, December 2006 [doi>10.1109/TNET.2006.886298]
• 16: Pradeep Kyasanur , Nitin H. Vaidya, Selfish MAC Layer Misbehavior in Wireless Networks, IEEE Transactions on Mobile Computing, v.4 n.5, p.502-516, September 2005 [doi>10.1109/TMC.2005.71]
• 17: A. Mas-Colell, M. D. Whinston, and J. R. Green, Microeconomic Theory. New York: Oxford Univ. Press, 1995.
• 18: G. Tan and J. Guttag, "The 802.11 MAC protocol leads to inefficient equilibria," in Proc. IEEE INFOCOM, 2005, pp. 1-11.
• 19: M. Cagalj, S. Ganeriwal, I. Aad, and J.-P. Hubaux, "On selfish behavior in CSMA/CA networks," in Proc. IEEE INFOCOM, 2005, pp. 2513-2524.
• 20: Z. Fang and B. Bensaou, "Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad hoc networks," in Proc. IEEE INFOCOM, 2004, pp. 1284-1295.
• 21: V. Srinivasan, P. Nuggehalli, C. Chiasserini, and R. Rao, "Cooperation in wireless ad hoc networks," in Proc. IEEE INFOCOM, 2003, pp. 808-817.
• 22: R. T. B. Ma, V. Misra, and D. Rubenstein, "Cooperative and non-co-operative models for slotted-Aloha type MAC protocols," presented at the 7th Workshop on Mathematical Performance Modeling and Analysis, Banff, Canada, 2005.
• 23: Richard T. B. Ma , Vishal Misra , Dan Rubenstein, Modeling and Analysis of Generalized Slotted-Aloha MAC Protocols in Cooperative, Competitive and Adversarial Environments, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.62, July 04-07, 2006 [doi>10.1109/ICDCS.2006.56]
• 24: A. MacKenzie and S. Wicker, "Selfish users in Aloha: A game theoretic approach," in Proc. Fall 2001 IEEE Vehicular Technology Conf., 2001, pp. 1354-1357.
• 25: A. MacKenzie and S. Wicker, "Stability of multipacket slotted Aloha with selfish users and perfect information," in Proc. IEEE INFOCOM, 2003, pp. 1583-1590.
• 26: Y. Jin and G. Kesidis, "Equilibria of a noncooperative game for heterogeneous users of an Aloha network," IEEE Commun. Lett., vol. 6, no. 7, pp. 282-284, Jul. 2002.
• 27: Eitan Altman , Rachid El Azouzi , Tania Jiménez, Slotted Aloha as a game with partial information, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.45 n.6, p.701-713, 21 August 2004 [doi>10.1016/j.comnet.2004.02.013]
• 28: Can Emre Koksal , Hisham Kassab , Hari Balakrishnan, An analysis of short-term fairness in wireless media access protocols (poster session), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.118-119, June 18-21, 2000, Santa Clara, California, United States
• 29: R. T. Ma, D. Rubenstein, and V. Misra, "An analysis of generalized slotted-Aloha protocols," Dept. Electr. Eng., Columbia Univ., New York, Tech. Rep., Oct. 2007 [Online]. Available: http://www.dnawsl.cs.columbia.edu/pubsdb/citation/paperfile/156/TR.pdf
• 30: Yannis A. Korilis , Aurel A. Lazar , Ariel Orda, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.161-173, Feb. 1997 [doi>10.1109/90.554730]
• 31: A. A. Economides and J. A. Silvester, "Priority load sharing: An approach using Stackelberg games," presented at the 28th Annu. Allerton Conf. Communication, Control, and Computing, Monticello, IL, 1990.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
MAC protocols, Markovian decision, Prisoner's Dilemma, Stackelberg game, short-term fairness, slotted-Aloha