Publications [#235772] of Robert Calderbank

Journal articles or Book chapters 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] .

    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.