近年來個人行動裝置相關應用普及，透過智慧型手機和平板電腦經網際網路瀏覽或收看串流直播影音，例如比賽實況直播和遠距教學等。行動即時影音服務功能需求受到重視，但行動網路品質變動較大，需提供可調式視訊編碼(scalable video coding, SVC)或轉碼服務(transcoding)以因應處在不同頻寬環境用戶之需求。視訊轉碼功能對於行動裝置而言屬於高度CPU計算能力的作業，為了降低使用者的負擔與縮短作業執行時間，此一轉碼作業可以在雲端叢集上去執行。考量終端用戶裝置與伺服器的相容互通，MPEG提出一可在HTTP上進行動態與適應性媒體串流的新標準MPEG-DASH (Dynamic Adaptive Streaming over HTTP)，期望透過此一新標準來改進現有媒體串流之效率。本論文開發基於HTTP動態自適性串流(DASH)之雲端影音即時轉碼系統，我們研究可達到最佳效率的區塊封包切割大小，並將來源影音切割成一連串的影音片段(video segment)，每個影音片段支援數種編碼格式，如解析度(resolution)、位元率(bit rate)、畫面更新率(frame rate)等，以適應不同用戶之需求。為了加速影音轉碼(Transcode)，我們開發基於雲端平台之影音轉碼機制，並透過分散式檔案系統(Hadoop Distributed File System, HDFS)進行影音片段儲存及管理。而為了讓整個雲端叢集更有效地被利用，本論文提出了依檔案複雜度的多層次排程演算法，透過多層次的切割方式，並考量整體作業任務的複雜度，優先排程複雜度較高的第一層次切割(First layer division)任務，能減少作業後段因任務執行時間不一樣所導致的護送效應，再利用第二層次切割(Second layer division)任務去填補所產生的護送效應，如此能讓整體叢集保持較佳負載平衡。且配合動態調整slot數的執行策略，能更有效率的執行作業。實驗結果顯示，本論文所提出的方法，可達成較佳的負載平衡，而多層次的切割方法能讓資源利用率有效的提升。資源利用率皆能維持在98%左右，且能縮短約10%到13.4%的轉碼時間。

Personal mobile communication devices become popular in recent years. Smartphones and tablet PCs are used to browse webpages or watch live streaming video through the Internet, such as the games live, distance education, etc. How to achieve a compromised perception quality under this condition is a challenging issue. However, the transmission is unstable under wireless/mobile network environment, and the user devices may not support high quality video consumption. To solve this problem, it needs to transform the video format from one to another that is supported by the target devices, i.e., video transcoding. As video transcoding is a computationally intensive process, it is usually carried out based on a cloud computing platform to achieve fast transcoding for more than one users with different end devices. A MPEG-DASH (Dynamic Adaptive Streaming over HTTP) standard, which can dynamically adapt media streaming over HTTP, had been proposed by MPEG to make video streaming compatible with different end devices. It has been widely used in various video streaming application systems, such as Youtube, YouKu and VideoLAN etc. In this research, a cloud transcoding system is designed that support MPEG-DASH to serve users with different devices and bandwidth environment. One input video can be transcoded to another format with different resolution, bitrates and frame rates to meet user’s requirement. For cloud computation, the input video would be divided into several smaller video segments, and we investigate how to perform the division to yield the minimum system transcoding time. In addition, we proposed a Multi-layer Division of Max-MCT scheduling algorithm (MDMCT) to reduce the overall job’s convoy effect. It helps to coordinate the system operations and dynamically adjust the number of slots so that the cloud clusters can finish the process more efficiently. Experimental results show that the proposed method can help to achieve better system load balancing. The entire cloud clusters of resource utilization maintained at about 98%, and can be shortened by about 10%-13.4% of the transcoding time.

[1] J. Dean and S. Ghemawat, “MapReduce: simplified data processing on large clusters,” Comm. of the ACM, vol. 51, pp.107-113, 2008.
[2] F. Chang et al, “Bigtable: a distributed storage system for structured data,” in UENIX Sym. on Operating Systems Design and Implementation, pp. 205-218, 2006.
[3] I.-W. Wu, D.-H. Shiue, and J.-L. Liu, “Cloud Transcoding System for HLS/DASH,” ICL Technical Journal, Aug 2012.
[4] Dynamic adaptive streaming over HTTP (DASH). http://dashif.org/
[5] The Apache Hadoop. http://hadoop.apache.org/
[6] Y. Sambe et al, “High speed distributed video transcoding for multiple rates and formats,” IEICE Trans., vol. E88-D, no. 8, pp. 1923–1931, 2005.
[7] S. Tang, B.-S. Lee, and B. He, “Dynamic slot allocation technique for MapReduce clusters, ” IEEE Int. Conf. Cluster Computing (CLUSTER), vol., no., pp.1,8, 23-27 Sept 2013.
[8] T. Wiegand et al, “Overview of the H.264/AVC video coding standard,” IEEE Trans. Circuits Systems Video Technology, vol. 13, no. 7, pp. 560-576, July 2003.
[9] G. J. Sullivan and T. Wiegand, “Video compression-from concepts to the H.264/AVC standard,” Proceedings of the IEEE, vol. 93, no. 1, pp. 18-31, Jan 2005.
[10] D. Marpe, T. Wiegard, and G. J. Sullivan, “The H.264/MPEG4 advanced video coding standard and its applications,” IEEE Communications Magazine, vol. 44, no.8, pp. 134-143, Aug 2006.
[11] T. Wiegard, and G. J. Sullivan, “The H.264/AVC video coding standard,” IEEE Signal Processing Magazine, vol. 24, no. 2, pp. 148-153, Mar 2007.
[12] “Advanced video coding for generic audiovisual services” Joint Video Team of ISO/IEC and ITU-T, March 2005.
[13] The Moving Picture Experts Group. http://mpeg.chiariglione.org/
[14] International Telecommunication Union. http://www.itu.int/en/pages/default.aspx
[15] J. Xin, C.-W. Lin, and M.-T. Sun, “Digital Video Transcoding, ” Proceedings of the IEEE, vol.93, no.1, pp.84,97, Jan 2005.
[16] T. Shanableh, and M. Ghanbari, “Heterogeneous video transcoding to lower spatial-temporal resolutions and different encoding formats,” IEEE Trans. Multimedia, vol. 2, no. 2, pp. 101–110, Jun 2000.
[17] K.-S. Candan et al, “Scalable multimedia data processing in server clusters,” IEEE MultiMedia, pp.3-5, 2010.
[18] A. Verma et al, “Scaling genetic algorithms using MapReduce,” Int. Conf. Intelligent Systems Design &Applications, 2009.
[19] W. Xu et al, “Detecting large-scale system problems by mining console logs,” In Proc. of the ACM SOSP, 2009.
[20] F. Lao, X. Zhang, and Z. Guo, “Parallelizing video transcoding using Map-Reduce-based cloud computing,” Int. Symp. Circuits and Systems (ISCAS), pp. 2905-2908, 20-23 May 2012.
[21] Z. Li et al, “Cloud transcoder: bridging the format and resolution gap between internet videos and mobile devices,” SIGMM of NOSSDAV, June 2012.
[22] YouConvertIt. http://www.youconvertit.com.
[23] Online-convert. http://www.online-convert.com.
[24] Mov-avi. http://online.movavi.com.
[25] T.-Y. Chen et al, “LaSA: A locality-aware scheduling algorithm for Hadoop-MapReduce resource assignment,” Int. Conf. Collaboration Technologies and Systems (CTS), pp. 342-346, 20-24 May 2013.
[26] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The Google File System,” in ACM Symp. on SOSP, 2003.
[27] Apache Lucene. http://lucene.apache.org/
[28] M. Satyanarayanan, “Scalable, secure, and highly available distributed file access,” Computer, May 1990.
[29] F. Jokhio et al, “Prediction-based dynamic resource allocation for video transcoding in cloud computing,” Euromicro Int. Conf. Parallel, Distributed and Network-Based Processing (PDP), pp. 254-261, Feb. 27-March 1 2013.
[30] H. Mao et al, “A Load-Driven Task Scheduler with Adaptive DSC for MapReduce, ” IEEE/ACM Int. Conf. Green Computing and Communications, vol., no., pp.28,33, 4-5 Aug 2011.
[31] D. Seo, J. Kim, and I. Jung, “Load Distribution Algorithm Based on Transcoding Time Estimation for Distributed Transcoding Servers, ” Int. Conf. Information Science and Applications, vol., no., pp.1,8, 21-23 April 2010.
[32] Z. Tian et al, “High performance cluster based transcoder,” in ICCASM, Taiyuan, pp. V2 48–52, Oct 2010.
[33] T. Braun, “A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems,” Journal of Parallel and Distributed Computing, vol. 61, no. 6, pp. 810–837, 2001.
[34] VMware. http://www.vmware.com/tw/
[35] FFmpeg. https://www.ffmpeg.org/