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.

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