Title

雲端影片串流系統排程演算法之實現與比較分析

Translated Titles

Implementation and Comparison Analysis of Various Scheduling Algorithms on Video Streaming Cloud System

DOI

10.6844/NCKU.2013.00110

Authors

朱立石

Key Words

雲端 ; 排程 ; 串流 ; Cloud ; Scheduling ; Video Streaming

PublicationName

成功大學工程科學系學位論文

Volume or Term/Year and Month of Publication

2013年

Academic Degree Category

碩士

Advisor

黃悅民

Content Language

英文

Chinese Abstract

過去的幾年由於影片串流的技術以及雲端系統的研發一直在進步當中,因此對於高品質影片的需求也不停的提升。許多雲端影片串流系統已被實現並且可提供影片串流功能,因此如何有效的提供管理資源來運用有限的資源變成一個重要的討論議題。此論文討論如何有效的用一個管理層來分配使用者需求在不同數目的雲端系統。 此論文也實現了一個有管理層的影片串流系統來使用OpenStack雲來管理所有的資源。在此系統裡有三樣不同自創的排程演算法會用來做效能以及反應速度上的比較,演算法有Round Robin,可靠雲端排程,以及基因演算法。此論文也提出一系列的雲端實驗來測試排程在不同種使用者輸入行為下的排程效能以及反應速度。每個排程演算法在不同行為下的效率最後會做一個比較及分析。

English Abstract

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.

Topic Category 工學院 > 工程科學系
工程學 > 工程學總論
Reference
  1. [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.
    連結:
  2. [4] N. Antonopoulos and L. Gillam, “Cloud Computing: Principles, Systems and Applications,” Springer, August 2010.
    連結:
  3. [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.
    連結:
  4. [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.
    連結:
  5. [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.
    連結:
  6. [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.
    連結:
  7. [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.
    連結:
  8. [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.
    連結:
  9. [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.
    連結:
  10. [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.
    連結:
  11. [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.
    連結:
  12. [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.
    連結:
  13. [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.
    連結:
  14. [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.
    連結:
  15. http://collectd.org/, retrieved June 2013
    連結:
  16. [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.
  17. [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.
  18. [5] T. White, “Hadoop: The Definitive Guide (2nd ed.),” O'Reilly Media, Inc., 2009.
  19. [6] D. Johnson, M. Kiran, R. Murthy, R. B. Suseendran, and G. Yogesh, “Eucalyptus Beginners Guide (UEC ed.),” CSS, CSS Corp., 2010.
  20. [7] K. Pepple, “Deploying OpenStack (1st ed.),” O’Reilly Media, Inc., 2011.
  21. [8] “Logical Architecture for the OpenStack Cloud Components”, http://docs.openstack.org/essex/openstack-compute/admin/content/logical-architecture.html, retrieved June 2013.
  22. [9] “The Companies Supporting the OpenStack Foundation”, http://www.openstack.org/foundation/companies/, retrieved June 2013.
  23. [10] A. M. Ali, M. S. Zalzala, P. J. Fleming, “Genetic Algorithms in Engineering Systems,” The Institution of Electrical Engineers, 1997.
  24. [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.
  25. [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.
  26. [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.
  27. [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.
  28. [27] “What is StackOps Community distro (StackOps documentations)”, http://docs.stackops.org/display/STACKOPSDOCS/What+is+StackOps+Community+distro, retrieved June 2013
  29. [28] “Collectd The System Statistics Collection Daemon”,
  30. [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.