JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2018, Vol. 53 ›› Issue (1): 63-74.doi: 10.6040/j.issn.1671-9352.2.2017.247

Previous Articles     Next Articles

Graph model based trustworthy resource scheduling algorithm in cloud environment

  

  1. 1. School of Management, Hefei University of Technology, Hefei 230039, Anhui, China;
    2. Department of Mathematics and Computer Science, Tongling University, Tongling 244000, Anhui, China
  • Received:2017-07-04 Online:2018-01-20 Published:2018-01-19

PDF (PC)

431

Abstract: The characteristics of the graph structure of parallel task and fat tree cloud system are analyzed. Then, by combining cloud tasks trust requirement for resource nodes together with the trust requirement for communication links, an execution-behavior based reliability measurement model is established. Then, we present a graph based trustworthy cloud resource scheduling model. It is easy to express taskstrust scheduling requirement and resource supply on a unified way, which can be transformed to a minimum cost maximum flow network construction and solution problem. Finally, in consideration of reducing computational complexity, algorithms are applied on the quotient network to approximately obtain the minimum cost flow of original network. The simulation experimental results show that the proposed algorithms can effectively improve the success rate of cloud tasks execution and significantly reduce runtime of flow network.

Key words: cloud resource scheduling, quotient network, graph based model, minimum cost maximum flow

CLC Number: 

  • TP301.6
[1] ROCHWERGER B, BREITGAND D, LEVY E, et al. The reservoir model and architecture for open federated cloud computing[J]. IBM Journal of Research & Development, 2009, 53(4):535-545.
[2] BUYYA R, YEO C S, VENUGOPAL S, et al. Cloud computing and emerging IT platforms: Vision, hype and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems, 2009, 25(6):599-616.
[3] 张建华, 张文博, 徐继伟, 等. 一种基于隐马尔可夫模型的虚拟机失效恢复方法[J]. 软件学报, 2014(11):2702-2714. ZHANG Jianhua, ZHANG Wenbo, XU Jiwei, et al. Approach of virtual machine failure recovery based on hidden Markov model[J].Journal of Software, 2014(11):2702-2714.
[4] 曹洁, 曾国荪, 匡桂娟, 等.支持随机服务请求的云虚拟机按需物理资源分配方法[J].软件学报, 2017, 28(2):457-472. CAO Jie, ZENG Guosun, KUANG Guijuan, et al. An on- demand physical resource allocation method for cloud virtual machine to support random service requests[J]. Journal of Software, 2017, 28(2):457-472.
[5] DARBHA S, AGRAWAL D P, Optimal scheduling algorithm for distributed memory machines[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 9(1):87-95.
[6] ZHU D, MOSSE D, MELHEM R. Power-aware scheduling for and/or graphs in real-time systems [J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 15(9):849-864.
[7] 李青, 李勇, 涂碧波, 等. QoS保证的数据中心动态资源供应方法[J].计算机学报, 2014, 37(12):2395-2406. LI Qing, LI Yong, TU Bibo, et al. QoS-guaranteed dynamic resource provision in internet data centers[J].Chinese Journal of Computers, 2014, 37(12):2395-2406.
[8] 师雪霖, 徐恪.云虚拟机资源分配的效用最大化模型[J].计算机学报, 2013, 36(2):252-262. SHI Xuelin, XU Ke. Utility maximization model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013, 36(2):252-262.
[9] TOPCUOGLU H, HARIRI S, WU M Y. Performance-effective and low complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 13(3):260-274.
[10] MEZMAZ M, MELAB N, KESSACI Y, et al. A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems[J]. Journal of Parallel and Distributed Computing, 2011, 71(10):1497-1508.
[11] 丁滟, 王怀民, 史佩昌, 等.可信云服务[J].计算机学报,2015,38(1):133-149. DING Yan, WANG Haiming, SHI Peichang, et al. Trusted cloud service[J]. Chinese Journal of Computers, 2015, 38(1): 133-149.
[12] WANG W, ZENG Guosun, TANG Daizhong, et al. Cloud-DLS: dynamic trusted scheduling for cloud computing[J]. Expert Systems with Applications, 2012, 39(2012): 2321-2329.
[13] 曹洁, 曾国荪, 姜火文, 等. 云环境下服务信任感知的可信动态级调度算法[J]. 通信学报, 2014,35(11):39-49. CAO Jie, ZENG Guosun, JIANG Huowen, et al. Trust-aware dynamic level scheduling algorithm in cloud environment[J].Journal on Communications, 2014, 35(11): 39-49.
[14] 曹洁,曾国荪,钮俊,等.云环境下可用性感知的并行任务调度算法[J]. 计算机研究与发展,2013, 50(7):1563-1572. CAO Jie, ZENG Guosun, NIU Jun, et al. Availability- aware scheduling method for parallel task in cloud environment[J].Journal of Computer Research and Development, 2013, 50(7):1563-1572.
[15] 王守信, 张莉, 李鹤松. 一种基于云模型的主观信任评价方法[J]. 软件学报,2010,21(6):1341-1352. WANG Shouxin, ZHANG Li, LI Hesong. Evaluation approach of subjective trust based on cloud model[J]. Journal of Software, 2010, 21(6):1341-1352.
[16] 唐文,陈钟.基于模糊集合理论的主观信任管理模型研究[J]. 软件学报,2003,14(8):1401-1408. TANG Wen, CHEN Zhong. Research of subjective trust management model based on the fuzzy set theory[J]. Journal of Software, 2003, 14(8):1401-1408.
[17] 罗俊海,范明钰.基于置信度的MANETs主观信任管理模型[J]. 计算机研究与发展,2013,47(3):516-523. LUO Junhai, FAN Mingyu. A subjective trust management model based on certainty-factor for MANETs[J]. Journal of Computer Research and Development, 2013, 47(3):516-523.
[18] 邓晓衡,卢锡成,王怀民.iVCE中基于可信评价的资源调度研究[J]. 计算机学报, 2017,30(10):1750-1762. DENG Xiaoheng, LU Xicheng, WANG Haimin. Study on trust evaluation based resource scheduling in iVCE[J]. Chinese Journal of Computers, 2017,30(10):1750-1762.
[19] ABAWAJY J. Determining service trustworthiness in intercloud computing environments[C] //Proceedings of 2009 10th International Symposium on Pervasive Systems, Algorithms and Networks. New York: IEEE, 2009:784-788.
[20] RAGHEBI Z, HASHEMI M R. A new trust evaluation method based on reliability of customer feedback for cloud computing[C] // International ISC Conference on Information Security and Cryptology. New York: IEEE, 2013:1-6.
[21] LI X, DU J. Adaptive and attribute-based trust model for service-level agreement guarantee in cloud computing[J].IET Information Security, 2013, 7(1): 39-50.
[22] FAN W, YANG S, PEI J. A novel two-stage model for cloud service trustworthiness evaluation[J]. Expert Systems, 2014, 31(2): 136-153.
[23] 田冠华,孟丹,詹剑锋.云计算环境下基于失效规则的资源动态提供策略[J]. 计算机学报,2010,33(10):1859-1872. TIAN Guanhua, MENG Dan, ZHAN Jianfeng. Reliable resource provision policy for cloud computing[J]. Chinese Journal of Computers, 2010, 33(10):1859-1872.
[24] ISARD M, PRABHAKARAN V, CURRY J, et al. Quincy: fair scheduling for distributed computing clusters[C] //ACM Sigops, Symposium on Operating Systems Principles. New York: ACM, 2009: 261-276.
[25] 匡桂娟,曾国荪,曹洁,等.基于图匹配理论的云任务与云资源满意“婚配”方法[J]. 电子学报,2014,42(8):1582-1886. KUANG Guijuan, ZENG Guosun, CAO Jie. Satisfactory marriage method between cloud tasks and resources based on graph theory[J]. Acta Electronica Sinica, 2014, 42(8): 1582-1886.
[26] YAGER R. On the entropy of fuzzy measures[J]. IEEE Transactions on Fuzzy Systems,2000,8(4):453-461.
[27] 陈晓旭,吴恒,吴悦文等.基于最小费用最大流的大规模资源调度方法[J]. 软件学报,2017,28(3):598-610. CHEN Xiaoxu, WU Heng, WU Yuewen, et al. Sirius: large-scale resource scheduling based on minimum cost maximum flow[J].Journal of Software, 2017, 28(3):598-610.
[28] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E Statistical Nonlinear &Soft Matter Physics, 2007, 76(3): 36-106.
[29] CALHEIROS R N, RANJAN R, ROSE C A F, et al. Cloudsim:a novel framework for modeling and simulation of cloud computing infrastructures and services[J/OL]. Computer Science, 2009. http://www.doc88.com/p-514938859172.html
[30] TOPCUOUGLU H, HARIRI S, Wu M Y. Performance-effective and low complexity task scheduling for heterogeneous computing[J]. IEEE Transaction on Parallel Distribution System, 2002, 13(3):260-274.
[1] XIE Jian-min, YAO Bing, ZHAO Ting-gang. An algorithm and its implementation for odd-elegant labeling of general sun graph Sm,n [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 79-85.
[2] ZHANG Chun-ying, WANG Li-ya, LIU Bao-xiang. Dynamic reduction theory for interval concept lattice based on covering and its realization [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(08): 15-21.
[3] ZHENG Xiang-Wei,LIU Hong . A diversity-guided two stages multi-objective particle swarm optimizer [J]. J4, 2008, 43(11): 5-10 .
[4] SONG Le-hui,CHENG Yue-gui,PAN Meng . A hybrid evolutionary modeling algorithm for dynamic systems [J]. J4, 2008, 43(11): 27-30 .
[5] YUAN Xiao-hang,DU Xiao-yong . iRIPPER: an improved rule-based text categorization algorithm [J]. J4, 2007, 42(11): 66-68 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd