Reverse engineering MAC

Journal Article

This paper reverse engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that 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 protocol description, through a stochastic subgradient method in which link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of best response strategy are established as a function of user density. Convergence properties and connection with best response strategy are also proved for variants of stochastic-subgradient-based dynamics of game. Together with known results in reverse engineering TCP and BGP, this paper completes recent efforts in reverse engineering main protocols in layers 2-4. © 2006 IEEE.

Full Text

Duke Authors

Cited Authors

  • Tang, A; Lee, JW; Huang, J; Chiang, M; Calderbank, AR

Published Date

  • December 1, 2006

Published In

  • 2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Wiopt 2006

Digital Object Identifier (DOI)

  • 10.1109/WIOPT.2006.1666466

Citation Source

  • Scopus