在點對點隨選視訊系統中最佳化頻寬之使用以確保錄放影功能的品質

Optimizing Bandwidth Utilization for Quality of VCR Operations in P2P VoD Systems

鍾孜孟(Tzu-Meng Chung)

指導教授 ： 金仲達

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

摘要

近年來，點對點隨選視訊系統的使用已有愈來愈受歡迎的趨勢。現今已有不少的點對點隨選視訊系統發表，而其中有些是可以支援錄放影功能的，譬如隨意跳至任意位置的播放點。不過這些系統卻需要一個強大的來源伺服器來提供一定程度的播放品質。所以，在這裡值得探討的議題是對一個可支援錄放影功能的點對點隨選視訊系統而言，如何不依靠一個強大的來源伺服器而能夠提供良好的播放品質。
目前的做法是依靠在點對點網路上複製多份的影片區塊，讓每一影片區塊在網路上都有多份的複製來減少對來源伺服器的依靠。但是這樣的做法並沒有把每個節點的上傳頻寬給考慮進去，這對現今網路頻寬多樣化而言是不合理的。在這篇論文中，我們把網路頻寬的不同給考慮進去，並且也考慮每個節點能提供儲存影片區塊的容量是有限制的。加上上述的這些考量之後，我們重新將問題規劃成一個最佳化頻寬使用的問題。我們首先證明這個問題是NP-hard，並提出一個使用動態規劃的最佳解。最後我們介紹一個能在分散式環境上實際運用的啟發式演算法。

關鍵字

點對點 ； 隨選視訊系統 ； 錄放影

並列摘要

Peer-to-peer (P2P) video-on-demand (VoD) is increasingly popular with Internet users. Many P2P VoD systems have been proposed. Some of them can support VCR operations, such as fast forward and jumping to arbitrary playback points, but they require very well provisioned source servers to guarantee the quality. The challenge is to do the same without requiring well provisioned source servers.
Most previous works tackle the quality issue by replicating the blocks of the video uniformly in the overlay to reduce the dependence on the source servers. However, ensuring the number of replicas per blocks is not enough, since the bandwidth of peers in the P2P network is often heterogeneous. In this thesis, we take the heterogeneity of bandwidth into consideration, and also consider the practical case in which the capacity of the streaming buffer is limited. With these conditions, we formulate the problem as a bandwidth utilization optimization problem. We first prove that this problem is NP-hard and then propose an optimal dynamic programming solution. Finally, we introduce a distributed heuristic to solve this problem practically.

並列關鍵字

HASH(0x1cff1d40) ； HASH(0x1cff1de0) ； HASH(0x1cff1e80)

參考文獻

[1] T. T. Do, K. A. Hua, and M. A. Tantaoui, “P2VoD: Providing Fault Tolerant Video-on-Demand Streaming in Peer-to-Peer Environment,” Proc. of the IEEE International Conference on Communications (ICC), Jun. 2004.

[8] B. Cheng, H. Jin, and X. Liao, “Supporting VCR Functions in P2P VoD Services Using Ring-Assisted Overlays,” Proc. of the IEEE International Conference on Communications (ICC), 2007.

[10] J. Ganesh, A. M. Kermarrec, and L. Massoulie, “Peer-to-Peer membership management for gossip-based protocols,” IEEE Transaction on Computer, 52(2), Feb. 2003.

[2] Y. Guo, K. Suh, J. Kurose, and D. Towsley, “P2Cast: Peer-to-peer Patching Scheme for VoD Service,” Proc. of the 12th International Conference on World Wide Web, 2003.

[3] L. H. Ying, and A. Basu, “pcVOD: Internet Peer-to-Peer Video-On-Demand with Storage Caching on Peers,” Proc. of the 11th International Conference on Distributed Multimedia Systems (DMS), 2005.