Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks

被引:116
作者
Garetto, Michele [1 ]
Salonidis, Theodoros [2 ]
Knightly, Edward W. [3 ]
机构
[1] Univ Torino, Dept Comp Sci, I-10149 Turin, Italy
[2] Thomson Paris Res Lab, F-92648 Boulogne, France
[3] Rice Univ, Dept Elect & Comp Engn, Houston, TX 77005 USA
关键词
CSMA; CSMA/CA; fairness; wireless networks;
D O I
10.1109/TNET.2007.902687
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Multi-hop wireless networks employing random access protocols have been shown to incur large discrepancies in the throughputs achieved by the flows sharing the network. Indeed, flow throughputs can span orders of magnitude from near starvation to many times greater than the mean. In this paper, we address the foundations of this disparity. We show that the fundamental cause is not merely differences in the number of contending neighbors, but a generic coordination problem of CSMA-based random access in a multi-hop environment. We develop a new analytical model that incorporates this lack of coordination, identifies dominating and starving flows and accurately predicts per-flow throughput in a large-scale network. We then propose metrics that quantify throughput imbalances due to the MAC protocol operation. Our model and metrics provide a deeper understanding of the behavior of CSMA protocols in arbitrary topologies and can aid the design of effective protocol solutions to the starvation problem.
引用
收藏
页码:864 / 877
页数:14
相关论文
共 50 条
[41]   Stable routing scheduling algorithms in multi-hop wireless networks [J].
Cholvi, Vicent ;
Garncarek, P. ;
Jurdzinski, T. ;
Kowalski, Dariusz R. .
THEORETICAL COMPUTER SCIENCE, 2022, 921 :20-35
[42]   Distributed node location in clustered multi-hop wireless networks [J].
Mitton, N ;
Fleury, E .
TECHNOLOGIES FOR ADVANCED HETEROGENEOUS NETWORKS, PROCEEDINGS, 2005, 3837 :112-127
[43]   Approaching Optimal Broadcast Efficiency in Multi-Hop Wireless Networks [J].
Liu, Jingyong ;
Jingi, Xiaorong ;
Li, Lemin ;
Zhang, Tianqi .
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2009, E92A (11) :2949-2954
[44]   Throughput Modeling of Single Hop CSMA Networks with Non-Negligible Propagation Delay [J].
Koseoglu, Mehmet ;
Karasan, Ezhan .
IEEE TRANSACTIONS ON COMMUNICATIONS, 2013, 61 (07) :2911-2923
[45]   Low Complexity Multi-layer Optimization for Multi-hop Wireless Networks [J].
Shi, Yi ;
Sagduyu, Yalin E. ;
Li, Jason H. .
2012 IEEE MILITARY COMMUNICATIONS CONFERENCE (MILCOM 2012), 2012,
[46]   Adaptive CSMA for Decentralized Scheduling of Multi-Hop Networks With End-to-End Deadline Constraints [J].
Singh, Rahul ;
Kumar, P. R. .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2021, 29 (03) :1224-1237
[47]   A Novel Approximation for Multi-Hop Connected Clustering Problem in Wireless Networks [J].
Gao, Xiaofeng ;
Zhu, Xudong ;
Li, Jun ;
Wu, Fan ;
Chen, Guihai ;
Du, Ding-Zhu ;
Tang, Shaojie .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2017, 25 (04) :2223-2234
[48]   Optimal resource allocation for multicast sessions in multi-hop wireless networks [J].
Bui, By Loc ;
Srikant, R. ;
Stolyar, Alexander .
PHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 2008, 366 (1872) :2059-2074
[49]   Delay-aware TDMA Scheduling for Multi-Hop Wireless Networks [J].
Chilukuri, Shanti ;
Sahoo, Anirudha .
PROCEEDINGS OF THE 16TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING, 2015,
[50]   Distributed SINR based Scheduling Algorithm for Multi-hop Wireless Networks [J].
Ryu, Jiho ;
Joo, Changhee ;
Kwon, Ted 'Taekyoung' ;
Shroff, Ness B. ;
Choi, Yanghee .
MSWIM 2010: PROCEEDINGS OF THE 13TH ACM INTERNATIONAL CONFERENCE ON MODELING, ANALYSIS, AND SIMULATION OF WIRELESS AND MOBILE SYSTEMS, 2010, :376-+