What are good resource allocation schemes in wireless multi-hop networks, and especially how can we access wireless media without message passing? For this purpose, we seek to propose theory-driven algorithms and then apply the achievements to the commodity 802.11 hardware by bridging gaps between theory and practice.

Overview

Carrier Sense Multiple Access (CSMA) has been widely used as a medium access control (MAC) scheme in wireless networks mainly due to its simple and totally distributed operations. Recently, it has been reported in the community that even such simple CSMA-type algorithms can achieve optimality in terms of throughput and utility, by smartly controlling its operational parameters such as backoff and holding times.

multi hop networks

Publications

  • "Making 802.11 DCF Near-Optimal: Design, Implementation, and Evaluation," Jinsung Lee, Hojin Lee, Yung Yi, Song Chong, Bruno Nardelli, Edward W. Knightly, and Mung Chiang, to appear in IEEE/ACM Transactions on Networking, 2015 (the extended version of the IEEE SECON 2013 paper).
  • "A-DCF: Design and Implementation of Delay and Queue Length Based Wireless MAC," Hojin Lee, Sangwoo Moon, and Yung Yi, in Proc. IEEE Infocom, 2015.
  • "Distributed Learning for Utility Maximization over CSMA-based Wireless Multihop Networks," Hyeryung Jang, Se-Young Yun, Jinwoo Shin and Yung Yi, in Proc. IEEE Infocom, 2014.
  • "Provable Per-Link Delay-Optimal CSMA for General Wireless Network Topology," Dongmyung Lee, Donggyu Yun, Jinwoo Shin, Se-Young Yun and Yung Yi, in Proc. IEEE Infocom, 2014.
  • "CSMA over Time-varying Channels: Optimality, Uniqueness and Limited Backoff Rate," Se-Young Yun, Jinwoo Shin and Yung Yi, in Proc. ACM MobiHoc, 2013. Best Paper Award.
  • "CSMA using the Bethe Approximation for Utility Maximization," Se-Young Yun, Jinwoo Shin and Yung Yi, in Proc. IEEE ISIT, 2013.
  • "Making 802.11 DCF Near-Optimal: Design, Implementation, and Evaluation," Jinsung Lee, Hojin Lee, Yung Yi, Song Chong, Bruno Nardelli, and Mung Chiang, in Proc. IEEE SECON, 2013. Best Paper Award.
  • "Making 802.11 DCF Near-Optimal: Design, Implementation, and Evaluation," Jinsung Lee, Hojin Lee, Yung Yi, Song Chong, Bruno Nardelli, Edward W. Knightly, and Mung Chiang, Technical Report, 2013.
  • "Optimal CSMA: A Survey," Se-Young Yun, Yung Yi, Jinwoo Shin, and Do Young Eun, in Proc. IEEE ICCS, 2012.
  • "From Glauber Dynamics to Metropolis Algorithm: Smaller Delay in Optimal CSMA," Chul-ho Lee, Do Young Eun, Se-young Yun, Yung Yi, in Proc. IEEE ISIT, 2012.
  • "Improving TCP Performance Over Optimal CSMA in Wireless Multi-hop Networks," Jinsung Lee, Hyang-Won Lee, Yung Yi, and Song Chong, IEEE Communications Letters, vol. 16, no. 9, September 2012.
  • "Experimental Evaluation of Optimal CSMA," Bruno Nardelli, Jinsung Lee, Kangwook Lee, Yung Yi, Song Chong, Edward W. Knightly, and Mung Chiang, in Proc. IEEE Infocom, 2011.
  • "Resource Allocation over Network Dynamics without Timescale Separation," Alexandre Proutiere, Yung Yi, Tian Lan and Mung Chiang, in Proc. IEEE Infocom mini-conference, 2010.
  • "Towards utility-optimal random access without message passing," Jiaping Liu, Yung Yi, Alexandre Proutiere, Mung Chiang, and Vincent H. Poor, Wiley Wireless Communcations and Mobile Computing, vol.10, no.1, Janurary 2010.
  • "Implementing Utility-Optimal CSMA," Jinsung Lee, Junhee Lee, Yung Yi, Chong Song, Alexandre Proutiere, and Mung Chiang, in Proc. Allerton, 2009.
  • "Convergence and Tradeoff of Utility-Optimal CSMA," Jiaping Liu, Yung Yi, Alexandre Proutiere, Mung Chiang, and Vincent H. Poor, in Proc. Broadnets, 2009.
  • "Towards Optimal MAC without Message Passing in Wireless Networks," Yung Yi, Jinsung Lee, Song Chong, Mung Chiang, and Alexandre Proutiere, in Proc. CFI, 2009.
  • "Throughput of Random Access Without Message Passing," Alexandre Proutiere, Yung Yi and Mung Chiang, in Proc. CISS, 2008.
  • Software

    A-DCF

  • Implementation of A-DCF in Atheros ath9k device driver: download (adcf-driver-0.1.tar.bz2)
  •    A-DCF driver guide: download (A-DCF_driver_guide.pdf)
       A-DCF driver API document: download (A-DCF_driver_API_document.pdf)
  • Implementation of A-DCF in NS-3.14.1: download (adcf-simulator-0.1.tar.bz2)
  •    A-DCF simulator guide: download (A-DCF_simulator_guide.pdf)
       A-DCF simulator API document: download (A-DCF_simulator_API_document.pdf)

    O-DCF

  • Implementation of O-DCF in NS-3.14.1: download (O-DCF_v1.0.tar.gz)
  • First, install ns-3.14.1 (refer to http://www.nsnam.org).

    In ns-3.14.1 directory,

    $ ./tar -xvzf O-DCF_v1.0.tar.gz
    Then, you can find the O-DCF source files, odcf*.{cc, h}, in ns-3.14.1/src/wifi/model/ directory. Additionally, two sample scenarios, flow-in-the-middle.cc and fully-connected.cc, are extracted in ns-3.14.1/scratch/ directory.

    You can compile and run the sample scenarios in ns-3.14.1 directory as follows:

    $ ./waf --run flow-in-the-middle
    $ ./waf --run fully-connected
    Note that you should not type the file extension (i.e., ".cc").

    People

  • Students: Dongyu Yun, Hyeryung Jang, Sangwoo Moon
  • Faculties: Yung Yi, Jinwoo Shin, Song Chong
  • Industrial collaborators: Hojin Lee, Dongmyung Lee
  • International collaborators: Mung Chiang, Edward W. Knightly, Bruno Nardelli