权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

RUI: Scaling Limits of Infinite Dimensional Queueing Models

RUI：无限维排队模型的扩展限制

基本信息

批准号：
2054505
负责人：
Amber Puha
金额：
$ 23.24万
依托单位：
California State University San Marcos Corporation
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-15 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2054505&HistoricalAwards=false
关键词：
RUI Scaling Limits Infinite Dimensional

项目摘要

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.

该项目需要研究在分析某些排队模型的性能时出现的一些数学问题。排队模型是概率模型，可以捕获各种现代网络中固有的随机性，例如客户服务系统、计算和电信、运输以及高科技制造中出现的网络。网络结构通常是确定性的，并且调度策略通常是指定的。随机性是由外部到达时间、服务时间和内部路由产生的。反馈和非队列调度策略在此类网络中很常见。这些局部动态相互作用产生复杂且常常逃避封闭形式分析的聚合行为。因此，需要易于处理的近似值。在此项目中，PI 将指定并验证各种模型近似值，分析其性能和/或最优控制，并解释原始系统的这些结果。该项目为研究生和本科生提供研究培训机会。该研究项目涉及研究在一般分布假设下运行的三种排队模型，这些模型具有独特的数学挑战，其独特的特征如下：（1）在存在反馈的情况下为处理器共享队列网络开发扩散近似； (2)通过流体和扩散控制问题的研究，得到多类多服务器队列放弃的渐近最优调度策略； (3) 证明极限定理，以证明流体不变状态是随机负载平衡算法的平稳分布的近似值。这些模型已经以各种形式进行了分析，包括马尔可夫分布假设，即指数分布的到达间隔、服务和/或放弃时间。然而，对于现代计算机、通信和客户服务系统的行为建模来说，这样的假设并不特别现实。此外，在存在非马尔可夫分布假设的情况下，此类系统的性能可能会显着不同。因此，需要更全面地了解系统性能。从数学的角度来看，一般的分布假设导致需要跟踪更多的信息才能表示系统状态。例如，必须跟踪系统中每个作业的剩余服务时间、服务年龄和/或系统年龄。这导致了无限维系统，其中测量值状态描述符提供了有效的表示。尽管有这个共同的描述符，但由于不同的系统动力学，每个模型面临的数学挑战都是不同的。对于处理器共享网络，将开发一种用于分析流体模型解决方案的长期行为的新方法。预计该方法将转化为存在分时的其他系统。对于多类别队列的控制，非指数分布放弃时间的流体控制问题中出现的非线性给证明渐近最优性带来了新的挑战。这种非线性预计会在二阶扩散控制问题的分析中引入需要克服的进一步困难。对于随机负载平衡算法，将开发一种方法来证明随着时间接近无穷大流体模型解收敛到不变状态。这里的一个挑战是设计策略来处理由流体模型解满足的耦合测量值方程的可数系统。此类策略预计将与其他具有负载平衡的模型的分析相关。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。