Candidate: Thirupathaiah Vasantam
Title: On Occupancy Based Randomized Load Balancing for Large Systems with General Distributions
Date: November 4, 2019
Time: 9:30 AM
Place: EIT 3142
Supervisor(s): Mazumdar, Ravi R.
Abstract:
In a multi-server system, a job dispatcher employs load balancing techniques to balance the load on servers for efficient usage of available resources. An incoming job should be routed to the server that is least loaded in the entire system. Hence, it is inevitable for an optimal load balancing policy to be dependent on the state of servers. Since getting the information about the remaining workload of servers for every arrival is cumbersome, it is desirable to design load balancing policies which use occupancy or number of progressing jobs information of servers. Furthermore, if the system has a large number of servers, it is not desirable to use the occupancy information of all the servers to dispatch or route an arrival due to huge implementation cost. In large-scale systems that have thousands of servers, the policies which use the occupancy information of only a finite number of randomly selected servers to dispatch an arrival result in lower implementation cost than the policies which use the occupancy information of all the servers. Such policies are referred to as the occupancy based randomized load balancing policies.
Motivated by cloud computing systems and web-server farms, we study two types of models. In the first model, each server is an Erlang loss server, and this model is an abstraction to Infrastructure-as-a-Service (IaaS) clouds. We consider processor sharing servers in the second model. This is an abstraction to web-server farms which serve customers in a round-robin manner with small time granularity. Web-server farms provide service to delay sensitive applications. In most prior works, the analysis of these models was restricted to the case of exponential job length distributions. In this dissertation, we study the case of general job length distributions.
To analyze the impact of a load balancing policy, we need to develop models for the system dynamics. In this dissertation, we show that one can construct useful Markovian models. For occupancy based randomized routing policies, due to complex inter-dependencies between servers, an exact analysis is mostly intractable. However, we show that the multi-server systems that have an occupancy based randomized load balancing policy are examples of weakly interacting particle systems. In these systems, servers are interacting particles whose states lie in an uncountable state space. We develop a mean-field analysis to understand a server's behavior as the number of servers becomes large. We show that under certain assumptions, as the number of servers increases, the sequence of empirical measure-valued Markov processes which model the system dynamics converges to a deterministic measure-valued process referred to as the mean-field limit. We observe that the mean-field equations correspond to the dynamics of the distribution of a non-linear Markov process. A consequence of having the mean-field limit is that under minor and natural assumptions on the initial states of severs, any finite set of servers can shown to be independent of each other as the number of servers goes to infinity. Furthermore, the mean-field limit approximates each server's distribution in the transient regime when the number of servers is large.
A salient feature of loss and processor sharing systems in the setting where their time evolution can be modeled by reversible Markov processes is that their stationary occupancy distribution is insensitive to the type of job length distribution, but it depends only on the average job length. This property does not hold when the number of servers is finite in our context due to lack of reversibility. We however show that he fixed-point of the mean-field is insensitive to the job length distributions for all occupancy based randomized load balancing policies when the fixed-point is unique for job lengths that have exponential distributions. We also provide some deeper insights into the relationship between the mean-field and the distributions of servers and the empirical measure in the stationary regime.
Finally, we address the accuracy of mean-field approximations. We address the case of loss models. To do so we establish a functional central limit theorem under the assumption that the job lengths have exponential distributions. We show that a suitably scaled fluctuation of the stochastic empirical process around the mean-field converges to an Ornstein-Uhlenbeck process. Our analysis is also valid for the Halfin-Whitt regime in which servers are critically loaded. We then exploit the functional central limit theorem to quantify the error between the actual blocking probability of the system with a large number of servers and the blocking probability obtained from the fixed-point of the mean-field. Under the Halfin-Whitt regime, the error is of the order inverse square root of the number of servers. On the other hand, for light load regime, the error is smaller than the inverse square root of the number of servers.