Candidate
Arpan Mukhopadhyay
Title
Randomized Job Assignment in Heterogeneous Multi-Server Systems
Supervisor
Ravi Mazumdar
Abstract
We consider a class of large multi-server systems, that arise in the context of web-server farms and cloud data centers. In such systems, servers with heterogeneous capacities work in parallel to process incoming jobs or requests. We study schemes to assign the incoming jobs to the servers with the goal of achieving optimal performance in terms of certain metrics of interest while requiring the state information of only a small number of servers in the system. To this end, we consider randomized dynamic job assignment schemes which sample a small random subset of servers at every job arrival instant and assign the incoming job to one of the sampled servers based on their instantaneous states. Using mean field techniques the performances of such schemes are studied in the limit as the arrival rate of jobs and the number of servers in the system are scaled by the same large factor.
We show that for heterogeneous systems, naive sampling of the servers may result in an `unstable' system. We propose schemes which maintain stability by suitably sampling the servers. The performances of these schemes are studied via the corresponding mean field limits, that are shown to exist. The existence and uniqueness of a globally attractive equilibrium point of the mean field is established in every case. Furthermore, it is shown that, in the large system limit, the servers become independent of each other and the stationary distribution of occupancy of each server can be obtained from the unique equilibrium point of the mean field. The stationary tail distribution of server occupancies is shown to have a fast decay rate which suggests significantly improved performance for the appropriate metrics relevant to the application. Numerical studies are presented which show that the proposed randomized dynamic schemes significantly outperform randomized static schemes where job assignments are made independently of the server states. In certain scenarios, the randomized dynamic schemes are observed to be nearly optimal in terms of their performances.