Rigorous Approximations of Stochastic Network Dynamics, with Applications to Real-World Networks

随机网络动力学的严格近似及其在现实世界网络中的应用

基本信息

批准号：
1538706
负责人：
Kavita Ramanan
金额：
$ 25万
依托单位：
Brown University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2015
资助国家：
美国
起止时间：
2015-09-01 至 2018-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1538706&HistoricalAwards=false
关键词：
Rigorous Approximations Stochastic Network Dynamics

项目摘要

Stochastic networks are comprised of "jobs" in the form of packets or customers that arrive to a network and wait in buffers at different nodes of the networks until their processing requirements are fulfilled. Stochastic variability arises from randomness in arrival and processing times, as well as from routing and scheduling decisions. Such networks are ubiquitous and arise as models in diverse fields ranging from telecommunications and service systems to biological systems. A better understanding of these networks has the potential to lead to new algorithms that dramatically improve performance and enable the support of novel network applications. This award supports the development of a general mathematical framework for the analysis of two broad classes of stochastic networks: large-scale load-balancing networks that arise, for example, in web-server farms, and queueing networks that use scheduling policies involving prioritization, which are relevant for real-time scheduling in computer networks and health care systems. The goal is to identify tractable approximations of both transient dynamics and equilibrium behavior, rigorously establish their accuracy for suitable values of network parameters, and to use them to gain insight into network design. There will be mentorship of graduate students, a multidisciplinary project for an undergraduate student and opportunity for outreach. The project also involves interactions with industry, which increases the potential of impacting the design of real networks.Stochastic networks are typically too complex to admit an exact analysis. The goal then is to obtain tractable approximations, whose accuracy can be rigorously justified in a suitable (asymptotic) regime of network parameters via limit theorems for suitably scaled state processes. While there is a well developed mathematical theory of "scaling limits" for certain classes of networks, it does not cover the networks considered in this project, which involve many servers at a single node, general service distributions and non-head of the line scheduling policies. One of the challenges is that Markovian scaling limits of these networks are typically not finite-dimensional. The research will develop tractable infinite-dimensional Markovian representations of these systems, involving interacting measure-valued processes and infinite-dimensional Skorokhod maps, and rigorously establish scaling limit theorems. The analysis will combine methods from different fields, including probability, stochastic analysis, dynamical systems, partial differential equations and optimization. The tools developed will potentially be applicable more broadly for the study of analogous stochastic models arising in other applications. Simulations will also be carried out to ascertain the validity of these approximations for finite systems.

随机网络由数据包或客户形式的“作业”组成，这些“作业”到达网络并在网络不同节点的缓冲区中等待，直到满足其处理要求。随机变化源于到达和处理时间的随机性，以及路由和调度决策的随机性。这种网络无处不在，并且作为模型出现在从电信和服务系统到生物系统的各个领域。更好地了解这些网络有可能产生新的算法，从而显着提高性能并支持新颖的网络应用程序。该奖项支持开发一个通用数学框架，用于分析两大类随机网络：例如在网络服务器场中出现的大规模负载平衡网络，以及使用涉及优先级的调度策略的排队网络，这与计算机网络和医疗保健系统中的实时调度相关。目标是识别瞬态动力学和平衡行为的易于处理的近似值，严格确定其网络参数合适值的准确性，并使用它们来深入了解网络设计。将为研究生提供指导、为本科生提供多学科项目以及外展机会。该项目还涉及与行业的互动，这增加了影响真实网络设计的潜力。随机网络通常过于复杂，无法进行精确分析。然后的目标是获得易于处理的近似值，其准确性可以通过适当缩放的状态过程的极限定理在适当的（渐近）网络参数机制中得到严格证明。虽然对于某些类别的网络有一个完善的“扩展限制”数学理论，但它并不涵盖本项目中考虑的网络，其中涉及单个节点上的许多服务器、一般服务分布和非线头调度政策。挑战之一是这些网络的马尔可夫尺度限制通常不是有限维的。该研究将开发这些系统的易于处理的无限维马尔可夫表示，包括相互作用的测值过程和无限维 Skorokhod 图，并严格建立标度极限定理。该分析将结合不同领域的方法，包括概率、随机分析、动力系统、偏微分方程和优化。开发的工具可能会更广泛地适用于其他应用中出现的类似随机模型的研究。还将进行模拟以确定这些近似对于有限系统的有效性。