Fairness of Multi-Resource Allocations





One of our motivating examples for exploring multi-resource fairness comes from datacenters: when processing jobs, resources such as memory and CPU cannot be readily exchanged for each other, yet different jobs need different combinations of these resources. We consider a simple example of a datacenter with two clients and two resources: memory and CPUs. User 1 requires 1 CPU and 4 GB of RAM for each job, and user 2 requires 3 CPUs and 1 GB of RAM for each job. There are 9 CPUs and 18 GB of RAM at first. We then vary these constraint values to observe their impact on fairness. Overall, we have the allocation problem \begin{equation*} \displaystyle\max_{x,y}\; f(x, y) \quad {\rm s.t.}\; x + 3y \leq 9,\;4x + y \leq 18 \end{equation*} where \(f\) denotes the fairness function used and \(x\) and \(y\) are the number of jobs allocated to users 1 and 2 respectively.

We first add more clients to the system to compare the amount of capacity left over as the number of users increased. Users' CPU requirements were fixed at 2 CPUs; their RAM requirements were drawn from a uniform distribution. Other randomly chosen RAM requirements yield similar plots. In all cases, only RAM capacity was leftover; all of the CPUs were used. For a large number of users, we see that FDS and GFJ both use more capacity than DRF (dominant resource fairness, obtained from FDS by takes \(\beta\rightarrow\infty\), \(\lambda\rightarrow -1\)).

Leftover\_Capacity\_Uniform img

To further explore the efficiency of different optimal allocations, we vary the RAM capacity and measure the efficiency of the resulting allocations, for various \(\beta\) and \(\lambda\) parameter values. The figure below shows the results for both FDS and GFJ; the line denotes the efficiency at the DRF-optimal allocation. We see that when the dominant shares for both users are equal, at 12 GB of RAM capacity, GFJ and FDS have the same range of achievable efficiency. Moreover, \(\beta\) and \(\lambda\) can be chosen to achieve higher efficiency in FDS and GFJ. The DRF function serves as a "lower bound" to the efficiency values attainable with the FDS functions.

Efficiency\_Region\_Both img

We next evaluate the fairness-efficiency tradeoff evinced by this datacenter example for different values of \(\beta\) (using \(\beta = \alpha\)-fairness, so that \(\lambda = (1 - \beta)/\beta\)). In the figure below, we measure the fairness and efficiency of the optimal allocation as \(\beta\) increases; fairness is measured as a percentage of dominant resource fairness, while efficiency is measured as a percentage of the maximum efficiency. As \(\beta\) grows larger, the percent efficiency from the FDS measure drops, approaching DRF in the limit \(\beta\rightarrow\infty\). The GFJ fairness increases until \(\beta = 2.6\), at which point the GFJ-optimal allocation is also DRF-optimal. For larger values of \(\beta\), GFJ quickly converges to an allocation with a more equal number of jobs per user; thus, its efficiency decreases. But efficiency in FDS decreases more slowly since FDS attempts to make the dominant shares, not the number of jobs, more equitable.


Finally, we explore the fairness-efficiency tradeoffs achieved for a full range of parameter values. The figure below shows different achieved tradeoffs for GFJ as the RAM capacity varies from 4 GB to 27 GB; we again use DRF as the maximal fairness metric. In this case, the range of attainable efficiency at the maximum allocation decreases as the fairness value increases. Thus, one can increase both fairness and efficiency as RAM capacity goes from 4 GB to 25 GB. Moreover, the contour lines "bend back" on themselves, indicating that for different \(\beta\) and \(\lambda\) parameters, the same fairness value can result in many efficiency values at the optimal allocation. When RAM capacity equals 11.25 GB, there is no tradeoff between fairness and efficiency.

TradeOff_EfficiencyVsFairness img