Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235772] of Robert Calderbank

Papers Published

  1. Tang, A; Lee, J-W; Huang, J; Chiang, M; Calderbank, AR, Reverse engineering MAC, 2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2006 (2006) [doi]
    (last updated on 2018/11/18)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320