Name
Title | ||
|---|---|---|
Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks |
Abstract | ||
|---|---|---|
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 an d accurately predicts per-flow throughput in a large-scale ne twork. 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. I. I NTRODUCTION as it also enables using the model in applications related to admission control and analysis of rate-control mechanisms. Starvation manifests as a throughput distribution in which a few dominating flows receive very high throughput and many starving flows receive very low (sometimes zero) throughput . Flow starvation is naturally captured by our model as extended periods of carrier sensing or high packet loss probability o r both. We show that such effects are not due to a particular CSMA protocol such as IEEE 802.11 but rather have their foundations in a generic coordination problem of CSMA random access when applied to multi-hop wireless networks, and in the use of carrier sense itself. To evaluate any solution to the starvation problem we must be able to quantify the effect of the MAC-related starvation problem on the throughput distribution. As different solutions can produce radically different per-flow throughput distri bu- tions, we show that traditional metrics such as aggregate utility are not sufficient to quantify starvation. Instead, we utili ze Lorenz curves and the Gini index, used in the economics literature to quantify a society's distribution of wealth t o indi- viduals, to evaluate the network's distribution of through put to flows. These metrics, as well as new metrics including flow- preference graphs, a "poverty index," and a "disproportionality index" accurately capture throughput inequalities caused by a specific protocol solution; they also distinguish starvat ion effects due to lack of coordination from inherent throughput imbalances due to differences in the number of contending neighbors. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/TNET.2007.902687 | IEEE\/ACM Transactions on Networking |
Keywords | Field | DocType |
Throughput,Multiaccess communication,Spread spectrum communication,Wireless networks,Access protocols,Analytical models,Network topology,Computer networks,Large-scale systems,Media Access Protocol | Wireless network,Computer science,Flow (psychology),Computer network,Network topology,Throughput,Hop (networking),Distributed computing,Spread spectrum | Journal |
Volume | Issue | ISSN |
16 | 4 | 0743-166X |
ISBN | Citations | PageRank |
1-4244-0221-2 | 204 | 9.85 |
References | Authors | |
34 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michele Garetto | 1 | 1228 | 65.57 |
| Theodoros Salonidis | 2 | 1247 | 93.31 |
| Edward W. Knightly | 3 | 4763 | 371.38 |