research-article

Capacity-aware routing in heterogeneous mesh networks: an analytical approach

Authors:

Raffaele Bruno,

Antonio PinizzottoAuthors Info & Claims

MSWiM '09: Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems

Pages 73 - 81

https://doi.org/10.1145/1641804.1641819

Published: 26 October 2009 Publication History

Abstract

In wireless mesh networks (WMNs), gateway nodes may become a severe bottleneck for Internet flows. Indeed, if traffic is routed in the mesh without considering traffic distribution, as well as link capacities, some gateways or intermediate mesh routers may rapidly get overloaded due to unevenly utilization of network resources. To address this issue, in this paper we firstly develop a multi-class queuing network model to analyze feasible throughput allocations in heterogeneous WMNs, as well as to predict the residual capacity of network paths. Guided by our analysis, we design a Capacity-Aware Route Selection algorithm (CARS), which allocates network paths to downstream and upstream Internet flows so as to ensure a more balanced utilization of wireless network resources and gateways' Internet connections. Through simulations in a number of different network scenarios we show that CARS significantly outperforms shortest path routing using routing metrics that capture only inter-flow interference.

References

[1]

H. Aiache, L. Lebrun, V. Conan, and S. Rousseau. A load dependent metric for balancing Internet traffic in Wireless Mesh Networks. In Proc. IEEE MeshTech 2008, pages 629--634, Atlanta, GA, USA, September 29, 2008.

[2]

F. Alizadeh-Shabdiz and S. Subramaniam. A Finite Load Analytical Model for IEEE 802.11 Distributed Coordination Fucntion MAC. In Proc. ACM WiOpt'03, Sophia-Antipolis, France, March 3-5 2003.

[3]

Y. Bejerano, S.-J. Han, and A. Kumar. Efficient load-balancing routing for wireless mesh networks. Computer Networks, 51(10):2450--2466, 2007.

Digital Library

[4]

N. Bisnik and A. Abouzeid. Queuing network models for delay analysis of multihop wireless ad hoc networks. Ad Hoc Networks, 7(1):79--97, January 2009.

Digital Library

[5]

G. Bolch, S. Greiner, H. de Meer, and K. S. Trivedi. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications. WileyBlackwell, May 2006.

[6]

R. Bruno, M. Conti, and E. Gregori. Mesh Networks: Commodity Multihop Ad Hoc Networks. IEEE Commun. Mag., 43(3):123--131, March 2005.

Digital Library

[7]

R. Bruno, M. Conti, and A. Pinizzotto. A Queuing Modeling Approach for Load-Aware Route Selection in Heterogenous Mesh Networks. In Proc. of IEEE WoWMoM'09, Kos, Greece, June 15-19 2009.

[8]

R. Bruno, M. Conti, and A. Pinizzotto. Capacity-Aware Routing in Heterogeneous Mesh Networks: An Analytical Approach. Technical report, IIT-CNR, May 2009. http://bruno1.iit.cnr.it/~raffaele/techreport.html.

[9]

D. De Couto, D. Aguayo, J. Bicket, and R. Morris. A High-Throughput Path Metric for Multi-Hop Wireless Routing. In Proc. of ACM MobiCom, pages 134--146, San Diego, CA, USA, September, 14-19 2003.

Digital Library

[10]

R. Draves, J. Padhye, and B. Zill. Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks. In Proc. of ACM MobiCom'04, pages 114--128, Sept. 26-Oct. 1 2004.

Digital Library

[11]

Y. Gao, D.-M. Chiu, and J. C. Lui. Determining the end-to-end throughput capacity in multi-hop networks: methodology and applications. SIGMETRICS Perform. Eval. Rev., 34(1):39--50, 2006.

Digital Library

[12]

M. Genetzakis and V. Siris. A Contention-Aware Routing Metric for Multi-Rate Multi-Radio Mesh Networks. In Proc. IEEE SECON 2008, pages 242--250, San Francisco, CA, USA, June 16-20, 2008.

[13]

R. Karrer, A. Sabharwal, and E. Knightly. Enabling Large-Scale Wireless Broadband: The Case for TAPs. ACM SIGMOBILE Comp. Comm. Review, 34(1):27--34, 2004.

Digital Library

[14]

A. Kashyap, S. Ganguly, A. Das, and S. Banerjee. VoIP on Wireless Meshes: Models, Algorithms and Evaluation. In Proc. IEEE INFOCOM'07, pages 2036--2044, Anchorage, USA, May 6-12 2007.

[15]

A. Kumar, E. Altman, D. Miorandi, and M. Goyal. New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs. IEEE/ACM Trans. Networking, 15(3):588--601, Jan. 2007.

Digital Library

[16]

L. Ma and M. Denko. A Routing Metric for Load-Balancing in Wireless Mesh Networks. In Proc. of IEEE AINAW '07, volume 2, pages 21--23, May 21-23, 2007.

Digital Library

[17]

Meraki Networks Inc. Residential&MDU Case Studies. http://meraki.com/.

[18]

V. Mhatre, F. Baccelli, H. Lundgren, and C. Diot. Joint MAC-aware routing and load balancing in mesh networks. In Proc. ACM CoNEXT'07, pages 1--12, New York, USA, December 10-13 2007.

Digital Library

[19]

M. Özdemir and A. McDonald. An M/MMGI/1/K queuing model for IEEE 802.11 ad hoc networks. In Proc. IEEE PE-WASUN '04, pages 107--111, Venice, Italy, 2004.

Digital Library

[20]

Ozone. French Wireless ISP. http://wwwo.zone.net/.

[21]

V. Siris, I. Askoxylakis, M. Conti, and R. Bruno. Enhanced, Ubiquitous and Dependable Broadband Access using MESH Networks. ERCIM News, 73:50--51, April 2008.

[22]

O. Tickoo and B. Sikdar. Modeling Queueing and Channel Access Delay in Unsaturated IEEE 802.11 Random Access MAC Based Wireless Networks. IEEE/ACM Trans. Networking, 16(4):878--891, Aug. 2008.

Digital Library

[23]

S. Waharte and R. Boutaba. Totally Disjoint Multipath Routing in Multihop Wireless Networks. In Proc. IEEE ICC'06, Istanbul, Turkey, June 2006.

[24]

Y. Yang, J. Wang, and R. Kravets. Designing Routing Metrics for Mesh Networks. In Proc. of IEEE WiMesh, 2005, Santa Clara, CA, USA, September, 26 2005.

[25]

Y. Yang, J. Wang, and R. Kravets. Load-balanced Routing For Mesh Networks. ACM Mobile Comp. and Comm. Review (M2CR), 1, 2006.

Digital Library

[26]

P. Zou, X. Wang, and R. Rao. Asymptotic Capacity of Infrastructure Wireless Mesh Networks. IEEE Trans. Mobile Comput., 7(8):1011--1024, August 2008.

Digital Library

Cited By

Daher R(2014)Fairness-oriented channel-capacity distribution in wireless multi-hop networks2014 International Conference on Connected Vehicles and Expo (ICCVE)10.1109/ICCVE.2014.7297705(986-993)Online publication date: Nov-2014
https://doi.org/10.1109/ICCVE.2014.7297705
Goyal TKumar N(2014)LBASMPL: Load balancing adaptive scheduling with minimum packet loss in Wireless Mesh Network2014 IEEE International Conference on Advanced Communications, Control and Computing Technologies10.1109/ICACCCT.2014.7019233(946-950)Online publication date: May-2014
https://doi.org/10.1109/ICACCCT.2014.7019233
Chakraborty SNandi S(2014)Selective greedy routingWireless Networks10.1007/s11276-014-0724-z20:7(1995-2017)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1007/s11276-014-0724-z
Show More Cited By

Index Terms

Capacity-aware routing in heterogeneous mesh networks: an analytical approach
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies
2. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

Routing Internet traffic in heterogeneous mesh networks: Analysis and algorithms

In practical wireless mesh networks (WMNs), gateways are subject to hard capacity limits on the aggregate number of flows (in terms of bit rate) that they can support. Thus, if traffic is routed in the mesh network without considering those constraints, ...
An adaptive load-aware routing algorithm for multi-interface wireless mesh networks

In wireless mesh networks, the number of gateway nodes are limited, when the nodes access to the internet by fixed gateway node, different requirements of nodes lead to the dataflow shows heterogeneity. Many new routing metrics and algorithms existing ...
Load-aware routing in mesh networks: Models, algorithms and experimentation

In this paper we consider wireless mesh networks (WMNs) used to share the Internet connectivity of sparsely deployed fixed lines with heterogeneous capacity, ranging from ISP-owned high-speed links to subscriber-owned low-speed connections. If traffic ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

MSWiM '09: Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems

October 2009

438 pages

ISBN:9781605586168

DOI:10.1145/1641804

General Chairs:
Nael Abu-Ghazaleh
State University of New York at Binghamton, USA
,
Luciano Bononi
University of Bologna, Italy
,
Program Chairs:
Brahim Bensaou
The Hong Kong University of Science and Technology, Hong Kong
,
Violet R. Syrotiuk
Arizona State University, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MSWiM '09

Sponsor:

SIGSIM

MSWiM '09: The 12th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems

October 26 - 29, 2009

Tenerife, Canary Islands, Spain

Acceptance Rates

Overall Acceptance Rate 398 of 1,577 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
307
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Daher R(2014)Fairness-oriented channel-capacity distribution in wireless multi-hop networks2014 International Conference on Connected Vehicles and Expo (ICCVE)10.1109/ICCVE.2014.7297705(986-993)Online publication date: Nov-2014
https://doi.org/10.1109/ICCVE.2014.7297705
Goyal TKumar N(2014)LBASMPL: Load balancing adaptive scheduling with minimum packet loss in Wireless Mesh Network2014 IEEE International Conference on Advanced Communications, Control and Computing Technologies10.1109/ICACCCT.2014.7019233(946-950)Online publication date: May-2014
https://doi.org/10.1109/ICACCCT.2014.7019233
Chakraborty SNandi S(2014)Selective greedy routingWireless Networks10.1007/s11276-014-0724-z20:7(1995-2017)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1007/s11276-014-0724-z
McAuley AKant LSinkar KGraff CPatel M(2012)Understanding the delay and loss tradeoffs in large wireless military networks using queuing analysis and MAC modelsMILCOM 2012 - 2012 IEEE Military Communications Conference10.1109/MILCOM.2012.6415811(1-6)Online publication date: Oct-2012
https://doi.org/10.1109/MILCOM.2012.6415811
Pinheiro BNascimento VLopes RCerqueira EAbelem A(2012)A fuzzy queue-aware routing approach for wireless mesh networksMultimedia Tools and Applications10.1007/s11042-011-0933-861:3(747-768)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1007/s11042-011-0933-8
Pinheiro BNascimento VGomes RCerqueira EAbelem A(2011)A Multimedia-Based Fuzzy Queue-Aware Routing Approach for Wireless Mesh Networks2011 Proceedings of 20th International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN.2011.6006076(1-7)Online publication date: Jul-2011
https://doi.org/10.1109/ICCCN.2011.6006076
Bruno RConti MPinizzotto A(2011)Routing Internet traffic in heterogeneous mesh networksPerformance Evaluation10.1016/j.peva.2011.01.00668:9(841-858)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1016/j.peva.2011.01.006
Ancillotti EBruno RConti MPinizzotto A(2011)Load-aware routing in mesh networksComputer Communications10.1016/j.comcom.2010.03.00434:8(948-961)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.comcom.2010.03.004
Kumar NChilamkurti NPark JPark D(2011)Load Balancing with Fair Scheduling for Multiclass Priority Traffic in Wireless Mesh NetworksFuture Information Technology10.1007/978-3-642-22333-4_12(101-109)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22333-4_12
Tragos EBrunoy RAncillottiz EGrochlaz KSiris V(2010)Automatically configured, optimised and QoS aware wireless mesh networks21st Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications10.1109/PIMRC.2010.5671649(2081-2086)Online publication date: Sep-2010
https://doi.org/10.1109/PIMRC.2010.5671649

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten