FEBA: a bandwidth allocation algorithm for service differentiation in IEEE 802.16 mesh networks

ABSTRACT

In wireless mesh networks, the end-to-end throughput of traffic flows depends on the path length, i.e., the higher the number of hops, the lower becomes the throughput. In this paper, a fair end-to-end bandwidth allocation (FEBA) algorithm is introduced to solve this problem. FEBA is implemented at the medium access control (MAC) layer of single-radio, multiple channels IEEE 802.16 mesh nodes, operated in a distributed coordinated scheduling mode. FEBA negotiates bandwidth among neighbors to assign a fair share proportional to a specified weight to each end-to-end traffic flow. This way traffic flows are served in a differentiated manner, with higher priority traffic flows being allocated more bandwidth on the average than the lower priority traffic flows. In fact, a node requests/grants bandwidth from/to its neighbors in a round-robin fashion where the amount of service depends on both the load on its different links and the priority of currently active traffic flows. If multiple channels are available, they are all shared evenly in order to increase the network capacity due to frequency reuse. The performance of FEBA is evaluated by extensive simulations. It is shown that wireless resources are shared fairly among best-effort traffic flows, while multimedia streams are provided with a differentiated service that enables quality of service.

REFERENCES

• 1: Ian F. Akyildiz , Xudong Wang , Weilin Wang, Wireless mesh networks: a survey, Computer Networks and ISDN Systems, v.47 n.4, p.445-487, 15 March 2005 [doi>10.1016/j.comnet.2004.12.001]
• 2: Paramvir Bahl , Atul Adya , Jitendra Padhye , Alec Walman, Reconsidering wireless systems with multiple radios, ACM SIGCOMM Computer Communication Review, v.34 n.5, October 2004 [doi>10.1145/1039111.1039122]
• 3: A. Raniwala and T. Chiueh, "Architecture and algorithms for and IEEE 802.11-based multi-channel wireless mesh network," in Proc. IEEE INFOCOM , Miami, FL, Mar. 2005, pp. 2223-2234.
• 4: Giuseppe Anastasi , Eleonora Borgia , Marco Conti , Enrico Gregori, IEEE 802.11b Ad Hoc Networks: Performance Measurements, Cluster Computing, v.8 n.2-3, p.135-145, July 2005 [doi>10.1007/s10586-005-6179-3]
• 5: Violeta Gambiroza , Bahareh Sadeghi , Edward W. Knightly, End-to-end performance and fairness in multihop wireless backhaul 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.1023749]
• 6: T. Salonidis and L. Tassiulas, "Distributed on-line schedule adaptation for balanced slot allocation in wireless ad hoc networks," in Proc. IEEE IWQoS, Montreal, Canada, Jun. 2004, pp. 20-29.
• 7: L. Bui, A. Eryilmaz, R. Srikant, and X. Wu, "Joint asynchronous congestion control and distributed scheduling for multi-hop wireless networks," in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006, pp. 1-12 (DOI: 10.1109/INFOCOM.2006.210).
• 8: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications. ESS Mesh Networking. IEEE 802.11s/D1.06, 2007.
• 9: R. Zhao, B. Walke, and G. R. Hiertz, "An efficient IEEE 802.11 ESS mesh network supporting quality-of-service," IEEE J. Sel. Areas Commun., vol. 24, no. 11, pp. 2005-2017, Nov. 2006.
• 10: Xudong Wang , Azman O. Lim, IEEE 802.11s wireless mesh networks: Framework and challenges, Ad Hoc Networks, v.6 n.6, p.970-984, August, 2008 [doi>10.1016/j.adhoc.2007.09.003]
• 11: Air Interface for Fixed Broadband Wireless Access Systems. IEEE 802. 16d, 2004.
• 12: M. Cao, W. Ma, Q. Zhang, and X. Wang, "Analysis of IEEE 802.16 mesh mode scheduler performance," IEEE Trans. Wireless Commun., vol. 6, no. 4, pp. 1455-1464, Apr. 2007.
• 13: C. Cicconetti, I. F. Akyildiz, and L. Lenzini, "Bandwidth balancing in multi-channel IEEE 802.16 wireless mesh networks," in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 2108-2116.
• 14: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 3, pp. 388-404, Mar. 2000.
• 15: Q. Dong, S. Banerjee, and B. Liu, "Throughput optimization and fair bandwidth allocation in multi-hop wireless LANs," in Proc. IEEE INFOCOM , Barcelona, Spain, Apr. 2006, pp. 1-12 (DOI 10.1109/INFOCOM.2006.247).
• 16: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 17: E. L. Hahne, "Round-robin scheduling for max-min fairness in data networks," IEEE J. Sel. Areas Commun., vol. 9, no. 9, pp. 1024-1039, Sep. 1991.
• 18: Yuan Xue , Baochun Li , Klara Nahrstedt, Optimal Resource Allocation in Wireless Ad Hoc Networks: A Price-Based Approach, IEEE Transactions on Mobile Computing, v.5 n.4, p.347-364, April 2006 [doi>10.1109/TMC.2006.1599404]
• 19: L. Tassiulas and S. Sarkar, "Maxmin fair scheduling in wireless networks," in Proc. IEEE INFOCOM, Jun. 2002, pp. 763-772.
• 20: Yung Yi , Sanjay Shakkottai, Hop-by-hop congestion control over a wireless multi-hop network, IEEE/ACM Transactions on Networking (TON), v.15 n.1, p.133-144, February 2007 [doi>10.1109/TNET.2006.890121]
• 21: Songwu Lu , Vaduvur Bharghavan , R. Srikant, Fair scheduling in wireless packet networks, IEEE/ACM Transactions on Networking (TON), v.7 n.4, p.473-489, Aug. 1999 [doi>10.1109/90.793003]
• 22: M. A. Nichols , H. J. Siegel , H. G. Dietz , R. W. Quong , W. G. Nation, Eliminating Memory for Fragmentation Within Partitionable SIMD/SPMD Machines, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.290-303, July 1991 [doi>10.1109/71.86105]
• 23: 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]
• 24: 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]
• 25: Media Access Control (MAC) Bridges. IEEE 802.1d, 2004.
• 26: Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
• 27: Claudio Cicconetti , Enzo Mingozzi , Giovanni Stea, An integrated framework for enabling effective data collection and statistical analysis with ns-2, Proceeding from the 2006 workshop on ns-2: the IP network simulator, October 10-10, 2006, Pisa, Italy [doi>10.1145/1190455.1190466]
• 28: R. Jain, W. Hawe, and D. Chiu, "A quantitative measure of fairness and discrimination for resource allocation in shared computer systems," Digital Equipment Corp., New York, Tech. Rep. DEC-TR-301, 1984.
• 29: C. R. Baugh, J. Huang, R. Schwartz, and D. Trinkwon, "Traffic model for 802.16 TG3 MAC/PHY simulations," Tech. Rep., IEEE 802.16 Broadband Wireless Access Working Group, 2001.
• 30: C.-N. Chuah and R. H. Katz, "Characterizing packet audio streams from Internet multimedia applications," in Proc. IEEE ICC, New York, Apr. 2002, pp. 1199-2203.
• 31: Transmission Impairments due to Speech Processing. ITU-T Recommendation G.113, 2001.
• 32: F. H. P. Fitzek and M. Reisslein, "MPEG4 and H.263 video traces for network performance evaluation," IEEE Network, vol. 15, no. 6, pp. 40-54, Nov. 2001.
• 33: Claudio Cicconetti , Alessandro Erta , Luciano Lenzini , Enzo Mingozzi, Performance evaluation of the mesh election procedure of ieee 802.16/wimax, Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, October 22-26, 2007, Chania, Crete Island, Greece [doi>10.1145/1298126.1298181]
• 34: N. Bayer, B. Xu, V. Rakocevic, and J. Habermann, "Improving the performance of the distributed scheduler in IEEE 802.16 mesh networks," in Proc. IEEE VTC-Spring, Apr. 22-25, 2007, pp. 1193-1197.
• 35: M. Cao, V. Raghunathan, and P. Kumar, "A tractable algorithm for fair and efficient uplink scheduling of multi-hop WiMAX mesh networks," in Proc. IEEE WiMesh, 2006, pp. 93-100.
• 36: D. Kim and A. Ganz, "Fair and efficient multihop scheduling algorithm for IEEE 802.16 BWA systems," in Proc. Broadnets, Oct. 3-7, 2005, pp. 833-839.
• 37: H.-Y. Wei, S. Ganguly, R. Izmailov, and Z. Haas, "Interference-aware IEEE 802.16 WiMax mesh networks," in Proc. IEEE VTC-Spring, May-Jun. 30-1, 2005, vol. 5, pp. 3102-3106.
• 38: Shin-Ming Cheng , Phone Lin , Di-Wei Huang , Shun-Ren Yang, A study on distributed/centralized scheduling for wireless mesh network, Proceedings of the 2006 international conference on Wireless communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada [doi>10.1145/1143549.1143668]
• 39: G. Narlikar, G. Wilfong, and L. Zhang, "Designing multihop wireless backhaul networks with delay guarantees," in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006, pp. 1-12 (DOI 10.1109/INFOCOM.2006.319).
• 40: D. Ghosh, A. Gupta, and P. Mohapatra, "Admission control and interference-aware scheduling in multi-hop WiMAX networks," in Proc. IEEE MASS, Oct. 8-11, 2007, pp. 1-9.

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; Network topology
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

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

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Management, Performance

Keywords:
access protocols, packet reservation multiaccess, scheduling, wireless LAN