Dynamic distributed scheduling in random access networks

Research output: Contribution to journalArticle

Abstract

We consider a model of random access (slotted-aloha-type) communication networks of general topology. Assuming that network links receive exogenous arrivals of packets for transmission, we seek dynamic distributed random access strategies whose goal is to keep all network queues stable. We prove that two dynamic strategies, which we collectively call queue length based random access (QRA), ensure stability as long as the rates of exogenous arrival flows are within the network saturation rate region. The first strategy, QRA-I, can be viewed as a random-access-model counterpart of the max-weight scheduling rule, while the second strategy, QRA-II, is a counterpart of the exponential (EXP) rule. The two strategies induce different dynamics of the queues in the fluid scaling limit, which can be exploited for the quality-of-service control in applications.

Original languageEnglish (US)
Pages (from-to)297-313
Number of pages17
JournalJournal of Applied Probability
Volume45
Issue number2
DOIs
StatePublished - Jun 1 2008
Externally publishedYes

Fingerprint

Distributed Scheduling
Dynamic Scheduling
Random Access
Queue
Fluid Limits
Scaling Limit
Queue Length
Communication Networks
Quality of Service
Saturation
Scheduling
Strategy
Network access
Topology
Model

Keywords

  • Medium access control
  • Queueing network
  • Random multiple access
  • Slotted aloha
  • Stability

ASJC Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)
  • Statistics, Probability and Uncertainty

Cite this

Dynamic distributed scheduling in random access networks. / Stolyar, Alexander L.

In: Journal of Applied Probability, Vol. 45, No. 2, 01.06.2008, p. 297-313.

Research output: Contribution to journalArticle

@article{bc1c206bf43a4fd58489465b6ce342e7,
title = "Dynamic distributed scheduling in random access networks",
abstract = "We consider a model of random access (slotted-aloha-type) communication networks of general topology. Assuming that network links receive exogenous arrivals of packets for transmission, we seek dynamic distributed random access strategies whose goal is to keep all network queues stable. We prove that two dynamic strategies, which we collectively call queue length based random access (QRA), ensure stability as long as the rates of exogenous arrival flows are within the network saturation rate region. The first strategy, QRA-I, can be viewed as a random-access-model counterpart of the max-weight scheduling rule, while the second strategy, QRA-II, is a counterpart of the exponential (EXP) rule. The two strategies induce different dynamics of the queues in the fluid scaling limit, which can be exploited for the quality-of-service control in applications.",
keywords = "Medium access control, Queueing network, Random multiple access, Slotted aloha, Stability",
author = "Stolyar, {Alexander L.}",
year = "2008",
month = "6",
day = "1",
doi = "10.1239/jap/1214950349",
language = "English (US)",
volume = "45",
pages = "297--313",
journal = "Journal of Applied Probability",
issn = "0021-9002",
publisher = "University of Sheffield",
number = "2",

}

TY - JOUR

T1 - Dynamic distributed scheduling in random access networks

AU - Stolyar, Alexander L.

PY - 2008/6/1

Y1 - 2008/6/1

N2 - We consider a model of random access (slotted-aloha-type) communication networks of general topology. Assuming that network links receive exogenous arrivals of packets for transmission, we seek dynamic distributed random access strategies whose goal is to keep all network queues stable. We prove that two dynamic strategies, which we collectively call queue length based random access (QRA), ensure stability as long as the rates of exogenous arrival flows are within the network saturation rate region. The first strategy, QRA-I, can be viewed as a random-access-model counterpart of the max-weight scheduling rule, while the second strategy, QRA-II, is a counterpart of the exponential (EXP) rule. The two strategies induce different dynamics of the queues in the fluid scaling limit, which can be exploited for the quality-of-service control in applications.

AB - We consider a model of random access (slotted-aloha-type) communication networks of general topology. Assuming that network links receive exogenous arrivals of packets for transmission, we seek dynamic distributed random access strategies whose goal is to keep all network queues stable. We prove that two dynamic strategies, which we collectively call queue length based random access (QRA), ensure stability as long as the rates of exogenous arrival flows are within the network saturation rate region. The first strategy, QRA-I, can be viewed as a random-access-model counterpart of the max-weight scheduling rule, while the second strategy, QRA-II, is a counterpart of the exponential (EXP) rule. The two strategies induce different dynamics of the queues in the fluid scaling limit, which can be exploited for the quality-of-service control in applications.

KW - Medium access control

KW - Queueing network

KW - Random multiple access

KW - Slotted aloha

KW - Stability

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

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

U2 - 10.1239/jap/1214950349

DO - 10.1239/jap/1214950349

M3 - Article

AN - SCOPUS:48549100459

VL - 45

SP - 297

EP - 313

JO - Journal of Applied Probability

JF - Journal of Applied Probability

SN - 0021-9002

IS - 2

ER -