Opportunistic use of client repeaters to improve performance of WLANs

ABSTRACT

Currently deployed IEEE 802.11 WLANs (Wi-Fi networks) share access point (AP) bandwidth on a per-packet basis. However, various stations communicating with the AP often have different signal qualities, resulting in different transmission rates. This induces a phenomenon known as the rate anomaly problem, in which stations with lower signal quality transmit at lower rates and consume a significant majority of airtime, thereby dramatically reducing the throughput of stations transmitting at higher rates.

We propose SoftRepeater, a practical, deployable system in which stations cooperatively address the rate anomaly problem. Specifically, higher rateWi-Fi stations opportunistically transform themselves into repeaters for lower rate stations when transmitting data to/from the AP. The key challenge is to determine when it is beneficial to enable the repeater functionality. In view of this, we propose an initiation protocol that ensures that repeater functionality is enabled only when appropriate. Also, our system can run directly on top of today's 802.11 infrastructure networks. In addition, we describe a novel, zero-overhead network coding scheme that further alleviates undesirable symptoms of the rate anomaly problem. Using simulation and testbed implementation, we find that SoftRepeater can improve cumulative throughput by up to 200%.

REFERENCES

• 1: Atul Adya , Paramvir Bahl , Ranveer Chandra , Lili Qiu, Architecture and techniques for diagnosing faults in IEEE 802.11 infrastructure networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023724]
• 2: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 3: R. Ahlswede, N. Cai, R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, Jul. 2000.
• 4: "Atheros Wireless LAN," Atheros [Online]. Available: http://www. atheros.com/
• 5: Paramvir Bahl , Ranveer Chandra , Patrick P. C. Lee , Vishal Misra , Jitendra Padhye , Dan Rubenstein , Yan Yu, Opportunistic use of client repeaters to improve performance of WLANs, Proceedings of the 2008 ACM CoNEXT Conference, p.1-12, December 09-12, 2008, Madrid, Spain [doi>10.1145/1544012.1544041]
• 6: Sanjit Biswas , Robert Morris, ExOR: opportunistic multi-hop routing for wireless networks, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 7: Szymon Chachulski , Michael Jennings , Sachin Katti , Dina Katabi, Trading structure for randomness in wireless opportunistic routing, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 8: R. Chandra, V. Bahl, and P. Bahl, "MultiNet: Connecting to multiple IEEE 802.11 networks using a single wireless card," in Proc. INFOCOM, 2004, pp. 882-893.
• 9: Ranveer Chandra , Venkata N. Padmanabhan , Ming Zhang, WiFiProfiler: cooperative diagnosis in wireless LANs, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134702]
• 10: P. A. Chou, Y. Wu, and K. Jain, "Practical network coding," in Proc. Allerton Conf. Commun., Control and Comput., 2003, pp. 40-49.
• 11: "Aironet 1200 Series Access Point," Cisco [Online]. Available: http:// www.cisco.com/en/US/products/hw/wireless/ps430/index.html
• 12: "Air Pro Wireless Access Point," D-Link [Online]. Available: http:// www.dlink.com/
• 13: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 14: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 15: Richard Draves , Jitendra Padhye , Brian Zill, Comparison of routing metrics for static multi-hop wireless networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 16: Joseph Dunn , Michael Neufeld , Anmol Sheth , Dirk Grunwald , John Bennett, A practical cross-layer mechanism for fairness in 802.11 networks, Mobile Networks and Applications, v.11 n.1, p.37-45, February 2006 [doi>10.1007/s11036-005-4459-z]
• 17: Cheng Tien Ee , Ruzena Bajcsy, Congestion control and fairness for many-to-one routing in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031513]
• 18: L. Guo, X. Ding, H. Wang, Q. Li, S. Chen, and X. Zhang, "Cooperative relay service in a wireless LAN," IEE J. Sel. Areas Commun., vol. 25, no. 2, pp. 355-368, Feb. 2007.
• 19: M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda, "Performance anomaly of 802.11b," in Proc. INFOCOM, 2003, pp. 836-843.
• 20: Martin Heusse , Franck Rousseau , Romaric Guillier , Andrzej Duda, Idle sense: an optimal access method for high throughput and fairness in rate diverse wireless LANs, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 21: S. Jaggi, P. Sanders, P. A. Chou, M. Effros, K. J. S. Egner, and L. Tolhuizen, "Polynomial time algorithms for multicast network code construction," IEEE Trans. Inf. Theory, vol. 51, no. 6, pp. 1973-1982, Jun. 2003.
• 22: Srikanth Kandula , Kate Ching-Ju Lin , Tural Badirkhanli , Dina Katabi, FatVAP: aggregating AP backhaul capacity to maximize throughput, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.89-104, April 16-18, 2008, San Francisco, California
• 23: Sachin Katti , Hariharan Rahul , Wenjun Hu , Dina Katabi , Muriel Médard , Jon Crowcroft, XORs in the air: practical wireless network coding, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 24: F. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: Shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, pp. 237-252, 1998.
• 25: J. Le, J. C. S. Lui, and D. M. Chiu, "How many packets can we encode?--An analysis of practical wireless network coding," in Proc. IEEE INFOCOM, 2008, pp. 371-375.
• 26: S. Lee, S. Banerjee, and B. Bhattacharjee, "The case for a multi-hop wireless local area network," in Proc. INFOCOM, 2004, pp. 894-905.
• 27: P. Liu, Z. Tao, S. Narayanan, T. Korakis, and S. Panwar, "CoopMAC: A cooperative MAC protocol for wireless LANs," IEEE J. Sel. Areas Commun., vol. 25, no. 2, pp. 340-354, Feb. 2007.
• 28: S. Narayanan, P. Liu, and S. Panwar, "On the advantages of multi-hop extensions to the IEEE 802.11 infrastructure mode," in Proc. WCNC, 2005, pp. 132-138.
• 29: B. Sadeghi , V. Kanodia , A. Sabharwal , E. Knightly, Opportunistic media access for multirate ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570650]
• 30: "Qualnet Network Simulator," Scalable Network Technologies.
• 31: Anmol Sheth , Christian Doerr , Dirk Grunwald , Richard Han , Douglas Sicker, MOJO: a distributed physical layer anomaly detection system for 802.11 WLANs, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134701]
• 32: G. Tan and J. Guttag, "Time-based fairness improves performance in multi-rate WLANs," 2004.
• 33: G. Tan and J. Guttag, "The 802.11 MAC protocol leads to inefficient equilibria," in Proc. INFOCOM, 2005, pp. 1-11.
• 34: TTCP, "The story of the TTCP program," [Online]. Available: http:// ftp.arl.mil/mike/ttcp.html
• 35: WiDeFi, Two radio repeaters, [Online]. Available: http://www.widefi. com/
• 36: Starsky H. Y. Wong , Hao Yang , Songwu Lu , Vaduvur Bharghavan, Robust rate adaptation for 802.11 wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161107]
• 37: Y. Wu, P. A. Chou, and S. Kung, "Information exchange in wireless networks with network coding and physical-layer broadcast," MSR-TR-2004-78, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Design studies

  E. Data
  E.4 CODING AND INFORMATION THEORY

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
IEEE 802.11, rate anomaly, wireless