More Web Proxy on the site http://driver.im/

article

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

Authors:

Claudio Cicconetti,

Ian F. Akyildiz,

Luciano LenziniAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 3

Pages 884 - 897

https://doi.org/10.1109/TNET.2008.2005221

Published: 01 June 2009 Publication History

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]

I. F. Akyildiz, X. Wang, and W. Wang, "Wireless mesh networks: A survey," Comput. Netw., vol. 47, pp. 445-487, Mar. 2005.

Digital Library

[2]

P. Bahl, A. Adya, J. Padhye, and A. Wolman, "Reconsidering wireless systems with multiple radios," ACM SIGCOMM Comput. Commun. Rev., vol. 34, pp. 39-46, Oct. 2004.

Digital Library

[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]

G. Anastasi, E. Borgia, M. Conti, and E. Gregori, "IEEE 802.11b ad hoc networks: Performance measurements," Cluster Computing, vol. 8, pp. 135-145, Jul. 2005.

Digital Library

[5]

V. Gambiroza, B. Sadeghi, and E. W. Knightly, "End-to-end performance and fairness in multihop wireless backhaul networks," in Proc. ACM MobiCom, Philadelphia, PA, Sep. 2004, pp. 287-301.

Digital Library

[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 (

[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.

Digital Library

[10]

X. Wang and A. O. Lim, "IEEE 802.11s wireless mesh networks: Framework and challenges," Ad Hoc Netw., 2007. adhoc.2007.09.003.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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]

D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, 1992.

Digital Library

[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.

Digital Library

[18]

Y. Xue, B. Li, and K. Nahrstedt, "Optimal resource allocation in wireless ad hoc networks: A price-based approach," IEEE Trans. Mobile Comput., vol. 5, no. 4, pp. 347-364, Apr. 2006.

Digital Library

[19]

L. Tassiulas and S. Sarkar, "Maxmin fair scheduling in wireless networks," in Proc. IEEE INFOCOM, Jun. 2002, pp. 763-772.

[20]

Y. Yi and S. Shakkottai, "Hop-by-hop congestion control over a wireless multi-hop network," IEEE/ACM Trans. Networking, vol. 15, no. 1, pp. 133-144, Feb. 2007.

Digital Library

[21]

S. Lu, V. Bharghavan, and R. Srikant, "Fair scheduling in wireless packet networks," IEEE/ACM Trans. Networking, vol. 7, no. 4, pp. 473-489, Aug. 1999.

Digital Library

[22]

M. A. Nichols, H. J. Siegel, H. G. Dietz, R. W. Quong, and W. G. Nation, "Eliminating memory for fragmentation within partitionable SIMD/SPMD machines," IEEE Trans. Parallel Distrib. Syst., vol. 2, no. 7, pp. 290-303, Jul. 1991.

Digital Library

[23]

T. Nandagopal, T. Kim, X. Gao, and V. Bharghavan, "Achieving MAC layer fairness in wireless packet networks," in Proc. ACM MobiCom, Boston, MA, Aug. 2000, pp. 87-98.

Digital Library

[24]

M. Shreedhar and G. Varghese, "Efficient fair queueing using deficit round robin," IEEE/ACM Trans. Networking, vol. 4, no. 3, pp. 375-385, Jun. 1996.

Digital Library

[25]

Media Access Control (MAC) Bridges. IEEE 802.1d, 2004.

[26]

A. M. Law and W. D. Kelton, Simulation Modeling and Analysis. New York: McGraw-Hill, 2000.

Digital Library

[27]

C. Cicconetti, E. Mingozzi, and G. Stea, "An integrated framework for enabling effective data collection and statistical analysis with ns-2," in Proc. WNS2, Pisa, Italy, Oct. 2006, http://doi.acm.org/10.1145/ 1190455.1190466.

Digital Library

[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.

Digital Library

[33]

C. Cicconetti, A. Erta, L. Lenzini, and E. Mingozzi, "Performance evaluation of the mesh election procedure of IEEE 802.16/WiMAX," in Proc. IEEE MSWiM, Chania, Crete, Greece, Apr. 22-26, 2007, pp. 323-327.

Digital Library

[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]

S.-M. Cheng, P. Lin, D.-W. Huang, and S.-R. Yang, "A study on distributed/centralized scheduling for wireless mesh network," in Proc. IWCMC, Vancouver, BC, Canada, Jul. 2006, pp. 599-604.

Digital Library

[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.

Cited By

Alsarhan AQuttoum AKilani Y(2017)Optimizing Spectrum Sharing in Wireless Mesh Network Using Cognitive TechnologyWireless Personal Communications: An International Journal10.1007/s11277-017-4274-496:2(1887-1905)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s11277-017-4274-4
Kumuthini CKrishnakumari P(2016)Evolving intuitionistic fuzzy priority classifier with bio-inspiration based scheduling scheme for WiMAX in vehicular ad-hoc networksWireless Networks10.1007/s11276-015-0978-022:2(403-415)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s11276-015-0978-0
Pounambal MKrishna P(2016)Efficient channel assignment method for multimedia traffic in wireless mesh networksInternational Journal of Communication Systems10.1002/dac.300029:5(929-941)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1002/dac.3000
Show More Cited By

Index Terms

Recommendations

An approach to pricing, optimal allocation and quality of service provisioning in high-speed packet networks
INFOCOM '95: Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 3)-Volume - Volume 3

Proposes a new methodology based on economic models to provide quality of service (QoS) guarantees to competing traffic classes (classes of sessions) in packet networks. The authors consider an economic model of a packet network where resources are ...
Semi-Random Backoff: Towards resource reservation for channel access in wireless LANs
ICNP '09: Proceedings of the 2009 17th IEEE International Conference on Network Protocols. ICNP 2009

In this paper, we propose a semi-random backoff (SRB) mechanism to combat network collisions for 802.11 DCF/EDCA in wireless LANs. SRB is fundamentally different from traditional random backoff methods because it provides a form of resource reservation ...
Resource allocation and wireless scheduling scheme for a HiperLAN/2 system

In this paper, a dynamic resource allocation scheme for a wireless local area network system is presented. It aims at enforcing the Quality of Service requirements of the applications that are carried on the wireless link even when errors occur on it. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 3

June 2009

329 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 June 2009

Revised: 19 March 2008

Received: 02 August 2007

Published in TON Volume 17, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
537
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alsarhan AQuttoum AKilani Y(2017)Optimizing Spectrum Sharing in Wireless Mesh Network Using Cognitive TechnologyWireless Personal Communications: An International Journal10.1007/s11277-017-4274-496:2(1887-1905)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s11277-017-4274-4
Kumuthini CKrishnakumari P(2016)Evolving intuitionistic fuzzy priority classifier with bio-inspiration based scheduling scheme for WiMAX in vehicular ad-hoc networksWireless Networks10.1007/s11276-015-0978-022:2(403-415)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s11276-015-0978-0
Pounambal MKrishna P(2016)Efficient channel assignment method for multimedia traffic in wireless mesh networksInternational Journal of Communication Systems10.1002/dac.300029:5(929-941)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1002/dac.3000
Xu DLiu X(2015)Throughput-fairness optimization in energy-limited user-relay wireless networksWireless Networks10.1007/s11276-014-0829-421:3(1047-1060)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s11276-014-0829-4
Reddy CKrishna P(2014)Cross Layer Based Congestion Control in Wireless Mesh NetworksCybernetics and Information Technologies10.2478/cait-2014-002014:2(65-80)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.2478/cait-2014-0020
Vijayalayan KHarwood AKarunasekera S(2013)Distributed scheduling schemes for wireless mesh networksACM Computing Surveys10.1145/2522968.252298246:1(1-34)Online publication date: 11-Jul-2013
https://dl.acm.org/doi/10.1145/2522968.2522982
Ahmed IMohammed AAlnuweiri H(2013)On the fairness of resource allocation in wireless mesh networksWireless Networks10.1007/s11276-013-0544-619:6(1451-1468)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1007/s11276-013-0544-6
Fowler SZhang X(2012)Ubiquitous fair bandwidth allocation for multimedia traffic on a WiMAX mesh network with multi-channelsInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2012.0470099:4(224-240)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1504/IJAHUC.2012.047009
Tu YChen MSun Y(2011)Adaptive on-the-go scheduling for end-to-end delay control in TDMA-based wireless mesh networksProceedings of the 10th international IFIP TC 6 conference on Networking - Volume Part II10.5555/2008826.2008851(263-274)Online publication date: 9-May-2011
https://dl.acm.org/doi/10.5555/2008826.2008851
Vejarano GMcNair JPerrone LStea GLiu JUhrmacher AVillén-Altamirano M(2010)WiMAX-RBDS-SimProceedings of the 3rd International ICST Conference on Simulation Tools and Techniques10.5555/1808143.1808178(1-10)Online publication date: 15-Mar-2010
https://dl.acm.org/doi/10.5555/1808143.1808178
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents