Discrete Interior Search Algorithm for Multi-resource Fair Allocation in Heterogeneous Cloud Computing Systems
The mechanism of resource allocation for cloud computing not only affects the users’ fairness, but also has a significant impact on resource utilization. Most current resource allocation models did not take into account the indivisible demands, the hetero
- PDF / 2,382,832 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 200 Views
Abstract. The mechanism of resource allocation for cloud computing not only affects the users’ fairness, but also has a significant impact on resource utilization. Most current resource allocation models did not take into account the indivisible demands, the heterogeneity servers, and the situations multi-server. Dominant resource fairness allocation in heterogeneous systems (DRFH) is a fair and efficient resource allocation mechanism. But solving the DRFH problem is NP-hard. There are significant gaps between solutions obtained by existing heuristic algorithms and optimal solutions. They cannot effectively use server resources, resulting in a waste of resources of servers. In this paper, we propose a novel discrete interior search algorithm (DISA) to solve indivisible demands in heterogeneous servers, with a specific repair operator and task-fit value. Experimental results demonstrate that DISA can well adapt to dynamic changes in user resource request type, obtain the near-optimal solutions, maximize the value of minimum global dominant share and resource utilization. Keywords: Dominant resource fairness Interior search algorithm Multi-resource fair allocation Heterogeneous cloud
1 Introduction Cloud computing resource allocation problem is that the server resources allocated to each user according to the needs of different requests. And users can efficient use of resources on the server, in order to save energy and reduce the cost. However, there are a large of heterogeneous servers in cloud computing environment, so how to efficiently allocate server resources is a key issue and the current hot issue need to be resolved. Therefore, Wang et al. [1] proposed dominant resource fairness in heterogeneous environment (DRFH) where resource are pooled by a large number of heterogeneous servers. DRFH is to maximize the user’s minimum global dominant share in heterogeneous cloud computing systems. It well solved the resource allocation in heterogeneous system. Towards addressing the indivisible and divisible demands, it is easy to find optimization solution by solving linear programming for divisible demands. But the tasks of users are indivisible in real world system. For example, user who gets 1/2 of © Springer International Publishing Switzerland 2016 D.-S. Huang et al. (Eds.): ICIC 2016, Part I, LNCS 9771, pp. 615–626, 2016. DOI: 10.1007/978-3-319-42291-6_61
616
X. Liu et al.
resource request can complete 1/2 its task. Some cloud computing platform cannot save any compute results, so user gets final result after must complete its whole task [2]. So this is unrealistic, and it’s meaningless that the resources which are available to the user cannot run a task completely. Finding the optimal integer solution of DRFH problem for indivisible demands is often impossible. Wang et al. [1] designed a simple heuristic algorithm, called Best-Fit algorithm, to find a feasible allocation. Best-Fit cannot get optimal solutions of global dominant resource, leading to lower resource utilization. Zhu and Oh [3] extended to the distri
Data Loading...