CAREER: Scheduling and Resource Allocation in the Cloud using Graphical Models and Randomized Algorithms

职业：使用图形模型和随机算法在云中进行调度和资源分配

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

Scalability is crucial for cloud computing to be widely adopted. Failure to scale has resulted in the demise of the social networking giant MySpace, the inability to support a user load greater than 10% of system capacity, a $4.5 billion annual power expenditure on data centers and a lack of any sophisticated measurement and monitoring systems in the cloud. The size of a cloud, which often consists of tens of thousands of machines, compels the use of low-complexity algorithms, which, when naively designed, cause significant performance degradation as the system grows large. Existing algorithms are often designed for exact, optimal solutions for smaller in-house systems and do not scale due to their centralized high-complexity nature.This research overcomes the limitation of existing work by designing a suite of low-complexity algorithms for web services, data management, and measurement and monitoring in the cloud, which are exactly optimal only as the system size grows to infinity, but very close to optimal in finite and large systems. The algorithms are designed to address the challenges with dynamic scaling, multi-tenancy and data-intensiveness in the cloud, and for different application workloads including search, social networks and map-reduce. The research draws upon and contributes to the fields of graphical models and randomized algorithms, both of which exchange sparse information locally to achieve complex global objectives in large systems. The project also includes significant outreach programs in the form of workshops and lab open-houses, to promote undergraduate research, and the participation of women and under-represented minorities.

可扩展性对于云计算的广泛采用至关重要。无法扩展导致社交网络巨头MySpace的消亡，无法支持超过系统容量10%的用户负载，数据中心每年的电力支出为45亿美元，并且缺乏任何复杂的测量和监控系统。云的规模通常由数万台机器组成，这迫使使用低复杂度算法，当天真地设计时，随着系统变大，会导致显着的性能下降。现有的算法通常是为较小的内部系统设计的精确的最优解决方案，并且由于其集中的高复杂性而不能扩展。本研究通过设计一套低复杂度的算法来克服现有工作的局限性，用于Web服务，数据管理，以及云中的测量和监控，这些算法只有当系统大小增长到无穷大时才是最优的，但在有限和大型系统中非常接近最优。这些算法旨在解决云中动态扩展、多租户和数据密集型的挑战，以及不同的应用程序工作负载，包括搜索、社交网络和map-reduce。该研究借鉴并有助于图形模型和随机算法领域，这两者都在本地交换稀疏信息，以实现大型系统中复杂的全局目标。该项目还包括以讲习班和实验室开放的形式开展的重要外联方案，以促进本科生研究以及妇女和代表性不足的少数民族的参与。