Balancing Global and Local Fairness Allocation Model in Heterogeneous Data Center

Abstract

Aiming at the problem that the bandwidth allocation method in heterogeneous data center can’t take into account the global and local fairness, we propose an allocation method called GLA that satisfies fair attributes and can improve the utilization of system resources by nearly 20% when the number of clients are more than six contrasting with the existing methods. The algorithm is also protable and scalable that can adapt to most of systems.

1 Introduction

The existing methods of bandwidth allocation [6, 8] in the heterogeneous data center such as DRF, DRFH(e.g., [1,2,3]), BAA [4, 5] and UAF [7] have a poor performance for that the utilization only can up to 70% in the best situation and the usage of resource is unbalanced. Through contrasting the distribution result among above methods, we found the situation that the allocation in the entire data center meet the fairness but on each server is unfair or the global allocation shows unfairness and the total throughput is at a low level for applying fair allocation algorithm on each server. These methods are restricted to fair policies and the efficiency of global and local, so we must balance the allocation of global and local to enhance the utilization rate. The allocation model called Balancing Global and Local Fairness Allocation(GLA) we proposed in the paper can solve this problem. It includes global allocation strategy and local allocation strategy, meanwhile setting the global parameters to coordinate the consistency of the two strategies.

In the second part, we introduce the GLA model and implementation architecture. The performance evaluation results will be described in Sect. 3. In the end, we will conclude our work.

2 GLA Allocation Model and Scheduling Architecture

The functions of GLA model are shown as follows:

$$ {\mathbf{Maximize}}\,\,\,\,\,\sum\limits_{i \in D} {(\sum\limits_{l = 1}^{k} {(x_{ild} \times \tfrac{1}{{m_{il} }})} )} + \sum\limits_{j \in S} {(\sum\limits_{l = 1}^{k} {(x_{jls} \times \tfrac{1}{{h_{jl} }}))} } $$

(3.1)

$$ \left\{ {\begin{array}{*{20}l} {\sum\limits_{l = 1}^{k} {\varpi_{il} } = 1} \hfill \\ {\sum\limits_{l = 1}^{k} {(\varpi_{il} \times h_{il} )} = 1} \hfill \\ {i \in D(or\;i \in S)} \hfill \\ \end{array} } \right. $$

(3.2)

$$ \left\{ {\begin{array}{*{20}l} {x_{ild} \times (\sum\nolimits_{i \in D} {} + \omega \times \tfrac{{C_{sl} }}{{C_{dl} }} \times \sum\nolimits_{j \in S} {\tfrac{{m_{jl} }}{{h_{jl} }}} ) \le C_{dl} } \hfill \\ {x_{ild} \times (\sum\nolimits_{i \in D} {\,\tfrac{{h_{il} }}{{m_{il} }}} + \omega \times \tfrac{{C_{sl} }}{{C_{dl} }} \times \sum\nolimits_{j \in S} {} ) \le C_{sl} } \hfill \\ {\forall l \in V,\;i \in D_{l} ,\;j \in S_{l} } \hfill \\ \end{array} } \right. $$

(3.3)

$$ \left\{ {\begin{array}{*{20}l} {x_{ild} \ge \tfrac{{C_{dl} }}{n},\;x_{jls} \ge \tfrac{{C_{sl} }}{n}} \hfill \\ {x_{ild} \ge x_{jls} \times \tfrac{{m_{jl} }}{{h_{jl} }},\;x_{jls} \ge x_{ild} \times \frac{{h_{il} }}{{m_{il} }}} \hfill \\ {\forall i \in D_{l} ,\;j \in S_{l} } \hfill \\ \end{array} } \right. $$

(3.4)

$$ \left\{ {\begin{array}{*{20}l} {\sum\limits_{l = 1}^{k} {x_{ild} } \ge \sum\limits_{l = 1}^{k} {x_{jls} } \times \tfrac{{m_{j} }}{{h_{j} }}} \hfill \\ {\sum\limits_{l = 1}^{k} {x_{jls} } \ge \sum\limits_{l = 1}^{k} {x_{ild} } \times \tfrac{{h_{i} }}{{m_{i} }}} \hfill \\ {\forall i \in D,\;j \in S} \hfill \\ \end{array} } \right. $$

(3.5)

$$ \left\{ {\begin{array}{*{20}l} {\forall i,j \in D,\;if\,\;\sum\limits_{l = 1}^{k} {x_{ild} } \times \tfrac{{h_{i} }}{{m_{i} }} \ge \sum\limits_{l = 1}^{k} {x_{jld} } \times \tfrac{{h_{j} }}{{m_{j} }},\;then\,\;\sum\limits_{l = 1}^{k} {x_{ild} } \le \sum\limits_{l = 1}^{k} {x_{jld} } } \hfill \\ {\forall i,j \in S,\;if\,\;\sum\limits_{l = 1}^{k} {x_{ils} } \times \tfrac{{m_{i} }}{{h_{i} }} \ge \sum\limits_{l = 1}^{k} {x_{jls} } \times \tfrac{{m_{j} }}{{h_{j} }},\;then\;\;\sum\limits_{l = 1}^{k} {x_{ils} } \le \sum\limits_{l = 1}^{k} {x_{jls} } } \hfill \\ \end{array} } \right. $$

(3.6)

The scheduling architecture of the heterogeneous data center has two layers (Fig. 1), GLA is deployed in the second layer. The first layer scheduler assigns the requests of clients to the corresponding server in terms of the original weight, the second tier calculate the bandwidth allocated to each client based on the GLA algorithm. Different form other algorithm, the global parameters produced by GLA will be send to the first layer to assist the next allocation. The algorithm obeys the principle of conservation. The throughput of allocation subjects to the limitations that are presented into progressive from local to the whole.

Fig. 1.

The scheduling architecture of heterogeneous data center

3 Performance Evaluation

We use a parallel simulator called PFSsim and a Linux cluster test I/O performance of GLA. The cluster are configured as AMD Quad-core processor, 8 GB RAM, 1 TB Seagate 7200RPM hard drive, on which we configure three servers: $server_{1} (HDD:$ $500IOPS,SSD:1000IOPS)$, $server_{2} (HDD:1000IOPS,SSD:2000IOPS)$, $server_{3} (HDD:3000IOPS,$ $SSD:500IOPS)$. The workloads we used are from Umass Trace and Microsoft Exchange server. The test will be compared between BAA and UAF.

Figure 2(a) show the allocation of UAF and GLA on each server for PFSsim. It’s obviously that the local allocation of UAF does not obey fair properties. For GLA, the hit ratios on each server for clients are $h_{11} = h_{12} = h_{13} = 0.4$, $h_{21} = h_{22} = 0.96$, $h_{23} = 0.65$, $h_{31} = h_{32} = 0.9$, $h_{33} = 0.38$, the global hit ratios are $\sum\nolimits_{l = 1}^{3} {(h_{1l} \times \varpi_{1l} )} = 0.4 = h_{1}$, $\sum\nolimits_{l = 1}^{3} {(h{}_{2l} \times \varpi_{21} )} = 0.9 = h_{2}$, $\sum\nolimits_{l = 1}^{k} {(h_{3l} \times \varpi_{3l} )} = 0.8 = h_{3}$. We also get $A_{1,hdd} \ge \{ A_{2,hdd} ,A_{3,hdd} \}$, $A_{2,ssd} \ge A_{1,ssd}$, hence the GLA is a fair strategy. Figure 2(b) shows the throughput will increase with the number of clients arise, GLA has a best performance in the large-clients cases.

Fig. 2.

The comparison of utilization between GLA, BAA and UAF

Figure 3 express the throughput of GLA are 20% high than that of UAF on Linux cluster, GLA model has practical significance.

Fig. 3.

The throughput GLA and CFQ for four clients

4 Conclusion

In this paper, we focus on the problem that the existing allocation methods can’t balance global and local fairness, and propose a bandwidth allocation algorithm called GLA. Through experiments, we exhibit that GLA is fairness and improve the throughput of heterogeneous data center for 19.8% when the number of clients are more than six. GLA is more suitable for large-scale clients.