Fog computing is transforming the network edge into an intelligent platform by bringing storage, computing, control, and networking functions closer to end-users, things, and sensors. How to allocate multiple resource types (e.g., CPU, memory, bandwidth) of capacity-limited heterogeneous fog nodes to competing services with diverse requirements and preferences in a fair and efficient manner is a challenging task. To this end, we propose a novel market-based resource allocation framework in which the services act as buyers and fog resources act as divisible goods in the market. The proposed framework aims to compute a market equilibrium (ME) solution at which every service obtains its favorite resource bundle under the budget constraint while the system achieves high resource utilization. This work extends the General Equilibrium literature by considering a practical case of satiated utility functions. Also, we introduce the notions of non-wastefulness and frugality for equilibrium selection, and rigorously demonstrate that all the non-wasteful and frugal ME are the optimal solutions to a convex program. Furthermore, the proposed equilibrium is shown to possess salient fairness properties including envy-freeness, sharing-incentive, and proportionality. Another major contribution of this work is to develop a privacy-preserving distributed algorithm, which is of independent interest, for computing an ME while allowing market participants to obfuscate their private information. Finally, extensive performance evaluation is conducted to verify our theoretical analyses.
This work is also closely related to the MRA literature, which has received considerable attention recently. The state-of-the-art research on MRA for data centers is surveyed in @cite_25 . Noticeably, (DRF) @cite_34 is the most prominent approach to MRA fairness in data centers. In a nutshell, DRF is a generalization of max-min fairness for multiple resources, which aims to maximize the minimum dominant resource share across all the users. For the simplistic setting where all resources are pooled together in a single location and with some strong assumptions @cite_34 , DRF offers many compelling properties. This approach has been extended in the follow-up works @cite_14 @cite_46 @cite_13 @cite_27 to address more realistic assumptions such as user demands are finite and resources are distributed over multiple nodes. Both of these aspects are captured in our work. To the best of our knowledge, this is the problem in a general setting with , each of which has multiple resource types, and multiple users with . While similar market-based approaches have been examined in @cite_13 @cite_32 , they consider simpler settings (e.g., a single resource pool, a single resource type, and or infinite demands).
@cite_14 @cite_32 @cite_27 @cite_46 @cite_34 @cite_13 @cite_25
2003859203 2055748525 2155053108 1987354455 1890643295 103955348 2745464933
Quantifying the notion of fairness is underexplored when there are multiple types of resources and users request different ratios of the different resources. A typical example is data centers processing jobs with heterogeneous resource requirements on CPU, memory, network bandwidth, etc. In such cases, a tradeoff arises between equitability, or "fairness," and efficiency. This paper develops a unifying framework addressing the fairness-efficiency tradeoff in light of multiple types of resources. We develop two families of fairness functions that provide different tradeoffs, characterize the effect of user requests' heterogeneity, and prove conditions under which these fairness measures satisfy the Pareto efficiency, sharing incentive, and envy-free properties. Intuitions behind the analysis are explained in two visualizations of multiresource allocation. We also investigate people's fairness perceptions through an online survey of allocation preferences. Max-Min Fairness is a flexible resource allocation mechanism used in most datacenter schedulers. However, an increasing number of jobs have hard placement constraints, restricting the machines they can run on due to special hardware or software requirements. It is unclear how to define, and achieve, max-min fairness in the presence of such constraints. We propose Constrained Max-Min Fairness (CMMF), an extension to max-min fairness that supports placement constraints, and show that it is the only policy satisfying an important property that incentivizes users to pool resources. Optimally computing CMMF is challenging, but we show that a remarkably simple online scheduler, called Choosy, approximates the optimal scheduler well. Through experiments, analysis, and simulations, we show that Choosy on average differs 2 from the optimal CMMF allocation, and lets jobs achieve their fair share quickly. We study the problem of allocating multiple resources to agents with heterogeneous demands. Technological advances such as cloud computing and data centers provide a new impetus for investigating this problem under the assumption that agents demand the resources in fixed proportions, known in economics as Leontief preferences. In a recent paper, [2011] introduced the dominant resource fairness (DRF) mechanism, which was shown to possess highly desirable theoretical properties under Leontief preferences. We extend their results in three directions. First, we show that DRF generalizes to more expressive settings, and leverage a new technical framework to formally extend its guarantees. Second, we study the relation between social welfare and properties such as truthfulness; DRF performs poorly in terms of social welfare, but we show that this is an unavoidable shortcoming that is shared by every mechanism that satisfies one of three basic properties. Third, and most importantly, we study a realistic setting that involves indivisibilities. We chart the boundaries of the possible in this setting, contributing a new relaxed notion of fairness and providing both possibility and impossibility results. We study the multi-resource allocation problem in cloud computing systems where the resource pool is constructed from a large number of heterogeneous servers, representing different points in the configuration space of resources such as processing, memory, and storage. We design a multi-resource allocation mechanism, called DRFH, that generalizes the notion of Dominant Resource Fairness (DRF) from a single server to multiple heterogeneous servers. DRFH provides a number of highly desirable properties. With DRFH, no user prefers the allocation of another user; no one can improve its allocation without decreasing that of the others; and more importantly, no coalition behavior of misreporting resource demands can benefit all its members. DRFH also ensures some level of service isolation among the users. As a direct application, we design a simple heuristic that implements DRFH in real-world systems. Large-scale simulations driven by Google cluster traces show that DRFH significantly outperforms the traditional slot-based scheduler, leading to much higher resource utilization with substantially shorter job completion times. We consider the problem of fair resource allocation in a system containing different resource types, where each user may have different demands for each resource. To address this problem, we propose Dominant Resource Fairness (DRF), a generalization of max-min fairness to multiple resource types. We show that DRF, unlike other possible policies, satisfies several highly desirable properties. First, DRF incentivizes users to share resources, by ensuring that no user is better off if resources are equally partitioned among them. Second, DRF is strategy-proof, as a user cannot increase her allocation by lying about her requirements. Third, DRF is envy-free, as no user would want to trade her allocation with that of another user. Finally, DRF allocations are Pareto efficient, as it is not possible to improve the allocation of a user without decreasing the allocation of another user. We have implemented DRF in the Mesos cluster resource manager, and show that it leads to better throughput and fairness than the slot-based fair sharing schemes in current cluster schedulers. We consider the age-old problem of allocating items among different agents in a way that is efficient and fair. Two papers, by and , have recently studied this problem in the context of computer systems. Both papers had similar models for agent preferences, but advocated different notions of fairness. We formalize both fairness notions in economic terms, extending them to apply to a larger family of utilities. Noting that in settings with such utilities efficiency is easily achieved in multiple ways, we study notions of fairness as criteria for choosing between different efficient allocations. Our technical results are algorithms for finding fair allocations corresponding to two fairness notions: Regarding the notion suggested by , we present a polynomial-time algorithm that computes an allocation for a general class of fairness notions, in which their notion is included. For the other, suggested by , we show that a competitive market equilibrium achieves the desired notion of fairness, thereby obtaining a polynomial-time algorithm that computes such a fair allocation and solving the main open problem raised by Multi-resource allocation in data centers determines a network and service management task of crucial importance. While, traditionally computing systems are shared based on a single resource, it was shown that in data centers this simplification often impedes overall efficiency and fairness. Therefore, newer approaches consider data center resource allocations as a multi-resource allocation problem. However, the capability of these approaches to reach overall fairness or efficiency is limited due to theoretical assumptions they make or due to practical means they deploy to control resources. This survey: 1) details all steps necessary to allocate data center resources and puts these steps in relation to each other; 2) highly relevant concepts in support of fair data center resource allocations, such as utility functions and allocation characteristics, are discussed and compared; and 3) in turn, major approaches to allocate multiple data center resources in a fair manner are outlined, mapped to practical steps and economically driven-targets, and compared with respect to their suitability of being applied in today’s data centers.