Reverse Engineering MAC
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 the main protocols in layers 2-4.
Additional Information
© 2007 IEEE. This work was supported by Yonsei University research fund of 2005 and NSF Grants CCF-0440443, CNS-0417607, CCF-0448012, and CNS-0427677.Attached Files
Published - 01666466.pdf
Files
Name | Size | Download all |
---|---|---|
md5:b267efddacd5cc501c01e245ce8e9b1d
|
290.2 kB | Preview Download |
Additional details
- Eprint ID
- 77029
- Resolver ID
- CaltechAUTHORS:20170427-154257955
- Yonsei University
- CCF-0440443
- NSF
- CNS-0417607
- NSF
- CCF-0448012
- NSF
- CNS-0427677
- NSF
- Created
-
2017-04-27Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field