基於LT編碼的熱門影片分散式儲存與傳輸技術

Distributed Storage and Delivery for Popular Videos using LT Codes

顏嘉呈(Chia-Cheng Yen)

指導教授 ： 王家祥

國立清華大學/電機資訊學院/資訊工程學系/碩士(2014年)

摘要

由於高效率無線區域網路(High efficiency WLAN)、Beyond 4G技術與設備、裝置廣域且高密度的佈建等關係，現今的影像串流應用已經逐漸轉向行動寬頻。本篇論文的動機是研究如何在超高密度設備佈建且會發生資料散失的無線網路環境下用分散式儲存與傳輸技術串流熱門點閱的影片。H.264 SVC可適性視訊編碼 (Scalable Video Coding)與Luby Transform (LT)編碼也都被整合及應用於本研究中，希望在無線網路的環境下能提供不同品質的影像與提高網路傳輸的可靠度。
本篇論文的研究動機是希望達到在無線網路的環境中將影像經過編碼並且隨機地分散儲存至網路上的各個儲存點(node)，為了能夠以更大的頻寬與更快的速度去處理串流的訊息(request)，一旦最靠近使用者(client)的儲存點(server node)收到訊息後，會立即開始解碼自己所擁有的資料且將解碼完成的部分影像資料串流給使用者以及其他鄰近的儲存點，讓鄰近的儲存點一起加入解碼的行列，使解碼能夠達到平行的效果，而使用者則可以從多方同時收取影像資料來達到頻帶加總的效果(bandwidth aggregation)。我們考慮了兩種不同的資料配置的方式來使儲存空間(storage space)、傳輸量(transmission bandwidth)以及容錯數(fault tolerance)達到平衡。此外，只要解碼程序開始進行，修復程序也會被啟動來處理損毀的儲存點。

在資料配置過程中，主要是先用Scalable Video Coding (SVC)之技術對影像作壓縮，再來用Luby Transform (LT) codes或Expanding Window LT codes對壓縮過後的影像(bitstream)進行編碼，編碼完成後再將資料(LT encoded data)隨機地分散儲存於各個儲存點中，在LT編碼過程中，因為SVC的基礎層(Base Layer)是最重要的資料，所以會被賦予較重的比例以確保它能夠第一個被解出來，愈後面的SVC的增強層(Enhancement Layer)重要性越低，所以被賦予的比例會愈來愈少，依此類推。在資料傳輸過程中，我們提出了分散式解碼(distributed decoding)的方式對存在於各個儲存點的資料同時且平行地進行解碼，而各個儲存點透過廣播(broadcast)的資料傳遞方式來與鄰近點(neighboring nodes)交換各自所持有的資料，進而達到上述提到的分散且平行地解碼的效果，最後，我們也提出有快取資料的方式來處理被點閱多次的影片。
在高密度設備配置的情況下，我們的實驗目的希望在資料遺失率設為1%~10%時能達到最大容錯數量為1、每個request至少都能得到最低畫質的影像基礎層(Base Layer)與一層的增強層(Enhancement Layer)且應對可能發生的儲存點資料損毀。

關鍵字

分散式儲存 ； 分散式解碼 ； 資料配置 ； 資料傳輸 ； 可適性視訊編碼 ； 盧比變換碼 ； 無線區域網路

並列摘要

The application of video streaming is expected to shift to mobile broadband as soon as the High efficiency WLAN (HEW), Beyond 4G technologies and related devices become large-scale and dense deployed. The motivation of this thesis is to study distributed storage and delivery technologies for streaming popular videos over such ultra-dense error-prone wireless environment. The H.264 SVC scalable source coding and the LT codes of rateless channel coding are both considered and integrated to provide reliable and scalable video services wirelessly.
To serve popular requests with broadband and high-speed requirements, one nearby node (server) immediately decode its own LT encoded data once a request coming and broadcast them to the clients and the neighboring nodes to proceed the undone decoding process in parallel. Thus, the clients can receive data from multiple nodes to achieve the goal of bandwidth aggregation. Two storage allocation schemes are considered to balance the storage space, transmission bandwidth and fault tolerance requirements. Besides, once the decoding process being completed, the repairing process is ignited to recover the possible node failures.
In the storage allocation process, the video segments are applied SVC encoder first, and coded by LT codes or the Expanding Window LT codes. Then, the LT encoded data are randomly distributed among nodes. The data proportion of SVC layers is tuned to let the base layer being completely decoded first. In the delivery process, a distributed LT decoder is proposed to decode and transmit in parallel, where each node passing its own self-generated degree one data with neighbors by broadcasting. Finally, the delivery with caching mechanism is proposed to serve hot requests effectively.
In the ultra-dense scenarios, our experiments show that each request can be served with at least base layer and with one more enhancement layer in average under communication loss rate ranging 1%~10% and possible node failures.

Keywords: Distributed storage, Distributed decoding, Data allocation, Data delivery, Scalable Video Coding, LT codes, WLAN.

並列關鍵字

Distributed storage ； Distributed decoding ； Data allocation ； Data delivery ； Scalable Video Coding ； LT codes ； WLAN

參考文獻

[1] J.W. Byers, M. Luby, M. Mitzenmacher, and A. Rege, “A Digital Fountain Approach to Reliable Distribution of Bulk Data,” in Proceedings of the ACM SIGCOMM, Vancouver, September 1998, pp. 56–67.

[3] M. Luby, “LT Codes,” in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, November 2002, pp. 271–280.

[5] Henry C. H. Chen, Yuchong Hu, Patrick P. C. Lee, and Yang Tang, “NCCloud: A Network-Coding-Based Storage System in a Cloud-of-Clouds,” IEEE Transactions on Computers, Vol. 63, No. 1, January 2014.

[8] Hsu-Feng Hsiao, and Yong-Jhih Ciou , “Layer-aligned Multi-priority Rateless Codes for Layered Video Streaming,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. PP, No. 99, January 2014.

[9] Nikolaos Thomos, Jacob Chakareski, and Pascal Frossard, “Prioritized Distributed Video Delivery With Randomized Network Coding,” IEEE Transactions on Multimedia, Vol. 13, No. 4, August 2011.