Markovian polling systems with an application to wireless random-access networks

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
4 Downloads (Pure)

Abstract

Motivated by an application in wireless random-access networks, we study a class of polling systems with Markovian routing, in which the server visits the queues in an order governed by a discrete-time Markov chain. Assuming that the service disciplines at each of the queues fall in the class of branching-type service disciplines, we derive a functional equation for (the probability generating function of) the joint queue length distribution conditioned on a point in time when the server visits a certain queue. From this functional equation, expressions for the (cross-)moments of the queue lengths follow. We also derive a pseudo-conservation law for this class of polling systems. Using these results, we compute expressions for certain system parameters that minimise the total expected amount of work in systems that arise from the wireless random-access network setting. In addition, we derive approximations for those same parameters that minimise a weighted sum of mean waiting times in these systems. Based on these expressions, we also present an adaptive control algorithm for finding the optimal parameter values in a distributed fashion, which is particularly relevant in the context of wireless random-access networks. Keywords: Queue lengths; Binomial service disciplines; Markovian routing; Random routing; Wireless random-access networks
Original languageEnglish
Pages (from-to)33-51
Number of pages19
JournalPerformance Evaluation
Volume85-86
DOIs
Publication statusPublished - 2015

Fingerprint

Polling Systems
Random Access
Queue
Routing
Queue Length
Functional equation
Servers
Server
Queue Length Distribution
Minimise
Probability generating function
Optimal Parameter
Weighted Sums
Adaptive Algorithm
Waiting Time
Joint Distribution
Adaptive Control
Markov processes
Conservation Laws
Control Algorithm

Cite this

@article{81ce42cbdd264b8ba5594fd8662cdb76,
title = "Markovian polling systems with an application to wireless random-access networks",
abstract = "Motivated by an application in wireless random-access networks, we study a class of polling systems with Markovian routing, in which the server visits the queues in an order governed by a discrete-time Markov chain. Assuming that the service disciplines at each of the queues fall in the class of branching-type service disciplines, we derive a functional equation for (the probability generating function of) the joint queue length distribution conditioned on a point in time when the server visits a certain queue. From this functional equation, expressions for the (cross-)moments of the queue lengths follow. We also derive a pseudo-conservation law for this class of polling systems. Using these results, we compute expressions for certain system parameters that minimise the total expected amount of work in systems that arise from the wireless random-access network setting. In addition, we derive approximations for those same parameters that minimise a weighted sum of mean waiting times in these systems. Based on these expressions, we also present an adaptive control algorithm for finding the optimal parameter values in a distributed fashion, which is particularly relevant in the context of wireless random-access networks. Keywords: Queue lengths; Binomial service disciplines; Markovian routing; Random routing; Wireless random-access networks",
author = "J.L. Dorsman and S.C. Borst and O.J. Boxma and M. Vlasiou",
year = "2015",
doi = "10.1016/j.peva.2015.01.008",
language = "English",
volume = "85-86",
pages = "33--51",
journal = "Performance Evaluation",
issn = "0166-5316",
publisher = "Elsevier",

}

Markovian polling systems with an application to wireless random-access networks. / Dorsman, J.L.; Borst, S.C.; Boxma, O.J.; Vlasiou, M.

In: Performance Evaluation, Vol. 85-86, 2015, p. 33-51.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Markovian polling systems with an application to wireless random-access networks

AU - Dorsman, J.L.

AU - Borst, S.C.

AU - Boxma, O.J.

AU - Vlasiou, M.

PY - 2015

Y1 - 2015

N2 - Motivated by an application in wireless random-access networks, we study a class of polling systems with Markovian routing, in which the server visits the queues in an order governed by a discrete-time Markov chain. Assuming that the service disciplines at each of the queues fall in the class of branching-type service disciplines, we derive a functional equation for (the probability generating function of) the joint queue length distribution conditioned on a point in time when the server visits a certain queue. From this functional equation, expressions for the (cross-)moments of the queue lengths follow. We also derive a pseudo-conservation law for this class of polling systems. Using these results, we compute expressions for certain system parameters that minimise the total expected amount of work in systems that arise from the wireless random-access network setting. In addition, we derive approximations for those same parameters that minimise a weighted sum of mean waiting times in these systems. Based on these expressions, we also present an adaptive control algorithm for finding the optimal parameter values in a distributed fashion, which is particularly relevant in the context of wireless random-access networks. Keywords: Queue lengths; Binomial service disciplines; Markovian routing; Random routing; Wireless random-access networks

AB - Motivated by an application in wireless random-access networks, we study a class of polling systems with Markovian routing, in which the server visits the queues in an order governed by a discrete-time Markov chain. Assuming that the service disciplines at each of the queues fall in the class of branching-type service disciplines, we derive a functional equation for (the probability generating function of) the joint queue length distribution conditioned on a point in time when the server visits a certain queue. From this functional equation, expressions for the (cross-)moments of the queue lengths follow. We also derive a pseudo-conservation law for this class of polling systems. Using these results, we compute expressions for certain system parameters that minimise the total expected amount of work in systems that arise from the wireless random-access network setting. In addition, we derive approximations for those same parameters that minimise a weighted sum of mean waiting times in these systems. Based on these expressions, we also present an adaptive control algorithm for finding the optimal parameter values in a distributed fashion, which is particularly relevant in the context of wireless random-access networks. Keywords: Queue lengths; Binomial service disciplines; Markovian routing; Random routing; Wireless random-access networks

U2 - 10.1016/j.peva.2015.01.008

DO - 10.1016/j.peva.2015.01.008

M3 - Article

VL - 85-86

SP - 33

EP - 51

JO - Performance Evaluation

JF - Performance Evaluation

SN - 0166-5316

ER -