Reverse Engineering MAC
- 8 August 2006
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper reverse-engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. The minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of the best response strategy are established as a function of user density. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse engineering TCP and BGP, this paper completes the recent efforts in reverse engineering layers 2-4 protocols.Keywords
This publication has 15 references indexed in Scilit:
- Price-based rate control in random access networksIEEE/ACM Transactions on Networking, 2005
- Optimization flow control with estimation errorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Stability of multipacket slotted Aloha with selfish users and perfect informationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- The Mathematics of Internet Congestion ControlPublished by Springer Nature ,2004
- Fair end-to-end window-based congestion controlIEEE/ACM Transactions on Networking, 2000
- Performance analysis of the IEEE 802.11 distributed coordination functionIEEE Journal on Selected Areas in Communications, 2000
- Optimization flow control. I. Basic algorithm and convergenceIEEE/ACM Transactions on Networking, 1999
- S-modular games, with queueing applicationsQueueing Systems, 1995
- Manifolds, Tensor Analysis, and ApplicationsPublished by Springer Nature ,1988
- Equilibrium Points in Nonzero-Sum n-Person Submodular GamesSIAM Journal on Control and Optimization, 1979