RUI: Analysis and Control of Infinite Dimensional Queueing Models

California State University San Marcos Corporation, San Marcos CA

Investigators

Abstract

This project entails investigating some mathematical questions that emerge in the behavioral analysis 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, as well as 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 (HL) 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. The project involves specifying and validating various model approximations, analyzing their performance and/or optimal control and interpreting those results for the original system. More specifically, this project concerns the study of three queueing models with distinct features presenting unique mathematical challenges as follows: (1) to develop a diffusion approximation for networks of processor sharing queues, under general distributional assumptions in the presence of feedback; (2) to employ nonstandard, distribution dependent scaling to obtain a diffusion approximation for shortest remaining processing time queues; (3) to obtain asymptotically optimal scheduling policies for multiclass queues with abandonment under general distributional assumptions through the study of fluid control problems. Each model has been analyzed in various forms that include some Markovian distributional assumptions (i.e., exponentially distributed interarrival, service, and/or abandonment times). Such assumptions aren't particularly realistic for modeling the behavior of modern applications. 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 track the system state. For example, residual service times or residual abandonment times for each job in the system must be tracked in some form. This naturally leads to an infinite dimensional system where measure-valued state descriptors provide an effective tool for tracking the system state. In spite of employing this common modeling tool, the nature of the mathematical challenges are distinct for each model due to the distinct system dynamics. For processor sharing networks, a new strategy for analyzing the long time behavior of fluid model solutions will be developed. We anticipate that this methodology will translate to other systems where time-sharing is present. For shortest remaining processing time queues, nonstandard distribution dependent scaling is required to account for the order of magnitude difference between the queue length and workload processes in heavy traffic. Such behavior has not been observed for other scheduling policies. For the control of multiclass queues, new frameworks need to be developed to provide an analysis of the fluid control problem for generally distributed abandonment times. Such advances should further help in the analysis of a diffusion control problem.