PaperlayerView exact revision on arXiv

Source-linked AI summary

Dominant Resource Fairness in Cloud Computing Systems with Heterogeneous Servers

Wei Wang, Baochun Li, Ben Liang

arXiv:1308.0083v1cs.DC

TL;DR

Cloud allocation must reconcile heterogeneous server configurations and resource demands, while existing slot abstractions can ignore those differences. The paper proposes DRFH, a fairness mechanism for heterogeneous servers, and reports higher resource utilization and shorter job completion times than traditional slot scheduling.

  • Problem

    Heterogeneous servers and resource demands challenge allocation, while slot-based abstractions ignore those differences and can lead to inefficient allocation.

    Source: §I · p. 1

  • Method

    DRFH generalizes DRF by equalizing users’ global dominant shares across a pool of heterogeneous servers.

    Source: §I · p. 2, A. Basic Setting · p. 2

  • Results

    DRFH implementations significantly outperform Slots in resource utilization, and Best-Fit DRFH gives higher task-completion ratios for almost all users, with around 20% completing all tasks only under Best-Fit DRFH.

    Source: §VI · pp. 8–9

  • Takeaways & Limitations

    DRFH provides Pareto optimality, envy-freeness, and truthfulness, while its heuristic offers a practical way to schedule tasks in real-world systems.

    Source: §I · p. 2, B. Scheduling Tasks as Entities · p. 7

Abstract

from arXiv · show

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 user has an incentive to lie about its resource demand. 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.

I. INTRODUCTION

Cloud allocation must address heterogeneous servers and workload demands, while extending multi-resource fairness beyond the single-server model. The paper proposes DRFH, defines a heterogeneous-server allocation model, and evaluates a scheduling heuristic using Google cluster traces.

I. INTRODUCTION

  • Cloud systems combine diverse server configurations and workload demand profiles, challenging allocation mechanisms to balance fairness and efficiency.The paper notes that CPU-intensive and high-memory applications can have distinct demands.Source: §I · p. 1

II. RELATED WORK

  • Prior cloud schedulers allocate fixed-resource slots, an abstraction that ignores server and demand heterogeneity and can produce inefficient allocations.Related work on multi-resource fairness also largely assumes a single all-in-one server.Source: §I · p. 1, §II · p. 2
  • Earlier DRF work handles multi-resource demand but assumes resources are concentrated in one server, leaving heterogeneous-server allocation and dominant-resource definitions unresolved.Applying DRF separately on each server is described as highly inefficient.Source: §I · p. 1

I. INTRODUCTION

  • DRFH equalizes users’ global dominant shares and is Pareto optimal, envy-free, and truthful in heterogeneous-server systems.The paper also reports single-server DRF, single-resource fairness, bottleneck fairness, and population monotonicity properties.Source: §I · p. 2

A. Basic Setting

  • The model represents the resource pool as heterogeneous servers with multiple resource capacities and users with per-task demand vectors.Its basic-setting example contrasts memory-intensive and CPU-heavy users across high-memory and high-CPU servers.Source: A. Basic Setting · pp. 2–3

B. Resource Allocation

The section defines allocations by the resources assigned to users on each server and evaluates them by how many tasks users can schedule. It also introduces non-wastefulness: an allocation should not include resources that can be removed without reducing scheduled tasks.

B. Resource Allocation

  • A user’s allocation across servers determines its total schedulable tasks, and users prefer allocations that let them schedule more tasks.The per-server task count is aggregated across the user’s allocation.Source: B. Resource Allocation · p. 3
  • An allocation is non-wasteful when removing any allocated resource reduces the number of tasks the user can schedule.The definition applies per user and server, then to the overall allocation.Source: B. Resource Allocation · p. 3
  • Allocated resources that are never used can be revoked without changing the number of tasks scheduled, yielding a non-wasteful allocation.Source: B. Resource Allocation · p. 3

C. Allocation Mechanism and Desirable Properties

The section defines core fairness and efficiency criteria for allocation mechanisms, while noting that sharing incentive lacks a clear benchmark in heterogeneous systems.

D. Naive DRF Extension and Its Inefficiency

Applying DRF independently on heterogeneous servers can be inefficient; DRFH instead jointly allocates across servers by maximizing users’ minimum global dominant share.

D. Naive DRF Extension and Its Inefficiency

  • Per-server DRF gives each user six tasks in the example, while assigning each server exclusively to the user best suited to it lets both schedule 10.The naive extension can produce arbitrarily low resource utilization.Source: D. Naive DRF Extension and Its… · p. 4

IV. DRFH ALLOCATION AND ITS PROPERTIES

  • DRFH generalizes DRF to heterogeneous servers and is analyzed for the desirable properties defined earlier.Source: §IV · p. 4

A. DRFH Allocation

  • DRFH jointly allocates across heterogeneous servers by maximizing the minimum global dominant share subject to server capacity and fairness constraints.For a non-wasteful allocation, each user’s allocation on a server is proportional to its demand there.Source: A. DRFH Allocation · pp. 4–5
  • Both users schedule 10 tasks in the example under DRFH, with maximum global dominant share g = 5/7.The allocation assigns server 1 exclusively to user 1 and server 2 exclusively to user 2.Source: Figure 3 · p. 5, A. DRFH Allocation · p. 5

B. Analysis of Essential Properties

The analysis establishes that DRFH satisfies envy-freeness, Pareto optimality, and truthfulness.

C. Analysis of Important Properties

DRFH recovers several established fairness properties in special cases and satisfies population monotonicity when a user leaves.

D. Discussions of Sharing Incentive

For heterogeneous multi-server pools, an equal-share benchmark is ambiguous, so the paper uses a dedicated-cloud comparison based on servers drawn from the system’s configuration distribution. It compares tasks scheduled on that cloud with tasks scheduled in the shared system.

D. Discussions of Sharing Incentive

  • With multiple heterogeneous servers, infinitely many allocations can evenly divide the resource pool, so an equal division does not provide a unique benchmark.The passage illustrates two allocations that each give both users 7 CPUs and 7 GB of memory.Source: D. Discussions of Sharing Incentive · p. 7
  • Giving every user 1/n of each server’s resources has little practical meaning when n is large, because each slice may be unusable by computing tasks.The paper therefore considers another benchmark.Source: D. Discussions of Sharing Incentive · p. 7
  • The sharing-incentive benchmark compares tasks scheduled on each user’s dedicated cloud with tasks scheduled in the shared cloud.Each dedicated cloud contains k/n servers drawn from the system’s server-configuration distribution.Source: D. Discussions of Sharing Incentive · p. 7

V. PRACTICAL CONSIDERATIONS

The section introduces relaxing assumptions that may not hold in real-world systems and discussing practical DRFH implementation.

V. PRACTICAL CONSIDERATIONS

  • The section frames its practical discussion as relaxing assumptions that may not hold in real-world systems.It discusses how DRFH can be implemented in practice.Source: §V · p. 7

A. Weighted Users with a Finite Number of Tasks

DRFH can accommodate unequal user weights and finite task demands. With finite demands, it allocates iteratively until users finish their tasks or resources run out.

A. Weighted Users with a Finite Number of Tasks

  • For unequal user weights, DRFH seeks weighted max-min fairness by maximizing the minimum weight-normalized global dominant share under the same resource constraints.The discussion begins from assumptions of equal weights and infinite computing demands, which it says can be removed with minor modifications.Source: A. Weighted Users with a Finite Number… · p. 7
  • With finite task counts, DRFH raises active users’ global dominant shares iteratively until a user’s tasks are all scheduled, then removes that user from later rounds.The process repeats until no users remain active or no more resources can be allocated; the analysis also extends to weighted users with finite task counts.Source: A. Weighted Users with a Finite Number… · p. 7

B. Scheduling Tasks as Entities

For indivisible tasks, the paper describes progressive filling and proposes Best-Fit DRFH to implement DRFH with higher resource utilization. Best-Fit selects the lowest-global-dominant-share user and assigns its task to a server that best matches its resource demand.

B. Scheduling Tasks as Entities

  • For indivisible tasks, progressive filling serves the user with the lowest global dominant share and uses First-Fit to pick the first server that fits the task.First-Fit offers a fairly good approximation to DRFH.Source: B. Scheduling Tasks as Entities · p. 7
  • The proposed Best-Fit DRFH heuristic can lead to a better allocation with higher resource utilization than First-Fit.Both heuristics choose the user with the lowest global dominant share to serve.Source: B. Scheduling Tasks as Entities · p. 8
  • Best-Fit assigns the selected user’s task to the server with the lowest H(i, l), a score comparing the task’s resource demand vector with the server’s remaining resource vector.A smaller score indicates a better fit; for example, CPU-heavy tasks better fit servers with more available CPU resources.Source: B. Scheduling Tasks as Entities · p. 8

VI. SIMULATION RESULTS

Simulations evaluate DRFH under dynamic arrivals, resource utilization, job completion, per-user task completion, and cloud sharing. Best-Fit DRFH improves utilization over Slots, with completion-time gains concentrated in larger jobs; sharing benefits most users but not all.

Dynamic allocation

  • With dynamic arrivals and departures, Best-Fit DRFH precisely achieves DRFH allocations, equalizing users’ global dominant shares as competition changes.In the three-user simulation, users receive equal global dominant shares when sharing the system.Source: §VI · p. 8, Figure 4 · p. 8

Resource utilization

  • The two DRFH implementations significantly outperform the traditional Slots scheduler, with much higher CPU and memory utilization, mainly because Slots ignores heterogeneity in both servers and workload.Fig. 5 depicts the time series of CPU and memory utilization for the three algorithms.Source: §VI · p. 8, Figure 5 · p. 9

Job completion times

  • Best-Fit DRFH reduces job completion times versus Slots for larger jobs, while small jobs show no improvement.The analysis compares completion-time CDFs and groups jobs into five categories by task count.Source: Figure 6 · p. 9, §VI · p. 9

Resource utilization

  • Best-Fit DRFH achieves uniformly higher resource utilization than the First-Fit DRFH alternative.The comparison reports this advantage throughout the evaluation period.Source: §VI · p. 9

Task completion ratio

  • Best-Fit DRFH yields higher task completion ratios for almost all users; around 20% finish all tasks under Best-Fit but not Slots.The per-user comparison measures completed tasks divided by submitted tasks.Source: Figure 7 · p. 9, §VI · p. 9

Sharing incentive

  • Only 2% of users complete fewer tasks in the shared cloud than in proportional dedicated clouds, and their completion-ratio decreases are slight.DRFH does not guarantee a sharing incentive for every user.Source: Figure 8 · p. 9, §VI · p. 9

VII. CONCLUDING REMARKS

DRFH extends DRF to heterogeneous multi-server resource pools by equalizing users’ global dominant shares. The paper reports that it retains key fairness properties and that a Best-Fit implementation improves utilization and job completion times over slot scheduling.

Concluding remarks

  • DRFH generalizes DRF by equalizing each user’s global dominant share across a heterogeneous cloud resource pool.The pool contains servers with different resource configurations.Source: §VII · p. 9
  • DRFH is envy-free, Pareto optimal, and truthful, retaining almost all desirable properties of single-server DRF.Source: §VII · p. 9
  • Google-trace simulations show that Best-Fit DRFH improves resource utilization and job completion times over traditional slot-based scheduling.Source: §VII · p. 9
Loading 1308.0083v1…