Stability of a standard decentralised medium access

Seva Shneer, Aleksandr Stolyar

Research output: Contribution to journalConference article

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 packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in that: a node with 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 non-zero. 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 condition < 2/5. This result is intuitive for the circle topology as the throughput each node receives in a 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 to prove our result.) The result is not intuitive at all for the line topology as in a saturated system some nodes receive a throughput lower than 2/5.

Original languageEnglish (US)
Pages (from-to)33-35
Number of pages3
JournalPerformance Evaluation Review
Volume46
Issue number2
DOIs
StatePublished - Jan 17 2019
Event2018 Workshop on MAthematical Performance Modeling and Analysis, MAMA 2018 and Workshop on Critical Infrastructure Network Security, CINS 2018 - Irvine, United States
Duration: Jun 1 2018 → …

Fingerprint

Topology
Throughput
Parking
Wireless networks

Keywords

  • Carrier-Sense Multiple Access
  • Discrete parking process
  • Medium access protocols
  • Non-monotone process
  • Queueing networks
  • Stochastic stability
  • Wireless systems

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Stability of a standard decentralised medium access. / Shneer, Seva; Stolyar, Aleksandr.

In: Performance Evaluation Review, Vol. 46, No. 2, 17.01.2019, p. 33-35.

Research output: Contribution to journalConference article

@article{b85ad3c51dca4efb800183dcf536b810,
title = "Stability of a standard decentralised medium access",
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 packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in that: a node with 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 non-zero. 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 condition < 2/5. This result is intuitive for the circle topology as the throughput each node receives in a 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 to prove our result.) The result is not intuitive at all for the line topology as in a saturated system some nodes receive a throughput lower than 2/5.",
keywords = "Carrier-Sense Multiple Access, Discrete parking process, Medium access protocols, Non-monotone process, Queueing networks, Stochastic stability, Wireless systems",
author = "Seva Shneer and Aleksandr Stolyar",
year = "2019",
month = "1",
day = "17",
doi = "10.1145/3305218.3305231",
language = "English (US)",
volume = "46",
pages = "33--35",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

TY - JOUR

T1 - Stability of a standard decentralised medium access

AU - Shneer, Seva

AU - Stolyar, Aleksandr

PY - 2019/1/17

Y1 - 2019/1/17

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 packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in that: a node with 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 non-zero. 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 condition < 2/5. This result is intuitive for the circle topology as the throughput each node receives in a 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 to prove our result.) The result is not intuitive at all for the line topology as in a 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 packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in that: a node with 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 non-zero. 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 condition < 2/5. This result is intuitive for the circle topology as the throughput each node receives in a 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 to prove our result.) The result is not intuitive at all for the line topology as in a 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 - Non-monotone process

KW - Queueing networks

KW - Stochastic stability

KW - Wireless systems

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

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

U2 - 10.1145/3305218.3305231

DO - 10.1145/3305218.3305231

M3 - Conference article

AN - SCOPUS:85061099554

VL - 46

SP - 33

EP - 35

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 2

ER -