基于补丁算法的流媒体代理缓存的高效方法研究
摘要
随着Internet技术的不断发展和广泛应用,网络中流媒体数据越来越多。流媒体的实时性、宽带性的特点使得Internet资源不能满足要求,网络资源的紧张和流媒体广泛应用之间的矛盾日益严重,因此节约网络资源保证流媒体应用成为迫切需要解决的课题。
本文对流媒体代理缓存和流调度技术进行了分析和研究。处于网络边缘的流媒体代理服务器缓存并转发流媒体数据,它不仅可以加快用户访问请求的响应速度,减轻流媒体服务器的负载,而且还能有效的节省从原始服务器到代理服务器之间的骨干网络带宽。研究表明流媒体调度技术中的补丁算法是有效的、能够提供即时服务的动态调度方法。
因此本文结合代理缓存和补丁算法的优点,提出了一种基于补丁算法的流媒体代理缓存的高效方法。它的基本思想是:在一个常规流启动周期T内,代理服务器为用户请求转发数据,并且分块缓存这些数据,当后继用户的请求落后于常规流播放时,该用户可以直接加入常规流通道,同时用代理缓存中的数据补偿该用户错过的数据。该方法由于设有代理服务器,不需要在原始服务器到代理服务器开启补丁通道来传输补丁流,只需要代理服务器转发缓存的数据作为后继用户的补丁数据。经过分析和实验研究表明,该方法能进一步降低骨干网络带宽资源和原始服务器的磁盘I/O资源,以及加快用户访问请求的响应速度。
Since the concept of streaming media has been introduced in recentyears,it has experienced a dramatic growth. Streaming media has turn froma novel technology into one of the mainstream manners in which peopleexperience the Internet service such as VOD, network TV, distanceeducation ,vedio conference and network amusement. Users can play backsome parts of a streaming media, which is being downloaded. However,due to the high bandwidth requirements and the long-live nature of video,server and network bandwidths are proved to be major limiting resource inthe widespread usage of steaming media over the internet. The conflictsbetween limited internet's resources and wide application of streaming mediaare more serious, So it become a popular question in the streaming mediaarea that how to improve the delivery quality.
In order to solve the problem, The researchers have put forward lots oftechniques to improve the delivery quality of the streaming media. Such asthe prefix catching, dynamic catching in the proxy caching, the Patching andBatch Patching in the delivery are the most efficient techniques.
This paper introduce the streaming media proxy caching and thepatching algorithm firstly, then we propose an efficient method of streamingmedia proxy caching based on patching algorithm. Lastly ,we design andimplement this method.
The.proxy caching of streaming media is brought forward because thebottleneck resource is in short supply,The bottleneck often exit on the remoteserver and the backbone network. For example, the most providers, thejam-up because of the lacking of backbone network's bandwidth.The
streaming media proxy server can resolve the above questions partially. Theproxy cache can decrease the network bandwidth, depress the network flux,reduce the network delay and alleviate the pressure of the server. At the sametime, it can promised the quality of server.Batching scheduling technology divide the time that the proxy serve toclient into lots of interval .In order to use the multicast priority and save thenetwork bindwidth,the proxy will give multicast delivery to the clients whoreach the proxy at the interval and will have only one regular channel at eachinternal .In the real system designing process, we want to fulfill maximumservice capability using the limited resourse. But the batching scheduling hasthe defect that it will have sometime start-up delay for some clients becauseit have lots of clients sharing a multicast streaming . So someone proposethe patching algorithm base on the batching schduling. The client will join inthe regular channel if he miss some media data, then he can get the data fromthe patching channel. The method will remove the start-up delay .We can find that the streaming media proxy caching and patchingalgorithm are two main methods to improve the delivery quality by theanalysis and research. So we apply the patching method in the streamingmedia server to streaming meidia proxy caching, and propose an efficientmethod of streaming media proxy caching based on patching algorithm. Ourmethod is as fellows:we can give a regular streaming start-up period ,theproxy server can get streaming media data from the original server by unicastin this period,the time of the proxy serving to the client can divide into lots ofinterval, the client can join into the regular channel at the batching interval,when the proxy transmit the data for the one interval clients, it will also cachethe dada for the latter client. When the latter client miss some data, the proxy
can compensate the missing data using the caching data. In a regularstreaming period ,we can only start-up one regular channel ,we can meet lotsof batching clients. The method combines the proxy caching with patchingalgorithm, and we needn't start the patching channel between the orginalserver and the proxy server. From the analysis, we can find the method canreduce significantly the consumption of aggregate bandwidth on backbonenetwork bindwidth.At last, based on the above method we design and implement astreaming media proxy caching program,divide the trasmitting media into thesame size block and cache them in the proxy .In this program ,we create thecaching mapping node to manage the data in the disk.When a new client askfor the data,the proxy caching judges the client's state.Then the proxy cachingtransmits the regular data and the patching data by multicast at the batchinginterval.We make use of RTSP protocol as the stream service protocol. RTSPis an application-level protocol for control over the delivery of data withreal-time properties. It provides VRC functions, such as play, pause, playbacketc. we can setup RTSP proxy of the client's player to carry out the datadelivery. The transition of stream data is not confined on network protocol, itcan use either RTP (UDP)/RTCP (UDP);lastly ,the data can transmit to theclient from the remote server by the proxy cachingWe believe that the method proposed in this paper have some referencemerit.
本文对流媒体代理缓存和流调度技术进行了分析和研究。处于网络边缘的流媒体代理服务器缓存并转发流媒体数据,它不仅可以加快用户访问请求的响应速度,减轻流媒体服务器的负载,而且还能有效的节省从原始服务器到代理服务器之间的骨干网络带宽。研究表明流媒体调度技术中的补丁算法是有效的、能够提供即时服务的动态调度方法。
因此本文结合代理缓存和补丁算法的优点,提出了一种基于补丁算法的流媒体代理缓存的高效方法。它的基本思想是:在一个常规流启动周期T内,代理服务器为用户请求转发数据,并且分块缓存这些数据,当后继用户的请求落后于常规流播放时,该用户可以直接加入常规流通道,同时用代理缓存中的数据补偿该用户错过的数据。该方法由于设有代理服务器,不需要在原始服务器到代理服务器开启补丁通道来传输补丁流,只需要代理服务器转发缓存的数据作为后继用户的补丁数据。经过分析和实验研究表明,该方法能进一步降低骨干网络带宽资源和原始服务器的磁盘I/O资源,以及加快用户访问请求的响应速度。
Since the concept of streaming media has been introduced in recentyears,it has experienced a dramatic growth. Streaming media has turn froma novel technology into one of the mainstream manners in which peopleexperience the Internet service such as VOD, network TV, distanceeducation ,vedio conference and network amusement. Users can play backsome parts of a streaming media, which is being downloaded. However,due to the high bandwidth requirements and the long-live nature of video,server and network bandwidths are proved to be major limiting resource inthe widespread usage of steaming media over the internet. The conflictsbetween limited internet's resources and wide application of streaming mediaare more serious, So it become a popular question in the streaming mediaarea that how to improve the delivery quality.
In order to solve the problem, The researchers have put forward lots oftechniques to improve the delivery quality of the streaming media. Such asthe prefix catching, dynamic catching in the proxy caching, the Patching andBatch Patching in the delivery are the most efficient techniques.
This paper introduce the streaming media proxy caching and thepatching algorithm firstly, then we propose an efficient method of streamingmedia proxy caching based on patching algorithm. Lastly ,we design andimplement this method.
The.proxy caching of streaming media is brought forward because thebottleneck resource is in short supply,The bottleneck often exit on the remoteserver and the backbone network. For example, the most providers, thejam-up because of the lacking of backbone network's bandwidth.The
streaming media proxy server can resolve the above questions partially. Theproxy cache can decrease the network bandwidth, depress the network flux,reduce the network delay and alleviate the pressure of the server. At the sametime, it can promised the quality of server.Batching scheduling technology divide the time that the proxy serve toclient into lots of interval .In order to use the multicast priority and save thenetwork bindwidth,the proxy will give multicast delivery to the clients whoreach the proxy at the interval and will have only one regular channel at eachinternal .In the real system designing process, we want to fulfill maximumservice capability using the limited resourse. But the batching scheduling hasthe defect that it will have sometime start-up delay for some clients becauseit have lots of clients sharing a multicast streaming . So someone proposethe patching algorithm base on the batching schduling. The client will join inthe regular channel if he miss some media data, then he can get the data fromthe patching channel. The method will remove the start-up delay .We can find that the streaming media proxy caching and patchingalgorithm are two main methods to improve the delivery quality by theanalysis and research. So we apply the patching method in the streamingmedia server to streaming meidia proxy caching, and propose an efficientmethod of streaming media proxy caching based on patching algorithm. Ourmethod is as fellows:we can give a regular streaming start-up period ,theproxy server can get streaming media data from the original server by unicastin this period,the time of the proxy serving to the client can divide into lots ofinterval, the client can join into the regular channel at the batching interval,when the proxy transmit the data for the one interval clients, it will also cachethe dada for the latter client. When the latter client miss some data, the proxy
can compensate the missing data using the caching data. In a regularstreaming period ,we can only start-up one regular channel ,we can meet lotsof batching clients. The method combines the proxy caching with patchingalgorithm, and we needn't start the patching channel between the orginalserver and the proxy server. From the analysis, we can find the method canreduce significantly the consumption of aggregate bandwidth on backbonenetwork bindwidth.At last, based on the above method we design and implement astreaming media proxy caching program,divide the trasmitting media into thesame size block and cache them in the proxy .In this program ,we create thecaching mapping node to manage the data in the disk.When a new client askfor the data,the proxy caching judges the client's state.Then the proxy cachingtransmits the regular data and the patching data by multicast at the batchinginterval.We make use of RTSP protocol as the stream service protocol. RTSPis an application-level protocol for control over the delivery of data withreal-time properties. It provides VRC functions, such as play, pause, playbacketc. we can setup RTSP proxy of the client's player to carry out the datadelivery. The transition of stream data is not confined on network protocol, itcan use either RTP (UDP)/RTCP (UDP);lastly ,the data can transmit to theclient from the remote server by the proxy cachingWe believe that the method proposed in this paper have some referencemerit.
引文
1. S.Sen, J.Rexford, and D.Towsley, “Proxy prefix caching for multimedia streams,” in Proc. IEEE INFOCOM, April 1999.
2. S.Sen, D.Towsley, Z.-L.Zhang, and J.Dey, “Optimal multicast smoothing of streaming video over an internetwork” in Proc. IEEE INFOCOM, A pril 1999.
3. K.L.Wu and P.S.Yu, “Segment-Based Proxy Caching of Multimedia Streams” In Proc. of IEEE INFOCOM ,May, 2001.
4. C. Aggarwal, J. Wolf, and P. Yu, “On optimal batching policies for video-on-demand storage servers,” in Proc. IEEE International Conference on Multimedia Computing and Systems, June 1996.
5. A. Dan, D. Sitaram, , and P. Shahabuddin. Scheduling policies for an on-demand video server with batching. In Proc. of ACM Multimedia, pages 15-23, San Francisco, California, October 1994.
6. Y.Cai, K.Hua and K.Vu, “Optimizing Patching Performance.” In Proceedings of ACM/SPIE Multimedia Computing and Networking, Jan 1999.
7. Zhiwen Xu, Xiaoxin Guo , Zhengxuan Wang, Yunjie Pang;“The Dynamic Cache-Multicast Method for Streaming Media.” In proceeding of 3rd European Conference on Universal Multiservice Networks, ECUMN 2004, Porto, Portugal, October 25-27, 2004.
8. Zhiwen Xu, Xiaoxin Guo, Yunjie Pang, Zhengxuan Wang;“The patched algorithm of dynamic cache for streaming media,” in Proc.of IEEE 2004 International Conference on Communications, Circuits and System, Chengdu, China June 2004, pp558-5 (IEEE Catelog Number: 04EX914, ISBN: 0-7803-8647-7)
9. 钟玉琢、向哲、沈洪,“流媒体和视频服务器”清华大学出版社 2003 年 6 月 (ISBN 7-302-06580-2/TP.4930)。
10. D.Hoffman, G.Fernando, V.Goyal, and M. R.Civanlar, “RTP payload format for MPEG1/MPEG2 video.” IETF RFC 2250,January 1998
11. .H. Schulzrinne, A. Rao, and R. Lanphier, “Real Time Streaming Protocol (RTSP).” IETF RFC 2326, April 1998.
12. http://www.liumeiti.org (流媒体知识网站)
13. S E D eering,D Estrin,D Farinacci.An Architecture for Wide-area Multicast Routing[C].In ACMSIGCOMM1994.1994-8.126135.
14. W.Feng and J.Rexford, “Performance evaluation of smoothing algorithms for transmitting prerecorded variability-bit-rate video,” IEEE Transaction on Multimedia, pp.302-313, 1999 September.
15. 庄伟强,集群服务器代理缓存技术研究,博士学位论文,清华大学研究生院, 1999
16. R. Tewari, H. Vin, A. Dan, and D. Sitaram. Resource-Based Caching for Web Servers. In Proceeding of SPIE/ACM Conference on Multimedia Computing, January 1998.
17. D. Eager, M. Vernon, and J. Zahorjan, “Optimal and efficient merging schedules for video-on-demand servers,” in Proc.ACM Multimedia, November 1999.
18. Paul P.White,Jon Crowcroft.”Optimised Batch Patching with Classes of Service.” ACM Cpmputer communication Review (2000), Vol 30 no .4.
19. White PP, Crowcroft J. Optimized batch patching with classes of sevice . ACM Commum. Rev . , 2002 , 6(4).
20. Wendy Boggs,Michael Boggs,Mastering UML with Rational Rose 2002, SYBEX,2002-7
21. 严蔚敏,吴伟民,数据结构,清华大学出版社[M],1997
22. 陈兵、王立松:“基于哈西表和时间连表的 HTTP 代理缓存机制的实现” 南京航空航天大学学报 2002 年 2 月 第 34 卷第 1 期:50-54
23. [美]Anthony Jones Windows 网络编程(第 2 版)杨合庆译 清华大学出版社 2002.10
24. http://www.rfc-editor.org/(RFC 知识网站)
25. http://www.ietf.org(流媒体知识网站)
26. Almedia J ,Krueger D ,Vernon M. Analysis of educational media server workloads.In:Proceedings of ACM NOSSDAV, PortJefferson ,NY,2001,21-30
27. Acharya S ,Smith B ,Parnes P Characterizing user access to vedios on the world wide web .In: Proceedings of SPIE/ACM MMCN ,San Jose ,CA,2000,130-141
2. S.Sen, D.Towsley, Z.-L.Zhang, and J.Dey, “Optimal multicast smoothing of streaming video over an internetwork” in Proc. IEEE INFOCOM, A pril 1999.
3. K.L.Wu and P.S.Yu, “Segment-Based Proxy Caching of Multimedia Streams” In Proc. of IEEE INFOCOM ,May, 2001.
4. C. Aggarwal, J. Wolf, and P. Yu, “On optimal batching policies for video-on-demand storage servers,” in Proc. IEEE International Conference on Multimedia Computing and Systems, June 1996.
5. A. Dan, D. Sitaram, , and P. Shahabuddin. Scheduling policies for an on-demand video server with batching. In Proc. of ACM Multimedia, pages 15-23, San Francisco, California, October 1994.
6. Y.Cai, K.Hua and K.Vu, “Optimizing Patching Performance.” In Proceedings of ACM/SPIE Multimedia Computing and Networking, Jan 1999.
7. Zhiwen Xu, Xiaoxin Guo , Zhengxuan Wang, Yunjie Pang;“The Dynamic Cache-Multicast Method for Streaming Media.” In proceeding of 3rd European Conference on Universal Multiservice Networks, ECUMN 2004, Porto, Portugal, October 25-27, 2004.
8. Zhiwen Xu, Xiaoxin Guo, Yunjie Pang, Zhengxuan Wang;“The patched algorithm of dynamic cache for streaming media,” in Proc.of IEEE 2004 International Conference on Communications, Circuits and System, Chengdu, China June 2004, pp558-5 (IEEE Catelog Number: 04EX914, ISBN: 0-7803-8647-7)
9. 钟玉琢、向哲、沈洪,“流媒体和视频服务器”清华大学出版社 2003 年 6 月 (ISBN 7-302-06580-2/TP.4930)。
10. D.Hoffman, G.Fernando, V.Goyal, and M. R.Civanlar, “RTP payload format for MPEG1/MPEG2 video.” IETF RFC 2250,January 1998
11. .H. Schulzrinne, A. Rao, and R. Lanphier, “Real Time Streaming Protocol (RTSP).” IETF RFC 2326, April 1998.
12. http://www.liumeiti.org (流媒体知识网站)
13. S E D eering,D Estrin,D Farinacci.An Architecture for Wide-area Multicast Routing[C].In ACMSIGCOMM1994.1994-8.126135.
14. W.Feng and J.Rexford, “Performance evaluation of smoothing algorithms for transmitting prerecorded variability-bit-rate video,” IEEE Transaction on Multimedia, pp.302-313, 1999 September.
15. 庄伟强,集群服务器代理缓存技术研究,博士学位论文,清华大学研究生院, 1999
16. R. Tewari, H. Vin, A. Dan, and D. Sitaram. Resource-Based Caching for Web Servers. In Proceeding of SPIE/ACM Conference on Multimedia Computing, January 1998.
17. D. Eager, M. Vernon, and J. Zahorjan, “Optimal and efficient merging schedules for video-on-demand servers,” in Proc.ACM Multimedia, November 1999.
18. Paul P.White,Jon Crowcroft.”Optimised Batch Patching with Classes of Service.” ACM Cpmputer communication Review (2000), Vol 30 no .4.
19. White PP, Crowcroft J. Optimized batch patching with classes of sevice . ACM Commum. Rev . , 2002 , 6(4).
20. Wendy Boggs,Michael Boggs,Mastering UML with Rational Rose 2002, SYBEX,2002-7
21. 严蔚敏,吴伟民,数据结构,清华大学出版社[M],1997
22. 陈兵、王立松:“基于哈西表和时间连表的 HTTP 代理缓存机制的实现” 南京航空航天大学学报 2002 年 2 月 第 34 卷第 1 期:50-54
23. [美]Anthony Jones Windows 网络编程(第 2 版)杨合庆译 清华大学出版社 2002.10
24. http://www.rfc-editor.org/(RFC 知识网站)
25. http://www.ietf.org(流媒体知识网站)
26. Almedia J ,Krueger D ,Vernon M. Analysis of educational media server workloads.In:Proceedings of ACM NOSSDAV, PortJefferson ,NY,2001,21-30
27. Acharya S ,Smith B ,Parnes P Characterizing user access to vedios on the world wide web .In: Proceedings of SPIE/ACM MMCN ,San Jose ,CA,2000,130-141