Discrete Interior Search Algorithm for Multi-resource Fair Allocation in Heterogeneous Cloud Computing Systems

详细信息    查看全文

• 关键词：Dominant resource fairness ; Interior search algorithm ; Multi ; resource fair allocation ; Heterogeneous cloud
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9771
• 期：1
• 页码：615-626
• 全文大小：2,326 KB
• 参考文献：1.Wang, W., Liang, B., Li, B.: Multi-resource fair allocation in heterogeneous cloud computing systems. IEEE Trans. Parallel Distrib. Syst. 26(10), 2822–2835 (2015)CrossRef
  2.Psomas, C., Schwartz, J.: Beyond beyond dominant resource fairness: indivisible resource allocation in clusters. Technical report, Berkeley (2013)
  3.Zhu, Q., Oh, J.C.: An approach to dominant resource fairness in distributed environment. In: Ali, M., Kwon, Y.S., Lee, C.-H., Kim, J., Kim, Y. (eds.) IEA/AIE 2015. LNCS, vol. 9101, pp. 141–150. Springer, Heidelberg (2015)
  4.Gandomi, A.H.: Interior search algorithm (ISA): a novel approach for global optimization. ISA Trans. 53(4), 1168–1183 (2014)CrossRef
  5.Max-Min Fairness [EB/OL]. http://​en.​wikipedia.​org/​wiki/​Max-min_​fairness . Accessed 10 June 2015
  6.Ghodsi, A., Zaharia, M., Hindman, B., et al.: Dominant resource fairness: fair allocation of multiple resource types. In: NSDI 2011: 8th USENIX Symposium on Networked Systems Design and Implementation, pp. 323–336 (2011)
  7.Parkes, D.C., Procaccia, A.D., Shah, N.: Beyond dominant resource fairness: extensions, limitations, and indivisibilities. Proc. Sixteenth ACM Conf. Econ. Comput. 3(1), 808–825 (2015)MathSciNet
  8.Friedman, E., Ghodsi, A., Psomas, CA.: Strategyproof allocation of discrete jobs on multiple machines. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, pp. 529–546 (2014)
  9.Li, W., Liu, X., Zhang, X., Zhang, X.: Dynamic fair allocation of multiple resources with bounded number of tasks in cloud computing systems. Multiagent Grid Syst. Int. J. 11, 245–247 (2016)CrossRef
  10.Zarchy, D., Hay, D., Schapira, M.: Capturing resource tradeoffs in fair multi-resource allocation. In: 2015 IEEE Conference on Computer Communications (INFOCOM), pp. 1062–1070 (2015)
  11.Gutman, A., Nisan, N.: Fair allocation without trade. In: International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, pp. 719–728 (2012)
  12.Joe, W.C., Sen, S., Lan, T., Chiang, M.: Multi-resource allocation: fairness-efficiency tradeoffs in a unifying framework. IEEE/ACM Trans. Netw. 21(6), 1785–1798 (2013)CrossRef
  13.Li, W., Liu, X., Zhang, X., Zhang, X.: Multi-resource fair allocation with bounded number of tasks in cloud computing systems. Eprint Arxiv, pp. 1410–1255 (2014)
  14.Liu, X., Zhang, X., Zhang, X., Li, W.: Dynamic fair division of multiple resources with satiable agents in cloud computing systems. In: Big Data and Cloud Computing (BDCloud), pp. 131–136 (2015)
  15.Pacini, E., Mateos, C., Garino, CG.: Multi-objective swarm intelligence schedulers for online scientific clouds. Computing 1–28 (2014)
  16.Shen, H., Liu, G.P., Chandler, H.: Swarm intelligence based file replication and consistency maintenance in structured P2P file sharing systems. IEEE Trans. Comput. 64(1), 2953–2967 (2015)MathSciNet CrossRef
  17.Wilkes, J., Reiss, C.: Google ClusterData2011\_2. https://​code.​google.​com/​p/​googleclusterdat​a/​
  
• 作者单位：Xi Liu (16)
  Xiaolu Zhang (16)
  Weidong Li (16)
  Xuejie Zhang (16)
  
  16. School of Information Science and Engineering, Yunnan University, No. 2, North Cuihu Road, Wuhua District, Kunmming, 650091, Yunnan, People’s Republic of China
  
• 丛书名：Intelligent Computing Theories and Application
• ISBN：978-3-319-42291-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9771

文摘

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.