|
Title
|
|
|
|
Analysis of large scale randomized load balancing policies
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| In the load balancing literature, there has been a lot of interest in policies which balance load based on some information of $d$ randomly selected servers. The analysis of these policies for a finite system is intractable in most cases, therefore one often relies on mean field methods. That is, you assume that all queues are i.i.d.~which allows to describe the system's behaviour through the behaviour of a single queue. Most prior work has focused on load balancing methods which balance the load based on the queue length. While reducing response times, small jobs may still get stuck behind long jobs for these policies. In contrast, our main focus is on policies which employ the actual work present at the servers. While causing additional overhead, these policies do allow to detect all large jobs. This includes policies which either favour servers with a low load, use some form of redundancy, have a memory at the dispatcher, assign jobs in batches,... We additionally consider policies which combine the queue length information with the runtime of the job currently receiving service. This allows us to detect large jobs if they have been receiving service for some time. For all policies considered we obtain a numerical method to study its performance. We make use of simulations to illustrate the accuracy of the mean field approximation. Moreover, assuming exponential job sizes often allows us to compute performance metrics in closed form. In particular we noticed that by using a proper scaling, we can often obtain simple closed form formulas for the expected waiting time in case the system load is either close to instability or close to zero. |
| |
|
Language
|
|
|
|
English
| |
|
Publication
|
|
|
|
Antwerp
:
University of Antwerp, Faculty of Sciences
,
2021
| |
|
Volume/pages
|
|
|
|
347 p.
| |
|
Note
|
|
|
|
:
Van Houdt, Benny [Supervisor]
| |
|
Full text (open access)
|
|
|
|
| |
|