On max-min fairness and scheduling in wireless ad-hoc networks: analytical framework and implementation

ABSTRACT

This paper addresses the problem of fairness in wireless ad-hoc networks. Usually, the problem of fairness in wireless ad-hoc networks is addressed in a classic approach inherited from wired networks. The common assumption is that nodes/flows have pre-assigned fair shares. The task becomes then to modify wired networks' fair queueing algorithms to address wireless network nature. Wired networks have efficient means of allocating fiar shares through admission control and additionally, the fair shares remain constant throughout the session duration due to the static nature of the nodes. In ad-hoc networks, it is meaningless to assume statically pre-assigned fair shares, since on one hand, not only the nodes move, but also the routers are mobile, and on the other hand, contention is location dependent, such that in terms of absolute guarantees, fairness would at most mean "avoiding starvation": thus applying rate proportional fiar queueing algorithms is beyond the original goal of such algorithm, viz. flow isolation/protection and bandwidth guarantee. In this work we argue in favor of multi-level scheduling for wireless ad-hoc networks with max-min fair allocation of the fair shares at the lower-most layer (MAC layer). This paper, mainly lays down the theoretical framework by which one can calculate the fair shares that would achieve max-min fairness in an ad-hoc network. We design distributed algorithms that allow each node to determine its max-min per-link fair share in a global ad-hoc network without knowledge of the global topology of the network. The results are then used in conjunction with a novel practical scheduling algorithm for IEEE 802.11 to show how fairness is achieved

REFERENCES

• 1: IEEE Computer Society LAN MAN Standards Committee, ed., IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Std 802.11-1997, The Institute of Electrical and Electronics Engineers, New York, 1997.
• 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: Chane Lee Fullmer , J. J. Garcia-Luna-Aceves, Collision avoidance techniques for packet-radio networks, 1998
• 4: Haiyun Luo , Songwu Lu , Vaduvur Bharghavan, A new model for packet scheduling in multihop wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.76-86, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345923]
• 5: N. H. Vaidya and P. Bahl, "Fair scheduling in broadcast environments," Tech. Rep. MSR-TR-99-61, Microsoft Research, Dec. 1999.
• 6: 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]
• 7: 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
• 8: Y. Wang and B. Bensaou, "Achieving Fairness in IEEE 802.11 DFWMAC with Variable Packet Lengths," in IEEE Globecom'01 (to appear, Nov. 2001.
• 9: C. Perkins, "On the different mac protocols used with manet routing." Discussions on IETF MANET mailing list, May 2001.
• 10: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round-robin, IEEE/ACM Transactions on Networking (TON), v.4 n.3, p.375-385, June 1996 [doi>10.1109/90.502236]
• 11: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 12: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982

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.4 Distributed Systems

General Terms:
Algorithms, Design

Keywords:
ad-hoc networks, admission control, distributed algorithms, max-min fairness, per-link/per-flow fairness, scheduling