article

A game-theoretic study of CSMA/CA under a backoff attack

Author:

Jerzy KonorskiAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 14, Issue 6

Pages 1167 - 1178

https://doi.org/10.1109/TNET.2006.886298

Published: 01 December 2006 Publication History

Abstract

CSMA/CA, the contention mechanism of the IEEE 802.11 DCF medium access protocol, has recently been found vulnerable to selfish backoff attacks consisting in nonstandard configuration of the constituent backoff scheme. Such attacks can greatly increase a selfish station's bandwidth share at the expense of honest stations applying a standard configuration. The paper investigates the distribution of bandwidth among anonymous network stations, some of which are selfish. A station's obtained bandwidth share is regarded as a payoff in a noncooperative CSMA/CA game. Regardless of the IEEE 802.11 parameter setting, the payoff function is found similar to a multiplayer Prisoners' Dilemma; moreover, the number (though not the identities) of selfish stations can be inferred by observation of successful transmission attempts. Further, a repeated CSMA/CA game is defined, where a station can toggle between standard and nonstandard backoff configurations with a view of maximizing a long-term utility. It is argued that a desirable station strategy should yield a fair, Pareto efficient, and subgame perfect Nash equilibrium. One such strategy, called CRISP, is described and evaluated.

References

[1]

{1} A. Akella, S. Seshan, R. Karp, S. Shenker, and C. Papadimitriou, "Selfish behavior and stability of the internet: a game-theoretic analysis of TCP," in Proc. ACM SIGCOMM'02, Pittsburgh, PA, Aug. 2002, pp. 117-130.

[2]

{2} E. Altman, R. El Azouzi, and T. Jimenez, "Slotted Aloha as a game with partial information," Comput. Netw., vol. 45, pp. 701-713, 2004.

[3]

{3} R. Axelrod, The Evolution of Cooperation. New York: Basic Books, 1984.

[4]

{4} J. Bellardo and S. Savage, "802.11 denial-of-service attacks: real vulnerabilities and practical solutions," in Proc. USENIX Security Symp., Washington DC, Aug. 2003, pp. 15-28.

[5]

{5} N. Ben Salem, L. Buttyan, J.-P. Hubaux, and M. Jakobsson, "A charging and rewarding scheme for packet forwarding in multi-hop cellular networks," in Proc. ACM Symp. Mobile Ad Hoc Networking and Computing (MobiHoc 2003), Annapolis, MD, Jun. 2003, pp. 13-24.

[6]

{6} G. Bianchi, "Performance analysis of the IEEE 802.11 distributed coordination function," IEEE J. Sel. Areas Commun., vol. 18, no. 3, pp. 535-547, Mar. 2000.

[7]

{7} M. Cagalj, S. Ganeriwal, I. Aad, and J.-P. Hubaux, "On selfish behavior in CSMA/CA networks," in Proc. IEEE INFOCOM 2005, Miami, FL, Mar. 2005, pp. 2513-1514.

[8]

{8} J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, "A BGP-based mechanism for lowest-cost routing," in Proc. 21st Symp. Principles of Distributed Computing, Monterey, CA, Jul. 2002, pp. 173-182.

[9]

{9} W. Feller, An Introduction to Probability Theory and its Applications . New York: Wiley, 1966.

[10]

{10} D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA: MIT Press, 1991.

[11]

{11} B. Grofman and J. Pool, "How to make cooperation the optimizing strategy in a two-person game," J. Math. Sociology, vol. 5, pp. 173-186, 1977.

[12]

{12} J.-P. Hubaux, L. Buttyan, and S. Capkun, "The quest for security in mobile ad hoc networks," in Proc. ACM Symp. Mobile Ad Hoc Networking and Computing (MobiHoc 2001), Long Beach, CA, Oct. 2001.

[13]

{13} IEEE Standard for Information Technology--LAN/MAN--Specific Requirements--Part II: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, ISO/IEC 8802-11:1999.

[14]

{14} E. Kalai and E. Lehrer, "Rational learning leads to Nash equilibrium," Econometrica, vol. 61, pp. 1019-1045, 1993.

[15]

{15} V. Knoblauch, "Computable strategies for repeated Prisoners' Dilemma," Games and Economic Behavior, vol. 7, pp. 381-389, 1994.

[16]

{16} C. E. Koksal, H. Kassab, and H. Balakrishnan, "An analysis of short-term fairness in wireless media access protocols," in Proc. ACM SIGMETRICS , Santa Clara, CA, Jun. 2000, pp. 118-119.

[17]

{17} J. Konorski, "Multiple access in ad hoc wireless LANs with noncooperative stations," in Proc. Networking 2002, vol. LNCS 2345, pp. 1141-1146.

[18]

{18} J. Konorski, "Solvability of a Markovian model of an IEEE 802.11 LAN under a backoff attack," in Proc. IEEE MASCOTS 2005, Atlanta, GA, Sep. 2005, pp. 491-498.

[19]

{19} Y. A. Korilis, A. A. Lazar, and A. Orda, "Architecting noncooperative networks," IEEE J. Sel. Areas Commun., vol. 13, no. 7, pp. 1241-1251, Jul. 1995.

[20]

{20} P. Kyasanur and N. H. Vaidya, "Detection and handling of MAC layer misbehavior in wireless networks," in Proc. Int. Conf. Dependable Systems and Networks, San Francisco, CA, Jun. 2003, pp. 173-182.

[21]

{21} A. B. MacKenzie and S. B. Wicker, "Game theory and the design of self-configuring, adaptive wireless networks," IEEE Commun. Mag., vol. 39, no. 11, pp. 126-131, Nov. 2001.

[22]

{22} A. B. MacKenzie and S. B. Wicker, "Selfish users in ALOHA: a game-theoretic approach," in Proc. Vehicular Technology Conf. Fall 2001, Atlantic City, NJ, Oct. 2001, pp. 1354-1357.

[23]

{23} P. Michiardi and R. Molva, "A game theoretical approach to evaluate cooperation enforcement mechanisms in mobile ad hoc networks," in Proc. WiOpt'03, Sophia-Antipolis, France, Mar. 2003.

[24]

{24} P. Obreiter, B. Koenig-Ries, and M. Klein, "Stimulating cooperative behavior of autonomous devices--an analysis of requirements and existing approaches," in Proc. 2nd Int. Workshop Wireless Information Systems, Angers, France, Apr. 2003.

[25]

{25} A. Orda, R. Rom Rand, and N. Shimkin, "Competitive routing in multiuser communication networks," IEEE/ACM Trans. Networking, vol. 1, no. 5, pp. 510-521, Oct. 1993.

[26]

{26} O. Queseth, "Cooperative and selfish behaviour in unlicensed spectrum using the CSMA/CA protocol," in Proc. Nordic Radio Symp., Oulu, Finland, Aug. 2004.

[27]

{27} V. Ramaiyan, A. Kumar, and E. Altman, "Fixed point analysis of single cell IEEE 802.11e WLANs: uniqueness, multistability and throughput differentiation," in Proc. ACM SIGMETRICS'05, Banff, Canada, Jun. 2005, pp. 109-120.

[28]

{28} M. Raya, J.-P. Hubaux, and I. Aad, "DOMINO: a system to detect greedy behavior in IEEE 802.11 hotspots," in Proc. MobiSys 2004, Boston, MA, Jun. 2004, pp. 84-97.

[29]

{29} A. Rubinstein, "Finite automata play the repeated Prisoners' Dilemma," J. Econ. Theory, vol. 39, pp. 83-96, 1986.

[30]

{30} B. A. Sanders, "An incentive compatible flowcontrol algorithm for rate allocation in computer networks," IEEE Trans. Comput., vol. 37, no. 9, pp. 1067-1072, Sep. 1988.

[31]

{31} S. Shenker, "Making greedwork in networks: a game-theoretic analysis of switch service disciplines," IEEE/ACM Trans. Netw., vol. 3, no. 6, pp. 819-831, Dec. 1995.

[32]

{32} H. W. Shin and I. J. Wassell, "Application of game theory for distributed dynamic channel allocation," in Proc. IEEE 55th Vehicular Technology Conf., Spring 2002, Birmingham, AL, May 2002, pp. 404-408.

[33]

{33} S. Smale, "The Prisoners' Dilemma and dynamical systems associated to noncooperative games," Econometrica, vol. 48, pp. 1617-1634, 1980.

[34]

{34} V. Srinivasan, P. Nuggehalli, C. F. Chiasserini, and R. R. Rao, "Cooperation in wireless ad hoc networks," in Proc. IEEE INFOCOM 2003, San Francisco, CA, Mar./Apr. 2003, pp. 808-817.

[35]

{35} W. Stanford, "Symmetric paths and evolution to equilibrium in the discounted Prisoners' Dilemma," Econ. Lett., vol. 31, pp. 139-143, 1989.

[36]

{36} A. Urpi, M. Bonuccelli, and S. Giordano, "Modelling cooperation in mobile ad hoc networks: a formal description of selfishness," in Proc. WiOpt'03, Sophia-Antipolis, France, Mar. 2003.

[37]

{37} H. Wu, Y. Peng, K. Long, S. Cheng, and J. Ma, "Performance of reliable transport protocol over IEEE 802.11 wireless LAN: analysis and enhancement," in Proc. IEEE INFOCOM 2002, New York, Jun. 2002, pp. 599-607.

[38]

{38} X. Yao, "Evolutionary stability in the n-person iterated Prisoners' Dilemma," BioSystems, vol. 39, pp. 189-197, 1996.

[39]

{39} E. Ziouva and T. Antonakopoulos, "CSMA/CA performance under high traffic conditions: throughput and delay analysis," Comput. Commun., vol. 25, pp. 313-321, 2002.

Cited By

Khan TSingh K(2023)RTM: Realistic Weight-Based Reliable Trust Model for Large Scale WSNsWireless Personal Communications: An International Journal10.1007/s11277-022-10165-7129:2(953-991)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1007/s11277-022-10165-7
Zhang YLazos L(2020)Misbehavior in Multi-Channel MAC ProtocolsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2018.281917017:4(760-774)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1109/TDSC.2018.2819170
Chakraborty SSanyal DChattopadhyay S(2019)Performance of Random Access Games over an IEEE 802.11ac Testbed2019 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS)10.1109/ANTS47819.2019.9118092(1-4)Online publication date: 16-Dec-2019
https://dl.acm.org/doi/10.1109/ANTS47819.2019.9118092
Show More Cited By

Index Terms

A game-theoretic study of CSMA/CA under a backoff attack
1. General and reference
  1. Cross-computing tools and techniques
    1. Design
  2. Document types
    1. Computing standards, RFCs and guidelines
2. Networks
  1. Network properties
    1. Network structure

Recommendations

Studying misbehavior in CSMA/CA Wireless LANs
PM2HW2N '08: Proceedings of the 3nd ACM workshop on Performance monitoring and measurement of heterogeneous wireless and wired networks

Security is a fundamental aspect for achieving high availability and reliability in wireless networks. Wireless medium access control (MAC) protocols use distributed contention resolution mechanisms for sharing the wireless medium. Wireless nodes decide ...
Generalized CSMA/CA for OFDMA systems: protocol design, throughput analysis, and implementation issues

In this paper, we present a multi-channel carrier sense multiple access with collision avoidance (CSMA/CA) protocol for orthogonal frequency division multiple access (OFDMA) systems. The CSMA/CA system in conventional single-channel operation has the ...
CSMA/CA Bottleneck Remediation in Saturation Mode with New Backoff Strategy
MACOM 2013: Proceedings of the 6th International Workshop on Multiple Access Communcations - Volume 8310

Many modern wireless networks integrate carrier sense multiple access/collision avoidance (CSMA/CA) with exponential backoff as medium access control (MAC) technique. In order to decrease the MAC overhead and the collision probability, we propose in ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 14, Issue 6

December 2006

247 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2006

Published in TON Volume 14, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
1,075
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Khan TSingh K(2023)RTM: Realistic Weight-Based Reliable Trust Model for Large Scale WSNsWireless Personal Communications: An International Journal10.1007/s11277-022-10165-7129:2(953-991)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1007/s11277-022-10165-7
Zhang YLazos L(2020)Misbehavior in Multi-Channel MAC ProtocolsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2018.281917017:4(760-774)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1109/TDSC.2018.2819170
Chakraborty SSanyal DChattopadhyay S(2019)Performance of Random Access Games over an IEEE 802.11ac Testbed2019 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS)10.1109/ANTS47819.2019.9118092(1-4)Online publication date: 16-Dec-2019
https://dl.acm.org/doi/10.1109/ANTS47819.2019.9118092
Wu HWang Z(2018)Multi-source fusion-based security detection method for heterogeneous networksComputers and Security10.1016/j.cose.2018.01.00374:C(55-70)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1016/j.cose.2018.01.003
Bayat-Yeganeh HShah-Mansouri VKebriaei H(2018)A multi-state Q-learning based CSMA MAC protocol for wireless networksWireless Networks10.1007/s11276-016-1402-024:4(1251-1264)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s11276-016-1402-0
Seijo Simó MLópez López GMoreno Novella J(2017)Cybersecurity Vulnerability Analysis of the PLC PRIME StandardSecurity and Communication Networks10.1155/2017/73696842017Online publication date: 5-Jul-2017
https://dl.acm.org/doi/10.1155/2017/7369684
Al-Terri DOtrok HBarada HAl-Qutayri MAl Hammadi Y(2017)Cooperative based tit-for-tat strategies to retaliate against greedy behavior in VANETsComputer Communications10.1016/j.comcom.2017.02.008104:C(108-118)Online publication date: 15-May-2017
https://dl.acm.org/doi/10.1016/j.comcom.2017.02.008
Banchs AOrtin JGarcia-Saavedra ALeith DSerrano P(2016)Thwarting selfish behavior in 802.11 WLANsIEEE/ACM Transactions on Networking10.1109/TNET.2014.236953524:1(492-505)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TNET.2014.2369535
AlSkaif TGuerrero Zapata MBellalta B(2015)Game theory for energy efficiency in Wireless Sensor NetworksJournal of Network and Computer Applications10.1016/j.jnca.2015.03.01154:C(33-61)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.jnca.2015.03.011
Ghazvini MMovahhedinia NJamshidi K(2015)GCWWireless Personal Communications: An International Journal10.1007/s11277-015-2441-z83:2(1101-1130)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s11277-015-2441-z
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents