Reverse Engineering MAC

Ao Tang; Jang-Won Lee; Jianwei Huang; Mung Chiang; A. Robert  Calderbank

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

Research Article

Reverse Engineering MAC

Cite: BibTeX Plain Text

@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},
    publisher={IEEE},
    proceedings_a={WIOPT},
    year={2006},
    month={8},
    keywords={Wireless network Ad hoc network Medium access control Mathematical programming/optimization Network utility maximization Game theory Network control by pricing Reverse engineering.},
    doi={10.1109/WIOPT.2006.1666466}
}

Ao Tang
Jang-Won Lee
Jianwei Huang
Mung Chiang
A. Robert Calderbank
Year: 2006
Reverse Engineering MAC
WIOPT
IEEE
DOI: 10.1109/WIOPT.2006.1666466

Ao Tang¹^,*, Jang-Won Lee ^2,3,4^,*, Jianwei Huang⁵^,*, Mung Chiang⁵^,*, A. Robert Calderbank⁵^,*

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

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.

Keywords: Wireless network Ad hoc network Medium access control Mathematical programming/optimization Network utility maximization Game theory Network control by pricing Reverse engineering.

Published: 2006-08-07
Publisher: IEEE

: http://dx.doi.org/10.1109/WIOPT.2006.1666466