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

合作研究：云中的资源分配：随机建模和控制视角

• 批准号: 1202065
• 负责人: Rayadurgam Srikant
• 金额: $ 22.46万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1202065&HistoricalAwards=false
• 关键词: Collaborative; Research; Resource; Allocation; Clouds

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.

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