Achieving MAC layer fairness in wireless packet networks

ABSTRACT

Link-layer fairness models that have been proposed for wireline and packet cellular networks cannot be generalized for shared channel wireless networks because of the unique characteristics of the wireless channel, such as location-dependent contention, inherent conflict between optimizing channel utilization and achieving fairness, and the absence of any centralized control. In this paper, we propose a general analytical framework that captures the unique characteristics of shared wireless channels and allows the modeling of a large class of system-wide fairness models via the specification of per-flow utility functions. We show that system-wide fairness can be achieved without explicit global coordination so long as each node executes a contention resolution algorithm that is designed to optimize its local utility function. We present a general mechanism for translating a given fairness model in our framework into a corresponding contention resolution algorithm. Using this translation, we derive the backoff algorithm for achieving proportional fairness in wireless shared channels, and compare the fairness properties of this algorithm with both the ideal proportional fairness objective, and state-of-the-art backoff-based contention resolution algorithms. We believe that the two aspects of the proposed framework, i.e. the ability to specify arbitrary fairness models via local utility functions, and the ability to automatically generate local contention resolution mechanisms in response to a given utility function, together provide the path for achieving flexible service differentiation in future shared channel wireless networks.

REFERENCES

• 1: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 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: J. J. Garcia-Luna-Aceves , Chane L. Fullmer, Floor acquisition multiple access (FAMA) in single-channel wireless networks, Mobile Networks and Applications, v.4 n.3, p.157-174, Oct 1999 [doi>10.1023/A:1019146831447]
• 4: IEEE, "Wireless LAN Medium Access Control(MAC) and Physical Layer(PHY) specifications." IEEE Standard 802.11, June 1999.
• 5: F. P. Kelly, A. Maulloo, and D. Tan, "Kate control in communication networks: shadow prices, proportional fairness and stability," journal of the Operational Research Society, vol. 49, pp. 237-252, March 1998.
• 6: Timucin Ozugur , Mahmoud Naghshineh , Parviz Kermani , C. Michael Olsen , Babak Rezvani , John A. Copeland, Balanced media access methods for wireless networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.21-32, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288244]
• 7: S. Lu, T. Nandagopal, and V. Bharghavan, "Fair scheduling in wireless packet networks," in A CM MO- BICOM, October 1998.
• 8: 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]
• 9: V. Bharghavan, "Performance Analysis of a Medium Access Protocol for Wireless Packet Networks," in IEEE Performance and Dependability Symposium, August 1998.
• 10: Scott Shenker, Some conjectures on the behavior of acknowledgement-based transmission control of random access communication channels, Proceedings of the 1987 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.245-255, May 11-14, 1987, Banff, Alberta, Canada
• 11: "ns-2 Network Simulator," http://www-mash.cs.berkeley, edu/ns/, 1998.
• 12: T. Nandagopal, T. Kim, X. Gao, and V. Bharghavan, "Fairness Models for Medium Access Control in Wireless Packet Networks," TIMELY Research Report, June 2000.
• 13: S. Shenker, "Fundamental Design Issues for the Future Internet," IEEE Journal on Selected Areas in Communications(JSAC), vol. 13, pp. 1176-1188, 1995.
• 14: S. Kunniyur and R. Srikant, "End-to-End Congestion Control Schemes: Utility Functions, Random Losses and ECN Marks," in IEEE iNFOCOM, March 2000.
• 15: L. Massoulie and J. Roberts, "Bandwidth Sharing: Objectives and Algorithms," in iEEE INFOCOM, March 1999.

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Management, Performance, Reliability, Theory