Performance evaluation of a fair backoff algorithm for IEEE 802.11 DFWMAC

ABSTRACT

Due to hidden terminals and a dynamic topology, contention among stations in an ad-hoc network is not homogeneous. Some stations are at a disadvantage in opportunity of access to the shared channel and can suffer severe throughput degradation when the traffic load is high. This is the so-called "fairness problem" encountered mainly in existing MAC protocols such as IEEE 802.11 Distributed Foundation Wireless Medium Access Control (DFWMAC) that is used as a basis for most performance evaluation of routing protocols in mobile ad-hoc networks (MANET). The binary exponential backoff (BEB) used in DFWMAC protocol to resolve contention is known to always favor the last station that succeeds its transmission, which exacerbates the fairness problem in heavy traffic. This paper reviews a measurement-based backoff algorithm for the DFWMAC protocol that achieves statistical fair access to the shared medium, and then models analytically the resultant system as a feedback control system. The analytical model confirms the fairness property of the algorithm, as well as its convergence and show the impact of different parameters of the algorithm on the performance of the system.

REFERENCES

• 1: MANET charter. urlhttp://www.ietf.org/html.charters/manet-charter.html.
• 2: Brahim Bensaou , Yu Wang , Chi Chung Ko, Fair medium access in 802.11 based wireless ad-hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 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: Fang, Z. Y., Bensaou, B., and Wang, Y. Fair bandwidth sharing in IEEE 802.11 DFWMAC protocol. In Preparation, May 2002.
• 5: 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]
• 6: Jain, R. The Art of Computer Systems Performance Analysis. Wiley, 1991, ch. 3, p. 36.
• 7: Ozugur, T., Naghshineh, M., Kermani, P., and Copeland, J. A. Fair Media Access for Wireless LANs. In IEEE GLOBCOM'99/ (Dec. 1999).
• 8: 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]
• 9: Vaidya, N. H., and Bahl, P. Fair scheduling in broadcast environments. Tech. Rep. MSR-TR-99-61, Microsoft Research, Dec. 1999.
• 10: Wang, Y., and Bensaou, B. Achieving Fairness in IEEE 802.11 DFWMAC with Variable Packet Lengths. In IEEE Globecom'01 (Nov. 2001).
• 11: Xu, S., and Saadawi, T. Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks? IEEE Communications Magazine (June 2001), 130--137.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.5 Local and Wide-Area Networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Modeling techniques; Reliability, availability, and serviceability

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
IEEE 802.11, ad-hoc networks, backoff procedure, fairness, max-min fairness, medium access control, performance