進階搜尋


下載電子全文  
系統識別號 U0026-0208201310384100
論文名稱(中文) 雲端影片串流系統排程演算法之實現與比較分析
論文名稱(英文) Implementation and Comparison Analysis of Various Scheduling Algorithms on Video Streaming Cloud System
校院名稱 成功大學
系所名稱(中) 工程科學系碩博士班
系所名稱(英) Department of Engineering Science
學年度 101
學期 2
出版年 102
研究生(中文) 朱立石
研究生(英文) Li-Shi Ju
學號 N96004109
學位類別 碩士
語文別 英文
論文頁數 67頁
口試委員 指導教授-黃悅民
口試委員-林志敏
口試委員-賴槿峰
口試委員-黃宗傳
口試委員-李維聰
中文關鍵字 雲端  排程  串流 
英文關鍵字 Cloud  Scheduling  Video Streaming 
學科別分類
中文摘要 過去的幾年由於影片串流的技術以及雲端系統的研發一直在進步當中,因此對於高品質影片的需求也不停的提升。許多雲端影片串流系統已被實現並且可提供影片串流功能,因此如何有效的提供管理資源來運用有限的資源變成一個重要的討論議題。此論文討論如何有效的用一個管理層來分配使用者需求在不同數目的雲端系統。
此論文也實現了一個有管理層的影片串流系統來使用OpenStack雲來管理所有的資源。在此系統裡有三樣不同自創的排程演算法會用來做效能以及反應速度上的比較,演算法有Round Robin,可靠雲端排程,以及基因演算法。此論文也提出一系列的雲端實驗來測試排程在不同種使用者輸入行為下的排程效能以及反應速度。每個排程演算法在不同行為下的效率最後會做一個比較及分析。
英文摘要 For the past few years with the advancing of video streaming and cloud system technologies, the need for high quality videos has increased more in the general public. Various cloud streaming systems have been implemented to offers video stream functions, therefore how to effectively provide and effectively manage the resources as well as how to use limited resources becomes an important topic of discussion. This study discusses how to effective distribute user requests using a management layer for different number of cloud clusters.
This study implements a video streaming system with a management layer to manage all the resources in the system using OpenStack Infrastructure as a Service clouds. In this system, three different scheduling algorithms are tested for efficiency and response time. The algorithms tested are Round Robin, Reliable Cloud Scheduling Algorithm implemented within this research, and Genetic Algorithm. This study also proposes a series of cloud scheduling experiments to test the scheduling efficiency and the system responsiveness to different patterns of user requests. The effectiveness of each scheduling algorithms for all user request patterns will be compared and analyzed at the end of this research.
論文目次 摘要 iii
Abstract iv
Acknowledgements v
Table of Contents vi
Table of Figures viii
Table of Tables x
Chapter 1: Introduction 1
1.1 Motivation 1
1.2 Contribution 2
1.3 Overview 3
Chapter 2: Background Knowledge and Related Work 4
2.1 Cloud Computing 4
2.1.1 Common Services Models in Cloud 4
2.2 Cloud Infrastructures 5
2.2.1 Hadoop 5
2.2.2 Eucalyptus 8
2.2.3 OpenStack 11
2.3 Job Shop Problem Model 14
2.4 Related Researches 15
2.4.1 Scheduling Algorithms 15
2.4.2 Cloud Computing Scheduling 17
Chapter 3: Software and Experimental Architectures 20
3.1 Software System 20
3.1.1 StackOps 20
3.1.2 Collectd 26
3.1.3 FFmpeg and FFserver 29
Chapter 4: Research System and Algorithm Method 31
4.1 The System Architecture 31
4.2 Research Constraints 33
4.3 System Process 34
4.4 Algorithms 36
4.4.1 Round Robin Algorithm 36
4.4.2 Genetic Algorithm 39
4.4.3 Reliable Cloud Scheduling Algorithm 46
Chapter 5: Results and Analysis 49
5.1 Experimental Environment 49
5.2 Experimental Results and Data Analysis 52
5.2.1 Bursty Experiment 55
5.2.2 Computationally Intensive Experiment 57
5.2.3 Lengthy Experiment 59
5.2.4 Composite (Lengthy Comp. Intensive Bursty) Experiment 61
Chapter 6: Conclusions and Future Works 63
References 64
參考文獻 [1] W. Zhu, C. Luo, J. Wang, and S. Li, “Multimedia Cloud Computing,” Signal Processing Magazine, IEEE , Vol.28, No.3, pp. 59-69, May 2011.
[2] M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia, “A view of cloud computing,” Commun, ACM, Vol.53, No.4, April 2010.
[3] R. N. Calheiros, R. Ranjan, and R. Buyya, “Virtual Machine Provisioning Based on Analytical Performance and QoS in Cloud Computing Environments,” Parallel Processing (ICPP), 2011 International Conference on , Vol.1, No.1, pp. 295-304, 13-16 September 2011.
[4] N. Antonopoulos and L. Gillam, “Cloud Computing: Principles, Systems and Applications,” Springer, August 2010.
[5] T. White, “Hadoop: The Definitive Guide (2nd ed.),” O'Reilly Media, Inc., 2009.
[6] D. Johnson, M. Kiran, R. Murthy, R. B. Suseendran, and G. Yogesh, “Eucalyptus Beginners Guide (UEC ed.),” CSS, CSS Corp., 2010.
[7] K. Pepple, “Deploying OpenStack (1st ed.),” O’Reilly Media, Inc., 2011.
[8] “Logical Architecture for the OpenStack Cloud Components”, http://docs.openstack.org/essex/openstack-compute/admin/content/logical-architecture.html, retrieved June 2013.
[9] “The Companies Supporting the OpenStack Foundation”, http://www.openstack.org/foundation/companies/, retrieved June 2013.
[10] A. M. Ali, M. S. Zalzala, P. J. Fleming, “Genetic Algorithms in Engineering Systems,” The Institution of Electrical Engineers, 1997.
[11] S. C. Cheng, D. F. Shiau, Y. M. Huang, and Y. T. Lin, “Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints,” Expert Systems with Applications, Vol. 36, Issue 1, pp. 852-860, January 2009.
[12] M. Liu, Z. J. Sun, J. W. Yan, and J. S. Kang, “An adaptive annealing genetic algorithm for the job-shop planning and scheduling problem,” Expert Systems with Applications, Vol. 38, Issue 8, pp. 9248-9255, August 2011.
[13] D. Karger, C. Stein, and J. Wein, “Scheduling algorithms”, In Algorithms and theory of computation handbook (2 ed.), Mikhail J. Atallah and Marina Blanton (Eds.), Chapman & Hall CRC 20-20, 2010.
[14] W. Li, J. Tordsson, and E. Elmroth, “Modeling for Dynamic Cloud Scheduling Via Migration of Virtual Machines,” Cloud Computing Technology and Science (CloudCom), 2011 IEEE Third International Conference on , Vol.1, No.1, pp. 163-171, December 2011.
[15] M. S. Xie, M. X. Huang, and B. Wan, “A Resource Scheduling Algorithm Based on Trust Degree in Cloud Computing,” Software Engineering Research, Management and Applications, Vol.430, pp. 177-184, 2012.
[16] R. N. Calheiros, R. Ranjan, and R. Buyya, “Virtual Machine Provisioning Based on Analytical Performance and QoS in Cloud Computing Environments,” Parallel Processing (ICPP), 2011 International Conference on , Vol.1, No.1, pp. 295-304, 13-16 September 2011.
[17] P. Salot, “A Survey of Various Scheduling Algorithm in Cloud Computing Environment,” International Journal of Research in Engineering and Technology, Vol.2, Issue 2, pp.131-135, 2013.
[18] A. G. Delavar, M. Javanmard , M. B. Shabestari and M. K. Talebi “RSDC (Reliable Scheduling Distributed in Cloud Computing),” International Journal of Computer Science, Engineering and Applications (IJCSEA), Vol.2, No.3, June 2012.
[19] M. Dakshayini and H. S. Guruprasad, “An Optimal Model for Priority based Service Scheduling Policy for Cloud Computing Environment,” International Journal of Computer Applications, Vol. 32, No.9, pp. 975-8887, October 2011.
[20] S. Ghanbari and M. Othman, “A Priority based Job Scheduling Algorithm in Cloud Computing,” International Conference on Advances Science and Contemporary Engineering 2012 (ICASCE 2012), Vol.50, pp. 778-785, 2012.
[21] E. T. El-kenawy, A. I. El-Desoky, and M. F. Al-rahamawy, “Extended Max-Min Scheduling Using Petri Net and Load Balancing,” International Journal of Soft Computing and Engineering (IJSCE), Vol. 2, Issue 4, September 2012.
[22] Y. M. Huang, and J. C. Lin, “A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling problems,” Expert Systems with Applications, Vol. 38, Issue 5, pp. 5438-5447, May 2011.
[23] S. T. Lo, R. M. Chen, Y. M. Huang, and C. L. Wu, “Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system,” Expert Systems with Applications, Vol. 34, Issue 3, pp. 2071-2081, April 2008.
[24] Y. M. Huang and D. F. Shiau, “Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling,” The International Journal of Advanced Manufacturing Technology, Vol. 38, Issue 7-8, pp. 691-704, September 2008.
[25] R. M. Chen and Y. M. Huang, “Competitive neural network to solve scheduling problems,” Neurocomputing, Vol. 37, Issues 1–4, pp. 177-196, April 2001.
[26] Y. M. Huang and R. M. Chen, “Scheduling multiprocessor job with resource and timing constraints using neural networks,” Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on , Vol.29, No.4, pp.490,502, August 1999.
[27] “What is StackOps Community distro (StackOps documentations)”, http://docs.stackops.org/display/STACKOPSDOCS/What+is+StackOps+Community+distro, retrieved June 2013
[28] “Collectd The System Statistics Collection Daemon”,
http://collectd.org/, retrieved June 2013
[29] A. Quiroz, H. Kim, M. Parashar, N. Gnanasambandam, and N. Sharma “Towards autonomic workload provisioning for enterprise grids and clouds,” Grid Computing, 2009 10th IEEE/ACM International Conference on. IEEE, pp. 50-57, 2009.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2018-08-09起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2018-08-09起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw