臺灣博碩士論文加值系統

隨著視訊分享服務的盛行，如何能有效率的在異質性網路上散佈影片成為一個相當重要的技術議題。我們所發展出來的NTUStreaming是一套同儕式網路電視系統，它整合了同儕網路技術與視訊編碼技術上的創新，以達到最佳化之使用者經驗。本系統包含三個主要的元件：夥伴關係形成、強健視訊編碼技術與視訊區塊下載排程。於夥伴關係形成，我們發展出基於圖形建置機制之TYPHOON協定，來減低斷線時間與被孤立節點的個數。於編碼技術上，我們提出於空間與時間域上做修補之多重描述編碼技術，可隨著可用頻寬及設備能力來調整所傳送之資料。對於資料下載排程，我們發展出考慮可用頻寬及可取得之視訊區塊種類的最佳化之排程演算法。
因即時多重描述編碼並不完全可行，當傳輸即時視訊串流時，運算能力的支援就為一大挑戰。此現象將視訊傳輸的瓶頸由網路傳輸延遲轉移到了運算上的延遲。為了解決這個難題，我們在NTUStreaming上發展出協同式轉碼以及複雜度感知之視訊調整機制以使其能支援多頻道之即時視訊廣播。於協同式轉碼，我們利用NTUStreaming之同儕式網路架構，讓每個節點的運算資源共享。在這個架構下，視訊轉碼的工作被技術性的分配到不同的節點上，並被協力的完成。於複雜度感知之視訊調整機制，我們根據每個頻道之優先程度以及視訊品質做全域最佳化之分配。我們已經完成原型的實作並在PlanetLab上的一百個節點進行測試。實驗結果顯示，NTUStreaming可在易造成資料遺失且會動態變化的網路上提供最佳化之視訊品質。此外，即使在大部分的節點都只有有限的運算資源與頻寬的限制下，協同式轉碼也能有效的運作。並且，複雜度感知之視訊調整機制亦能準確調控有限之運算之資源。

As video sharing over broadband heterogeneous devices emerges, one major technical issue is how to disseminate video efficiently. To address this issue, we develop NTUStreaming, an overlay P2P-based IPTV system that integrates innovations in both overlay networking and video coding for optimal user experience. The system consists of three key components: partnership formation, robust video coding, and video segment request scheduling. For partnership formation, a graph construction mechanism TYPHOON based on epidemic algorithms is developed to reduce disconnect time and isolated peers. For robust video coding, a multiple description coding (MDC) scheme with spatial-temporal hybrid interpolation (STHI) is proposed to adjust streaming traffic according to the bandwidth and device capability of each peer. For request scheduling, an optimization algorithm is developed by taking the available bandwidth and the video segment type into account.
When streaming live videos to heterogeneous devices, the computing support for live video broadcasting becomes a challenge since real-time video encoding is not completely feasible. This shifts the bottleneck of video delivery from network delay to computational lag that strongly affects the quality of live video streaming. To solve this problem, NTUStreaming is integrated with collaborative transcoding and complexity-aware video adaptation to enable the support of live video broadcasting of multiple channels. For collaborative transcoding, we exploit the peering architecture of NTUStreaming and make the computational resources of video sources and receivers sharable. In this new content delivery paradigm, the video transcoding task is strategically distributed over the peers and completed collaboratively. We also develop a complexity-aware video adaptation scheme to adjust the computational resource of each channel based on the priority and video quality when a node needs to handle multiple live video streams. A prototype is implemented and evaluated over a 100-node testbed on the PlanetLab. Experimental results show that NTUStreaming is able to deliver optimal video quality in lossy and dynamic networking environments. In addition, collaborative transcoding works effectively even when the mass majority of the peers have limited computational resource and bandwidth, and complexity-aware video adaptation can accurately adjust the computational resource.

Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Contributions 5
1.3 Organization 7
Chapter 2 Partnership Formation Protocol – TYPHOON 8
2.1 Protocol Description 8
2.2 Evaluation 13
2.2.1 Stability Evaluation 15
2.2.2 Comparison between SCAMP and TYPHOON over Both Static and Dynamic Networks 18
Chapter 3 Multiple Description Coding with Spatial-Temporal Hybrid Interpolation (MDC-STHI) 21
3.1 Overview of MDC-STHI 24
3.2 Encoder & Decoder Architecture 29
3.2.1 Spatial Interpolation 31
3.2.2 Temporal Interpolation 32
3.2.3 Weight Determination 32
3.3 Comparison between MDC-STHI and LVC 33
3.4 Multiple Description Coding Evaluation 37
Chapter 4 System Integration 42
4.1 Integration 42
4.2 Segment Scheduling 45
4.3 Evaluation 47
4.3.1 Simulation 47
4.3.2 Evaluation on A Small-Scale Testbed 50
4.3.3 Evaluation on PlanetLab 55
Chapter 5 Collaborative Transcoding 56
5.1 Bottleneck of P2P Live Video Broadcasting 57
5.2 Related Work 59
5.3 System Overview 61
5.4 Computational Capability Estimation 65
5.5 Peer Information Exchange 67
5.6 Job Scheduling 69
5.6.1 Candidate Segment Selection 72
5.6.2 Transcoding Job Scheduling 73
5.6.3 Source Node 74
5.7 Experimental Results 76
5.7.1 Experimental Settings and Metrics 76
5.7.2 Peers with Homogeneous Computational Resource 78
5.7.3 Peers with Heterogeneous Computational Resource 82
5.7.4 Peers with Heterogeneous Computational Resource and Bandwidth 85
5.7.5 Parameter Choices 90
Chapter 6 Complexity-Aware Video Adaptation 94
6.1 Related Work 94
6.2 System Architecture 96
6.3 Block-Based Complexity Control (BCC) 99
6.4 Complexity-Distortion Modeling 102
6.5 Available Resource Calculation 111
6.6 Globally Optimized Resource Allocation 112
6.7 Simulation Results 115
Chapter 7 Discussions and Conclusion 120
7.1 Discussions and Future Work 120
7.1.1 Locality Awareness and ISP Friendliness 120
7.1.2 Balanced Segment Request Scheduling 121
7.1.3 Network Address Translation (NAT) Traversal 121
7.1.4 Pollution Attack Prevention 122
7.1.5 Extension of Collaborative Transcoding to Support Other Codecs 123
7.1.6 Modeling 123
7.2 Conclusion 124
Chapter 8 Bibliography 126

[1] “Coding of audio-visual objects, part-2 visual, ISO/IEC 14496-2,” Dec. 1998.
[2] S. Srinivasan, P. Hsu, T. Holcomb, K. Mukerjee, S. L. Regunathan, B. Lin, J. Liang, M.-C. Lee, and J. Ribas-Corbera, “Windows media video 9: overview and applications,” Signal Processing: Image Communication, vol. 19, no. 9, pp. 851-875, Oct. 2004.
[3] T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra, “Overview of the H.264/AVC video coding standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560–576, Jul. 2003.
[4] J.-R. Ohm, “Advances in scalable video coding,” in Proc. IEEE, vol.93, no. 1, pp. 42–56, Jan. 2005.
[5] H. Schwarz, D. Marpe, and T. Wiegand, “Overview of the scalable video coding extension of the H.264/AVC standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 9, pp. 1103-1120, Sept. 2007.
[6] “Coding of Audio-Visual Objects, Part-2 Visual, Amendment 4: Streaming Video Profile, ISO/IEC 14496-2/FPDAM4”, Jul. 2000.
[7] Y. Wang, A. R. Reibman, and S. Lin, “Multiple description coding for video delivery,” Proceedings of the IEEE, vol. 93, no. 1, pp. 57-70, Jan. 2005.
[8] V. K. Goyal, “Multiple description coding: compression meets the network,” IEEE Signal Processing Magazine, vol. 18, no. 5, pp. 74-93, Sept. 2001.
[9] J. G. Apostolopoulos, "Error-resilient video compression via multiple state streams," in Proc. Int. Workshop Very Low Bitrate Video Coding, pp. 168-171, Kyoto, Japan, Oct. 1999.
[10] J. G. Apostolopoulos, "Reliable video communication over lossy packet networks using multiple state encoding and Path diversity," in Proc. Visual Communications and Image Processing, pp. 392-409, San Jose, CA, Jan. 2001.
[11] G. Zhang and R. L. Stevenson, "Efficient error recovery for multiple description video coding," in Proc. Int. Conf. Image Processing, pp. 829-832, Singapore, Oct. 2004.
[12] YouTube. Available: http://www.youtube.com/
[13] Yahoo Video. Available: http://video.yahoo.com/
[14] MSN Video. Available: http://video.msn.com/
[15] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, “RTP: a transport protocol for real-time applications,” Request for Comments 3550, IETF Network Working Group, Jul. 2003.
[16] H. Schulzrine, A. Rao, and R. Lanphier, “Real time streaming protocol (RTSP),” Request for Comments 2326, IETF Network Working Group, Apr. 1998.
[17] M. Handley and V. Jacobson, “SDP: session description protocol,” Request for Comments 2327, IETF Network Working Group, Apr. 1998.
[18] D. Waitzman, C. Patridge, and S. Deering, "Distance vector multicast routing protocol," Request For Comments 1075, IETF Network Working Group, Nov. 1988.
[19] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, P. Sharma, and L. Wei, "Protocol independent multicast-sparse mode (PIM-SM): Protocol specification," Request for Comments 2362, IETF Network Working Group, Jun. 1998.
[20] S. Floyd, V. Jacobson, C. Liu, S. McCanne and L. Zhang., "A reliable multicast framework for light-weight sessions and application level framing," IEEE/ACM Trans. Networking, vol. 5, no. 6, pp. 784-803, Dec. 1997.
[21] PPStream. Available: http://www.ppstream.com/
[22] PPLive. Available: http://www.pplive.com/
[23] SopCast. Available: http://www.sopcast.com/
[24] Joost. Available: http://www.joost.com/
[25] X. Zhang, J. Liu, B. Li, and T.-S. P. Yum, “DONet/CoolStreaming: A data-driven overlay network for live media streaming,” in Proc. IEEE INFOCOM, vol. 3, pp. 2102-2111, Miami, FL, Mar. 2005.
[26] C. Huang, J. Li, and K. W. Ross, “Can Internet video-on-demand be profitable?” in Proc. ACM SIGCOMM, Kyoto, Japan, Aug. 2007.
[27] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, "Application-level multicast using content-addressable networks," in Proc. Third Int. Workshop Networked Group Communication, London, England, pp. 14-29, Nov. 2001.
[28] D. A. Tran, K. A. Hua, and T. T. Do., "A peer-to-peer architecture for media streaming (Zigzag)," IEEE J. Selected Areas in Communications, pp. 121-133, Jan. 2004.
[29] M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh, “SplitStream: high-bandwidth multicast in cooperative environments,” in Proc. ACM SOSP03, New York, Oct. 2003.
[30] X. Liao, H. Jin, Y. Liu, L. M. Ni, and D. Peng, “AnySee: peer-to-peer live streaming,” in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
[31] A. J. Ganesh, A. M. Kemarrec, and L. Massoulie, “Peer-to-peer membership management for gossip-based protocols,” IEEE Trans. Computers, vol. 52, no. 2, pp. 139-149, Feb. 2003.
[32] A. J. Demers, D.H. Greene, C. Hauser, W. Irish, and J. Larson, “Epidemic algorithms for replicated database maintenance,” in Proc. Sixth Ann. ACM Symp. Principles of Distributed Computing (PODC), pp. 1-12, Aug. 1987.
[33] P. T. Eugster, R. Guerraoui, S.B. Handurukande, A.-M. Kermarrec, and P. Kouznetsov, “Lightweight probabilistic broadcast,” in Proc. IEEE Int. Conf. Dependable Systems and Networks (DSN2001), 2001.
[34] L. Breslau, D. Estrin, K. Fall, S. Floyd, J. Heidemann, A. Helmy, P. Huang, S. McCanne, K. Varadhan, Y. Xu, and H. Yu, “Advances in network simulation,” IEEE Computer Mag., vol. 33, no. 5, pp. 59-67, May 2000.
[35] V. N. Padmanabhan, H. J. Wang, and P. A. Chou, "Resilient peer-to-peer streaming," in Proc. IEEE Int. Conf. Network Protocols, pp. 240-247, Atlanta, Georgia, Nov. 2003.
[36] M. Zink and A. Mauthe, "P2P streaming using multiple description coded video," in Proc. Euromicro Conf., pp. 240-247, Rennes, France, Sept. 2004.
[37] S. Khan, R. Schollmeier, and E. Seinbach, "A performance comparison of multiple description video streaming in peer-to-peer and content delivery networks," in Proc. IEEE Int. Conf. Multimedia and Expo, pp. 503-506, Taipei, Taiwan, Jun. 2004.
[38] Y. Cui and K. Nahrstedt, “Layered peer-to-peer streaming,” in Proc. Int. Workshop Network and Operating Systems Support for Digital Audio and Video, Monterey, CA, Jun. 2003.
[39] R. Rejaie and A. Ortega, “PALS: Peer-to-peer adaptive layered streaming,” in Proc. Int. Workshop Network and Operating Systems Support for Digital Audio and Video, Monterey, CA, Jun. 2003.
[40] Y. Shen, Z. Liu, S. S. Panwar, K. W. Ross, and Y. Wang, “Streaming layered encoded video using peers,” in Proc. IEEE Int. Conf. on Multimedia and Expo, Amsterdam, Netherlands, Jul. 2005.
[41] R. Puri and K. Ramchandran, “Multiple description source coding through forward error correction codes,” in Proc. Asilomr Conf. on Signals, Systems and Computers, Asilomar, CA, 1999.
[42] X. Xu, Y. Wang, S. S. Panwar, and K. W. Ross, “A peer-to-peer video-on-demand system using multiple description coding and server diversity,” in Proc. IEEE Int. Conf. on Image Processing, pp. 1759-1762, Singapore, Oct. 2005.
[43] J. Reichel, H. Schwarz, and M. Wien, ”Joint scalable video model JSVM-6,” Joint Video Team of ITU-T VCEG and ISO/IEC MPEG, Doc. JVT-S202, Geneva, Switzerland, Apr. 2006.
[44] H. Cai, B. Zeng, G. Shen, Z. Xiong, and S. Li, “Error-resilient unequal error protection of fine granularity scalable video bitstreams,” EURASIP J. Applied Signal Processing, vol. 2006, Article ID 45412, 11 pages, 2006.
[45] PlanetLab. Available: http://www.planet-lab.org/
[46] P. Li, B. Veeravalli, A. A. Kassim, “Design and implementation of parallel video encoding strategies using divisible load analysis, “ IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 9, pp. 1098-1112, Sep. 2005.
[47] G. Kola, T. Kosar, and M. Livny, “A fully automated fault-tolerant system for distributed video processing and off-site replication, “in Proc. Int. Workshop Network and Operating Systems Support for Digital Audio and Video, pp. 122-126, Cork, Ireland, Jun. 2004.
[48] F. Chen, T. Repaints, and V. Kalogeraki, “Coordinated media streaming and transcoding in peer-to-peer systems, “ in Proc. IEEE Int. Parallel and Distributed Processing Symp., Denver, Colorado, Apr. 2005.
[49] D. Liu, E. Setton, B. Shen, and S. Chen, “PAT: peer-assisted transcoding for overlay streaming to heterogeneous devices, “ in Proc. Int. Workshop Network and Operating Systems Support for Digital Audio and Video, Urbana, Illinois, Jun. 2007.
[50] W. Yuan and K. Nahrstedt, “Energy-efficient soft real-time CPU scheduling for mobile multimedia system, “ in Proc. ACM Symp. on Operating Systems Principles, pp. 149-163, New York, Oct. 2003.
[51] B. Urgaonkar, P. Shenoy, and T. Reoscoe, “Resource overbooking and application profiling in shared hosting platforms, “ in Proc. ACM Symp. on Operating Systems Design and Implementation, pp. 239-254, Boston, MA, Dec. 2002.
[52] Z. Yang, W. Wu, K. Nahrstedt, G. Kurillo, and R. Bajscy, “Viewcast: view dissemination and management for multi-party 3d tele-immersive environments, “ in Proc. ACM Multimedia, pp. 882-891, Augsburg, Germany, Sep. 2007.
[53] L.-J Chen, T. Sun, G. Yang, M. Y. Sanadidi, and M. Gerla, "Monitoring access link capacity using TFRC probe," Elsevier J. Computer Communications (ComCom), Special Issue on Monitoring and Measurements of IP Networks, vol. 29, no. 10, pp. 1605-1613, Jun. 2006.
[54] M.-T. Lu, C.-K. Lin, J. Yao, and H. H. Chen, "Multiple description coding with spatial-temporal hybrid interpolation for video streaming in peer-to-peer networks," in Proc. IEEE Packet Video Workshop, Hangzhou, Zejiang, China, Apr. 2006.
[55] J.-C. Wu, K.-J. Peng, M.-T. Lu, C.-K. Lin, Y.-H. Cheng, P. Huang, J. Yao, and H. H. Chen, "HotStreaming: Enabling scalable and quality IPTV services," in Proc. IPTV Workshop in conjunction with the 15th Int. World Wide Web Conf., Edinburgh, Scotland, UK, May 2006.
[56] M.-T. Lu, H. Nien, J.-C. Wu, K.-J. Peng, P. Huang, J. Yao, H. H. Chen, and C.-C. Lai, "A scalable peer-to-peer IPTV system," in Proc. of IEEE Consumer Communications and Networking Conf., pp. 313-317, Las Vegas, Jan. 2007.
[57] M.-T. Lu, J.-C. Wu, K.-J. Peng, P. Huang, J. J. Yao, and H. H. Chen, "Design and evaluation of a P2P IPTV system for heterogeneous networks", IEEE Trans. Multimedia, Special Issue on Content Storage and Delivery in Peer-to-Peer Networks, pp. 1568-1579, Oct. 2007.
[58] T. Chiang and Y.-Q. Zhang, “A new rate control scheme using quadratic rate distortion model,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 7, no. 2, pp. 246-250, Feb. 1997.
[59] Z. He and S. K. Mitra, “A unified rate-distortion analysis framework for transform coding,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 11, no. 12, pp. 1221-1236, Dec 2001.
[60] Z. He and S. K. Mitra, “A linear source model and a unified rate control algorithm for DCT video coding,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 12, no. 11, pp. 970-982, Nov. 2002.
[61] J. Ribas-Corbera and S. Lei, “Rate control in DCT video coding for low-delay communications,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 9, no. 2, pp. 172-185, Feb. 1999.
[62] P.-L. Tai, S.-Y Huang, C.-T. Liu, and J.-S. Wang, "Computation-aware scheme for software-based block motion estimation," IEEE Trans. on Circuits and Systems for Video Technology, vol. 13, no. 9, pp. 901-913, Sept. 2003.
[63] C.-Y. Chen, Y.-W. Huang, C.-L. Lee, and L.-G. Chen, “One-pass computation-aware motion estimation with adaptive search strategy," IEEE Trans. on Multimedia, vol. 8, no. 4, pp. 698-706, Aug. 2006.
[64] Y. Zhao and I. E G Richardson, “Complexity management for video encoders,” in Proc. ACM Int’l Conf. on Multimedia, France, Dec. 2002.
[65] Z. Zhong and Y. Chen, “Complexity regulation for real-time video encoding,” in Proc. Int’l Conf. on Image Processing, pp. 647-649, New York, USA, Sept. 2002.
[66] Z. He, Y. Liang, L. Chen, I. Ahmad, and D. Wu, "Power-rate-distortion analysis for wireless video communication under energy constraints," IEEE Trans. On Circuits and Systems for Video Technology, vol. 15, no. 5, pp. 645-658, May 2005.
[67] J. Stottrup-Andersen, S. Forchhammer, and S. M. Aghito, “Rate-distortion-complexity optimization of fast motion estimation in H.264/MPEG-4 AVC,” in Proc. Int’l Conf. on Image Processing, pp. 111-114, Singapore, Oct. 2004.
[68] M. van der Schaar, D. Turaga, and V. Akella, “Rate-Distortion-Complexity adaptive video compression and streaming”, in Proc. Int’l Conf. on Image Processing, pp. 2051-2054, Singapore, Oct. 2004.
[69] M. van der Schaar, Y. Andreopoulos, and Q. Li, “Real-time multimedia streaming using rate-distortion-complexity models,” in Proc. IEEE Global Telecommunications Conf., pp. 639-643, Dallas, USA, Nov. 2004.
[70] G. Landge, M. van der Schaar, and V. Akella, “Complexity metric driven energy optimization framework for implementing MPEG-21 scalable video decoders,” in Proc. IEEE Int’l Conf. on Acoustics, Speech, and Signal Processing, vol. 2, pp. 1141-1144, Philadelphia, USA, Mar. 2005.
[71] M. van der Schaar and Y. Andreopoulos, “Rate-distortion-complexity modeling for network and receiver aware adaptation,” IEEE Trans. on Multimedia, vol. 7, no. 3, pp 471-480, Jun. 2005.
[72] S.-F. Lin, M.-T. Lu, C.-H. Pan, and H. H. Chen, "Fast multi-frame motion estimation for H.264 and its applications to complexity-aware streaming," IEEE Int''l Conf. Circuits and Systems, pp. 1505-1508, Kobe, Japan, May 2005.
[73] M.-T. Lu, C.-K Lin, J. Yao, and H.H. Chen, "Complexity-aware live streaming system," in Proc. IEEE Int’l Conf. on Image Processing, vol. 1, pp. 193-196, Genova, Sept. 2005.
[74] M.-T. Lu, C.-K Lin, J. Yao, and H.H. Chen, "A Complexity-aware live streaming system with bit rate adjustment," in Proc. IEEE Int’l Symposium on Multimedia, Irvine, California, USA, Dec. 2005.
[75] M.-T. Lu, C.-K Lin, J. Yao, and H.H. Chen, "Block-based computation adjustment for complexity-aware live streaming systems," in Proc. Picture Coding Symposium, Beijing, China, Apr. 2006.
[76] Efficient Algorithms for K-Means Clustering. Available: http://www.cs.umd.edu/~mount/Projects/KMeans/.
[77] T. Kanungo, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu, “An efficient k-means clustering algorithm: analysis and implementation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 24, no. 7, pp. 881-892, July 2002.
[78] T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Wu, “A local search approximation algorithm for k-means clustering,” in Proc. of the 18th Annual ACM Symposium on Computational Geometry, pp. 10-18, 2002.
[79] GLPK (GNU Linear Programming Kit) package. Available: http://www.gnu.org/software/glpk/.
[80] Available:http://www.toshiba.com/taec/Catalog/Line.do?familyid=22&lineid=7185
[81] P. Dhungel, X. Hei, K. W. Ross, and N. Saxena, “The pollution attack in P2P live video streaming: measurement results and defenses,” in Proc. Sigcomm P2P-TV Workshop, Kyoto, Japan, Aug. 2007.
[82] Y. Zhou, D. M. Chiu, and J. C.S. Lui, “A simple model for analyzing P2P streaming protocols,” in Proc. IEEE Int’l Conf. on Network Protocols, pp. 226-235, Beijing, China, Oct. 2007.