最近幾年，多媒體串流服務，包括線上會議，遠距教學和線上電影等，在網路上已經相當受到歡迎。由於多媒體串流具有高頻寬的需求和長時間播放的特性，它需要相當大的傳輸成本去支援這些多媒體串流服務。此外，如何去轉換多媒體內容的格式來符合各種不同資源有限裝置的需求是一個很大的挑戰，網路有限且隨時間變動的頻寬增加了這個內容轉換工作的難度。為迎合各種不同客戶端裝置的特性和使用者的偏好系統需要傳送差別化的內容。因此，為了去減少傳輸的成本和服務異質性的客戶端，在這篇論文中，我們提出一些創新的機制，包括有格式轉換能力的快取伺服器之快取機制，反應式的傳輸機制和網路編碼的點對點網路內容分佈機制，來支援在設置有快取伺服器的網路環境中，提供有效率的多版本和多層式的影像傳輸，以及在點對點的網路環境中提供有效率的互動式網路電視服務。
首先，針對具有轉換格式能力之快取伺服器的多版本影片的快取問題，我們分析如何去快取最佳的影片版本來減少傳輸成本，根據延伸的權重轉換編碼圖，推導影片效益函數去計算一個影片特定版本的快取效益，這個函數考慮了這個版本的受歡迎程度，在不同的版本之間轉換編碼所需要的時間以及每個版本平均存取的時間長度。我們使用這個效益函數去設計了快取替代演算法，有效地快取最高效益的影片物件，來減少啟始影片的延遲時間和網路頻寬。
接著，我們提出一組快取伺服器輔助的傳輸機制，這機制是針對多層式影片的串流，藉由整合快取伺服器，互動式的傳輸機制，點對點的網路和群播能力。這些傳輸機制讓多個要求可以共享單一次的傳輸，因此大量減少了所需要的傳輸成本。對於每個傳輸機制，我們計算最佳化的快取配置去決定快取的影片層和快取的影片長度去最小化累積的傳輸成本。這個程序主要是考慮了快取了X層的影片，不僅是節省了要求X層的使用者的傳輸成本，也同時節省了那些要求少於X層的使用者的傳輸成本。
此外，我們提出了一個網路編碼的等價內容分佈機制去減少伺服器負載，影片啟動時間和隨機存取時間去支援隨機存取操作，在點對點隨選視訊串流服務，這些操作是需要的；由於使用者不同步的互動行為以及節點動態加入離開的特性，隨機存取操作是很難達成的。在網路編碼的等價內容分佈機制中，影片被分為一些片段，一個片段再分為一些區塊，這些區塊再進一步編碼為獨立的編碼區塊，然後再被分佈給不同節點來儲存。使用網路編碼的等價內容分佈機制，一個新來的節點只需要去連接到足夠的父節點就可以觀看整部影片，當執行隨機存取操作時，很少需要再去尋找新的父節點。然而大多數現存的方法都必須尋找特定的父節點包含特定的片段，而我們的方式使用網路編碼的特性去分佈等價的內容在父節點中，因此很少需要再去尋找新的特定父節點，此外，我們也分析系統參數來達到合理的區塊遺失率對於點對點互動性的隨選視訊串流。
實驗結果證明了這些提出的機制可以大量地減少傳輸成本，傳輸時間，頻寬需求，低的啟始影片時間和隨機存取時間，以及連接到新的父節點的時間，和較少的伺服器資源。這些機制可以進一步地整合和使用去建構一個有效的影片串流平台來提供給各種客戶端裝置一個高效能和高品質的網路電視服務。

For more than a decade, streaming media services, including on-line conferences, distance education and movie broadcasting, have gained much popularity on the Internet. Due to the high bandwidth requirements and long lived nature of video streaming, it requires huge transmission cost to support these streaming media services. In addition, how to adapt rich multimedia content to satisfy various resource-constrained devices presents a challenge. The limited and time-varying network bandwidth complicates the content adaptation tasks. Differentiated content delivery may be required to meet diverse client profiles and user preferences. Therefore, in order to reduce transmission cost to serve heterogeneous clients for efficient streaming, in this dissertation, several novel schemes including transcoding-enable proxy caching scheme, reactive transmission schemes, and network coding P2P content distribution scheme, are proposed to support efficient multiple-version and layered video delivery in the proxy-attached network environment as well as to provide efficient interactive IPTV service in a peer-to-peer network.
Firstly, for multiple-version cache consideration in the transcoding-enable proxy, we focus on reducing the required server bandwidth and startup delay by caching the optimal versions of the video. A generalized video object profit function is derived from the extended weighted transcoding graph to calculate the individual cache profit of certain version of a video object, and the aggregate profit from caching multiple versions of the same video object. This proposed function takes into account the popularity of certain version of a video object, the transcoding delay among versions and the average access duration of each version. Based on the profit function, cache replacement algorithms are proposed to reduce the startup delay and network traffic by efficiently caching video objects with maximum profits.
Next, a set of proxy-assisted transmission schemes are proposed to reduce the transmission cost for layered video streaming by integrating the proxy caching with reactive transmission schemes, peer-to-peer mesh networks and multicast capability. These proposed transmission schemes make multiple requests to be serviced by the single transmission and thus to significantly reduce the total required transmission cost. The optimal proxy prefix cache allocation is also calculated for each transmission scheme to identify the cache layers and cache length of each video to minimize the aggregate transmission cost. The process considers the fact that reduction in transmission cost by caching X layers of a video is not only from requests on X layers, but also from requests on less than X layers.
Finally, we proposed a network coding equivalent content distribution (NCECD) scheme to decrease server stress, startup delay and jumping latency to support random access operations which are desirable for peer-to-peer on-demand video streaming. The random access operations are difficult to be efficiently supported, due to the asynchronous interactive behaviors of users and the dynamic nature of peers. In NCECD, videos are divided into segments which are then further divided into blocks. These blocks are then encoded into independent encoded blocks that are distributed to the local storage of different peers. With NCECD, a new client only needs to connect to a sufficient number of parent peers in order to view the whole video and rarely needs to find new parents when performing random access operations. Whereas most existing methods must search for parent peers containing interested segments, NCECD uses the properties of network coding to cache equivalent content on most peers, so that searches are rarely needed. The analysis of system parameters is given to achieve reasonable block loss rates for peer-to-peer interactive video-on-demand streaming.
Experimental results demonstrate that these proposed schemes can lead to significant transmission cost saving, high delay saving ratio, high bandwidth saving ratio, low startup and jumping searching delays, connecting to a new parent peer delay and less server resources. Hence, these proposed schemes can further be integrated and utilized to build an efficient video streaming platform for providing high-performance and high-quality IPTV services to a diversity of clients.

Chapter 1. Introduction……………………………………………………………………….1
1.1 Transcoding and Layered Encoding…………………...……………………………...2
1.2 Streaming Media Caching…………………………………………………………….3
1.3 Reactive Transmission Schemes……………………………………………………...5
1.4 Combination of Caching and Transmission Schemes………………………………..6
1.5 Peer to Peer VOD Streaming………………………………………………………....7
1.6 Summary……………………………………………………………………………..12
1.7 Organization of the Dissertation…………...………………………………………...14
Chapter 2. Transcoding-enable Proxy Caching Scheme……………………………………..15
2.1 The Flowchart with Transcoding-enabled Caching Proxy…..…………………….....15
2.2 The Extended Weighted Transcoding Graph………………………………………...18
2.3 The Generalized Video Object Profit Function……………………………………....19
2.4 Design of Cache Replacement Algorithms…………………………………………...24
2.5 Performance Evaluation……………………………………………………………...25
Chapter 3. Proxy-assisted Transmission Schemes…………………………………………...39
3.1 The Scenario of Proxy-assisted Transmission Schemes for Layered Videos
Delivery……………………………………………………………………………....39
3.2 Optimal Proxy Prefix Cache Allocation……………………………………………...40
3.3 The Proxy-assisted Layered Video Transmission Schemes……………………….....43
3.4 Performance Evaluation……………………………………………………………....57
Chapter 4. Network Coding Equivalent Content Distribution Scheme……………………….71
4.1 The Scenario of NCECD Scheme for the Multi-sources P2P-based Interactive
VoD Streaming……………………………………………………………………….72
4.2 Network Coding Equivalent Content Distribution Scheme………………….………73
4.3 The Analysis of System Parameters for NCECD Scheme…………………………...79
4.4 Performance Evaluation……………………………………………………………...89
Chapter 5. Conclusions and Future Work…………………………………………………...101
5.1 Conclusions…………………………………………………………………………101
5.2 Future Work…………………………………………………………………………104
References..…………………………………………………………………………………106

[1] E. Amir, S. McCanne, and H. Zhang, “An application level video gateway,” in Proceedings of the third ACM international conference on Multimedia, pp. 255-265, Nov. 1995
[2] S. Chandra, C. S. Ellis, and A. Vahdat, “Application-level differentiated multimedia web services using quality aware transcoding,” IEEE J. Select. Areas Commun., vol. 18, pp. 2544–2565, Dec. 2000.
[3] R. Mohan, J. R. Smith, and C. S. Li, “Adapting multimedia internet content for universal access,” IEEE Trans. Multimedia, vol. 1, pp. 104–114, Mar. 1999.
[4] S. Acharya, H. Korth, and V. Poosala, “Systematic multiresolution and its application to the world wide web,” in Proc. IEEE ICDE’99, Sydney, Australia, pp. 40–49, Mar. 1999,.
[5] A. Maheshwari, A. Sharma, K. Ramamrithan, and P. Shenoy, “Tran-Squid: Transcoding and caching proxy for heterogeneous e-commerce environments,” in Proc. IEEE RIDE 2002, San Jose, CA, pp. 50-59, Feb. 2002.
[6] C. Y. Chang and M. S. Chen, “Exploring aggregate effect with weighted transcoding graphs for effcient cache replacement in transcoding proxies,” in Proc. IEEE ICDE 2002, San Jose, CA, Feb. 2002, pp. 383–392.
[7] K. Chandra and A. R. Reibman, “Modeling one- and two-layer variable bit rate video,” IEEE/ACM Trans. Networking, vol. 7, no. 3, pp. 398-413, June 1999.
[8] S. Sen, J. Rexford, and D. Towsley, “Proxy prefix caching for multimedia streams,” in Proc. IEEE INFOCOM, New York, Mar. 1999, pp. 1310–1319.
[9] Z. Miao and A. Ortega, “Scalable proxy caching of video under storage constraints,” IEEE J. Select. Areas Commun., vol. 20, pp. 1315–1327, Sept. 2002.
[10] O. Verscheure, C. Venkatramani, P. Frossard, and L. Amini, “Joint server scheduling and proxy caching for video delivery,” Comput. Commun., vol. 25, no. 4, pp. 413–423, Mar. 2002.
[11] W. Ma and D. H. C. Du, “Reducing bandwidth requirement for delivering video over wide area networks with proxy server,” IEEE Trans. Multimedia, vol. 4, pp. 539–550, Dec. 2002.
[12] Y. Wang, Z. L. Zhang, D. H. C. Du, and D. Su, “A network-conscious approach to end-to-end video delivery over wide area networks using proxy servers,” in Proc. IEEE INFOCOM, San Francisco, CA, vol. 2, pp. 660-667, Apr. 1998.
[13] S. H. Chang, R. I. Chang, J. M. Ho, and Y. J. Oyang, “An optimal cache algorithm for streaming VBR video over a heterogeneous network,” Computer Communications, vol. 28, pp 1852-1861, Oct. 2005.
[14] S. H. Chang, R. I. Chang, J. M. Ho, and Y. J. Oyang, “A priority selected cache algorithm for video relay in streaming applications,” IEEE Trans. on Broadcasting, vol. 53, np 1, pp. 79-91, Mar. 2007.
[15] Z. L. Zhang, Y. Wang, D. H. C. Du, and D. Su, “Video staging: A proxyserver-based approach to end-to-end video delivery over wide-area networks,” IEEE/ACM Trans. Networking, vol. 8, pp. 429–442, Aug. 2000.
[16] S. J. Lee, W. Y. Ma, and B. Shen, “An interactive video delivery and caching system using video summarization,” Comput. Commun., vol. 25, no. 4, pp. 424–435, Mar. 2002.
[17] R. Rejaie, H. Yu, M. Handely, and D. Estrin, “Multimedia proxy caching mechanism for quality adaptive streaming applications in the internet,” in Proc. IEEE INFOCOM, Tel Aviv, Vol 2, pp. 980-989, Mar. 2000.
[18] W. Ma and D. H. C. Du, “Design a progressive video caching policy for video proxy servers,” IEEE Trans. Multimedia, vol. 6, pp. 599–610, Aug. 2004.
[19] J. Kangasharju, F. Hartanto, M. Reisslein, and K. W. Ross, “Distributing layered encoded video through caches,” IEEE Trans. computer, vol. 51, no. 6, pp. 622-636, June 2002.
[20] C. Y. Chang and M. S. Chen, “On exploring aggregate effect for efficient cache replacement in transcoding proxies,” IEEE Trans. Parallel and Distributed Systems, vol. 14, pp. 611 - 624, June 2003.
[21] X. Tang, F. Zhang, and S. T. Chanson, “Streaming media caching algorithms for transcoding proxies,” in Proc. Intl Conf. on Parallel Processing, pp. 287 – 295, 2002.
[22] B. Shen, S. J. Lee, and S. Basu, “Caching strategies in transcoding-enabled proxy systems for streaming media distribution networks,” IEEE Trans. Multimedia, vol. 6, no. 2, pp. 375–386, Apr. 2004.
[23] C. F. Kao and C. N. Lee, “Aggregate profit-based caching replacement algorithms for streaming media transcoding proxy systems,” IEEE Trans. Multimedia, vol. 9, no. 2, pp. 221–230, Feb. 2007.
[24] C. Aggarwal, J. Wolf, and P. Yu, “On optimal batching policies for video-on-demand storage servers,” in Proc. IEEE Int. Conf. Multimedia Computing and Systems, pp. 253–258, June 1996.
[25] S. Carter and D. Long, “Improving video-on-demand server efficiency through stream tapping,” in Proc. Int. Conf. Computer Communications and Networks, Las Vegas, NV,pp. 200–207, Sept. 1997.
[26] L. Gao and D. Towsley, “Threshold-based multicast for continuous media delivery,” IEEE Trans. Multimedia, vol. 3, no. 4, pp. 405–414, Dec. 2001.
[27] K. Hua, Y. Cai, and S. Sheu, “Patching: A multicast technique for true video-on-demand services,” in Proc. ACM Multimedia, pp. 191–200, Sept. 1998.
[28] D. Eager, M. Vernon, and J. Zahorjan, “Optimal and efficient merging schedules for video-on-demand servers,” in Proc. ACM Multimedia, pp. 199–202, Nov. 1999.
[29] D. Eager, M. Vernon, and J. Zahorjan, “Minimizing bandwidth requirements for on-demand data delivery,” IEEE Trans. Knowledge and Data Engineering, vol. 13, no. 5, pp. 742–757, Sept./Oct. 2001.
[30] D. Eager, M. Ferris, and M. Vernon, “Optimized regional caching for on-demand data delivery,” in Proc. Multimedia Computing and Networking (MMCN ’99), San Jose, CA, pp. 301–316, Jan. 1999.
[31] S. Sen, L. Gao, and D. Towsley, “Frame-based periodic broadcast and fundamental resource tradeoffs,” in Proc. IEEE Int. Performance Computing and Communications Conf., Phoenix, AZ, pp. 77–83, Apr. 2001.
[32] S. Ramesh, I. Rhee, and K. Guo, “Multicast with cache (Mcache): An adaptive zero-delay video-on-demand service,” IEEE Trans. Circuits and Systems for Video Technology, vol.11, no. 3, pp. 440 – 456, March 2001.
[33] B. Wang, S. Sen, M. Adler, and D. Towsley, “Optimal proxy cache allocation for efficient streaming media distribution,” IEEE Trans. Multimedia, vol. 6, no. 2, pp. 366-374, Apr. 2004.
[34] [Online]. Available: http://www.bittorrent.com
[35] H. Chi, Q. Zhang, J. Jia, and X. Shen, “Efficient search and scheduling in P2P-based media-on-demand streaming service,” IEEE J. Select. Areas Commun., vol. 25, no. 1, pp. 119–130, Jan. 2007.
[36] A. Sharma, A. Bestavros, and I. Matta, “dPAM: A distributed prefetching protocol for scalable asynchronous multicast in P2P systems,” in Proceedings of IEEE INFOCOM, Miami, FL, USA, Mar. 2005.
[37] Y. Cui, B. Li, and K. Nahrstedt, “oStream: Asynchronous streaming multicast in application-layer overlay networks,” IEEE J. Select. Areas Commun., vol. 22, no. 1, pp. 91–106, Jan. 2004.
[38] T. T. Do, K. A. Hua, and M. A. Tantaoui, “P2VoD: Providing fault tolerant video-on-demand streaming in peer-to-peer environment,” in Proceedings of IEEE International Conference on Communications (ICC), Paris, France, June 2004.
[39] W. P. K. Yiu, X. Jin, and S. H. G. Chan, “VMesh: Distributed segment storage for peer-to-peer interactive video streaming,” IEEE J. Select. Areas Commun., vol. 25, no. 9, pp. 1717-1731, Dec. 2007.
[40] C. Xu, G. M. Muntean, E. Fallon, and A. Hanley, “A balanced tree-based strategy for unstructured media distribution in P2P networks,” in IEEE International Conference on Communications, 2008 (ICC’08), pp. 1797-1801, May 2008.
[41] C. Zheng, G. Shen, and S. Li, “Distributed prefetching scheme for random seek support in peer-to-peer streaming applications,” in Proceedings of ACM Multimedia Conference, Workshop on Advances in Peer-to-Peer Multimedia Streaming, Singapore, Nov. 2005.
[42] V. N. Padmanabhan, H. J. Wang, and P. A. Chou, “Distributing streaming media content using cooperative networking,” in Proceedings of NOSSDAV’02, USA, May 2002.
[43] M. Hefeeda, A. Habib, B. Botev, D. Xu, and B. Bhargava, “PROMISE: Peer-to-peer media streaming using CollectCast,” in Proceedings of the 11th ACM International Conference on Multimedia (MM), Berkeley, pp. 45–54, CA, USA, Nov. 2003.
[44] M.Wang and B. Li, “R2: Random push with random network coding in live peer-to-peer streaming,” IEEE J. Select. Areas Commun., Special Issue on Advances in Peer-to-Peer Streaming Systems, vol. 25, pp. 1655–1666, Dec. 2007.
[45] G. Wu, B. Li, and Z. Li, “Dynamic bandwidth auctions in multioverlay P2P streaming with network coding,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 6, pp. 806–820, June 2008.
[46] H. Chi, Q. Zhang, J. Jia, and X. Shen, ”Efficient search and scheduling in P2P-based media-on-demand streaming service,” IEEE J. Select. Areas Commun., vol. 25, no. 2, pp. 119-130, Jan. 2007.
[47] C. Gkantsidis, J. Miller, and P. Rodriguez, “Comprehensive view of a live network coding P2P system,” in Proc. ACM SIGCOMM/USENIX IMC’06, Brasil, Oct. 2006.
[48] S. Annapureddy, S. Guha, C. Gkantsidis, D. Gunawardena, and P. Rodriguez, “Exploring vod in P2P swarming systems,” in IEEE INFOCOM 2007, Anchorage, Alaska, USA, May 2007.
[49] K. Nguyen, T. Nguyen, and S. C. Cheung, “Peer-to-peer streaming with hierarchical network coding,” in IEEE International Conference on Multimedia and Expo, Beijing, China, July 2007.
[50] D. Wang and J. Liu, “A dynamic skip list-based overlay for on-demand media streaming with VCR interactions,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 4, pp. 503-514, APR. 2008.
[51] H. V. Jagadish, B. C. Ooi, and Q. H. Vu, “BATON: A balanced tree structure for peer-to-peer networks,” in Proc. Int. Conference on Very Large Data Bases (VLDB''05), August 2005.
[52] V. Cardellini, P. S. Yu, and Y. W. Huang, “Collaborative proxy system for distributed web content transcoding,” in Proc. ACM Int’l Conf. Information and Knowledge Management, pp. 520-527, 2000.
[53] M. Chesire, A.Wolman, G. M. Voelker, and H. M. Levy, “Measurement and analysis of a streaming-media workload,” in Proc. USITS 2001, San Francisco, CA, Mar. 2001.
[54] A. Maheshwari, A. Sharma, K. Ramamrithan, and P. Shenoy, “Tran-Squid: Transcoding and caching proxy for heterogeneous e-commerce environments,” in Proc. IEEE RIDE 2002, San Jose, CA, Feb. 2002.
[55] C. Diot, B. Levine, B. Lyles, H. Kassan, and D. Balsiefien, “Deployment issues for the IP multicast service and architecture,” IEEE Network, vol. 31, pp. 78–88, 2000.
[56] S. Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Transactions on Information Theory, vol. 49, no. 2, pp. 371-381, Feb. 2003.
[57] A. Habib and J. Chuang, “Service differentiated peer selection: An incentive mechanism for peer-to-peer media streaming,” IEEE Transactions on Multimedia, vol. 8, no. 3, pp. 610-621, June 2006.
[58] P. J. Wu, J. N. Hwang, C. N. Lee, C. C. Gau, and H. H. Kao, “Eliminating packet loss accumulation in peer-to-peer streaming systems,” IEEE Transctions on Circuits and Systems for Video Technology, vol. 19, no. 12, pp. 1766-1780, Dec. 2009.
[59] E. W. Zegura, K. L. Calvert, and S. Bhattacharjee, “How to model an internetwork,” in Proceedings of IEEE INFOCOM, vol. 2, pp. 594-602, San Francisco, CA, Mar. 1996.
[60] M. Wang and B. Li, “Lava: A reality check of network coding in peer-to-peer live streaming,” in Proc. of IEEE INFOCOM, 2007.