Collaborative Research: Resource Allocation in Clouds: A Stochastic Modeling and Control Perspective

云计算服务（如Amazon EC2系统、b谷歌AppEngine和Microsoft Azure）正变得无处不在，并开始成为企业和个人计算应用程序计算能力的主要来源。云计算平台（或者简单地说，云）可以按需方式向用户提供各种资源，包括基础设施、软件和服务。与传统的“拥有并使用”方法相比，云计算服务为云用户消除了购买和维护基础设施的成本，并允许用户根据自己的需要实时动态地扩大和缩小计算资源。云由许多机器（计算机）组成，每台机器都有一定数量的资源（CPU、RAM、硬盘空间等）。每台机器可以细分为多个虚拟机，每个虚拟机（VM）的行为就像一台拥有一定数量专用资源的小型机器。当用户向云提交作业时，他或她从云请求一定数量的资源，云通过在机器中创建具有所需资源的虚拟机来响应。资源分配问题是要弄清楚如何将作业分配给机器。此外，当多个作业等待服务时，云还必须决定下一步选择哪个作业进行服务。本项目的目标是设计资源分配算法，实现云的高效运行；设计定价机制，实现云服务提供商收益最大化，同时为竞争用户提供优质服务。智力优势：该领域的现有技术是将问题视为一系列静态问题，如下所示：考虑当前正在等待服务的作业，并通过解决组合优化问题将它们分配给机器。忽略系统动态特性的静态方法会导致不稳定。我们的观点是根本不同的：我们认为资源分配问题是一个动态的随机网络控制问题。我们将使用等待作业的队列长度信息作为反馈信号，以做出资源分配决策，例如将作业路由到机器和在机器上调度作业。为此，我们将回答一些基本问题：什么是云的稳定区域？;在计算复杂性和稳定性之间是否存在权衡？;除了稳定性之外，我们如何描述资源分配算法的性能？;云提供商应该如何为其资源定价，以实现社会福利或利润最大化？从理论角度来看，该方法的新颖之处在于在考虑计算复杂性的同时设计了控制和性能分析算法。更广泛的影响：pi教授研究生水平的课程，涵盖网络、游戏、控制理论和优化。我们是最早将网络应用纳入控制课程和控制应用纳入网络课程的公司之一。拟议的项目通过为控制理论方法开辟一个新的应用领域，即云计算，为这种交叉施肥提供了新的机会。私人学院在为来自代表性不足群体的本科生和研究生提供咨询方面有着良好的记录。我们也将继续为这个项目从这些学生团体中招募学生。我们还将利用具体的机会来实现这一目的，如NSF联盟研究生教育和教授（AGEP）计划，这是爱荷华州大学为招收少数民族学生而协调的努力，以及研究生少数民族助学金计划（GMAP），该计划为招收少数民族学生提供研究助学金资金。

Cloud computing services (such as Amazon EC2 system, Google AppEngine, and Microsoft Azure) are becoming ubiquitous and are starting to serve as the primary source of computing power for both enterprises and personal computing applications. A cloud computing platform (or simply, a cloud) can provide a variety of resources, including infrastructure, software, and services, to users in an on-demand fashion. Compared to traditional own-and-use approaches, cloud computing services eliminate the costs of purchasing and maintaining the infrastructures for cloud users, and allow the users to dynamically scale up and down computing resources in real time based on their needs.A cloud consists of a number of machines (computers), each with a certain amount of resources (CPU, RAM, hard disk space, etc.). Each machine can be subdivided into virtual machines, where each virtual machine (VM) behaves like a small machine with a certain amount of dedicated resources. When a user submits a job to the cloud, he or she requests a certain amount of resources from the cloud and the cloud responds by creating a VM with the required resources in a machine. The resource allocation problem is to figure out how to allocate jobs to machines. Further, when several jobs are waiting for service, the cloud must also decide which job to select for service next. The goal of this project is to design resource allocation algorithms for efficient operation of the cloud, and to design pricing mechanisms to maximize the cloud service provider revenue while providing good quality of service to competing users.Intellectual Merit: The prior art in this area is to view the problem as a sequence of static problems as follows: consider the jobs that are currently waiting for service and allocate them to machines by solving a combinatorial optimization problem. Static approaches which ignore the dynamic nature of the system lead to instability. Our viewpoint here is fundamentally different: we consider the resource allocation problem as a dynamic stochastic network control problem. We will use queue length information about waiting jobs as the feedback signal to take resource allocation decisions such as routing jobs to machines and scheduling jobs on machines. To this end, we will answer a number of fundamental questions: what is the stability region of a cloud? ; is there a tradeoff between computational complexity and stability? ; how can we characterize the performance of resource allocation algorithms beyond stability? ; and how should a cloud provider price its resources for maximizing social welfare or profit? From a theoretical perspective, the novelty in the proposed approach lies in the design of control and performance analysis algorithms while taking computational complexity considerations in account.Broader Impact: The PIs teach graduate-level courses spanning networks, games, control theory, and optimization. We were among the first to incorporate network applications in control courses and control applications in networking classes. The proposed project provides new opportunities for such cross-fertilization by opening up a new application area, namely cloud computing, for control-theoretic methodologies. The PIs have a strong record of advising undergraduate students and graduate students from underrepresented groups. We will continue our recruitment efforts from such student groups for this project also. We will also use specific opportunities for this purpose as applicable, such as the NSF Alliance Graduate Education and the Professoriate (AGEP) program, which is a coordinated effort by Iowa universities to recruit minorities, and the Graduate Minority Assistantship Program (GMAP), which provides funds for recruiting minority students on research assistantships.