4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks

Research Article

Reverse Engineering MAC

  • @INPROCEEDINGS{10.1109/WIOPT.2006.1666466,
        author={Ao Tang and Jang-Won Lee  and Jianwei Huang and Mung Chiang and  A. Robert  Calderbank},
        title={Reverse Engineering MAC},
        proceedings={4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks},
        keywords={Wireless network Ad hoc network Medium access control Mathematical programming/optimization Network utility maximization Game theory Network control by pricing Reverse engineering.},
  • Ao Tang
    Jang-Won Lee
    Jianwei Huang
    Mung Chiang
    A. Robert Calderbank
    Year: 2006
    Reverse Engineering MAC
    DOI: 10.1109/WIOPT.2006.1666466
Ao Tang1,*, Jang-Won Lee 2,3,4,*, Jianwei Huang5,*, Mung Chiang5,*, A. Robert Calderbank5,*
  • 1: Department of Electrical Engineering, Caltech, Pasadena, CA 91125, USA
  • 2: CITY - Center for Information Technology of Yonsei University, Department
  • 3: of Electrical and Electronic Engineering, Yonsei University, 134 Shinchondong,
  • 4: Seodaemun-gu, Seoul, Korea 120-749
  • 5: Department of Electrical, Engineering, Princeton University, Princeton, NJ 08544, USA
*Contact email: aotang@caltech.edu, jangwon@yonsei.ac.kr, jianweih@princeton.edu, chiangm@princeton.edu, calderbk@princeton.edu


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.