LN: a flexible algorithmic framework for layered queueing network analysis
File(s)3633457.pdf (702.35 KB)
Published version
Author(s)
Casale, Giuliano
Gao, Yicheng
Niu, Zifeng
Zhu, Lulai
Type
Journal Article
Abstract
Layered queueing networks (LQNs) are an extension of ordinary queueing networks to model simultaneous resource possession and
stochastic call graphs in distributed systems. Existing computational algorithms for LQNs have primarily focused on mean-value
analysis. However, other solution paradigms, such as normalizing constant analysis and mean-field approximation, can improve the
computation of LQN mean and transient performance metrics, state probabilities, and response time distributions. Motivated by this
observation, we propose the first LQN meta-solver, called LN, that allows for the dynamic selection of the performance analysis
paradigm to be iteratively applied to the submodels arising from layer decomposition. We report experiments where this added
flexibility helps us to reduce the LQN solution errors. We also demonstrate that the meta-solver approach eases the integration of
LQNs with other formalisms, such as caching models, enabling the analysis of more general classes of layered stochastic networks.
Additionally, to support the accurate evaluation of the LQN submodels, we develop novel algorithms for homogeneous queueing
networks consisting of an infinite server node and a set of identical queueing stations. In particular, we propose an exact method of
moment algorithms, integration techniques for normalizing constants, and a fast non-iterative mean-value analysis technique.
stochastic call graphs in distributed systems. Existing computational algorithms for LQNs have primarily focused on mean-value
analysis. However, other solution paradigms, such as normalizing constant analysis and mean-field approximation, can improve the
computation of LQN mean and transient performance metrics, state probabilities, and response time distributions. Motivated by this
observation, we propose the first LQN meta-solver, called LN, that allows for the dynamic selection of the performance analysis
paradigm to be iteratively applied to the submodels arising from layer decomposition. We report experiments where this added
flexibility helps us to reduce the LQN solution errors. We also demonstrate that the meta-solver approach eases the integration of
LQNs with other formalisms, such as caching models, enabling the analysis of more general classes of layered stochastic networks.
Additionally, to support the accurate evaluation of the LQN submodels, we develop novel algorithms for homogeneous queueing
networks consisting of an infinite server node and a set of identical queueing stations. In particular, we propose an exact method of
moment algorithms, integration techniques for normalizing constants, and a fast non-iterative mean-value analysis technique.
Date Issued
2024-07-10
Date Acceptance
2023-11-08
Citation
ACM Transactions on Modeling and Computer Simulation, 2024, 34 (3), pp.1-26
ISSN
1049-3301
Publisher
Association for Computing Machinery (ACM)
Start Page
1
End Page
26
Journal / Book Title
ACM Transactions on Modeling and Computer Simulation
Volume
34
Issue
3
Copyright Statement
© 2024 Copyright held by the owner/author(s).
This work is licensed under a Creative Commons Attribution International 4.0 License (https://creativecommons.org/licenses/by/4.0/)
This work is licensed under a Creative Commons Attribution International 4.0 License (https://creativecommons.org/licenses/by/4.0/)
License URL
Identifier
https://dl.acm.org/doi/10.1145/3633457
Publication Status
Published
Article Number
ARTN 17
Date Publish Online
2023-11-21