In this thesis, we study the queueing systems with heterogeneous servers and service rate uncertainty under the Halfin-Whitt heavy traffic regime. First, we analyse many server queues with abandonments when service rates are i.i.d. random variables. We derive a diffusion approximation using a novel method. The diffusion has a random drift, and hence depending on the realisations of service rates, the system can be in Quality Driven (QD), Efficiency Driven (ED) or Quality-Efficiency-Driven (QED) regime. When the system is under QD or QED regime, the abandonments are negligible in the fluid limit, but when it is under ED regime, the probability of abandonment will converge to a non-zero value. We then analyse the optimal staffing levels to balance holding costs with staffing costs combining these three regimes. We also analyse how the variance of service rates influence abandonment rate. Next, we focus on the state space collapse (SSC) phenomenon. We prove that under some assumptions, the system process will collapse to a lower dimensional process without losing essential information. We first formulate a general method to prove SSC results inside pools for heavy traffic systems using the hydrodynamic limit idea. Then we work on the SSC in multi-class queueing networks under the Halfin-Whitt heavy traffic when service rates are i.i.d. random variables within pools. For such systems, exact analysis provides limited insight on the general properties. Alternatively, asymptotic analysis by diffusion approximation proves to be effective. Further, limit theorems, which state the diffusively scaled system process weakly converges to a diffusion process, are usually the central part in such asymptotic analysis. The SSC result is key to proving such a limit. We conclude by giving examples on how SSC is applied to the analysis of systems.

We consider a class of queueing systems that consist of server pools in parallel and multiple customer classes. Customer service times are assumed to be exponentially distributed. We study the asymptotic behavior of these queueing systems in a heavy traffic regime that is known as the Halfin and Whitt many-server asymptotic regime. Our main contribution is a general framework for establishing state space collapse results in the Halfin and Whitt many-server asymptotic regime for parallel server systems having multiple customer classes. In our work, state space collapse refers to a decrease in the dimension of the processes tracking the number of customers in each class waiting for service and the number of customers in each class being served by various server pools. We define and introduce a state space collapse function, which governs the exact details of the state space collapse. Our methodology is similar in spirit to that in Bramson (1998); however, Bramson studies an asymptotic regime in which the number of servers is fixed and Bramson does not require a state space collapse function. We illustrate the applications of our results in three different parallel server systems. The first system is a distributed parallel server system under the minimum-expected-delay faster-server-first (MED-FSF) or minimumexpected- delay load-balancing (MED-LB) policies. We prove that the MED-FSF policy minimizes the stationary distribution of total number of customers in the system. However, under the MED-FSF policy all the servers in our distributed system except those with the lowest service rate experience 100% utilization but under the MED-LB policy, on the other hand, the utilizations of all the server pools are equal. The second system we consider is known as the N-model. We show that when the service times only depend on the server pool providing service a static priority rule is asymptotically optimal. Finally, we study two results conjectured in the literature for V-systems. We show for all of these systems that the conditions on the hydrodynamic limits can easily be checked using the standard tools that have been developed in the literature to analyze fluid models.

We study two classes of stochastic systems, the limited processor sharing system and the multi-server system. They share the common feature that multiple jobs/customers are being processed simultaneously, which makes the study of them intrinsically difficult. In the limited processor sharing system, a limited number of jobs can equally share a single server, and the excess ones wait in a first-in-first-out buffer. The model is mainly motivated by computer related applications, such as database servers and packet transmission over the Internet. This model is studied in the first part of the thesis. The multi-server queue is mainly motivated by call centers, where each customer is handled by an agent. The number of customers being served at any time is limited by number of agents employed. Customers who can not be served upon arrival wait in a first-in-first-out buffer. This model is studied in the second part of the thesis.

abstract: This dissertation presents a novel algorithm for recovering missing values of co-evolving time series with partial embedded network information. The idea is to connect two sources of data through a shared low dimensional latent space. The proposed algorithm, named NetDyna, is an Expectation-Maximization algorithm, and uses the Kalman filter and matrix factorization approaches to infer the missing values both in the time series and embedded network. The experimental results on real datasets, including a Motes dataset and a Motion Capture dataset, show that (1) NetDyna outperforms other state-of-the-art algorithms, especially with partially observed network information; (2) its computational complexity scales linearly with the time duration of time series; and (3) the algorithm recovers the embedded network in addition to missing time series values. This dissertation also studies a load balancing algorithm, the so called power-of-two-choices(Po2), for many-server systems (with N servers) and focuses on the convergence of stationary distribution of Po2 in the both light and heavy traffic regimes to the solution of mean-field system. The framework of Stein’s method and state space collapse (SSC) are used to analyze both regimes. In both regimes, the thesis first uses the argument of state space collapse to show that the probability of the state being far from the mean-field solution is small enough. By a simple Markov inequality, it is able to show that the probability is indeed very small with a proper choice of parameters. Then, for the state space close to the solution of mean-field model, the thesis uses Stein’s method to show that the stochastic system is close to a linear mean-field model. By characterizing the generator difference, it is able to characterize the dominant terms in both regimes. Note that for heavy traffic case, the lower and upper bound analysis of a tridiagonal matrix, which arises from the linear mean-field model, is needed. From the dominant term, it allows to calculate the coefficient of the convergence rate. In the end, comparisons between the theoretical predictions and numerical simulations are presented. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2020

abstract: This dissertation studies load balancing algorithms for many-server systems (with N servers) and focuses on the steady-state performance of load balancing algorithms in the heavy traffic regime. The framework of Stein’s method and (iterative) state-space collapse (SSC) are used to analyze three load balancing systems: 1) load balancing in the Sub-Halfin-Whitt regime with exponential service time; 2) load balancing in the Beyond-Halfin-Whitt regime with exponential service time; 3) load balancing in the Sub-Halfin-Whitt regime with Coxian-2 service time. When in the Sub-Halfin-Whitt regime, the sufficient conditions are established such that any load balancing algorithm that satisfies the conditions have both asymptotic zero waiting time and zero waiting probability. Furthermore, the number of servers with more than one jobs is o(1), in other words, the system collapses to a one-dimensional space. The result is proven using Stein’s method and state space collapse (SSC), which are powerful mathematical tools for steady-state analysis of load balancing algorithms. The second system is in even “heavier” traffic regime, and an iterative refined procedure is proposed to obtain the steady-state metrics. Again, asymptotic zero delay and waiting are established for a set of load balancing algorithms. Different from the first system, the system collapses to a two-dimensional state-space instead of one-dimensional state-space. The third system is more challenging because of “non-monotonicity” with Coxian-2 service time, and an iterative state space collapse is proposed to tackle the “non-monotonicity” challenge. For these three systems, a set of load balancing algorithms is established, respectively, under which the probability that an incoming job is routed to an idle server is one asymptotically at steady-state. The set of load balancing algorithms includes join-the-shortest-queue (JSQ), idle-one-first(I1F), join-the-idle-queue (JIQ), and power-of-d-choices (Pod) with a carefully-chosen d. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2019