Distributed optimal contention window control for elastic traffic in single-cell wireless LANs

ABSTRACT

This paper presents a theoretical study on distributed contention window control algorithms for achieving arbitrary bandwidth allocation policies and efficient channel utilization. By modeling different bandwidth allocation policies as an optimal contention window assignment problem, we design a general and fully distributed contention window control algorithm, called General Contention window Adaptation (GCA), and prove that it converges to the solution of the contention window assignment problem. By examining the stability of GCA, we identify the optimal stable point that maximizes channel utilization and provide solutions to control the stable point near the optimal point. Due to the generality of GCA, our work provides a theoretical foundation to analyze existing and design new contention window control algorithms.

REFERENCES

• 1: [1] IEEE 802.11 WG Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE 802.11 WG, 2003.
• 2: [2] P. Karn, "A new channel access method for packet radio," in Proc. 9th ARRL Computer Networking Conf., 1996.
• 3: 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
• 4: [4] S. Shenker, "Fundamental design issues for the future Internet," IEEE Int. J. Sel. Areas Commun., vol. 13, no. 7, Sep. 1995.
• 5: [5] Y. Yang and R. Kravets, "Distributed QoS guarantees for realtime traffic in ad hoc networks," in Proc. IEEE Int. Conf. Sensor and Ad Hoc Communications and Networks (SECON), 2004.
• 6: [6] Y. Yang and R. Kravets, "Achieving delay guarantees in ad hoc networks using distributed contention window adaptation," in Proc. IEEE INFOCOM, 2006.
• 7: Luciano Bononi , Marco Conti , Enrico Gregori, Runtime Optimization of IEEE 802.11 Wireless LANs Performance, IEEE Transactions on Parallel and Distributed Systems, v.15 n.1, p.66-80, January 2004 [doi>10.1109/TPDS.2004.1264787]
• 8: Hwangnam Kim , Jennifer C. Hou, Improving protocol capacity with model-based frame scheduling in IEEE 802.11-operated WLANs, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939005]
• 9: Frederico Calì , Marco Conti , Enrico Gregori, Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit, IEEE/ACM Transactions on Networking (TON), v.8 n.6, p.785-799, Dec. 2000 [doi>10.1109/90.893874]
• 10: [10] F. Cali, M. Conti, and E. Gregori, "IEEE 802.11 protocol: Design and performance evaluation of an adaptive backoff mechanism," IEEE J. Sel. Areas Commun., vol. 18, no. 9, pp. 1774-1786, Sep. 2000.
• 11: [11] IEEE P802.11, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 8: Medium Access Control (MAC) Quality of Service Enhancements, IEEE P802.11, TASK GROUP E, 2005.
• 12: [12] D. Qiao and K. G. Shin, "Achieving efficient channel utilization and weighted fairness for data communications in IEEE 802.11 WLAN under the DCF," in IWQoS, 2002.
• 13: 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]
• 14: [14] F. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: Shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, 1998.
• 15: A Class of End-to-End Congestion Control Algorithms for the Internet, Proceedings of the Sixth International Conference on Network Protocols, p.137, October 13-16, 1998
• 16: [16] S. Kunniyur and R. Srikant, "End-to-end congestion control schemes: Utility functions, random losses and ECN marks," in Proc. IEEE INFOCOM , 2000, pp. 1323-1332.
• 17: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 18: Rayadurgam Srikant, The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications), SpringerVerlag, 2004
• 19: [19] Y. Xue, B. Li, and K. Nahrstedt, "Price-based resource allocation in wireless ad hoc networks," in Int. Workshop QoS, 2004.
• 20: [20] B. Li and R. Battiti, "Performance analysis of an enhanced IEEE 802.11 distributed coordination function supporting service differentiation," in Int. Workshop on Quality of Future Internet Service, 2003.
• 21: Laurent Massoulié , James Roberts, Bandwidth sharing: objectives and algorithms, IEEE/ACM Transactions on Networking (TON), v.10 n.3, p.320-328, June 2002 [doi>10.1109/TNET.2002.1012364]
• 22: [22] D. Bertsekas, Nonlinear Programming, 2nd ed. Nashua, NH: Athena Scientific, 1999.
• 23: [23] G. Bianchi, "Performance analysis of the IEEE 802.11 distributed coordination function," IEEE Int. J. Sel. Areas Commun., vol. 18, no. 3, 2000.
• 24: [24] Y. Yang, J. Wang, and R. Kravets, Distributed Optimal Contention Window Control for Elastic Traffic in Single Cell Wireless LANs--Complete Version [Online]. Available: http://www.ece.vt. edu/yyang8/papers/ton07-complete.pdf Tech.Rep.
• 25: [25] K. Fall and K. Varadhan, "NS notes and documentation," The VINT Project Univ. California Berkely, LBL, USC/ISI, and Xerox PARC, 1997.
• 26: [26] R. Jain, The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation and Modeling . New York: Wiley, 1991.
• 27: [27] S. Shakkottai and R. Srikant, "How good are deterministic fluid models of Internet congestion control," in Proc. IEEE INFOCOM, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Management

Keywords:
LAN, dynamic bandwidth allocation, fairness, wireless