Queue-based random-access algorithms: Fluid limits and stability issues

J. Ghaderi, S.C. Borst, P.A. Whiting

Research output: Book/ReportReportAcademic

Abstract

We use ¿uid limits to explore the (in)stability properties of wireless networks with queue-based random-access algorithms. Queue-based random-access schemes are simple and inherently distributed in nature, yet provide the capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. Unfortunately, the type of activation rules for which throughput optimality has been established, may result in excessive queue lengths and delays. The use of more aggressive/persistent access schemes can improve the delay performance, but does not offer any universal maximum-stability guarantees. In order to gain qualitative insight and investigate the (in)stability properties of more aggressive/persistent activation rules, we examine ¿uid limits where the dynamics are scaled in space and time. In some situations, the ¿uid limits have smooth deterministic features and maximum stability is maintained, while in other scenarios they exhibit random oscillatory characteristics, giving rise to major technical challenges. In the latter regime, more aggressive access schemes continue to provide maximum stability in some networks, but may cause instability in others. Simulation experiments are conducted to illustrate and validate the analytical results.
Original languageEnglish
Publishers.n.
Number of pages46
Publication statusPublished - 2013

Publication series

NamearXiv.org
Volume1302.5945 [cs.NI]

Fingerprint

Fluids
Chemical activation
Throughput
Wireless networks
Scheduling
Experiments

Cite this

Ghaderi, J., Borst, S. C., & Whiting, P. A. (2013). Queue-based random-access algorithms: Fluid limits and stability issues. (arXiv.org; Vol. 1302.5945 [cs.NI]). s.n.
Ghaderi, J. ; Borst, S.C. ; Whiting, P.A. / Queue-based random-access algorithms: Fluid limits and stability issues. s.n., 2013. 46 p. (arXiv.org).
@book{734ac08bfa1348b3b30b097772ab1dac,
title = "Queue-based random-access algorithms: Fluid limits and stability issues",
abstract = "We use ¿uid limits to explore the (in)stability properties of wireless networks with queue-based random-access algorithms. Queue-based random-access schemes are simple and inherently distributed in nature, yet provide the capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. Unfortunately, the type of activation rules for which throughput optimality has been established, may result in excessive queue lengths and delays. The use of more aggressive/persistent access schemes can improve the delay performance, but does not offer any universal maximum-stability guarantees. In order to gain qualitative insight and investigate the (in)stability properties of more aggressive/persistent activation rules, we examine ¿uid limits where the dynamics are scaled in space and time. In some situations, the ¿uid limits have smooth deterministic features and maximum stability is maintained, while in other scenarios they exhibit random oscillatory characteristics, giving rise to major technical challenges. In the latter regime, more aggressive access schemes continue to provide maximum stability in some networks, but may cause instability in others. Simulation experiments are conducted to illustrate and validate the analytical results.",
author = "J. Ghaderi and S.C. Borst and P.A. Whiting",
year = "2013",
language = "English",
series = "arXiv.org",
publisher = "s.n.",

}

Ghaderi, J, Borst, SC & Whiting, PA 2013, Queue-based random-access algorithms: Fluid limits and stability issues. arXiv.org, vol. 1302.5945 [cs.NI], s.n.

Queue-based random-access algorithms: Fluid limits and stability issues. / Ghaderi, J.; Borst, S.C.; Whiting, P.A.

s.n., 2013. 46 p. (arXiv.org; Vol. 1302.5945 [cs.NI]).

Research output: Book/ReportReportAcademic

TY - BOOK

T1 - Queue-based random-access algorithms: Fluid limits and stability issues

AU - Ghaderi, J.

AU - Borst, S.C.

AU - Whiting, P.A.

PY - 2013

Y1 - 2013

N2 - We use ¿uid limits to explore the (in)stability properties of wireless networks with queue-based random-access algorithms. Queue-based random-access schemes are simple and inherently distributed in nature, yet provide the capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. Unfortunately, the type of activation rules for which throughput optimality has been established, may result in excessive queue lengths and delays. The use of more aggressive/persistent access schemes can improve the delay performance, but does not offer any universal maximum-stability guarantees. In order to gain qualitative insight and investigate the (in)stability properties of more aggressive/persistent activation rules, we examine ¿uid limits where the dynamics are scaled in space and time. In some situations, the ¿uid limits have smooth deterministic features and maximum stability is maintained, while in other scenarios they exhibit random oscillatory characteristics, giving rise to major technical challenges. In the latter regime, more aggressive access schemes continue to provide maximum stability in some networks, but may cause instability in others. Simulation experiments are conducted to illustrate and validate the analytical results.

AB - We use ¿uid limits to explore the (in)stability properties of wireless networks with queue-based random-access algorithms. Queue-based random-access schemes are simple and inherently distributed in nature, yet provide the capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. Unfortunately, the type of activation rules for which throughput optimality has been established, may result in excessive queue lengths and delays. The use of more aggressive/persistent access schemes can improve the delay performance, but does not offer any universal maximum-stability guarantees. In order to gain qualitative insight and investigate the (in)stability properties of more aggressive/persistent activation rules, we examine ¿uid limits where the dynamics are scaled in space and time. In some situations, the ¿uid limits have smooth deterministic features and maximum stability is maintained, while in other scenarios they exhibit random oscillatory characteristics, giving rise to major technical challenges. In the latter regime, more aggressive access schemes continue to provide maximum stability in some networks, but may cause instability in others. Simulation experiments are conducted to illustrate and validate the analytical results.

M3 - Report

T3 - arXiv.org

BT - Queue-based random-access algorithms: Fluid limits and stability issues

PB - s.n.

ER -

Ghaderi J, Borst SC, Whiting PA. Queue-based random-access algorithms: Fluid limits and stability issues. s.n., 2013. 46 p. (arXiv.org).