Multi-resource allocation in cloud data centers: A trade-off on fairness and efficiency

摘要

Fair allocation has been studied intensively in both economics and computer science. Many existing mechanisms that consider fairness of resource allocation focus on a single resource. With the advance of cloud computing that centralizes multiple types of resources under one shared platform, multi-resource allocation has come into the spotlight. In fact, fair/efficient multi-resource allocation has become a fundamental problem in any shared computer system. The widely used solution is to partition resources into bundles that contain fixed amounts of different resources, so that multiple resources are abstracted as a single resource. However, this abstraction cannot satisfy different demands from heterogeneous users, especially on ensuring fairness among users competing for resources with different capacity limits. A promising approach to this problem is dominant resource fairness (DRF), which tries to equalize each user's dominant share (share of a user's most highly demanded resource, that is, the largest fraction of any resource that the user has required for a task), but this method may still suffer from significant loss of efficiency (i.e., some resources are underused). This article develops a new allocation mechanism based on DRF aiming to balance fairness and efficiency. We consider fairness not only in terms of a user's dominant resource, but also in another resource dimension which is secondarily desired by this user. We call this allocation mechanism 2-dominant resource fairness (2-DF). Then, we design a non-trivial on-line algorithm to find a 2-DF allocation and extend this concept to k-dominant resource fairness (k-DF).