权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Algorithmic and Market Design Challenges in Cloud Computing

AF：小：云计算中的算法和市场设计挑战

基本信息

批准号：
2110707
负责人：
Ian Kash
金额：
$ 49.98万
依托单位：
University of Illinois at Chicago
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2110707&HistoricalAwards=false
关键词：
AF Small Algorithmic Market Design

项目摘要

The global market for cloud computing is worth hundreds of billions of dollars, consumes about one percent of worldwide electricity use, and is growing rapidly. Thus, even small improvements in its operation would have substantial impacts on economic activity and society's ability to meet sustainability goals. Despite their importance, cloud-computing resources are currently priced and allocated using simple approaches. On the pricing side, most resources are sold using utility-style pricing where resources whose usage can be measured are priced based on the time they are used for and quantity used. On the allocation side simple policies are used to assign resources to customers and manage contention. This project will develop new algorithms and market designs to enable fairer and more efficient solutions to resource allocation problems faced by cloud providers around two main themes: (1) managing future demand and (2) simultaneous allocation of multiple resources. While the focus of the project is on challenges arising from cloud computing, similar challenges arise in other contexts, for example in electricity markets adapting to increased use of renewable resources with high variability in supply. With utility-style pricing, cloud providers have no information about the future plans of their customers, resulting in challenging online problems when managing future demand. This project will develop new resource-allocation algorithms to manage highly stochastic demands in the online setting as well as analyze new market designs that pair richer information elicited from customers about their future needs with novel algorithms to make use of that information. What makes this problem particularly complex is that satisfying these demands requires simultaneous allocation of multiple resources. Fair and efficient division of multiple resources with Leontief utilities (which require resources to be perfectly matched in quantity, like hot dogs and buns) has been studied for a decade since the introduction of the dominant resource-fairness algorithm, which attempts to equalize the amount each customer receives of their most demanded resource and was explicitly inspired by the challenges of allocating cloud-computing resources. However, several important issues have received only limited attention, thereby limiting the opportunities to apply these techniques in cloud systems. This project is addressing two such issues. First, many customers are seeking to complete a fixed amount of work, and so care about the time taken to complete that work rather than directly about the immediate quantity of resources allocated. Second, this is not a static allocation problem to be solved but a dynamic, online one. Thus, this project is developing new analyses and variants of fair-division approaches such as dominant resource fairness and maximum Nash welfare (the product of customer values) suitable for settings with limited demands and dynamic allocations.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

全球云计算市场价值数千亿美元，耗电量约占全球用电量的1%，而且还在快速增长。因此，其运作即使稍有改进，也会对经济活动和社会实现可持续发展目标的能力产生重大影响。尽管云计算资源很重要，但目前它们的定价和分配都很简单。在定价方面，大多数资源是使用公用事业式定价出售的，其中可以测量使用情况的资源是根据使用时间和使用量来定价的。在分配端，使用简单的策略将资源分配给客户并管理争用。该项目将开发新的算法和市场设计，以使云提供商面临的资源分配问题能够围绕两个主题提供更公平、更高效的解决方案：(1)管理未来需求和(2)同时分配多种资源。虽然该项目的重点是云计算带来的挑战，但在其他情况下也出现了类似的挑战，例如，在适应更多地使用供应变化很大的可再生资源的电力市场。由于采用公用事业式的定价方式，云提供商无法获得有关客户未来计划的信息，这导致在管理未来需求时出现具有挑战性的在线问题。该项目将开发新的资源分配算法，以管理在线环境中高度随机的需求，并分析新的市场设计，这些设计将从客户那里获得关于其未来需求的更丰富的信息，并使用新的算法来利用这些信息。使这一问题特别复杂的是，满足这些需求需要同时分配多种资源。自引入占主导地位的资源公平算法以来，人们已经对Leontief实用程序(需要资源在数量上完全匹配，如热狗和小面包)公平高效地分配多种资源进行了十年的研究，该算法试图均衡每个客户收到的最需要的资源的数量，显然是受到了分配云计算资源的挑战的启发。然而，几个重要的问题只得到了有限的关注，从而限制了在云系统中应用这些技术的机会。该项目正在解决两个这样的问题。首先，许多客户正在寻求完成固定数量的工作，因此他们关心的是完成这项工作所花费的时间，而不是直接关心分配的资源的即时数量。其次，这不是一个需要解决的静态分配问题，而是一个动态的在线问题。因此，该项目正在开发新的分析和公平划分方法的变体，例如主导资源公平性和最大纳什福利(客户价值的产品)，适用于需求有限和动态分配的环境。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。