臺灣博碩士論文加值系統

在雲端運算環境中，使用者可以透過雲端服務提供者(CSP)所提供的資源，來執行作業系統或應用程式，而不需負擔硬體建置及維護費用。而CSP必須負責管理並分配實體機資源給虛擬機，以執行使用者的應用程式。如果發生分配不當造成負載失衡的情形，將會導致某些實體機上的有限資源幾乎被耗盡，因而在這一些實體機上運行的虛擬機會受限於硬體資源不足而無法有正常的效能，致使CSP可能需要賠償使用者的損失。如果能維持實體機之間的負載平衡，那麼就能避免這種因為少數機器負載過重而衍生的賠償。在本論文中，我們提出了一個資源重分配的架構給CSP來維持實體機之間的負載平衡。這個架構使用探測子來蒐集虛擬機的CPU使用率，並且定時回傳給控制伺服器。控制伺服器根據這些回傳的資料，使用我們所提出的演算法(GASd)來決定新的虛擬機佈署策略。GASd是一種基於基因演算法(GA)的演算法，可以讓CSP快速地得到新的佈署策略。GASd允許CSP偏好某一種資源使用率，讓最後結果傾向平衡該資源使用率，同時，GASd也允許CSP調整虛擬機的遷移比例。在實驗中，我們證明了GASd可以把各實體機的CPU跟記憶體的使用率標準差都降至3\%，而運算的時間大約是0.25秒。同時也可以針對其中一個資源，使得該資源的使用率標準差收斂到最小，而另一種資源的使用率標準差則是一個可接受的結果。我們也討論了GASd的可擴展性，並且模擬了一個有2500台實體機以及10000台虛擬機的環境，結果是GASd可以在2分半鐘內找出一個佈署策略，使得資源使用率的標準差總和是6.25%，從而證實GASd可擴展性。

In cloud computing, users can save hardware cost by using cloud resources provided and managed by cloud service provider (CSP). If an inappropriate distribution strategy is applied and a load unbalancing situation occurs, the virtual machines run on an overloading host can not work well. Thus, keeping load balancing is an issue for a CSP. In this research, we present a resource reallocating framework for a CSP to manage resources and keep physical machines in a load balanced state. The proposed framework uses probes to collect CPU utilization data and send the collection to the control server. Then the control server makes a distribution strategy using the proposed algorithm, GASd. GASd is an algorithm based on Genetic Algorithm(GA). The design of GASd allows a CSP to have preference to a load dimension of CPU or memory, and also to control the migration ratio of virtual machines. We conduct several experiments to evaluate the ability of GASd. In the experiments, we show that GASd can reduce the load deviation among physical machines to about 3% for both load dimensions in about 0.25 seconds. GASd can make a strategy to minimize utilization standard deviation of one load dimension with acceptable standard deviation of another load dimension. We also discuss the scalability of GASd to distribute 10000 virtual machines to 2500 physical machines, and GASd can find an optimal distribution strategy for the running cloud system in 2.5 minutes with distance 6.25%.

X i
Abstract ii
Table of Contents iii
List of Figures vi
List of Tables viii
Chapter 1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
1.4 Synopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Chapter 2 Gnentic Algorithm (GA) . . . . . . . . . . . . . . . . . . . 5
2.1 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
2.2 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Procedure of GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Chapter 3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15
3.1 Jinhua Hu’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Shin Chen’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .16
3.3 Noraini Mohd Razali’s Investigation . . . . . . . . . . . . . . 19
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20
Chapter 4 Proposed Framework . . . . . . . . . . . . . . . . . . . . . . . 21
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21
4.2 U-probe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.3 Resource Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.3.1 Monitor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3.2 Analyzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3.3 Strategy Maker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.4 GASd algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.4.1 Workflow of GASd . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4.2 Initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4.3 Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4.4 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.5 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.6 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Chapter 5 Evaluation 40
5.1 Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.2.1 Exp#1: Performance of different selection methods . . . . . . . 42
5.2.2 Exp#2: Influence of preference parameters . . . . . . . . . . . . . . . 45
5.2.3 Exp#3: Migration amount limit by preference parameter . . 49
5.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Chapter 6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.1 Data’s property: Continues value or Discrete value . . . 56
6.2 Extra load dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.3 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.4 GASd V.S. CloudSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.5 GASd’s accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Chapter 7 Conclusion . . . . . . . . . . . . . . . . . . . . . .63
References . . . . . . . . . . . . . . . . . . . . . .65

[1] J. Hu, J. Gu, G. Sun, and T. Zhao, ”A scheduling strategy on load balancing of virtual
machine resources in cloud computing environment,” Parallel Architectures, Algorithms
and Programming (PAAP), 2010 Third International Symposium on, pp. 89–96, Dec 2010.
[2] S. Chen, J. Wu, and Z. Lu, ”A cloud computing resource scheduling policy based on
genetic algorithm with multiple fitness,” Computer and Information Technology (CIT),
2012 IEEE 12th International Conference on, pp. 177–184, Oct 2012.
[3] N. M. Razali and J. Geraghty, ”Genetic algorithm performance with different selection
strategies in solving tsp,” Proceedings of the World Congress on Engineering, vol. 2, Jul.
2011.
[4] R. Patel, M. M. Raghuwanshi, and L. G. Malik, ”An improved ranking scheme for selection
of parents in multi-objective genetic algorithm,” Communication Systems and Network
Technologies (CSNT), 2011 International Conference on, pp. 734–739, June 2011.
[5] L. Zhang, H. Chang, and R. Xu, ”Equal-width partitioning roulette wheel selection in
genetic algorithm,” 2012 Conference on Technologies and Applications of Artificial Intelligence,
pp. 62–67, Nov 2012.
[6] J. Grover and S. Katiyar, ”Agent based dynamic load balancing in cloud computing,”
Human Computer Interactions (ICHCI), 2013 International Conference on, pp. 1–6, Aug
2013.
[7] Z. Gao, ”The allocation of cloud computing resources based on the improved ant colony
65
algorithm,” Intelligent Human-Machine Systems and Cybernetics (IHMSC), 2014 Sixth
International Conference on, vol. 2, pp. 334–337, Aug 2014.
[8] V. Behal and A. Kumar, ”Cloud computing: Performance analysis of load balancing algorithms
in cloud heterogeneous environment,” Confluence The Next Generation Information
Technology Summit (Confluence), 2014 5th International Conference, pp. 200–205,
Sept 2014.
[9] F. Bei, ”An improved ant colony algorithm based on distribution estimation,” Intelligent
Systems Design and Engineering Applications (ISDEA), 2014 Fifth International Conference
on, pp. 161–164, June 2014.
[10] M. Rana, S. Bilgaiyan, and U. Kar, ”A study on load balancing in cloud computing environment
using evolutionary and swarm based algorithms,” Control, Instrumentation, Communication
and Computational Technologies (ICCICCT), 2014 International Conference
on, pp. 245–250, July 2014.
[11] P. A. Pattanaik, S. Roy, and P. K. Pattnaik, ”Performance study of some dynamic load
balancing algorithms in cloud computing environment,” Signal Processing and Integrated
Networks (SPIN), 2015 2nd International Conference on, pp. 619–624, Feb 2015.
[12] Y. Dai, Y. Lou, and X. Lu, ”A task scheduling algorithm based on genetic algorithm
and ant colony optimization algorithm with multi-qos constraints in cloud computing,”
Intelligent Human-Machine Systems and Cybernetics (IHMSC), 2015 7th International
Conference on, vol. 2, pp. 428–431, Aug 2015.
[13] S. Aslam and M. A. Shah, ”Load balancing algorithms in cloud computing: A survey of
modern techniques,” 2015 National Software Engineering Conference (NSEC), pp. 30–35,
Dec 2015.
66
[14] F. T. Novais, L. S. Batista, A. J. Rocha, and F. G. Guimar˜aes, ”A multiobjective estimation
of distribution algorithm based on artificial bee colony,” Computational Intelligence and
11th Brazilian Congress on Computational Intelligence (BRICS-CCI CBIC), 2013 BRICS
Congress on, pp. 415–421, Sept 2013.
[15] P. K. Sundararajan, E. Fellery, J. Forgeaty, and O. J. Mengshoel, ”A constrained genetic
algorithm for rebalancing of services in cloud data centers,” 2015 IEEE 8th International
Conference on Cloud Computing, pp. 653–660, June 2015.
[16] R. Buyya, R. Ranjan, and R. N. Calheiros, ”Modeling and simulation of scalable cloud
computing environments and the cloudsim toolkit: Challenges and opportunities,” High
Performance Computing Simulation, 2009. HPCS ’09. International Conference on, pp.
1–11, June 2009.
[17] C. Y. Liu, C. M. Zou, and P.Wu, ”A task scheduling algorithm based on genetic algorithm
and ant colony optimization in cloud computing,” Distributed Computing and Applications
to Business, Engineering and Science (DCABES), 2014 13th International Symposium on,
pp. 68–72, Nov 2014.
[18] S. H. Z. Edwin K. P. Chong, An Introduction to optimization, 3rd edition, 3rd ed. John
Wiley & Sons Inc, Feb. 2008.
[19] J. Zhao,W. Zeng, M. Liu, G. Li, J. Zhao,W. Zeng, M. Liu, and G. Li, ”Multi-objective optimization
model of virtual resources scheduling under cloud computing and it’s solution,”
Cloud and Service Computing (CSC), 2011 International Conference on, pp. 185–190,
Dec 2011.
[20] N. Chen, X. Fang, and X. Wang, ”A cloud computing resource scheduling scheme based
67
on estimation of distribution algorithm,” Systems and Informatics (ICSAI), 2014 2nd International
Conference on, pp. 304–308, Nov 2014.
[21] Z. I. M. Yusoh and M. Tang, ”A penalty-based genetic algorithm for the composite saas
placement problem in the cloud,” Evolutionary Computation (CEC), 2010 IEEE Congress
on, pp. 1–8, July 2010.
[22] Z. Zheng, R. Wang, H. Zhong, and X. Zhang, ”An approach for cloud resource scheduling
based on parallel genetic algorithm,” Computer Research and Development (ICCRD),
2011 3rd International Conference on, vol. 2, pp. 444–447, March 2011.
[23] F. Xie, Y. Du, and H. Tian, ”A resource allocation strategy based on particle swarm
algorithm in cloud computing environment,” Digital Manufacturing and Automation
(ICDMA), 2013 Fourth International Conference on, pp. 69–72, June 2013.
[24] D. Kumar and Z. Raza, ”A pso based vm resource scheduling model for cloud computing,”
Computational Intelligence Communication Technology (CICT), 2015 IEEE International
Conference on, pp. 213–219, Feb 2015.
[25] S. Varshney, L. Srivastava, and M. Pandit, ”Comparison of pso models for optimal placement
and sizing of statcom,” Sustainable Energy and Intelligent Systems (SEISCON 2011),
International Conference on, pp. 346–351, July 2011.
[26] S.-C. Wang, K. Q. Yan, W.-P. Liao, and S.-S. Wang, ”Towards a load balancing in a threelevel
cloud computing network,” Computer Science and Information Technology (ICCSIT),
2010 3rd IEEE International Conference on, vol. 1, pp. 108–113, July 2010.