Stability conditions for a discrete-time decentralised medium access algorithm

Seva Shneer, Alexander Stolyar

Research output: Contribution to journalArticle

Abstract

We consider a stochastic queueing system modelling the behaviour of a wireless network with nodes employing a discrete-time version of the standard decentralised medium access algorithm. The system is unsaturated-each node receives an exogenous flow of packets at the rate of λ packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in the following sense: A node with an empty queue does not compete for medium access; the access procedure by a node does not depend on its queue length as long as it is nonzero. Two system topologies are considered, with nodes arranged in a circle and in a line. We prove that, for either topology, the system is stochastically stable under the condition λ<2/5. This result is intuitive for the circle topology as the throughput each node receives in the saturated system (with infinite queues) is equal to the so-called parking constant, which is larger than 2/5. (This fact, however, does not help us to prove the result.) The result is not intuitive for the line topology as in the saturated system some nodes receive a throughput lower than 2/5.

Original languageEnglish (US)
Pages (from-to)3600-3628
Number of pages29
JournalAnnals of Applied Probability
Volume28
Issue number6
DOIs
StatePublished - Dec 2018

Fingerprint

Stability Condition
Decentralized
Discrete-time
Vertex of a graph
Topology
Queue
Intuitive
Circle
Throughput
Node
Line
Queue Length
Queueing System
Stochastic Systems
System Modeling
Wireless Networks

Keywords

  • Carrier-sense multiple access
  • Discrete parking process
  • Medium access protocols
  • Nonmonotone process
  • Queueing networks
  • Stochastic stability
  • Wireless systems

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Cite this

Stability conditions for a discrete-time decentralised medium access algorithm. / Shneer, Seva; Stolyar, Alexander.

In: Annals of Applied Probability, Vol. 28, No. 6, 12.2018, p. 3600-3628.

Research output: Contribution to journalArticle

@article{c1d17bc63fe84eae9321780959b3dc58,
title = "Stability conditions for a discrete-time decentralised medium access algorithm",
abstract = "We consider a stochastic queueing system modelling the behaviour of a wireless network with nodes employing a discrete-time version of the standard decentralised medium access algorithm. The system is unsaturated-each node receives an exogenous flow of packets at the rate of λ packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in the following sense: A node with an empty queue does not compete for medium access; the access procedure by a node does not depend on its queue length as long as it is nonzero. Two system topologies are considered, with nodes arranged in a circle and in a line. We prove that, for either topology, the system is stochastically stable under the condition λ<2/5. This result is intuitive for the circle topology as the throughput each node receives in the saturated system (with infinite queues) is equal to the so-called parking constant, which is larger than 2/5. (This fact, however, does not help us to prove the result.) The result is not intuitive for the line topology as in the saturated system some nodes receive a throughput lower than 2/5.",
keywords = "Carrier-sense multiple access, Discrete parking process, Medium access protocols, Nonmonotone process, Queueing networks, Stochastic stability, Wireless systems",
author = "Seva Shneer and Alexander Stolyar",
year = "2018",
month = "12",
doi = "10.1214/18-AAP1398",
language = "English (US)",
volume = "28",
pages = "3600--3628",
journal = "Annals of Applied Probability",
issn = "1050-5164",
publisher = "Institute of Mathematical Statistics",
number = "6",

}

TY - JOUR

T1 - Stability conditions for a discrete-time decentralised medium access algorithm

AU - Shneer, Seva

AU - Stolyar, Alexander

PY - 2018/12

Y1 - 2018/12

N2 - We consider a stochastic queueing system modelling the behaviour of a wireless network with nodes employing a discrete-time version of the standard decentralised medium access algorithm. The system is unsaturated-each node receives an exogenous flow of packets at the rate of λ packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in the following sense: A node with an empty queue does not compete for medium access; the access procedure by a node does not depend on its queue length as long as it is nonzero. Two system topologies are considered, with nodes arranged in a circle and in a line. We prove that, for either topology, the system is stochastically stable under the condition λ<2/5. This result is intuitive for the circle topology as the throughput each node receives in the saturated system (with infinite queues) is equal to the so-called parking constant, which is larger than 2/5. (This fact, however, does not help us to prove the result.) The result is not intuitive for the line topology as in the saturated system some nodes receive a throughput lower than 2/5.

AB - We consider a stochastic queueing system modelling the behaviour of a wireless network with nodes employing a discrete-time version of the standard decentralised medium access algorithm. The system is unsaturated-each node receives an exogenous flow of packets at the rate of λ packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in the following sense: A node with an empty queue does not compete for medium access; the access procedure by a node does not depend on its queue length as long as it is nonzero. Two system topologies are considered, with nodes arranged in a circle and in a line. We prove that, for either topology, the system is stochastically stable under the condition λ<2/5. This result is intuitive for the circle topology as the throughput each node receives in the saturated system (with infinite queues) is equal to the so-called parking constant, which is larger than 2/5. (This fact, however, does not help us to prove the result.) The result is not intuitive for the line topology as in the saturated system some nodes receive a throughput lower than 2/5.

KW - Carrier-sense multiple access

KW - Discrete parking process

KW - Medium access protocols

KW - Nonmonotone process

KW - Queueing networks

KW - Stochastic stability

KW - Wireless systems

UR - http://www.scopus.com/inward/record.url?scp=85055008485&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85055008485&partnerID=8YFLogxK

U2 - 10.1214/18-AAP1398

DO - 10.1214/18-AAP1398

M3 - Article

AN - SCOPUS:85055008485

VL - 28

SP - 3600

EP - 3628

JO - Annals of Applied Probability

JF - Annals of Applied Probability

SN - 1050-5164

IS - 6

ER -