|
Title
|
|
|
|
Analysis of load balancing and scheduling policies in large-scale systems
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| Queueing theory plays a crucial role in modelling systems with congestion. It has been long applied in analyzing and improving the performance of communication systems. As modern communication systems often are composed of multiple heterogeneous resources, the analysis of such large-scale systems using traditional queueing theory can be prohibitive. When analyzing such systems exactly, one usually comes across the problem of the, so called, state space explosion. Large-scale systems are therefore often studied through mean field analysis: if a system consists of a large number of queues, it can be approximated by a system with infinitely many queues. The analysis of the model of the latter system, the mean field model, is generally more straightforward, as it circumvents the problem of the state space explosion. The goal of this thesis is to analyze and gain insight in the performance of existing and novel large-scale load balancing policies through the use of mean field modelling. Each chapter of this thesis contains the mean field analysis of a family of systems with these policies. In the analysis, techniques from dynamical systems, stochastic modelling, probability theory, numerical analysis and simulations are used. The chapters are grouped into three parts. The first of these parts deals with monotone systems. These systems have an apparent ordering of states that is maintained over time. The next part deals with the analysis of systems with job stealing and multithreaded computing. In these systems parts of a job can be transferred between queues and can be thus worked on by different queues concurrently. In the last part several hyperscalable policies with a single dispatcher are studied. These are policies where a central dispatcher distributes the jobs to the queues, based on their estimated queue lengths. The policies are called hyperscalable if the message overhead between the queues and the dispatcher is less than one message per job on average. For the systems in the last two parts, simulations are performed for finite number of queues to measure the accuracy of the mean field approximation. |
| |
|
Language
|
|
|
|
English
| |
|
Publication
|
|
|
|
Antwerp
:
University of Antwerp, Faculty of Science
,
2023
| |
|
Volume/pages
|
|
|
|
xii, 261 p.
| |
|
Note
|
|
|
|
:
Van Houdt, Benny [Supervisor]
| |
|
Full text (open access)
|
|
|
|
| |
|