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.
