Collaborative Research: Performance Analysis and Design of Systems with Interconnected Resources

许多信息处理、服务和制造系统可以看作是相互作用的资源网络。示例包括用于云计算的数据中心、在线广告系统、电子芯片生产线、互联网和医疗保健服务系统。来自此类系统的服务请求由一组相互连接的资源（如计算机、制造站和人工服务器）处理。在这样的应用程序中，一个共同的目标是确定服务策略（路由、服务顺序和服务器控制算法），以最大限度地减少使用系统的客户的延迟。除了少数特殊情况外，目前还没有可用的数学工具来计算性能指标，例如客户所经历的延迟，特别是在系统规模较大的情况下。该项目的目标是推进计算大型网络资源系统的性能指标所需的数学工具。这些数学技术将支持为前面提到的无数应用程序设计良好的服务策略。该项目的成果将被纳入课程。我们将努力将代表性不足的群体和少数民族的学生纳入项目。通常，交互资源网络的最优控制问题可以建模为马尔可夫决策问题（MDP），但是状态空间太大，无法获得最优解。因此，通常将这类问题（在适当的尺度下）作为流体控制问题、布朗控制问题或大偏差问题来研究。该项目的目标是实现一种替代方法，其中包括研究适当选择的李雅普诺夫函数在瞬态和稳态模式下的漂移。具体的挑战包括为高维系统开发低维模型，并使用低维模型来研究特定架构和算法的最优性或缺乏最优性。如果成功，该项目将产生(i)基于基于漂移的参数的新分析工具，它为大型网络中的控制和决策算法的稳态性能提供严格的界限，以及（ii）设计在所有流量负载下表现良好的最佳或接近最佳算法。

Many information processing, service and manufacturing systems can be viewed as networks of interacting resources. Examples include data centers for cloud computing, online advertising systems, electronic chip manufacturing lines, the Internet, and health care service systems. Requests for services from such systems are processed by an interconnected set of resources such as computers, manufacturing stations, and human servers. In such applications, a common objective is to identify service policies (routing, service order, and server control algorithms) that minimize delays for customers using the system. Except in a few special cases, currently there are no mathematical tools available to compute performance metrics such as the delay experienced by the customers, especially when the system size is large. The goal of this project is to advance the mathematics tools needed to compute performance metrics of large systems of networked resources. These mathematical techniques will enable the design of good service policies for the myriad of applications mentioned earlier. The results from the project will be incorporated into courses. Outreach efforts will be made to include students from underrepresented groups and minorities in the project. Often the problem of optimal control of networks of interacting resources can be modeled as a Markov Decision Problem (MDP), but the state-space is prohibitively large to obtain optimal solutions. Therefore, it is common to study such problems (under some appropriate scaling) either as fluid control problems, or Brownian control problems, or large-deviations problems. The objective of this project is to enable an alternative approach, which involves studying the drift of appropriately-chosen Lyapunov functions, in transient and steady-state modes. The specific challenge involves developing lower-dimensional models for high-dimensional systems, and using the lower-dimensional models to study the optimality, or lack thereof, of specific architectures and algorithms. If successful, this project will result in (i) new analysis tools based on the drift-based arguments, which provide tight bounds on the steady-state performance of control and decision algorithms in large networks, and (ii) design of optimal or near-optimal algorithms that perform well at all traffic loads.