QRF: an Optimization-Based Framework for Evaluating Complex Stochastic Networks
File(s)cr-main2.pdf (358.28 KB) cr-supplement.pdf (143.86 KB)
Accepted version
Supporting information
Author(s)
Casale, G
De Nitto-Persone, V
Smirni, E
Type
Journal Article
Abstract
The Quadratic Reduction Framework (QRF) is a numerical modeling framework to evaluate complex stochastic
networks composed of resources featuring queueing, blocking, state-dependent behavior, service variability,
temporal dependence, or a subset thereof. Systems of this kind are abstracted as network of queues
for which QRF supports two common blocking mechanisms: blocking-after-service and repetitive-service
random-destination. State-dependence is supported for both routing probabilities and service processes. To
evaluate these models, we develop a novel mapping, called Blocking-Aware Quadratic Reduction (BQR),
which can describe an intractably large Markov process by a large set of linear inequalities. Each model is
then analyzed for bounds or approximate values of performance metrics using optimization programs that
provide different levels of accuracy and error guarantees. Numerical results demonstrate that QRF offers
very good accuracy and much greater scalability than exact analysis methods.
networks composed of resources featuring queueing, blocking, state-dependent behavior, service variability,
temporal dependence, or a subset thereof. Systems of this kind are abstracted as network of queues
for which QRF supports two common blocking mechanisms: blocking-after-service and repetitive-service
random-destination. State-dependence is supported for both routing probabilities and service processes. To
evaluate these models, we develop a novel mapping, called Blocking-Aware Quadratic Reduction (BQR),
which can describe an intractably large Markov process by a large set of linear inequalities. Each model is
then analyzed for bounds or approximate values of performance metrics using optimization programs that
provide different levels of accuracy and error guarantees. Numerical results demonstrate that QRF offers
very good accuracy and much greater scalability than exact analysis methods.
Date Issued
2016-01-01
Date Acceptance
2015-01-20
Citation
ACM TOMACS, 26 (3)
ISSN
1049-3301
Publisher
Association for Computing Machinery
Journal / Book Title
ACM TOMACS
Volume
26
Issue
3
Copyright Statement
© ACM, 2015. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Modeling and Computer Simulation (TOMACS), 2015
Subjects
Operations Research
0802 Computation Theory And Mathematics
0806 Information Systems
Publication Status
Published
Article Number
15