research-article

Practical service provisioning for wireless meshes

Authors:

Saumitra M. Das,

Dimitrios Koutsonikolas,

Y. Charlie HuAuthors Info & Claims

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

Article No.: 21, Pages 1 - 12

https://doi.org/10.1145/1364654.1364681

Published: 10 December 2007 Publication History

Abstract

Community wireless mesh networks (WMNs) are increasingly being deployed for providing cheap, low maintenance Internet access. For the successful adoption of WMNs as a last-mile technology, we argue that a guarantee of per-client fairness is critical. Specifically, WMNs should support a "bitrate-for-bucks" service model similar to other popular access technologies such as Cable/DSL.

We analyze the effectiveness of both off-the-shelf and theoretically optimal approaches towards providing such a service. We propose the APOLLO system that outperforms both these approaches.

APOLLO seamlessly integrates three synergistic components: theory-guided service planning and subscription, rate-based admission control to enforce the planned service, and a novel distributed light-weight fair scheduling scheme to deliver the admitted traffic. We evaluate APOLLO using simulations and testbed experiments.

References

[1]

I. Aad and C. Castellucia. Differentiation mechanisms for ieee 802.11. In Proc. of IEEE Infocom, 2001.

[2]

J. Bicket, D. Aguayo, S. Biswas, and R. Morris. Architecture and evaluation of an unplanned 802.11b mesh network. In Proc. of ACM MobiCom, 2005.

Digital Library

[3]

C. Bron and J. Kerbosch. Algorithm 457: Finding all cliques of an undirected graph. Commun. ACM, 16, 1973.

Digital Library

[4]

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

Digital Library

[5]

T. Clausen, P. Jacquet, C. Adjih, A. Laouiti, P. Minet, P. Muhlethaler, A. Qayyum, and L. Viennot. Optimized link state routing protocol (OLSR). RFC 3626, Oct 2003.

Digital Library

[6]

D. S. J. D. Couto, D. Aguayo, J. C. Bicket, and R. Morris. A high-throughput path metric for multi-hop wireless routing. In Proc. of ACM MobiCom, 2003.

Digital Library

[7]

S. M. Das, D. Koutsonikolas, Y. C. Hu, and D. Peroulis. Characterizing multi-way interference in wireless mesh networks. In Proc. of ACM WiNTECH 2006, 2006.

Digital Library

[8]

S. M. Das, H. Pucha, K. Papagiannaki, and Y. C. Hu. Studying wireless routing link dynamics. In Proc. of IMC, 2007.

Digital Library

[9]

R. Draves, J. Padhye, and B. Zill. Comparison of routing metrics for static multi-hop wireless networks. In Proc. of ACM SIGCOMM, 2004.

Digital Library

[10]

V. Gambiroza, B. Sadeghi, and E. W. Knightly. End-to-end performance and fairness in multihop wireless backhaul networks. In Proc. of ACM MobiCom, 2004.

Digital Library

[11]

K. Jain, J. Padhye, V. Padmanabhan, and L. Qiu. Impact of interference in multihop wireless network performance. In Proceedings of ACM Mobicom, 2003.

Digital Library

[12]

V. Kanodia, C. Li, A. Sabharwal, B. Sadeghi, and E. W. Knightly. Distributed multi-hop scheduling and medium access with delay and throughput constraints. In Proc. of ACM Mobicom, 2001.

Digital Library

[13]

V. Kanodia, C. Li, A. Sabharwal, B. Sadeghi, and E. W. Knightly. Distributed priority scheduling and medium access in ad hoc networks. ACM Wir. Ntws., 8, 2002.

Digital Library

[14]

S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft. Xors in the air: Practical wireless network coding. In Proc. of ACM SIGCOMM, August 2006.

Digital Library

[15]

H. Luo and S. Lu. A topology-independent fair queueing model in ad hoc wireless networks. In Proceedings of IEEE ICNP, 2000.

Digital Library

[16]

H. Luo, S. Lu, and V. Bharghavan. A new model for packet scheduling in multihop wireless networks. In Proc. of ACM MobiCom, 2000.

Digital Library

[17]

H. Luo, P. Medvedev, J. Cheng, and S. Lu. A self coordinating approach to distributed fair queueing in ad hoc wireless networks. In Proceedings of IEEE Infocom, 2001.

[18]

madwifi. http://madwifi.org.

[19]

R. Nelson and L. Kleinrock. Spatial TDMA: A colllision-free multihop channel access protocol. IEEE Transactions on communications, 33(9), 1985.

[20]

M. Neufeld, C. Doerr, J. Fifield, T. Weingart, D. C. Sicker, and D. Grunwald. Multimac: An adaptive mac framework for dynamic radio networking. In Proc. of DySPAN, 2005.

[21]

J. Padhye, S. Agarwal, V. Padmanabhan, L. Qiu, A. Rao, and B. Zill. Estimation of Link Interference in Static Multi-hop Wireless Networks. In Proceedings of IMC, 2005.

Digital Library

[22]

Y. Qu and A. Srinivasan. Multi-channel olsr with dedicated control interface. In Proc. of SPECTS, 2006.

[23]

QualNet. http://www.scalable-networks.com.

[24]

A. Rao and I. Stoica. An overlay mac layer for 802.11 networks. In Proceedings of Mobisys 2005, April 2005.

Digital Library

[25]

N. B. Salem and J.-P. Hubaux. A fair scheduling for wireless mesh networks. In Proc. of WiMesh, 2005.

[26]

J. Shi, T. Salonidis, and E. W. Knightly. Starvation mitigation through multi-channel coordination in csma multi-hop wireless networks. In Proc. of ACM MobiHoc, 2006.

Digital Library

[27]

S. M. Das, D. Koutsonikolas, and Y. C. Hu. Practical Service Provisioning for Wireless Meshes. Technical report, TR-ECE, Purdue University, November 2007.

[28]

A. P. Subramanian, M. M. Buddhikot, and S. C. Miller. Interference Aware Routing in Multi-Radio Wireless Mesh Networks. In Proc. of WiMesh, 2006.

[29]

N. Vaidya and P. Bahl. Fair scheudling in broadcast environments. Technical report, TR-99-61, Microsoft Research, Dec 1999.

[30]

S.-L. Wu, C.-Y. Lin, Y.-C. Tseng, and J.-P. Sheu. A new multi-channel mac protocol with on-demand channel assignment for multi-hop mobile ad hoc networks. In Proc. of I-SPAN, 2000.

Digital Library

[31]

X. Yang and N. H. Vaidya. Priority scheduling in wireless ad hoc networks. In Proceedings of ACM Mobihoc, 2002.

Digital Library

[32]

Champaign-Urbana community wireless network. http://www.cuwireless.net.

[33]

MIT Roofnet. http://www.pdos.lcs.mit.edu/roofnet.

[34]

http://www.engineering.purdue.edu/MESH.

[35]

Seattle wireless. http://www.seattlewireless.net.

Cited By

Das SPapagiannaki KBanerjee STay Y(2011)SWARMIEEE/ACM Transactions on Networking10.1109/TNET.2010.208906119:3(760-773)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2089061
Chiu HYeung K(2010)Maximizing Multicast Call Acceptance Rate in Multi-Channel Multi-Interface Wireless Mesh NetworksIEEE Transactions on Wireless Communications10.1109/TCOMM.2010.062310.0913239:8(2622-2631)Online publication date: Aug-2010
https://doi.org/10.1109/TCOMM.2010.062310.091323
Das SPapagiannaki KBanerjee STay YLiebeherr JVentre GBiersack EKeshav S(2009)SWARMProceedings of the 5th international conference on Emerging networking experiments and technologies10.1145/1658939.1658946(49-60)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1145/1658939.1658946

Index Terms

Practical service provisioning for wireless meshes
1. Networks
  1. Network architectures

Recommendations

Inter-AP coordination for fair throughput in infrastructure-based IEEE 802.11 mesh networks
IWCMC '06: Proceedings of the 2006 international conference on Wireless communications and mobile computing

This paper studies throughput fairness among different basic service sets (BSSs) in infrastructure-based IEEE 802.11 mesh networks, where inter-BSS interference is unavoidable because of the difficulty in frequency and coverage planning and the limited ...
A Distributed End-to-End Reservation Protocol for IEEE 802.11-Based Wireless Mesh Networks

This paper presents an end-to-end reservation protocol for quality-of-service (QoS) support in the medium access control layer of wireless multihop mesh networks. It reserves periodically repeating time slots for QoS-demanding applications, while ...
Adaptive Distributed Time-Slot Based Scheduling for Fairness in Multi-Hop Wireless Networks
ICDCS '08: Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems

Recent research indicates that multi-hop wireless networks can suffer from extreme imbalances in the throughput achieved by simultaneous competing flows. We address this problem by designing a practical distributed algorithm to compute a time-slot based ...

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

Author Tags

Qualifiers

Research-article

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
185
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Das SPapagiannaki KBanerjee STay Y(2011)SWARMIEEE/ACM Transactions on Networking10.1109/TNET.2010.208906119:3(760-773)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2089061
Chiu HYeung K(2010)Maximizing Multicast Call Acceptance Rate in Multi-Channel Multi-Interface Wireless Mesh NetworksIEEE Transactions on Wireless Communications10.1109/TCOMM.2010.062310.0913239:8(2622-2631)Online publication date: Aug-2010
https://doi.org/10.1109/TCOMM.2010.062310.091323
Das SPapagiannaki KBanerjee STay YLiebeherr JVentre GBiersack EKeshav S(2009)SWARMProceedings of the 5th international conference on Emerging networking experiments and technologies10.1145/1658939.1658946(49-60)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1145/1658939.1658946

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