research-article

Joint MAC-aware routing and load balancing in mesh networks

Authors:

Henrik Lundgren,

Francois Baccelli,

Christophe DiotAuthors Info & Claims

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

Article No.: 19, Pages 1 - 12

https://doi.org/10.1145/1364654.1364679

Published: 10 December 2007 Publication History

Abstract

Past approaches to routing in mesh networks either (i) do not account for the MAC-layer interactions between the links in a tractable manner, or (ii) are agnostic to load-balancing across gateways. Our answer to these problems is MaLB (MAC-aware and Load Balanced routing algorithm), a greedy, tractable, and distributed mesh routing algorithm. Since the underlying objective function has high combinatorial complexity, MaLB uses a greedy approach. MaLB finds an optimum routing forest (union of trees rooted at the gateways) by taking into account MAC-layer interaction between links, as well as optimum multi-hop association of mesh nodes to gateways. MaLB builds on top of ETP (Expected Through-Put), a recently proposed MAC-aware routing metric. We also propose a low complexity variant of MaLB called LB (Load Balanced routing algorithm) which performs load balancing in a MAC-agnostic manner. MaLB performs especially well in networks with skewed topologies that result from unplanned mesh network deployment, as well as in the presence of gateway failures. Simulations with an enhanced version of ns-2 show that MaLB results in up to 60% higher throughput than a shortest path algorithm with ETX (Expected Transmission Count). Furthermore, MaLB results in up to 30% improvement over the LB algorithm, as well as a shortest path algorithm with ETT (Expected Transmission Time).

References

[1]

J Bicket, D. Aguayo, S. Biswas, and R. Morris. Architecture and evaluation of an unplanned 802.11b mesh network. In ACM Mobicom 2005, August 2005. Cologne, Germany.

Digital Library

[2]

J. Camp, J. Robinson, C. Steger, and E. Knightly. Measurement driven deployment of a two-tier urban mesh access network. In ACM MobiSys 2006, June 2006. Uppsala, Sweden.

Digital Library

[3]

M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda. Performance anomaly of 802.11b. In IEEE Infocom 2003, March 2003. San Francisco, California.

[4]

D S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris. A high-throughput path metric formulti-hop wireless routing. In ACM Mobicom 2003, September 2003. San Diego, California, USA.

Digital Library

[5]

R. Draves J Padhye and B. Zill. Routing in multi-radio, multi-hop wireless mesh networks. In ACM MobiCom 2004, September 2004. Philadelphia, Pennsylvania, USA.

Digital Library

[6]

V Mhatre, H. Lundgren, and C. Diot. Mac-aware routing in wireless mesh networks. In IEEE/IFIP WONS 2007, January 2007. Obergurgl, Austria.

[7]

J C. Park and S. Kasera. Expected data rate: An accurate high-throughput path metric for multi-hop wireless routing. In IEEE Secon 2005, 2005. Santa Clara, California, USA.

[8]

Y Yang, J. Wang, and R. Kravets. Interference-aware load balancing for multihop wireless networks. Technical Report UIUCDCS-R-2005-2526, Department of Computer Science, University of Illinois at Urbana-Champaign, 2005.

[9]

http://www.netequality.net.

[10]

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

Digital Library

[11]

C Newport, D. Kotz, R. S., Gray J. Liu, Y. Yuan, and C. Elliott. Experimental evaluation of wireless simulation assumptions. SIMULATION: Transactions of The Society for Modeling and Simulation International, April 2007. To appear.

Digital Library

[12]

J L. Sobrinho. Algebra and algorithms for qos path computation and hop-by-hop routing in the internet. In IEEE Infocom 2001, April 2001. Anchorage, Alaska, USA.

[13]

J He, J. Chen, and S. H. Gary Chan. Extending wlan coverage using infrastructureless access points. In HPSR 2005, May 2005.

[14]

B Kauffmann, F. Baccelli, A. Chaintreau, V. Mhatre, D. Papagiannaki, and C. Diot. Measurement-based self organization of interfering 802.11 wireless access networks anchorage. In IEEE Infocom 2007, May 2007. Alaska, USA.

[15]

Y Gao, J. Lui, and D. M. Chiu. Determining the end-to-end throughput capacity in multi-hop networks: Methodology and applications. In ACM Sigmetrics 2006, June 2006. Saint Malo, France.

Digital Library

[16]

K. Ramachandran, I. Sheriff, E. Belding-Royer, and K. Almeroth. Routing stability in static wireless mesh networks. In Passive and Active Measurement Conference, April 2007. Louvain-la-neuve, Belgium.

Digital Library

[17]

R Chandra, J. Padhye, L. Ravindranath, and A. Wolman. Beacon-stuffing: Wi-fi without associations. In IEEE Hotmobile 2007, February 2007. Tucson, AZ, USA.

Digital Library

[18]

V Mhatre. Enhanced wireless mesh networking for ns-2 simulator. ACM SIGCOMM Computer Communications Review, July 2007. (editorial).

Digital Library

[19]

E Perahia and D. Cox. Shadow fading correlation between uplink and downlink. In IEEE VTC 2001, May 2001. Rhodes, Greece.

[20]

R Draves, J. Padhye, and B. Zill. Comparison of routing metrics for static multi-hop wireless networks. In ACM Sigcomm 2004, August 2004. Portland, Oregon, USA.

Digital Library

Cited By

Miao YVural SSun ZWang N(2016)A Unified Solution for Gateway and In-Network Traffic Load Balancing in Multihop Data Collection ScenariosIEEE Systems Journal10.1109/JSYST.2015.245767410:3(1251-1262)Online publication date: Sep-2016
https://doi.org/10.1109/JSYST.2015.2457674
Wang HChin KSoh S(2016)On Minimizing Data Forwarding Schedule in Multi Transmit/Receive Wireless Mesh NetworksIEEE Access10.1109/ACCESS.2016.25530484(1570-1582)Online publication date: 2016
https://doi.org/10.1109/ACCESS.2016.2553048
Capdehourat GLarroca FBelzarena P(2014)Optimal multipath forwarding in planned Wireless Mesh NetworksComputer Communications10.1016/j.comcom.2013.10.00738(36-49)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1016/j.comcom.2013.10.007
Show More Cited By

Joint MAC-aware routing and load balancing in mesh networks
1. Networks
  1. Network types

Recommendations

Load aware traffic engineering for mesh networks

Wireless Mesh Network (WMN) is a multi-hop mesh network that consists of mesh routers and mesh clients, where mesh routers are static and form the backbone of the mesh network. The static nature of mesh nodes imposes requirements for designing routing ...
Route-Aware Load-Balanced Resource Allocation for Wireless Mesh Networks
Proceedings of the 2007 IEEE Wireless Communications and Networking Conference

Multi-channel wireless mesh networks (WMNs) aim to perform ubiquitous wireless broadband network access. In WMNs, much attention has been paid to the problem of resource allocation, i.e., how to utilize multiple orthogonal channels and multiple ...
Efficient Load-Aware Routing Scheme for Wireless Mesh Networks

This paper proposes a load-aware routing scheme for wireless mesh networks (WMNs). In a WMN, the traffic load tends to be unevenly distributed over the network. In this situation, the load-aware routing scheme can balance the load, and consequently, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

December 2007

448 pages

ISBN:9781595937704

DOI:10.1145/1364654

General Chairs:
Jim Kurose
University of Massachusetts
,
Henning Schulzrinne
Columbia University

Copyright © 2007 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

Alcatel-Lucent
SIGCOMM: ACM Special Interest Group on Data Communication
Thomson
CISCO
IMDEA
IBM: IBM

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 December 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
451
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Miao YVural SSun ZWang N(2016)A Unified Solution for Gateway and In-Network Traffic Load Balancing in Multihop Data Collection ScenariosIEEE Systems Journal10.1109/JSYST.2015.245767410:3(1251-1262)Online publication date: Sep-2016
https://doi.org/10.1109/JSYST.2015.2457674
Wang HChin KSoh S(2016)On Minimizing Data Forwarding Schedule in Multi Transmit/Receive Wireless Mesh NetworksIEEE Access10.1109/ACCESS.2016.25530484(1570-1582)Online publication date: 2016
https://doi.org/10.1109/ACCESS.2016.2553048
Capdehourat GLarroca FBelzarena P(2014)Optimal multipath forwarding in planned Wireless Mesh NetworksComputer Communications10.1016/j.comcom.2013.10.00738(36-49)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1016/j.comcom.2013.10.007
Kumar NChilamkurti NPark JPark D(2013)Load balancing and adaptive scheduling for data intensive prioritised traffic in multi-radio multi-channel wireless mesh networksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2013.05137712:1(3-13)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1504/IJAHUC.2013.051377
Kim TJakllari GKrishnamurthy SFaloutsos M(2013)An integrated routing and rate adaptation framework for multi-rate multi-hop wireless networksWireless Networks10.1007/s11276-012-0513-519:5(985-1003)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1007/s11276-012-0513-5
Bruno R(2013)Quality of Service in Mesh NetworksMobile Ad Hoc Networking10.1002/9781118511305.ch8(275-314)Online publication date: 4-Mar-2013
https://doi.org/10.1002/9781118511305.ch8
Laufer RVelloso PVieira LKleinrock L(2012)PLASMA: A new routing paradigm for wireless multihop networks2012 Proceedings IEEE INFOCOM10.1109/INFCOM.2012.6195683(2706-2710)Online publication date: Mar-2012
https://doi.org/10.1109/INFCOM.2012.6195683
Galvez JRuiz PSkarmeta A(2012)Responsive on-line gateway load-balancing for wireless mesh networksAd Hoc Networks10.1016/j.adhoc.2011.06.00210:1(46-61)Online publication date: Jan-2012
https://doi.org/10.1016/j.adhoc.2011.06.002
Kim TJakllari GKrishnamurthy SFaloutsos M(2011)A Unified Metric for Routing and Rate Adaptation in Multi-Rate Wireless Mesh NetworksProceedings of the 2011 IEEE Eighth International Conference on Mobile Ad-Hoc and Sensor Systems10.1109/MASS.2011.31(242-251)Online publication date: 17-Oct-2011
https://dl.acm.org/doi/10.1109/MASS.2011.31
Ancillotti EBruno RConti M(2011)TALBProceedings of the 2011 IEEE Eighth International Conference on Mobile Ad-Hoc and Sensor Systems10.1109/MASS.2011.20(75-81)Online publication date: 17-Oct-2011
https://dl.acm.org/doi/10.1109/MASS.2011.20
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten