Scaling limits of queueing systems on graphs

嵌入式系统的网络在应用概率和运筹学中有着广泛的应用，例如在呼叫中心、工厂、商店、办公室、医院、公共交通服务和云计算系统的设计中。该项目的目标是了解网络对大型交互式嵌入式系统性能的影响，无论是在典型的场景中，还是在罕见的和意想不到的场景中，都会产生重大的后果。该研究有助于系统管理者设计调度网络和调度策略，从而提高系统的效率和稳定性。该项目还将为交互队列网络问题开发新的数学技术，其结果将有益于研究超越排队系统的领域，如社会科学和流行病学。本研究计划包括培养本科生、研究生及博士后研究人员，主要研究随机图上大规模负载均衡排队系统的渐近行为，包括加入最短队列、加入空闲队列及幂次策略。将考虑三类图：经典完全图，具有齐次极限的随机图和异质随机图。研究目标是严格理解随机网络对系统性能的关键和挑战性影响，特别是与经典完全图设置的显著偏离，通过获得各种缩放限制，包括大数定律，中心极限定理，长时间稳定性，大偏差原则和中等偏差原则，并分析了稀有事件概率数值估计的加速蒙特-卡罗格式。对典型渐近行为的研究需要弱相互作用粒子系统理论和随机图/图子理论的结合。获得大的和中等的偏差原则的主要挑战来自系统的无穷维动力学，消失的过渡率，和不连续的统计特性。除了使用经典的大偏差方法和弱收敛方法外，非典型渐进行为的研究还需要开发新技术，涉及随机分析和微分方程工具的组合。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Networks of queueing systems have broad applications in applied probability and operations research, such as in the design of call centers, factories, shops, offices, hospitals, public transportation services, and cloud computing systems. The goal of this project is to understand the impact of the network on the performance of large interacting queueing systems, in both typical scenarios and rare and unexpected scenarios with significant consequences. This research will help system managers design the queueing network and queueing policies, which will lead to better system efficiency and stability. The project will also develop new mathematical techniques for problems of networks of interacting queues, and the results will be beneficial to the study of areas beyond queueing systems, such as social science and epidemiology. This research project includes training undergraduate students, graduate students, and postdoctoral researchers.This project focuses mainly on the analysis of asymptotic behavior of large-scale load balancing queueing systems on random graphs, including join-the-shortest-queue, join-the-idle-queue and power-of-d policies. Three classes of graphs will be considered: classic complete graphs, random graphs with homogeneous limits, and heterogeneous random graphs. The research objectives are to rigorously understand the crucial and challenging impacts of stochastic networks on the system performance, in particular the significant deviation from the classic complete graph setup, via obtaining various scaling limits, including laws of large numbers, central limit theorems, long-time stability, large deviation principles and moderate deviation principles, together with analyzing the associated accelerated Monte-Carlo schemes of numerical estimation of rare event probabilities. The study of typical asymptotic behaviors will require a combination of tools from the theory of weakly interacting particle systems and random graph/graphon theory. The main challenges of obtaining large and moderate deviation principles arise from system features of infinite dimensional dynamics, vanishing transition rates, and discontinuous statistics. Besides using classic large deviation approaches and weak convergence approaches, the study of atypical asymptotic behaviors will also require the development of new techniques, involving a combination of tools from stochastic analysis and differential equations.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.