Thesis Defense :: State Space Collapse in Many-Server Diffusion Limits of Parallel Server Systems and Applications

Primary tabs

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 notion of state space collapse contrasts with that in Harrison and Van Mieghem [36], which establishes a deterministic relationship between a lower-dimensional workload process and the queue length processes. Our methodology is similar in spirit to that in Bramson [13]; 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 minimum-expected-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. We also show that under both policies the system performs as well as a corresponding single queue system. 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. The optimality is in terms of stochastically minimizing linear holding costs over any finite time interval. Finally, we study two results conjectured in the literature for V-systems. First, we prove a state space collapse result conjectured in Armony and Maglaras [3]. Then, we propose a policy whose asymptotic performance is arbitrarily close to the conjectured performance of the policy proposed by Milner and Olsen [53] and prove a state space collapse result under this policy. We show for all of these systems that the conditions on the hydrodynamic limits can easily be checked using the standard toolsthat have been developed in the literature to analyze fluid models.


  • Workflow Status: Published
  • Created By: Barbara Christopher
  • Created: 10/08/2010
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016


No keywords were submitted.

Target Audience