臺灣博碩士論文加值系統

雲端運算是一個非常熱門的議題，因為使用者可藉由網路來得到許多不同的網路服務。然而為了服務使用者龐大的需求，可能會使任務在傳輸的過程當中因為服務節點的滿載而導致任務遺失與服務效能的減低。因此在本論文當中，我們將提出一個新的佇列雲端運算架構來減少任務的遺失，而此架構包括Cloud Task Management (CTM)以及Cloud Server Cluster(CSC)。同時，為了讓佇列雲端架構能有較好的效能，我們也提出Weight-based dispatching algorithm (WBD) ， Random dispatching algorithm (RD) ， 和Round-Robin dispatching algorithm (RRD)此三種調度演算法來進行模擬研究。在模擬結果顯示，WBD 演算法在不同執行時間任務的環境下可以提供較高的任務吞吐量以及較穩定的佇列等待時間。最後，本研究也將透過馬可夫M/M/1 排隊理論來分析証明實驗的可靠度。

Cloud computing is attractive for users having more demands on the Internet services because it can provide a variety of services. A huge amount of service demands can make the overloads of service nodes and the losses of tasks during transmission. Therefore, the reasonable architectures and fair dispatching algorithms that provide high performance under several distributions of tasks in cloud computing environment are considered. In this paper, we propose a novel cloud computing architecture including cloud task management (CTM) and cloud service cluster (CSC). The CTM uses the queues and dispatching algorithms to reduce the lost tasks and achieve fairness for resources. We analyze the waiting time of queues in the CSCs. Furthermore, we study the weight-based dispatching (WBD), random dispatching (RD), and round-robin dispatching (RRD) algorithms for the queued cloud computing architecture. The simulation results show that WBD provides high throughput under a variety of distribution patterns and more stable than others on the performance of queue waiting time.

目錄
朝陽科技大學 I
摘要 V
ABSTRACT VI
誌謝 VII
第一章、緒論 1
1.1 雲端運算演化走向 1
1.2 雲端運算主要服務 7
第二章、研究動機與目的 9
2.1 研究動機與目的 9
3.1佇列型態的雲端運算架構 11
3.1.1 雲端任務管理 (Cloud Task Management, CTM) 12
3.1.2 雲端服務群集 (Cloud Service Cluster, CSC) 13
3.2 本研究提出之調度演算法 (Weight-based Dispatching, WBD) 14
第四章、仿真分析與模擬實驗 16
4.1實驗模擬 16
4.1.1 在一致性任務執行時間的吞吐量效能之表現 18
4.1.2 在一致性任務執行時間的佇列等待時間效能之表現 20
4.1.3 在非一致性任務執行時間的吞吐量效能之表現 23
4.1.4 在非一致性任務執行時間的佇列等待時間效能之表現 25
4.2 仿真分析 28
4.3 本章結論 30
第五章、結論與未來工作 31
參考文獻 32
圖目錄
圖1-1 Client-Server model 2
圖1-2 Peer-to-Peer model 3
圖1-3 Cloud computing architecture 6
圖3 1 Two-layer queued cloud computing architecture 11
圖3 2 Cloud task management architecture (CTM) 12
圖3 3 Cloud service cluster architecture (CSC) 13
圖3 4 Example of WBD in 4 CSCs 15
圖4-1 (a) Identical execution time of Tasks (b) Non-identical execution time of Tasks 17
圖4 2 Throughput performance of RD, RRD, and WBD with CSQ=2 under identical execution time of tasks 19
圖4 3 Throughput performance of RD, RRD, and WBD with CSQ=4 under identical execution time of tasks 19
圖4-4 Throughput performance of RD, RRD, and WBD with CSQ=16 under identical execution time of tasks 20
圖4-5 Queue waiting time by RD, RRD, and WBD with CSQ=2 under identical execution time of tasks 21
圖4-6 Queue waiting time by RD, RRD, and WBD with CSQ=4 under identical execution time of tasks 22
圖4-7 Queue waiting time by RD, RRD, and WBD with CSQ=16 under identical execution time of tasks 22
圖4-8 Throughput performance of RD, RRD, and WBD with CSQ=2 under non-identical execution time of tasks 24
圖4-9 Throughput performance of RD, RRD, and WBD with CSQ=4 under non-identical execution time of tasks 24
圖4-10 Throughput performance of RD, RRD, and WBD with CSQ=16 under non-identical execution time of tasks 25
圖4-11 Queue waiting time by RD, RRD, and WBD with CSQ=2 under non-identical execution time of tasks 26
圖4-12 Queue waiting time by RD, RRD, and WBD with CSQ=4 under non-identical execution time of tasks 27
圖4-13 Queue waiting time by RD, RRD, and WBD with CSQ=16 under non-identical execution time of tasks 27
圖4-14 Queue waiting time comparison of analysis and simulation with different number of tasks for CSQ 30

[1]Robert Armstrong, Debra Hensgen, and Taylor Kidd, “The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions,” Proceedings of the 7th IEEE Heterogeneous Computing Workshop, 1998, pp. 79-87.
[2]Tracy D. Braun, Howard Jay Siegel, Noah Beck, Lasislau L. Boloni, Muthucumara Maheswaran, Albert I. Reuther, James P. Robertson, Mitchell D. Theys, Bin Yao, Debra Hensgen, and Richard F. Freund, “A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems,” Journal of Parallel and Distributed Computing, 2001, Vol. 61, No. 6, pp. 810-837.
[3]Rajkumar Buyya1, Rajiv Ranjan, and Rodrigo N. Calheiros, “Modeling and Simulation of Scalable Cloud ComputingEnvironments and the CloudSim Toolkit: Challenges and Opportunities,” Proceedings of the International Conference on High Performance & Simulation, 2009, pp. 1-11.
[4]Hsun-Chang Chang, Kuan-Ching Li, Yaw-Ling Lin, Chao-Tung Tang, Hsiao-His Wang, and Liang-The Lee, “Performance issues of grid computing based on different architecture cluster computing platforms,” Proceedings of the 19th International Conference on Advanced Information Networking and Applications, 2005, pp. 321-324.
[5]Wilson C. H. Cheng and Xiaohua Jia, “A hierarchical framework for designing reliable distributed systems,” Proceedings of the International Conference on Asia Pacific Software Engineering Conference, 1995, pp. 180-188.
[6]Ian Foster, Yong Zhao, Ioan Raicu, and Shiyong Lu, “Cloud Computing and Grid Computing 360-Degree Compared,” Proceedings of the International Conference on Grid Computing Environments Workshop, 2008, pp. 1-10.
[7]Richard F. Freund, Michael Gherrity, Stephen Ambrosius, Mark Campbell, Mike Halderman, Debra Hensgen, Elaine Keith, Taylor Kidd, John D. Lima, Francesca Mirabile, Lantz Moore, Brad Rust, and H. J. Siegel, “Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet,” Proceedings of the 7th International Conference on Heterogeneous Computing Workshop, 1998, pp.184-199.
[8]R. L. Grossman, “The Case for Cloud Computing,” IT Professional, 2009, Vol. 11, No. 2, pp. 23-27.
[9]V. P. Koutras and A. N. Platis, “Modeling Perfect and Minimal Rejuvenation for Client Server Systems with Heterogeneous Load,” Proceedings of the 14th IEEE Pacific Rim International Symposium on Dependable Computing, 2008, pp. 95-103.
[10]Chuan-Bi Lin and Roberto Rojas-Cessa, “Module Matching Schemes for Input-Queued Clos-Network Packet Switches.” IEEE Communications Letters, 2007, Vol. 11, No. 2, pp. 194-196.
[11]Chuan-Bi Lin and Roberto Rojas-Cessa, “Module-First Matching Schemes for Scalable Input-Queued Space-Space-Space Clos-Network Packet Switches,” Proceedings of the IEEE Conference on Communications, 2008, pp. 5669-5673.
[12]Nick McKeown, Adisak Mekkittkul, Venkat Anantharam, and Jean Walrand, “Achieving 100% throughput in an input-queued switch,” IEEE Trans. Commun, 1999, Vol. 47, No. 8, pp. 1260-1267.
[13]Rajiv Ranjan, Liang Zhao, Xiaomin Wu, Anna Liu, Andres Quiroz, and Manish Parashar,“Peer-to-Peer Cloud Provisioning: Service Discovery andLoad-Balancing,” Computer Communications and Networks, 2010, Vol. 0,Part 2, pp. 195-217.
[14]Graham Ritchie and John Levine, “A Fast Effective Local Search for Scheduling Independent Jobs in Heterogeneous Computing Environments,” Journal of Computer Applications, 2011, Vol.25, No. 5, pp. 1190-1192.
[15]B. Rochwerger, D. Breitgand, E. Levy, A. Galis, K. Nagin, I. M. Llorente, R. Montero, Y, Wolfsthal, E. Elmroth, J. Caceres, M. Ben-Yehuda, W. Emmerich, and F. Galan, “The Reservoir Model and Architecture for Open Federated Cloud Computing,” IBM Journal of Research and Development, 2009, Vol.53, No. 4, pp. 535-545.
[16]Borja Sotomayor, Ruben S. Montero, Ignacio M. Llorente, and Ian Foster, “Virtual Infrastructure Management in Private and Hybrid Clouds,” IEEE Internet Computing, 2009, Vol. 13, No. 5, pp. 14-22. [17]Shu-ching Wang, Kuo-Qin Yan, Wen-Pin Liao, and Shun-Sheng Wang, “Towards a Load Balancing in a Three-level Cloud Computing Network,” Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology, 2010, pp. 108-113.
[18]Zhi Yan, Changqin Yin, and Yan Lin, “A Cost-Based Resource Scheduling Paradigm in Cloud Computing,” Proceedings of the 12th International Conference on Parallel and Distributed Computing Applications and Technologies, 2011, pp. 417-422.
[19]Xindong You, Xianghua Xu, Jian Wan, and Congfeng Jiang, “Analysis and Evaluation of the Scheduling Algorithm in Virtual Environment,” Proceedings of the International Conference on Embedded Software and Systems, 2009, pp. 291-296.
[20]Kai Zhang, Ying Song, Hai-Feng Fang, and Yu-Zhong Sun, “Trusted Connection System based on Virtual Machine Architecture,” Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology, 2010, pp. 192-196.
[21]Hai Zhong, Kun Tao, and Xuejie Zhang, “An Approach to Optimized Resource Scheduling Algorithm for Open-Source Cloud Systems,” Proceedings of the 5th Annual ChinaGrid Conference, 2010, pp. 124-129.
[22]Amazon Web Services, http://aws.amazon.com
[23]Citrix, http://www.citrix.com
[24]Google, http://www.google.com/options
[25]Nimbus, http://nimbusproject.org.
[26]Open Nebular, http://www.opennebula.org.
[27]openPBS, http://pbsgridworks.com.
[28]SEIT@HOME,http://setiathome.berkeley.edu/.
[29]SunGridEngine, http://gridengine.sunsource.net.
[30]Windows Azure Platform, http://www.microsoft.com/windowsazure.
[31]Youtube, http://www.youtube.com.
[32]Zeus, http://www.zeus.com.
[33]IBM Blue Cloud project, Http://www03.ibm.com/press/us/en/ pressrelease/22613.wss/, access on October 2009.