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
Publication statusPublished - Jun 1 2008
Externally publishedYes

    Fingerprint

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