article

Insensitivity and stability of random-access networks

Authors:

P. M. van de Ven,

J. S. H. van Leeuwaarden,

A. ProutièreAuthors Info & Claims

Performance Evaluation, Volume 67, Issue 11

Pages 1230 - 1242

https://doi.org/10.1016/j.peva.2010.08.011

Published: 01 November 2010 Publication History

Abstract

Random-access algorithms such as the Carrier-Sense Multiple-Access (CSMA) protocol provide a popular mechanism for distributed medium access control in large-scale wireless networks. In recent years, fairly tractable models have been shown to yield remarkably accurate throughput estimates for CSMA networks. These models typically assume that both the transmission durations and the back-off periods are exponentially distributed. We show that the stationary distribution of the system is in fact insensitive with respect to the transmission durations and the back-off times. These models primarily pertain to a saturated scenario where nodes always have packets to transmit. In reality however, the buffers may occasionally be empty as packets are randomly generated and transmitted over time. The resulting interplay between the activity states and the buffer contents gives rise to quite complicated queueing dynamics, and even establishing the stability criteria is usually a serious challenge. We explicitly identify the stability conditions in a few relevant scenarios, and illustrate the difficulties arising in other cases.

References

[1]

}}X. Wang, K. Kar, Throughput modeling and fairness issues in CSMA/CA based ad-hoc networks, in: Proc. Infocom 2005, Miami FL, March 13-17, 2005.

[2]

}}M. Durvy, O. Dousse, P. Thiran, Border effects, fairness, and phase transitions in large wireless networks, in: Proc. Infocom 2008, Phoenix AZ, April 13-18, 2008, pp. 601-609.

[3]

}}Durvy, M., Dousse, O. and Thiran, P., On the fairness of large CSMA networks. IEEE J. Sel. Areas Commun. v27 i7. 1093-1104.

[4]

}}M. Durvy, P. Thiran, A packing approach to compare slotted and non-slotted medium access control, in: Proc. Infocom 2006, Barcelona, Spain, April 23-26, 2006.

[5]

}}M. Durvy, O. Dousse, P. Thiran, Modeling the 802.11 protocol under different capture and sensing capabilities, in: Proc. Infocom 2007, Anchorage AK, May 6-12, 2007, pp. 2356-2360.

[6]

}}Garetto, M., Salonidis, T. and Knightly, E.W., Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks. IEEE/ACM Trans. Netw. v16 i4. 864-877.

[7]

}}K. Medepalli, F.A. Tobagi, Towards performance modeling of IEEE 802.11 based wireless networks: a unified framework and its applications, in: Proc. Infocom 2006, Barcelona, Spain, April 23-26, 2006.

[8]

}}R.R. Boorstyn, A. Kershenbaum, Throughput analysis of multihop packet radio, in: Proc. ICC, 1980, pp. 1361-1366.

[9]

}}Boorstyn, R.R., Kershenbaum, A., Maglaris, B. and Sahin, V., Throughput analysis in multihop CSMA packet radio networks. IEEE Trans. Commun. v35. 267-274.

[10]

}}Kelly, F.P., Stochastic models of computer communication systems. J. Roy. Stat. Soc. B. v47 i3. 379-395.

[11]

}}Kershenbaum, A., Boorstyn, R.R. and Chen, M., An algorithm for evaluation of throughput in multihop packet radio networks with complex topologies. IEEE J. Sel. Areas Commun. v5 i6. 1003-1012.

[12]

}}Kelly, F.P., Reversibility and Stochastic Networks. 1979. Wiley, Chichester.

[13]

}}Kelly, F.P., One-dimensional circuit-switched networks. Ann. Probab. v15 i3. 1166-1179.

[14]

}}Kelly, F.P., Loss networks. Ann. Appl. Probab. v1 i3. 319-378.

[15]

}}Suhov, Y. and Rozikov, U.A., A hard-core model on a Cayley tree: An example of a loss network. Queueing Syst. v46 i1-2. 197-212.

[16]

}}Zachary, S. and Ziedins, I., Loss networks and Markov random fields. J. Appl. Probab. v36 i2. 403-414.

[17]

}}Bianchi, G., Performance analysis of the IEEE 802.11 distributed coordination function. IEEE J. Sel. Areas Commun. v18 i3. 535-547.

[18]

}}Liew, S.C., Kai, C., Leung, J. and Wong, B., Back-of-the-envelope computation of throughput distributions in CSMA wireless networks. IEEE Trans. Mob. Comp. v9 i9. 1319-1331.

[19]

}}L. Jiang, D. Shah, J. Shin, J. Walrand, Distributed random access algorithm: scheduling and congestion control, IEEE Trans. Inform. Theory, 2010 (in press).

[20]

}}Jiang, L. and Walrand, J., A distributed CSMA algorithm for throughput and utility maximization in wireless networks. IEEE/ACM Trans. Netw. v18 i3. 960-972.

[21]

}}J. Liu, Y. Yi, A. Proutière, M. Chiang, H.V. Poor, Maximizing utility via random access without message passing, Technical report MSR-TR-2008-128, Microsoft Research, 2008.

[22]

}}P. Marbach, A. Eryilmaz, A backlog-based CSMA mechanism to achieve fairness and throughput-optimality in multihop wireless networks, in: Proc. 46th Annual Allerton Conf. Commun., Control, Comput., 2008.

[23]

}}S. Rajagopalan, D. Shah, J. Shin, Network adiabatic theorem: an efficient randomized protocol for content resolution, in: Proc. ACM SIGMETRICS/Performance 2009, Seattle WA, June 15-19, 2009, pp. 133-144.

[24]

}}S. Rajagopalan, D. Shah, J. Shin, Aloha that works, 2009, Preprint.

[25]

}}T. Bonald, The Erlang model with non-Poisson call arrivals, in: Proc. ACM SIGMETRICS/Performance 2006, Saint-Malo, France, June 26-30, 2006, pp. 276-286.

Digital Library

[26]

}}Fricker, C. and Jaibi, M.R., Monotonicity and stability of periodic polling models. Queueing Syst. v15. 211-238.

[27]

}}Borst, S.C., Boxma, O.J. and Jelenković, P.R., Reduced-load equivalence and induced burstiness in GPS queues with long-tailed traffic flows. Queueing Syst. v43 i4. 273-306.

[28]

}}Lelarge, M., Asymptotic behavior of generalized processor sharing queues under subexponential assumptions. Queueing Syst. v62 i1-2. 51-73.

[29]

}}Anantharam, V., The stability region of the finite-user slotted ALOHA protocol. IEEE Trans. Inform. Theory. v37 i3. 535-540.

[30]

}}Szpankowski, W., Stability conditions for multidimensional queueing systems with computer applications. Oper. Res. v36 i6. 944-957.

[31]

}}Szpankowski, W., Stability conditions for some distributed systems: Buffered random access systems. Adv. Appl. Probab. v26. 498-515.

[32]

}}Müller, A. and Stoyan, D., Comparison Methods for Stochastic Models and Risks. 2002. Wiley.

Cited By

Allmeier SGast N(2023)Bias and Refinement of Multiscale Mean Field ModelsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35793367:1(1-29)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3579336
Cheng YGraves ESwami ASabharwal A(2023)Estimating Traffic Rates in CSMA/CA Networks: A Feasibility Analysis for a Class of EavesdroppersIEEE Transactions on Wireless Communications10.1109/TWC.2023.327355022:12(9793-9807)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TWC.2023.3273550
Shneer SStolyar A(2019)Stability of a standard decentralised medium accessACM SIGMETRICS Performance Evaluation Review10.1145/3305218.330523146:2(33-35)Online publication date: 17-Jan-2019
https://dl.acm.org/doi/10.1145/3305218.3305231
Show More Cited By

Insensitivity and stability of random-access networks
1. General and reference
  1. Cross-computing tools and techniques

Recommendations

Performance evaluation of contention-based access in IEEE 802.16 networks with subchannelization
ICC'09: Proceedings of the 2009 IEEE international conference on Communications

IEEE 802.16 wireless networks, known as WiMAX, employ a mechanism for guaranteed time allocation to mobile stations in order to meet the different quality of service requirements for service flows. The base station allocates contention-based time slots ...
Spatial fairness in linear random-access networks

Random-access networks may exhibit severe unfairness in throughput, in the sense that some nodes receive consistently higher throughput than others. Recent studies show that this unfairness is due to local differences in the neighborhood structure: ...
Sequencing technique: an enhancement to 802.11 medium access control to improve the performance of wireless networks

This paper presents a technique known as sequencing on MAC layer for wireless networks. MAC layer issues are very important while accessing channel over wireless networks. Normally, communication uses Request To Send/Clear To Send (RTS/CTS) mechanism to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Performance Evaluation

Performance Evaluation Volume 67, Issue 11

November, 2010

313 pages

ISSN:0166-5316

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2010.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 November 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Allmeier SGast N(2023)Bias and Refinement of Multiscale Mean Field ModelsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35793367:1(1-29)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3579336
Cheng YGraves ESwami ASabharwal A(2023)Estimating Traffic Rates in CSMA/CA Networks: A Feasibility Analysis for a Class of EavesdroppersIEEE Transactions on Wireless Communications10.1109/TWC.2023.327355022:12(9793-9807)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TWC.2023.3273550
Shneer SStolyar A(2019)Stability of a standard decentralised medium accessACM SIGMETRICS Performance Evaluation Review10.1145/3305218.330523146:2(33-35)Online publication date: 17-Jan-2019
https://dl.acm.org/doi/10.1145/3305218.3305231
Zocca A(2019)Temporal starvation in multi-channel CSMA networksQueueing Systems: Theory and Applications10.1007/s11134-019-09598-y91:3-4(241-263)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s11134-019-09598-y
Cecchi FBorst Svan Leeuwaarden JWhiting P(2018)Spatial Mean-Field Limits for Ultra-Dense Random-Access NetworksACM SIGMETRICS Performance Evaluation Review10.1145/3199524.319954545:3(123-136)Online publication date: 20-Mar-2018
https://dl.acm.org/doi/10.1145/3199524.3199545
Cecchi FVan de Ven PShneer S(2018)Mean-field limits for multi-hop random-access networksACM SIGMETRICS Performance Evaluation Review10.1145/3199524.319954445:3(109-122)Online publication date: 20-Mar-2018
https://dl.acm.org/doi/10.1145/3199524.3199544
Van Houdt B(2017)Explicit Back-Off Rates for Achieving Target Throughputs in CSMA/CA NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2016.260446225:2(765-778)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TNET.2016.2604462
Faridi ABellalta BChecco A(2017)Analysis of Dynamic Channel Bonding in Dense Networks of WLANsIEEE Transactions on Mobile Computing10.1109/TMC.2016.261530516:8(2118-2131)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2615305
Laufer RKleinrock L(2016)The capacity of wireless CSMA/CA networksIEEE/ACM Transactions on Networking10.1109/TNET.2015.241546524:3(1518-1532)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2415465
Shneer Svan de Ven P(2015)Stability and instability of individual nodes in multi-hop wireless CSMA/CA networksACM SIGMETRICS Performance Evaluation Review10.1145/2825236.282524343:2(19-21)Online publication date: 16-Sep-2015
https://dl.acm.org/doi/10.1145/2825236.2825243
Show More Cited By

View Options

View options

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents