跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.169) 您好!臺灣時間:2025/02/18 20:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張信宏
研究生(外文):Shin-Hung Chang
論文名稱:串流視訊代理伺服器暫存機制之研究
論文名稱(外文):A Study of Proxy Cache Mechanism in Video Streaming Applications
指導教授:歐陽彥正歐陽彥正引用關係
學位類別:博士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:94
中文關鍵詞:異質性網路視訊暫存階段式視訊儲存視訊串流變動位元速率視訊
外文關鍵詞:Heterogeneous NetworkVideo CacheVideo StagingVideo StreamingVBR Video
相關次數:
  • 被引用被引用:0
  • 點閱點閱:531
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
高畫質的視訊內容,通常採用壓縮後的格式進行儲存,或透過網路傳輸提供串流服務。壓縮後的視訊內容,先天具備有變動位元速率 (VBR, variable bit rate) 特性,因此進行串流服務時,網路上流量需求變化是非常劇烈的。假如在客戶端沒有一套緩衝機制 (Buffering Mechanism) 來調整視訊資料的傳送,我們需要使用視訊內容資料的最高頻寬需求,進行網路頻寬配置,以保證視訊在串流播放時的品質。為了降低網路頻寬的使用需求,之前的研究者提出了一套階段式視訊儲存機制 (Video Staging)。此暫存機制將部分需要從遠端伺服器傳送的視訊資料,置於靠近客戶端的視訊代理伺服器中。在本論文中,我們提出了使用一回合 (One Pass)即可完成的 OC (Optimal Cache) 演算法,來處理階段式視訊儲存機制。透過數學理論分析,我們證明了使用OC 演算法,對於任一視訊內容在進行串流服務時,可以使用最少的視訊代理伺服器的儲存空間,卻可同時降低與傳統演算法等值的網路頻寬需求。更進一步,我們也考慮到資料封包在透過網路傳輸時,是容易出錯或遺失的。然而,這些載有視訊資料的封包若遺失,很可能影響視訊播放品質,更進一步可能會造成視訊無法完成播放。因此,我們精鍊了 OC 演算法,並提出一套 PSC (Priority Selected Cache) 演算法,選擇暫存最重要的視訊資料在視訊代理伺服器中。此 PSC 演算法具備與 OC 演算法同樣的特性,能使用最少的代理伺服器暫存空間,降低網路頻寬需求。但同時,當網路出現封包遺失狀況時,PSC 演算法能有效避免重要視訊資料遺失,而維持客戶端串流視訊的播放品質。我們透過實驗,針對一些標準視訊資料測試我們的演算法。我們發現,我們提出的演算法確實達到我們的目的,且效果較傳統的演算法,效果有著非常顯著的改進。
High quality video content for on-demand services is usually stored and streamed in a compressed format with a VBR (Variable Bit Rate) property; however, the streaming traffic is extremely bursty. If there is no client buffer to regulate the video’s delivery, the backbone WAN (Wide Area Network) bandwidth needs to allocate the video''s peak bit rate to guarantee playback quality. To reduce the bandwidth requirement in the backbone WAN, previous researchers have proposed a Video Staging Mechanism to cache portions of the video in a video proxy close to clients. In this dissertation, a one-pass OC (Optimal Cache) algorithm is proposed to handle the Video Staging Mechanism and prove theoretically that the proxy cache computed by our OC algorithm for each video is minimal when all other resources remain constant. Additionally, data packets are often lost while streaming video data over the unreliable Internet. These lost packets are often important enough to affect video playback quality and even halt the video playback. Therefore, we refine the OC algorithm and propose a novel PSC (Priority Selected Cache) algorithm to select maximum high-priority video data for caching in a video proxy. The PSC algorithm inherits to use minimum storage in video proxy and reduces the maximum bandwidth requirement of video server (as does the OC algorithm). Additionally, the PSC algorithm also prevents the decoding errors caused by packet loss, improve error recovery, and provide QoS-guaranteed video playback. On the basis of experiment results, we cache the least amount of video data in the video proxy by using the OC algorithm, and reduce the WAN bandwidth requirement by an amount equal to that of conventional algorithms. In contrast, given the equal size of the storage in a video proxy, the OC algorithm reduces the bandwidth requirement in the backbone WAN much more than conventional algorithms. Furthermore, we show that the PSC algorithm caches more high priority video data in a video proxy server than the original OC algorithm.
論文摘要 iii
Abstract v
Acknowledgement vii
List of Contents viii
List of Tables x
List of Figures xi
Chapter 1. Introduction 1
1.1 CBR and VBR Videos 2
1.2 Video Streaming Technology 6
1.3 Heterogeneous Internet 7
1.4 WAN Bandwidth Reduction 9
1.5 Frame Priority in a Compressed Video 14
Chapter 2. Related Works and Problem Formulations 18
2.1 Definitions and Notations 18
2.2 Video Smoothing Algorithm 22
2.3 Video Proxy Server 26
2.3.1 Proxy Prefix Cache Mechanism 26
2.3.2 Video Staging Mechanism 28
2.3.2.1 Cut-off Cache (CC) Algorithm 28
2.3.2.2 Cut-off after Smoothing (CAS) Algorithm 31
2.4 Proxy Cache Minimization (PCM) Problem 32
2.5 Priority Selected Cache Maximization (PSCM) Problem 33
Chapter 3. Proposed Proxy Cache Algorithms 35
3.1 Optimal Cache (OC) Algorithm 35
3.2 Theoretical Analysis of Minimum Proxy Cache 40
3.3 Priority Selected Cache (PSC) Algorithm 47
3.4 Fast Priority Selected Cache (FPSC) Algorithm 54
3.5 Cache Selected After Smoothing (CSAS) Algorithm 57
3.6 Domination Property in Cache Sharing Mechanism 60
Chapter 4. Analysis and Experiment Results 64
4.1 A Comparison between OC and CC Algorithms 64
4.2 Experiment Results by Using Several Benchmark Videos 66
4.2.1 The Proxy Cache Requirement 68
4.2.2 The Utilization of Allocated WAN Bandwidth 71
4.2.3 The Requirement of WAN Bandwidth 75
4.2.4 The Size of Cached I-frame Data 78
Chapter 5. Conclusions 81
Bibliography 85
[1]A. I. Elwalid and D. Mitra, "Effective Bandwidth of General Markovian Traffic Source and Admission Control of High Speed Networks," IEEE/ACM Transactions on Networking, 1993.
[2]A. Dan, D. Sitaram, and P. Shahabuddin, "Scheduling Policies for an On Demand Video Server with Batching," Proceedings of ACM Multimedia, 1994.
[3]A. Bestavros, R. L. Carter, and M. E. Crovella, "Application-level Document Caching in the Internet," Proceedings of International Workshop on Services in Distributed and Networked Environments, 1995.
[4]A. Dan, and D. Sitaram, "An Online Placement Policy Based on Bandwidth to Space," Proceedings of ACM SIGMOD, 1995.
[5]A. R. Reibman and A. W. Berger, "Traffic Descriptors for VBR Video Teleconferencing over ATM Networks," IEEE/ACM Transactions on Networking, June, 1995.
[6]A. Dan and D. Sitaram, "Multimedia Caching Strategies for Heterogeneous Application and Server Environments," Multimedia Tools and Applications, May 1997.
[7]B. C. Smith, "Fast Software Processing of Motion JPEG Video," Proceedings of ACM Multimedia, 1994.
[8]C. S. Freedman and D. J. DeWitt, "The SPIFFI Scalable Video on Demand System," Proceedings of ACM SIGMOD, 1995.
[9]C. Guillemost and R. Ansari, "Layered Coding Schemes for Video Transmission on ATM Networks," Journal of Visual Communication and Image Representation, 1994.
[10]C. C. Han and K. G. Shin, "Scheduling MPEG-Compressed Video with Firm Deadline Constraints," Proceedings of ACM Multimedia, 1995.
[11]D. Ferrari, "Client Requirements for Real-Time Communication Services," IEEE Network Magazine, 1990.
[12]D. L. Gall, "MPEG: A Video Compression Standard for Multimedia Applications," ACM Communications, 1991.
[13]D. J. Gemmell, "Multimedia Network File Servers: Multi-Channel Delay Sensitive Data Retrieval," Proceedings of ACM Multimedia, 1993.
[14]D. M. Cohen and D. P. Heyman, "Performance Modeling of Video Teleconferencing in ATM Network," IEEE Transaction on Circuits and Systems for Video Technology, 1993.
[15]D. Sanghi, A. K. Agrawala, O. Gudmundsson, and B. N. Jain, "Experimental Assessment of End-to-end Behavior on Internet," Proceedings of IEEE INFOCOM, 1993.
[16]David Taubman and Avideh Zakhor, "Highly Scalable, Low Delay Video Compression Method for Multi-resolution Coding Algorithm," Proceedings of IEEE International Conference on Image Processing, 1994.
[17]D. Deloddere, W. Verbiest, and H. Verhille, "Interactive Video On Demand," IEEE Communications Magazine, 1994.
[18]D. Rotem and J. L. Zhao, "Buffer Management for Video Database Systems," Proceedings of 11th International Conference on Data Engineering, 1995.
[19]E. P. Rathgeb, "Policing of realistic VBR video traffic in an ATM network," International Journal on Digital and Analog Communication Systems, 1993.
[20]E. Chang and A. Zakhor, "Scalable Video Data Placement on Parallel Disk Arrays," Proceedings of IS&T/SPIE Symposium on Electronic Imaging Science and Technology, 1994.
[21]Edward W. Knightly, D. E. Wrege, J. Liebeherr and H. Zhang, "Fundamental Limits and Tradeoffs of Providing Deterministic Guarantees to VBR Video Traffic," Proceedings of ACM SIGMETRICS, 1995.
[22]Edward W. Knightly and Hui Zhang, "Traffic Characterization and Switch Utilization Using a Deterministic Bounding Interval Dependent Traffic Model," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 1995.
[23]E. Amir, S. McCanne, and H. Zhang, "An Application Level Video Gateway," Proceedings of ACM Multimedia, November 1995.
[24]F. P. Preparata and M. I. Shamos, "Computational Geometry: An Introduction," 3rd Edition, T&M Computer Science, 1985.
[25]G. D. Stamoulis, M. E. Anagnoustou, and A. D. Georgantas, "Traffic Source Models for ATM Networks," Computer Communications, 1994.
[26]H. Vin, P. Goyal, and A. Goyal, "A Statistical Admission Control Algorithm for Multimedia Servers," Proceedings of ACM Multimedia, 1994.
[27]H. Zhang and E.W. Knightly, "A New Method to Support Delay-sensitive VBR Video in Packet-switched Networks," Proceedings of International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV), 1995.
[28]H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, "RTP: A Transport Protocol for Real-time Applications," RFC 1889," January 1996.
[29]Hui Zhang and Edward W. Knightly, "RED-VBR: A Renegotiation-based Approach to Support Delay Sensitive VBR Video," ACM Multimedia Systems Journal, 1997.
[30]H. Schulzrinne, A. Rao, and R. Lanphier, "Real-time Streaming Protocol (RTSP)," RFC 2326, 1998.
[31]I. Dalgic and F. A. Tobagi, "Performance Evaluation of ATM Networks Carrying Constant and Variable Bit-rate Video Traffic," IEEE Journal of Selected Areas in Communications (JSAC), August 1997.
[32]Ilhwan Kim, H. Y. Yeom and Joonwon Lee, "Analysis of Buffer Replacement Policies for WWW Proxy," Proceedings of the 20th International Conference on Information Networking, 1998.
[33]J. K. Dey, J. D. Salehi, J. F. Kurose, and D. Towsley, "Providing VCR Capabilities in Large Scale Video Servers," Proceedings of ACM Multimedia, 1994.
[34]J. Hui, E. Karasan, J. Li, and J. Zhang, "Client-Server Synchronization and Buffering for Variable Rate Multimedia Retrievals," IEEE Journal on Selected Areas in Communications, (JSAC), 1996.
[35]J. M. McManus and K. W. Ross, "Video On Demand over ATM: Constant-Rate Transmission and Transport," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 1996.
[36]J. Salehi, Zhi Li Zhang, J. Kurose and Don. Towsley, "Supporting Stored Video: Reducing Rate Variability and End-to-End Resource Requirements through Optimal Smoothing," Proceedings of the ACM SIGMETRICS, 1996.
[37]Jennifer Rexford, Subhabrata Sen and Don Towsley, "Online Smoothing for Live, Variable-Bit-Rate Video," Proceedings of the International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV), 1997.
[38]K. Zhu, Y. Zhuang, Y. Viniotis, "Achieving End-to-end Delay Bounds by EDF Scheduling Without Traffic Shaping," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 2001.
[39]M. C. Chuah and R.L. Cruz, "Approximate Analysis of Average Performance of (sigma, rho) Regulators," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 1990.
[40]M. Garrett and W. Willinger, "Analysis, Modeling and Generation of Self-similar VBR Video Traffic," Proceedings of ACM SIGCOMM, 1994.
[41]M. Grossglauser, S. Keshav, and Don Towsley, "PCBR: A Simple and Efficient Service for Multiple Time Scale Traffic," Proceedings of ACM SIGCOMM, 1995.
[42]M. Grossglauser and S. Keshav, "On CBR Service," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 1996.
[43]M. Krunz and S. K. Tripathi, "On the characteristics of VBR MPEG streams," Proceedings of ACM SIGMETRICS, June 1997.
[44]N. F. Maxemchuk and S. Lo, "Measurement and Interpretation of Voice Traffic on the Internet," Proceedings of International Conference on Communications, June 1997.
[45]P. V. Rangan and H. M. Vin, "Designing File Systems for Digital Video and Audio," Proceedings of 12th ACM Symposium on Operating Systems, 1991.
[46]P. Pancha and M. E. Zarki, "MPEG Coding for Variable Bit Rate Video Transmission, " IEEE Communications Magazine, 1994.
[47]P. Cao and S. Irani, "Cost-aware WWW proxy caching algorithms," Proceedings of USENIX Symposium on Internet Technologies and Systems, 1997.
[48]R. L. Cruz, "A Calculus for Network Delay, Part I: Network Elements in Isolation, " IEEE Transaction on Information Theory, 1991.
[49]Rahul Garg, "Characterization of Video Traffic," Technical Report TR-95-007, International Computer Science Institute, Berkeley, 1995.
[50]Ray I Chang, M. Chen, M. T. Ko and Jan-Ming Ho, "Designing the On-off CBR Transmission Schedule for Jitter-free VBR Media Playback in Real-time Networks," Proceedings of the IEEE International Conference on Real-Time and Embedded Computing Systems and Applications (RTCSA), 1997.
[51]R. Fielding, J. Gettys, J. C. Mogul, H. Frystyk, and T. Berners-Lee, "Hypertext transfer protocol –HTTP/1.1," RFC 2068, 1997.
[52]R. Tewari, H. M. Vin, A. Dan, and D. Sitaram, "Resource-Based Caching for Web Servers," Proceedings of SPIE/ACM Conference on Multimedia Computing and Networking, January 1998.
[53]Ray I Chang, M. C. Chen, Jan Ming Ho and M.T. Ko, "Characterizing the Minimal Required Resources for Admission Control of Pre-recorded VBR Video Transmission by An O(nlogn) Algorithm," Proceedings of International Conference on Computer Communications and Networks (ICCCN), 1998.
[54]Ray I Chang, M. C. Chen, Jan Ming Ho and M.T. Ko, "An Effective and Efficient Traffic-Smoothing Scheme for Delivery of Online VBR Media Streams," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 1999.
[55]Ray I Chang, M. C. Chen, M. T. Ko and Jang Ming Ho, "Schedulable Region for VBR Media Transmission with Optimal Resource Allocation and Utilization," Information Sciences, 2002.
[56]S. S. Lam, S. Chow and D. K. Y. Yau, "An Algorithm for Lossless Smoothing of MPEG Video," Proceedings of ACM SIGCOMM, 1994.
[57]S. Ghandeharizadeh and C. Shahabi, "On Multimedia Repositories, Personal Computers, and Hierarchical Storage Systems," Proceedings of ACM Multimedia, 1994.
[58]S. Williams, M. Abrams, C. R. Standbridge, G. Abdulla, and E. A. Fox, "Removal Policies in Network Caches for World Wide Web documents," Proceedings of ACM SIGCOMM, 1996.
[59]S. Acharya and B. Smith, "An Experiment to Characterize Videos on the World Wide Web," Proceedings of SPIE/ACM Conference on Multimedia Computing and Networking, January 1998.
[60]Subhabrata Sen, Jennifer Rexford and Don Towsley, "Proxy Prefix Caching for Multimedia Streams," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 1999.
[61]Shin Hung Chang, Ray I Chang, Jan Ming Ho and Yen Jen Oyang, "An Effective Approach to Video Staging in Streaming Applications," Proceedings of the IEEE Globe Communication Conference (GLOBECOM), 2002.
[62]Shin Hung Chang, Ray I Chang, Jan Ming Ho and Yen Jen Oyang, "OC: An Optimal Cache Algorithm for Video Staging," Proceedings of the IEEE International Conference on Networking (ICN), 2002.
[63]Shin Hung Chang, Ray I Chang, Jan Ming Ho and Yen Jen Oyang, “PSC: A Priority Selected Cache Algorithm for Streaming Video over Internet," Proceedings of the IEEE International Conference on Networks (ICON), 2003.
[64]Shin Hung Chang, Ray I Chang, Jan Ming Ho, and Yen Jen Oyang, "An Optimal Cache Algorithm for Streaming VBR Video over a Heterogeneous Network," Computer Communications, 2005.
[65]T. Ott, T. V. Lakshman and A. Tabatabai, "A Scheme for Smoothing Delay-Sensitive Traffic Offered to ATM networks," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 1992.
[66]T. C. Chiueh and R. H. Katz, "Multi-Resolution Video Representation for Parallel Disk Arrays," Proceedings of ACM Multimedia, 1993.
[67]T. Talley and K. Jeffay, "Two-Dimensional Scaling Technique for Adaptive Rate-Based Transmission," Proceedings of ACM Multimedia, 1994.
[68]T. V. Lakshman, A. Ortega, and A. R. Reibman, "Variable bit-rate (VBR) video: Tradeoffs and potentials," Proceedings of the IEEE Multimedia, May 1998.
[69]V. Paxson, "End-to-end Internet Packet Dynamics," Proceedings of ACM SIGCOMM, September 1997.
[70]W. B. Pennebarker and J. L. Mitchell, "JPEG Still Image Data Compression Standard," Van Nostrand Reinhold, 1992.
[71]W. Feng and S. Sechrest, "Smoothing and buffering for delivery of prerecorded compressed video," Computer Communications, October 1995.
[72]Wu Chi Feng and Jennifer Rexford, "A Comparison of Bandwidth Smoothing Techniques for the Transmission of Prerecorded Compressed Video," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 1997.
[73]W. Feng, F. Jahanian, and S. Sechrest, "An Optimal Bandwidth Allocation Strategy for the Delivery of Compressed Prerecorded Video," Springer-Verlag Multimedia Systems Journal, September, 1997.
[74]Wei Hsiu Ma and David H. C. Du, "Reducing Bandwidth Requirement for Delivering Video Over Wide Area Network With Proxy Server," Proceedings of the IEEE International Conference on Multimedia and Expo (ICME), 2000.
[75]You Ze Cho and Alberto Leon Garcia, "Performance of Burst-level Bandwidth reservation in ATM LANs," Proceedings of IEEE Conference on Computer Communications (INFOCOM), 1994.
[76]Y. N. Doganata and A. N. Tantawi, "Making a Cost-Effective Video Server," IEEE Multimedia, 1994.
[77]Zhourong Miao and Antonio Ortega, "Proxy Caching for Efficient Services over the Internet," Proceedings of the 9th International Packet Video Workshop, 1999.
[78]Zhi Li Zhang, Yuewei Wang, David H. C. Du and Dongli Su, "Video Staging: A Proxy Server Based Approach to End-to-End Video Delivery over Wide-Area-Networks," IEEE/ACM Transaction on Networking, 2000.
[79]http://www-info3.informatik.uni-wuerzburg.de/MPEG/traces/.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文