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

许多信息处理、服务和制造系统可以被视为相互作用的资源网络。例如，云计算数据中心、在线广告系统、电子芯片生产线、互联网和医疗保健服务系统。来自这样的系统的服务请求由诸如计算机、制造站和人工服务器的一组互连的资源来处理。在这类应用中，一个共同的目标是确定服务策略(路由、服务顺序和服务器控制算法)，以最大限度地减少客户使用系统的延迟。除了少数特殊情况外，目前还没有可用的数学工具来计算客户经历的延迟等性能指标，特别是当系统规模较大时。该项目的目标是改进计算大型网络资源系统的性能指标所需的数学工具。这些数学技术将支持为前面提到的无数应用程序设计良好的服务策略。该项目的成果将被纳入课程。将作出外联努力，将代表人数不足的群体和少数群体的学生纳入该项目。通常，相互作用的资源网络的最优控制问题可以建模为马尔可夫决策问题(MDP)，但状态空间太大，无法获得最优解。因此，通常将这类问题(在适当的尺度下)作为流体控制问题、布朗控制问题或大偏差问题来研究。这个项目的目标是实现另一种方法，包括研究适当选择的Lyapunov函数在暂态和稳态模式下的漂移。具体的挑战涉及为高维系统开发低维模型，并使用低维模型来研究特定体系结构和算法的最优性或缺乏最优性。如果成功，这个项目将导致(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.