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.

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

项目成果

Rare Nash Equilibria and the Price of Anarchy in Large Static Games

• DOI: 10.1287/moor.2018.0929
• 发表时间: 2017-02
• 期刊: Math. Oper. Res.
• 作者: D. Lacker;K. Ramanan