Academic Awards 2023 booklet

13 Mean Field Approximations for Heterogeneous Supermarket Models on Graphs When one loads a web page, a request is sent to a data centre. These requests (or jobs) are assigned to one of many servers and queue until the server is free to process it. This is depicted schematically in Figure 1. To reduce waiting times at low cost, efficient algorithms for assigning jobs to servers are employed. The data centre can be modelled as a random process meaning it is assumed that customers arrive and are served at random intervals. However, it is difficult to analyse this random system and instead it can be approximated by one that is easier to analyse. Known as the ‘mean field’ approximation, it uses the idea that as we increase the number of servers in the data centre, the effect of the randomness becomes smaller. If the system is scaled up sufficiently, then it behaves deterministically. This scaled system may then approximate our original one. For my research I considered models with applications to cloud computing and media streaming. In these models, not every server is connected to every other and they may process jobs at different speeds, depicted in Figure 2. In this case it is not obvious how to scale up the system such that it approximates it well. However, I showed that if each server is replaced by a cluster of servers and the cluster size is scaled up, then the approximation still holds. Figure 1. Servers Data Centre Arriving Job Processed Job 2 n 4 1 1 3 4 2 … n 3 Arrivals Arrivals Departures 4 n n Figure 2.