End-to-end performance and fairness in multihop wireless backhaul networks

ABSTRACT

Wireless IEEE 802.11 networks in residences, small businesses, and public "hot spots" typically encounter the wireline access link (DSL, cable modem, T1, etc.) as the slowest and most expensive part of the end-to-end path. Consequently, network architectures have been proposed that employ multiple wireless hops in route to and from the wired Internet. Unfortunately, use of current media access and transport protocols for such systems can result in severe unfairness and even starvation for flows that are an increasing number of hops away from a wired Internet entry point. Our objective is to study fairness and end-to-end performance in multihop wireless backhaul networks via the following methodology. First, we develop a formal reference model that characterizes objectives such as removing spatial bias (i.e., providing performance that is independent of the number of wireless hops to a wire) and maximizing spatial reuse. Second, we perform an extensive set of simulation experiments to quantify the impact of the key performance factors towards achieving these goals. For example, we study the roles of the MAC protocol, end-to-end congestion control, antenna technology, and traffic types. Next, we develop and study a distributed layer 2 fairness algorithm which targets to achieve the fairness of the reference model without modification to TCP. Finally, we study the critical relationship between fairness and aggregate throughput and in particular study the fairness-constrained system capacity of multihop wireless backhaul networks.

REFERENCES

• 1: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 2: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 3: G. Bianchi. Performance analysis of the IEEE 802.11 distributed coordination f unction. IEEE Journal on Selected Areas in Communications, 18(3):535--547, March 2000.
• 4: Marcelo M. Carvalho , J. J. Garcia-Luna-Aceves, A scalable model for channel access protocols in multihop ad hoc 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.1023753]
• 5: B. Chambers. The grid roofnet: a rooftop ad hoc wireless network. M.S. Thesis, MIT, May 2002.
• 6: K. Chen, Y. Xue, and K. Nahrstedt. On setting TCP's congestion window limit in mobile ad hoc networks. In Proceedings of IEEE International Conference on Communications, Anchorage, Alaska, May 2003.
• 7: Z. Fu, P. Zerfos, H. Luo, S. Lu, L. Zhang, and M. Gerla. The impact of multihop wireless channel on TCP throughput and loss. In Proceedings of IEEE INFOCOM'03, San Francisco, CA, April 2003.
• 8: Violeta Gambiroza , Ping Yuan , Laura Balzano , Yonghe Liu , Steve Sheafor , Edward Knightly, Design, analysis, and implementation of DVSR: a fair high-performance protocol for packet rings, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.85-102, February 2004 [doi>10.1109/TNET.2003.820432]
• 9: M. Gastpar and M. Vetterli. On the capacity of ad hoc wireless networks: the relay case. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002.
• 10: M. Grossglauser and D. Tse. Mobility increases the capacity of ad hoc networks. In Proceedings of IEEE INFOCOM '01, Anchorage, Alaska, April 2001.
• 11: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2), March 2000.
• 12: M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda. Performance anomaly of 802.11b. In Proceedings of IEEE INFOCOM'03, San Francisco, CA, April 2003.
• 13: Gavin Holland , Nitin Vaidya , Paramvir Bahl, A rate-adaptive MAC protocol for multi-Hop wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.236-251, July 2001, Rome, Italy [doi>10.1145/381677.381700]
• 14: Xiao Long Huang , Brahim Bensaou, On max-min fairness and scheduling in wireless ad-hoc networks: analytical framework and implementation, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501447]
• 15: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 16: V. Kanodia , A. Sabharwal , B. Sadeghi , E. Knightly, Ordered packet scheduling in wireless ad hoc networks: mechanisms and performance analysis, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513808]
• 17: R. Karrer, A. Sabharwal, and E. Knightly. Enabling large-scale wireless broadband: the case for TAPs. In Proceedings of HotNets-II, Cambridge, MA, November 2003.
• 18: F. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49:237--252, 1998.
• 19: A. Kherani and R. Shorey. Throughput analysis of TCP in multi-hop wireless networks with IEEE 802.11 MAC. In Proceedings of IEEE Wireless Communications and Networking Conference, Atlanta, GA, March 2004.
• 20: James F. Kurose , Keith Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 21: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 22: H. Luo, J. Cheng, and S. Lu. Self-coordinating localized fair queueing in wireless ad hoc networks. IEEE Transaction on Mobile Computing, 3(1), January-March 2004.
• 23: L. Massoulie and J. Roberts. Bandwidth sharing: objectives and algorithms. In Proceedings of IEEE INFOCOM '99, New York, NY, March 1999.
• 24: Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345925]
• 25: Jitendra Padhye , Victor Firoiu , Donald F. Towsley , James F. Kurose, Modeling TCP Reno performance: a simple model and its empirical validation, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.133-145, April 2000 [doi>10.1109/90.842137]
• 26: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 27: S. Pilosof, R. Ramjee, D. Raz, Y. Shavitt, and P. Sinha. Understanding TCP fairness over wireless LAN. In Proceedings of IEEE INFOCOM'03, San Francisco, CA, April 2003.
• 28: B. Radunovic and J. Le Boudec. Rate performance objectives of multi-hop wireless networks. In Proceedings of IEEE INFOCOM'04, Hong Kong, March 2004.
• 29: B. Sadeghi , V. Kanodia , A. Sabharwal , E. Knightly, Opportunistic media sccess 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: M. Sanchez, T. Giles, and J. Zander. CSMA/CA with beam forming antennas in multi-hop packet radio. In Proc. of Swedish Workshop on Wireless Ad Hoc Networks, March 2001.
• 31: L. Tassiulas and S. Sarkar. Maxmin fair scheduling in wireless networks. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002.
• 32: Kaixin Xu , Sang Bae , Sungwook Lee , Mario Gerla, TCP behavior across multihop wireless networks and the wired internet, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570790.570798]
• 33: K. Xu, M. Gerla, and S. Bae. How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks? In Proceedings of IEEE GLOBECOM'02, November 2002.
• 34: Y. Yang, J. Wang, and R. Kravets. Achievable bandwidth prediction in multihop wireless networks. Technical report, University of Illinois at Urbana-Champaign, Urbana, IL, 2003.
• 35: Y. Yi and S. Shakkottai. Hop-by-hop congestion control over a wireless multi-hop network. In Proceedings of IEEE INFOCOM'04, Hong Kong, March 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Design, Performance

Keywords:
CSMA, CSMA/CA, fairness, wireless backhaul networks