A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks

Xinwei Bai; Jasper Goseling

doi:10.1007/978-3-030-27181-7_13

A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks

Xinwei Bai^*, Jasper Goseling

^*Corresponding author for this work

Stochastic Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

In this paper, we present a numerical framework for constructing bounds on stationary performance measures of random walks in the positive orthant using the Markov reward approach. These bounds are established in terms of stationary performance measures of a perturbed random walk whose stationary distribution is known explicitly. We consider random walks in an arbitrary number of dimensions and with a transition probability structure that is defined on an arbitrary partition of the positive orthant. Within each component of this partition the transition probabilities are homogeneous. This enables us to model queueing networks with, for instance, break-downs and finite buffers. The main contribution of this paper is that we generalize the linear programming approach of [10] to this class of models.

Original language	English
Title of host publication	Queueing Theory and Network Applications - 14th International Conference, QTNA 2019, Proceedings
Editors	Tuan Phung-Duc, Shoji Kasahara, Sabine Wittevrongel
Publisher	Springer
Pages	201-220
Number of pages	20
ISBN (Print)	9783030271800
DOIs	https://doi.org/10.1007/978-3-030-27181-7_13
Publication status	Published - 2019
Event	14th International Conference on Queueing Theory and Network Applications, QTNA 2019 - Ghent, Belgium Duration: 27 Aug 2019 → 29 Aug 2019 Conference number: 14

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11688 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Queueing Theory and Network Applications, QTNA 2019
Abbreviated title	QTNA 2019
Country/Territory	Belgium
City	Ghent
Period	27/08/19 → 29/08/19

Keywords

Error bound
Linear programming
Markov reward approach
Multi-dimensional random walk
Stationary performance measures

Access to Document

10.1007/978-3-030-27181-7_13

Cite this

Bai, X., & Goseling, J. (2019). A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks. In T. Phung-Duc, S. Kasahara, & S. Wittevrongel (Eds.), Queueing Theory and Network Applications - 14th International Conference, QTNA 2019, Proceedings (pp. 201-220). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11688 LNCS). Springer. https://doi.org/10.1007/978-3-030-27181-7_13

Bai, Xinwei ; Goseling, Jasper. / A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks. Queueing Theory and Network Applications - 14th International Conference, QTNA 2019, Proceedings. editor / Tuan Phung-Duc ; Shoji Kasahara ; Sabine Wittevrongel. Springer, 2019. pp. 201-220 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{de8a15b2be97467e92e1cf8ff7ba6ae8,

title = "A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks",

abstract = "In this paper, we present a numerical framework for constructing bounds on stationary performance measures of random walks in the positive orthant using the Markov reward approach. These bounds are established in terms of stationary performance measures of a perturbed random walk whose stationary distribution is known explicitly. We consider random walks in an arbitrary number of dimensions and with a transition probability structure that is defined on an arbitrary partition of the positive orthant. Within each component of this partition the transition probabilities are homogeneous. This enables us to model queueing networks with, for instance, break-downs and finite buffers. The main contribution of this paper is that we generalize the linear programming approach of [10] to this class of models.",

keywords = "Error bound, Linear programming, Markov reward approach, Multi-dimensional random walk, Stationary performance measures",

author = "Xinwei Bai and Jasper Goseling",

year = "2019",

doi = "10.1007/978-3-030-27181-7_13",

language = "English",

isbn = "9783030271800",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "201--220",

editor = "Tuan Phung-Duc and Shoji Kasahara and Sabine Wittevrongel",

booktitle = "Queueing Theory and Network Applications - 14th International Conference, QTNA 2019, Proceedings",

note = "14th International Conference on Queueing Theory and Network Applications, QTNA 2019, QTNA 2019 ; Conference date: 27-08-2019 Through 29-08-2019",

}

Bai, X & Goseling, J 2019, A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks. in T Phung-Duc, S Kasahara & S Wittevrongel (eds), Queueing Theory and Network Applications - 14th International Conference, QTNA 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11688 LNCS, Springer, pp. 201-220, 14th International Conference on Queueing Theory and Network Applications, QTNA 2019, Ghent, Belgium, 27/08/19. https://doi.org/10.1007/978-3-030-27181-7_13

A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks. / Bai, Xinwei; Goseling, Jasper.
Queueing Theory and Network Applications - 14th International Conference, QTNA 2019, Proceedings. ed. / Tuan Phung-Duc; Shoji Kasahara; Sabine Wittevrongel. Springer, 2019. p. 201-220 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11688 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks

AU - Bai, Xinwei

AU - Goseling, Jasper

N1 - Conference code: 14

PY - 2019

Y1 - 2019

N2 - In this paper, we present a numerical framework for constructing bounds on stationary performance measures of random walks in the positive orthant using the Markov reward approach. These bounds are established in terms of stationary performance measures of a perturbed random walk whose stationary distribution is known explicitly. We consider random walks in an arbitrary number of dimensions and with a transition probability structure that is defined on an arbitrary partition of the positive orthant. Within each component of this partition the transition probabilities are homogeneous. This enables us to model queueing networks with, for instance, break-downs and finite buffers. The main contribution of this paper is that we generalize the linear programming approach of [10] to this class of models.

AB - In this paper, we present a numerical framework for constructing bounds on stationary performance measures of random walks in the positive orthant using the Markov reward approach. These bounds are established in terms of stationary performance measures of a perturbed random walk whose stationary distribution is known explicitly. We consider random walks in an arbitrary number of dimensions and with a transition probability structure that is defined on an arbitrary partition of the positive orthant. Within each component of this partition the transition probabilities are homogeneous. This enables us to model queueing networks with, for instance, break-downs and finite buffers. The main contribution of this paper is that we generalize the linear programming approach of [10] to this class of models.

KW - Error bound

KW - Linear programming

KW - Markov reward approach

KW - Multi-dimensional random walk

KW - Stationary performance measures

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

U2 - 10.1007/978-3-030-27181-7_13

DO - 10.1007/978-3-030-27181-7_13

M3 - Conference contribution

AN - SCOPUS:85077117729

SN - 9783030271800

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 201

EP - 220

BT - Queueing Theory and Network Applications - 14th International Conference, QTNA 2019, Proceedings

A2 - Phung-Duc, Tuan

A2 - Kasahara, Shoji

A2 - Wittevrongel, Sabine

PB - Springer

T2 - 14th International Conference on Queueing Theory and Network Applications, QTNA 2019

Y2 - 27 August 2019 through 29 August 2019

ER -

Bai X, Goseling J. A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks. In Phung-Duc T, Kasahara S, Wittevrongel S, editors, Queueing Theory and Network Applications - 14th International Conference, QTNA 2019, Proceedings. Springer. 2019. p. 201-220. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-27181-7_13

A Linear Programming Approach to Markov Reward Error Bounds for Queueing Networks

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this