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