research-article

XPRESS: a cross-layer backpressure architecture for wireless multi-hop networks

Authors:

Theodoros Salonidis,

Henrik Lundgren,

Pascal Le GuyadecAuthors Info & Claims

MobiCom '11: Proceedings of the 17th annual international conference on Mobile computing and networking

Pages 49 - 60

https://doi.org/10.1145/2030613.2030620

Published: 19 September 2011 Publication History

Abstract

Contemporary wireless multi-hop networks operate much below their capacity due to the poor coordination among transmitting nodes. In this paper we present XPRESS, a cross-layer backpressure architecture designed to reach the full capacity of wireless multi-hop networks. Instead of a collection of poorly coordinated wireless routers, XPRESS turns a mesh network into a wireless switch. Transmissions over the network are scheduled using a throughput-optimal backpressure algorithm. Realizing this theoretical concept entails several challenges, which we identify and address with a cross-layer design and implementation on top of our wireless hardware platform. In contrast to previous work, we implement and evaluate backpressure scheduling over a TDMA MAC protocol, as it was originally proposed in theory. Our experiments in an indoor testbed show that XPRESS can yield up to 128% throughput gains over 802.11.

Supplementary Material

JPG File (mobicom_2_2.jpg)

Download
16.23 KB

MP4 File (mobicom_2_2.mp4)

Download
157.85 MB

References

[1]

N. Ahmed, U. Ismail, S. Keshav, and K. Papagiannaki. Online Estimation of RF Interference. In Proc. ACM CoNEXT, Dec. 2008.

Digital Library

[2]

U. Akyol, M. Andrews, P. Gupta, J. Hobby, I. Saniee, and A. Stolyar. Joint Scheduling and Congestion Control in Mobile Ad-Hoc Networks. In Proc. IEEE INFOCOM, Apr. 2008.

[3]

A. Aziz, D. Starobinski, P. Thiran, and A. ElFawal. EZ-Flow: Removing Turbulence in IEEE 802.11 Wireless Mesh Networks without Message Passing. In Proc. ACM CoNEXT, Dec. 2009.

Digital Library

[4]

L. Chen, S. Low, M. Chiang, and J. Doyle. Cross-Layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless Networks. In Proc. IEEE INFOCOM, Apr. 2006.

[5]

Y.-C. Cheng, J. Bellardo, P. Benkö, A. Snoeren, G. Voelker, and S. Savage. Jigsaw: Solving the Puzzle of Enterprise 802.11 Analysis. In Proc. ACM SIGCOMM, 2006.

Digital Library

[6]

Atilla Eryilmaz and R. Srikant. Joint Congestion Control, Routing, and MAC for Stability and Fairness in Wireless Networks. IEEE Journal on Sel. Areas in Comm., 24(8):1514--1524, Aug. 2006.

Digital Library

[7]

iperf. http://dast.nlanr.net/projects/iperf.

[8]

F. Kelly, A. Maulloo, and D. Tan. Rate Control in Communication Networks: Shadow Prices, Proportional Fairness and Stability. Journal of the Operational Research Society, 49:237--252, 1998.

[9]

D. Koutsonikolas, T. Salonidis, H. Lundgren, P. LeGuyadec, C. Hu, and I. Sheriff. TDM MAC Protocol Design and Implementation for Wireless Mesh Networks. In Proc. ACM CoNEXT, Dec. 2008.

Digital Library

[10]

J. Lee, J. Ryu, S. Lee, and T. Kwon. Improved Modeling of IEEE 802.11a PHY through Fine-grained Measurements. Computer Networks, 54(4), Mar. 2009.

Digital Library

[11]

X. Lin and N. B. Shroff. Joint Rate Control and Scheduling in Multihop Wireless Networks. In CDC, Dec. 2004.

[12]

X. Lin and N. B. Shroff. The Impact of Imperfect Scheduling on Cross-Layer Congestion Control in Wireless Networks . IEEE Transactions on Networking, 14(2):302--315, Apr. 2006.

Digital Library

[13]

X. Liu, A. Sheth, M. Kaminsky, K. Papagiannaki, S. Seshan, and P. Steenkiste. DIRC: Increasing Indoor Wireless Capacity Using Directional Antennas. In Proc. ACM SIGCOMM, Aug. 2009.

Digital Library

[14]

R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Analyzing the Mac-Level Behavior of Wireless Networks in the Wild. In Proc. ACM SIGCOMM, Aug. 2006.

Digital Library

[15]

K. Makino and T. Uno. New algorithms for enumerating all maximal cliques. In In Proc. 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, Jul. 2004.

[16]

S. Moeller, A. Sridharan, B. Krishnamachari, and O. Gnawali. Routing Without Routes: The Backpressure Collection Protocol. In Proc. IEEE/ACM IPSN, Apr. 2010.

Digital Library

[17]

J. Padhye, S. Agarwal, V. Padmanabhan, L. Qiu, A. Rao, and B. Zill. Estimation of Link Interference in Static Multi-hop Wireless Networks. In Proc. ACM Internet Measurement Conference (IMC), Oct. 2005.

Digital Library

[18]

L. Qiu, Y. Zhang, F. Wang, M. Han, and R. Mahajan. A General Model of Wireless Interference. In Proc. ACM MobiCom, Oct. 2007.

Digital Library

[19]

B. Radunovic and Jean-Yves Le Boudec. Rate Performance Objectives of Multihop Wireless Networks. IEEE Transactions on Mobile Computing, 3(4):334--349, 2004.

Digital Library

[20]

B. Radunovic, C. Gkantsidis, D. Gunawardena, and P. Key. Horizon: Balancing TCP over Multiple Paths in Wireless Mesh Network. In Proc. ACM MobiCom, Sep. 2008.

Digital Library

[21]

C. Reis, R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Measurement-Based Models of Delivery and Interference. In Proc. ACM SIGCOMM, Sep. 2006.

Digital Library

[22]

J. Ryu, V. Bhargava, N. Paine, and S. Shakkottai. Back-Pressure Routing and Rate Control for ICNs. In Proc. ACM MobiCom, Sep. 2010.

Digital Library

[23]

V. Shrivastava, N. Ahmed, S. Rayanchu, S. Banerjee, S. Keshav, K. Papagiannaki, and A. Mishra. CENTAUR: Realizing the Full Potential of Centralized WLANs through a Hybrid Data Path. In Proc. ACM MobiCom, Sep. 2009.

Digital Library

[24]

L. Tassiulas and A. Ephremides. Stability Properties of Constrained Queuing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks. IEEE Transactions on Automatic Control, 37(12):1936--1948, Dec. 1992.

[25]

M. Vutukuru, K. Jamieson, and H. Balakrishnan. Harnessing Exposed Terminals in Wireless Networks. In Proc. NSDI, Apr. 2008.

Digital Library

[26]

P. Wang. Throughput Optimization of Urban Wireless Mesh Network. In Ph.D. Thesis, Department of Electrical and Computer Engineering, University of Delaware, 2009.

Digital Library

[27]

A. Warrier, S. Janakiraman, S. Ha, and I. Rhee. DiffQ: Practical Differential Backlog Congestion Control for Wireless Networks. In Proc. IEEE INFOCOM, Apr. 2009.

Cited By

Stahlbuhk TDeutsch PKelly DCipolle DWong TBartlett WHood K(2022)Robust Network Protocols for Large Swarms of Small UAVs2022 IEEE Aerospace Conference (AERO)10.1109/AERO53065.2022.9843316(1-18)Online publication date: 5-Mar-2022
https://doi.org/10.1109/AERO53065.2022.9843316
Kafetzis DVassilaras SVardoulias GKoutsopoulos I(2022)Software-Defined Networking Meets Software-Defined Radio in Mobile ad hoc Networks: State of the Art and Future DirectionsIEEE Access10.1109/ACCESS.2022.314407210(9989-10014)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3144072
Yau SHsieh PBhattacharyya RBhargav KShakkottai SHou IKumar P(2018)PULSProceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/3209582.3209609(261-270)Online publication date: 26-Jun-2018
https://dl.acm.org/doi/10.1145/3209582.3209609
Show More Cited By

Index Terms

XPRESS: a cross-layer backpressure architecture for wireless multi-hop networks
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

A cross-layer backpressure architecture for wireless multihop networks

Contemporary wireless multihop networks operate much below their capacity due to the poor coordination among transmitting nodes. In this paper, we present XPRESS, a cross-layer backpressure architecture designed to reach the capacity of wireless multihop ...
CSMA/CCA: a modified CSMA/CA protocol mitigating the fairness problem for IEEE 802.11 DCF

Carrier sense multiple access with collision avoidance (CSMA/CA) has been adopted by the IEEE 802.11 standards for wireless local area networks (WLANs). Using a distributed coordination function (DCF), the CSMA/CA protocol reduces collisions and ...
EBA: An Enhancement of the IEEE 802.11 DCF via Distributed Reservation

The IEEE 802.11 standard for Wireless Local Area Networks (WLANs) employs a Medium Access Control (MAC), called Distributed Coordination Function (DCF), which is based on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). The collision ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiCom '11: Proceedings of the 17th annual international conference on Mobile computing and networking

September 2011

362 pages

ISBN:9781450304924

DOI:10.1145/2030613

General Chair:
Parmesh Ramanathan
University of Wisconsin, Madison
,
Program Chairs:
Thyaga Nandagopal
Bell Laboratories, Alcatel-Lucent
,
Brian Levine
University of Massachusetts, Amherst

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

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 September 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

backpressure scheduling and routing

Qualifiers

Research-article

Conference

Mobicom'11

Sponsor:

SIGMOBILE

Mobicom'11: The 17th Annual International Conference on Mobile Computing and Networking

September 19 - 23, 2011

Nevada, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 440 of 2,972 submissions, 15%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
824
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Stahlbuhk TDeutsch PKelly DCipolle DWong TBartlett WHood K(2022)Robust Network Protocols for Large Swarms of Small UAVs2022 IEEE Aerospace Conference (AERO)10.1109/AERO53065.2022.9843316(1-18)Online publication date: 5-Mar-2022
https://doi.org/10.1109/AERO53065.2022.9843316
Kafetzis DVassilaras SVardoulias GKoutsopoulos I(2022)Software-Defined Networking Meets Software-Defined Radio in Mobile ad hoc Networks: State of the Art and Future DirectionsIEEE Access10.1109/ACCESS.2022.314407210(9989-10014)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3144072
Yau SHsieh PBhattacharyya RBhargav KShakkottai SHou IKumar P(2018)PULSProceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/3209582.3209609(261-270)Online publication date: 26-Jun-2018
https://dl.acm.org/doi/10.1145/3209582.3209609
Chen YWang XCai L(2017)Head-of-Line Access Delay-Based Scheduling Algorithm for Flow-Level DynamicsIEEE Transactions on Vehicular Technology10.1109/TVT.2016.262532666:6(5387-5397)Online publication date: Jun-2017
https://doi.org/10.1109/TVT.2016.2625326
Lu ZSagduyu YLi J(2017)Securing the Backpressure Algorithm for Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2016.258216116:4(1136-1148)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2582161
Soltani SSagduyu YScanlon SShi YLi JFeldman JMatyjas J(2017)Joint network coding and backpressure algorithm for cognitive radio networksMILCOM 2017 - 2017 IEEE Military Communications Conference (MILCOM)10.1109/MILCOM.2017.8170819(858-863)Online publication date: Oct-2017
https://doi.org/10.1109/MILCOM.2017.8170819
Sim GLi RCano CMalone DPatras PWidmer J(2016)Learning from experience: Efficient decentralized scheduling for 60GHz mesh networks2016 IEEE 17th International Symposium on A World of Wireless, Mobile and Multimedia Networks (WoWMoM)10.1109/WoWMoM.2016.7523520(1-9)Online publication date: Jun-2016
https://doi.org/10.1109/WoWMoM.2016.7523520
Xu WSun FShi Q(2016)Modular and Asynchronous Backpressure in Multihop Networks: Model and OptimizationIEEE Transactions on Vehicular Technology10.1109/TVT.2016.2603534(1-1)Online publication date: 2016
https://doi.org/10.1109/TVT.2016.2603534
Zhou ALiu MLi ZDutkiewicz E(2016)Joint Traffic Splitting, Rate Control, Routing, and Scheduling Algorithm for Maximizing Network Utility in Wireless Mesh NetworksIEEE Transactions on Vehicular Technology10.1109/TVT.2015.242709165:4(2688-2702)Online publication date: Apr-2016
https://doi.org/10.1109/TVT.2015.2427091
Seferoglu HModiano E(2016)Separation of routing and scheduling in backpressureIEEE/ACM Transactions on Networking10.1109/TNET.2015.243621724:3(1787-1800)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2436217
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.

Media

Figures

Other

Tables

View Table of Contents