The achievable rate region of 802.11-scheduled multihop networks

ABSTRACT

In this paper, we characterize the achievable rate region for any IEEE 802.11-scheduled static multihop network. To do so, we first characterize the achievable edge-rate region, that is, the set of edge rates that are achievable on the given topology. This requires a careful consideration of the interdependence among edges since neighboring edges collide with and affect the idle time perceived by the edge under study. We approach this problem in two steps. First, we consider two-edge topologies and study the fundamental ways they interact. Then, we consider arbitrary multihop topologies, compute the effect that each neighboring edge has on the edge under study in isolation, and combine to get the aggregate effect. We then use the characterization of the achievable edge-rate region to characterize the achievable rate region. We verify the accuracy of our analysis by comparing the achievable rate region derived from simulations with the one derived analytically. We make a couple of interesting and somewhat surprising observations while deriving the rate regions. First, the achievable rate region with 802.11 scheduling is not necessarily convex. Second, the performance of 802.11 is surprisingly good. For example, in all the topologies used for model verification, the max-min allocation under 802.11 is at least 64% of the max-min allocation under a perfect scheduler.

REFERENCES

• 1: 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]
• 2: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, Algorithmic aspects of capacity in wireless networks, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 3: John Bicket , Daniel Aguayo , Sanjit Biswas , Robert Morris, Architecture and evaluation of an unplanned 802.11b mesh network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080833]
• 4: D. Raychaudhuri, I. Seskar, M. Ott, S. Ganu, K. Ramachandran, H. Kremo, R. Siracusa, H. Liu, and M. Singh, "Overview of the orbit radio grid testbed for evaluation of next-generation wireless network protocols," in Proc. IEEE WCNC, 2005, vol. 3, pp. 1664-1669.
• 5: Jakob Eriksson , Sharad Agarwal , Paramvir Bahl , Jitendra Padhye, Feasibility study of mesh networks for all-wireless offices, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134689]
• 6: Joseph Camp , Joshua Robinson , Christopher Steger , Edward Knightly, Measurement driven deployment of a two-tier urban mesh access network, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134691]
• 7: S. Ray, D. Starobinski, and J. Carruthers, "Performance of wireless networks with hidden nodes: A queuing-theoretic analysis," J. Comput. Commun., vol. 28, pp. 1179-1192, 2005.
• 8: Claude Chaudet , Isabelle Guérin Lassous , Eric Thierry , Bruno Gaujal, Study of the impact of asymmetry and carrier sense mechanism in IEEE 802.11 multi-hops networks through a basic case, Proceedings of the 1st ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 04-04, 2004, Venezia, Italy [doi>10.1145/1023756.1023758]
• 9: Harshal S. Chhaya , Sanjay Gupta, Performance modeling of asynchronous data transfer methods of IEEE 802.11 MAC protocol, Wireless Networks, v.3 n.3, p.217-234, 1997 [doi>10.1023/A:1019109301754]
• 10: 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]
• 11: X. Wang and K. Kar, "Throughput modeling and fairness issues in CSMA/CA based ad-hoc networks," in Proc. IEEE INFOCOM, 2005, pp. 23-34.
• 12: C. Reis, R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan, "Measurement-based models of delivery and interference," in Proc. ACM SIGCOMM, 2006, pp. 51-62.
• 13: H. Chang, V. Misra, and D. Rubenstein, "A general model and analysis of physical layer capture in 802.11 networks," in Proc. IEEE INFOCOM , 2006.
• 14: Anand Kashyap , Samrat Ganguly , Samir R. Das, A measurement-based approach to modeling link capacity in 802.11-based wireless networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287883]
• 15: M. Garetto, T. Salonidis, and E. Knightly, "Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks," in Proc. IEEE INFOCOM, 2006.
• 16: Yan Gao , Dah-Ming Chiu , John C.S. Lui, Determining the end-to-end throughput capacity in multi-hop networks: methodology and applications, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 17: K. Medepalli and F. A. Tobagi, "Towards performance modeling of IEEE 802.11 based wireless networks: A unified framework and its applications," in Proc. IEEE INFOCOM, 2006.
• 18: Lili Qiu , Yin Zhang , Feng Wang , Mi Kyung Han , Ratul Mahajan, A general model of wireless interference, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287874]
• 19: Saumitra M. Das , Dimitrios Koutsonikolas , Y. Charlie Hu , Dimitrios Peroulis, Characterizing multi-way interference in wireless mesh networks, Proceedings of the 1st international workshop on Wireless network testbeds, experimental evaluation & characterization, September 29-29, 2006, Los Angeles, CA, USA [doi>10.1145/1160987.1160999]
• 20: Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications--Higher-Speed Physical Layer Extension in the 2.4 GHz Band, IEEE Std 802.11b-1999, Nov. 2002.
• 21: G. Bianchi, "Performance analysis of the IEEE 802.11 distributed coordination function," IEEE J. Sel. Areas Commun., vol. 18, no. 3, pp. 535-547, Mar. 2000.
• 22: G. Sharma, A. Ganesh, and P. Key, "Performance analysis of contention based medium access control protocols," in Proc. IEEE INFOCOM , 2006.
• 23: A. Jindal and K. Psounis, "Characterizing the achievable rate region of wireless multi-hop networks with 802.11 scheduling," Univ. of Southern California, Tech. Rep. CENG-2007-12, 2007.
• 24: P. Chaporkar, K. Kar, X. Luo, and S. Sarkar, "Throughput and fairness guarantees through maximal scheduling in wireless networks," IEEE Trans. Inf. Theory, vol. 54, no. 2, pp. 572-594, Feb. 2008.
• 25: V. I. Istratescu, Fixed Point Theory, An Introduction. Dordrecht, The Netherlands: D. Reidel, 1981.
• 26: A. Granas and J. Dugundji, Fixed Point Theory. New York: Springer-Verlag, 2003.
• 27: David Malone , Ken Duffy , Doug Leith, Modeling the 802.11 distributed coordination function in nonsaturated heterogeneous conditions, IEEE/ACM Transactions on Networking (TON), v.15 n.1, p.159-172, February 2007 [doi>10.1109/TNET.2006.890136]
• 28: Venkatesh Ramaiyan , Anurag Kumar , Eitan Altman, Fixed point analysis of single cell IEEE 802.11e WLANs: uniqueness, multistability and throughput differentiation, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 29: M. Durvy, O. Dousse, and P. Thiran, "Border effects, fairness, and phase transition in large wireless networks," in Proc. IEEE INFOCOM, 2008, pp. 601-609.
• 30: Kaixin Xu , Mario Gerla , Lantao Qi , Yantai Shu, Enhancing TCP fairness in ad hoc wireless networks using neighborhood RED, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938988]
• 31: K. Tan, F. Jiang, Q. Zhang, and X. Shen, "Congestion control in multihop wireless networks," IEEE Trans. Veh. Technol., vol. 56, no. 2, pp. 863-873, Mar. 2007.
• 32: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 33: 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]
• 34: A. Jindal and K. Psounis, "Achievable rate region and optimality of multi-hop wireless 802.11-scheduled network," in Proc. Inf. Theory Appl. Workshop, 2008.
• 35: Jitendra Padhye , Sharad Agarwal , Venkata N. Padmanabhan , Lili Qiu , Ananth Rao , Brian Zill, Estimation of link interference in static multi-hop wireless networks, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.28-28, October 19-21, 2005, Berkeley, CA
• 36: T. Salonidis, M. Garetto, A. Saha, and E. Knightly, "Identifying high throughput paths in 802.11 mesh networks: A model-based approach," in Proc. IEEE ICNP, 2007, pp. 21-30.
• 37: Sumit Rangwala , Apoorva Jindal , Ki-Young Jang , Konstantinos Psounis , Ramesh Govindan, Understanding congestion control in multi-hop wireless mesh networks, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA [doi>10.1145/1409944.1409978]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Management, Performance

Keywords:
IEEE 802.11, capacity region, multihop networks