RUI: Scaling Limits of Infinite Dimensional Queueing Models

This project entails investigating some mathematical questions that emerge in analyzing the performance of certain queueing models. Queueing models are probabilistic models that capture the inherent randomness in a variety of modern networks, such as those that arise in customer service systems, computing and telecommunications, transportation, and hi-tech manufacturing.

The network structure is typically deterministic, and the scheduling policy is usually specified. Randomness results from exogenous arrival times, service times, and internal routing. Feedback and non-head-of-the-line scheduling policies are common in such networks.

These local dynamics interact to produce aggregate behavior that is complex and often evades closed form analysis. Hence, tractable approximations are needed. In this project the PI will specify and validate various model approximations, analyzing their performance and/or optimal control, and interpreting those results for the original system. The project provides research training opportunities for graduate and undergraduate students.

This research project concerns the study of three queueing models operating under general distributional assumptions with distinct features presenting unique mathematical challenges as follows: (1) Develop a diffusion approximation for networks of processor sharing queues in the presence of feedback; (2) Obtain asymptotically optimal scheduling policies for multi-class many server queues with abandonment through the study of fluid and diffusion control problems; and (3) Prove limit theorems to justify fluid invariant states as approximations of stationary distributions for randomize load balancing algorithms. These models have been analyzed in various forms that include Markovian distributional assumptions, i.e., exponentially distributed inter-arrival, service, and/or abandonment times.

However, such assumptions are not particularly realistic for modeling the behavior of modern computers, communications, and customer service systems. Furthermore, the performance can be dramatically different for such systems in the presence of non-Markovian distributional assumptions. Therefore, system performance needs to be understood more fully.

From a mathematical point of view, general distributional assumptions result in the need to track significantly more information in order to represent the system state. For example, residual service times, age-in-service, and/or age-in-system must be tracked for each job in the system. This leads to an infinite dimensional system where measure-valued state descriptors provide an effective representation.

Despite this common descriptor, the mathematical challenges are different for each model due to distinct system dynamics. For processor sharing networks, a new methodology for analyzing the long-time behavior of fluid model solutions will be developed. It is anticipated that this methodology will translate to other systems where time sharing is present.

For the control of multi-class queues, non-linearity that arises in the fluid control problem for non-exponentially distributed abandonment times presents new challenges for demonstrating asymptotic optimality. Such non-linearities are expected to introduce further difficulties to be overcome in the analysis of a second order, diffusion control problem.

For randomized load balancing algorithms, a methodology for proving the convergence of fluid model solutions to invariant states as time approaches infinity will be developed. A challenge here is to devise strategies equipped to handle the countable system of couple measure-valued equations satisfied by fluid model solutions. Such strategies are expected to be relevant for the analysis of other models with load balancing.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.