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

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

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.