Combining queueing analysis and machine learning for performance modeling of distributed systems
File(s)
Author(s)
Niu, Zifeng
Type
Thesis
Abstract
Performance modeling is commonly used during the early design phase of a system to ensure that performance meets quality of service (QoS) requirements. Queueing analysis is a classic analytical approach that abstracts queueing networks (QNs) from systems and quantitatively characterizes system behavior to support decision-making. However, most realistic QNs are mathematically intractable, leading to two key challenges. The first challenge is characterizing complex response time distributions, a task beyond the capabilities of conventional approaches. The second challenge is accurately evaluating the performance of non-product-form QNs, for which queueing analysis lacks a closed-form solution. Machine learning (ML) advancement presents new opportunities for performance modeling. Nevertheless, the use of ML faces the challenge of lacking flexibility, making it difficult to apply to QNs with varying topologies and numbers of job classes, which limits its potential as a general-purpose solution.
We address these challenges by combining queueing analysis and ML approaches. To estimate response time distributions, we propose a phase-type density-passing framework which recursively propagates response time distributions predicted by mixture density networks, enabling accurate approximations. To address the challenges of evaluating non-product-form QNs, we leverage insights from queueing analysis to design graph neural network (GNN) models. First, we develop a model to solve closed multiclass QNs. Similar to analytical methods, our GNN predicts performance measures per job class at each service center. This exploration reveals the potential of a learning-based model as a general-purpose solver for various QNs. Next, we define a more fine-grained graph for open multiclass QNs abstracted from distributed edge AI systems and customize message passing based on queueing analysis of chain-based services. To broaden its applicability, we propose a solution for achieving out-of-distribution generalization ability. We demonstrate that the proposed model is an accurate yet efficient performance modeling tool for determining the optimal plan during the system design.
We address these challenges by combining queueing analysis and ML approaches. To estimate response time distributions, we propose a phase-type density-passing framework which recursively propagates response time distributions predicted by mixture density networks, enabling accurate approximations. To address the challenges of evaluating non-product-form QNs, we leverage insights from queueing analysis to design graph neural network (GNN) models. First, we develop a model to solve closed multiclass QNs. Similar to analytical methods, our GNN predicts performance measures per job class at each service center. This exploration reveals the potential of a learning-based model as a general-purpose solver for various QNs. Next, we define a more fine-grained graph for open multiclass QNs abstracted from distributed edge AI systems and customize message passing based on queueing analysis of chain-based services. To broaden its applicability, we propose a solution for achieving out-of-distribution generalization ability. We demonstrate that the proposed model is an accurate yet efficient performance modeling tool for determining the optimal plan during the system design.
Version
Open Access
Date Issued
2024-10-04
Date Awarded
01/12/2024
License URL
Advisor
Casale, Giuliano
Publisher Department
Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)