基于P2P点播系统的客户端缓存策略研究
|
摘要
如何能在保持系统整体性能的同时,有效地进行资源存储和定位,是P2P点播系统中所需要解决的重要问题。在P2P点播系统的服务器、代理服务器以及客户端中,缓存技术在缓解网络传输压力、平衡系统负载以及减少网络带宽消耗等方面扮演着重要角色,设计和选择适当的缓存策略可以改善系统性能。
本文研究重点是在基于有服务器结构对等网络环境的点播系统中,针对客户端缓存技术的研究还比较少的情况,提出了一种新的适合客户端的缓存替换策略。随后给出了该策略的模型,并对该模型进行了详细的阐述,分析了其优缺点。预测双缓存模型具有四个缓存队列,较传统点播系统多了三个缓存队列,其目的在于通过缓存更多有价值的媒体数据来提高缓存的命中率,进而提高系统的性能。然后对预测双缓存替换算法进行了研究,解决了缓存副本分布、缓存副本概率一致性以及阈值的选择等问题。接着又对缓存中数据调度问题进行了深入的讨论,给出了各个不同缓存的数据替换和调度算法,针对缓存调度以及VCR操作引起的数据调度分别给出了解决方案。
为了分析对比本文提出的预测双缓存模型与传统的点播系统中的缓存模型优缺点以及证明该模型的可行性和正确性,在分析了传统的仿真器的基础上,利用VC开发出了一个适合预测双缓存模型以及传统缓存模型的仿真器。文中先分析了仿真器的系统结构,对每个模块的实现给出了较为详细的描述,并对所需参数的设置进行了说明。最后使用该仿真器证明了本文提出的预测双缓存模型,能够在点播人数逐渐增多的同时,提高节目内部数据的点播概率,有效缩短VCR操作的时间,提高点播系统的服务质量。
How to actualize resource storage and location effectively while the systematic entirety is kept is an important problem that requires to be solved in peer to peer video on demand. In server, proxy server and client of peer to peer video to demand, cache technology plays an important role on aspects of relieving network transmission pressure, balancing overall load, and reducing network bandwidth consumption. Design and selection of caching strategies can improve system performance.
This paper focuses on the new cache replacement policy that is fit for client and is proposed towards the fact that few researches on client cache technology have been made and is based on the video on demand with server structure P2P network environment. Later, this paper proposes the model of this strategy, elaborates the model, and analyze its advantages and disadvantages. Double predictive caching model is composed of four cache queries, three more than the traditional video on demand, aiming at increasing hit ratio of cache through caching more valuable streaming data, and then promoting system performance. Then, this paper makes a research on double predictive caching replacement algorithm, which has solved the problems such as cached copy distribution, cached copy probabilistic consistency and selection of threshold. Then, this paper also makes a deep discussion on the problem of data scheduling in cache, puts forward the data substitutions and scheduling algorithms of different caches, and also proposes the solutions for the data scheduling resulted from cache scheduling and VCR operation.
In order to analyze and compare the advantages and disadvantages of double predictive caching model proposed in this paper and the model in traditional video on demand, and to prove the feasibility and correctness of this model, this paper develops a simulator which is fit for both double predictive caching model and traditional cache model by using of VC based on the analysis of traditional simulator. This paper analyses the system structure of simulator firstly, gives a detailed description of actualization of each module and also makes an explanation of setting up of required parameter. Finally, the use of the stimulator has proved that the double predictive caching model proposed in this paper is capable of increasing order probability of inner data, effectively shortening time of VCR operation and promoting QoS of video on demand when the number of people who order is increased gradually.
本文研究重点是在基于有服务器结构对等网络环境的点播系统中,针对客户端缓存技术的研究还比较少的情况,提出了一种新的适合客户端的缓存替换策略。随后给出了该策略的模型,并对该模型进行了详细的阐述,分析了其优缺点。预测双缓存模型具有四个缓存队列,较传统点播系统多了三个缓存队列,其目的在于通过缓存更多有价值的媒体数据来提高缓存的命中率,进而提高系统的性能。然后对预测双缓存替换算法进行了研究,解决了缓存副本分布、缓存副本概率一致性以及阈值的选择等问题。接着又对缓存中数据调度问题进行了深入的讨论,给出了各个不同缓存的数据替换和调度算法,针对缓存调度以及VCR操作引起的数据调度分别给出了解决方案。
为了分析对比本文提出的预测双缓存模型与传统的点播系统中的缓存模型优缺点以及证明该模型的可行性和正确性,在分析了传统的仿真器的基础上,利用VC开发出了一个适合预测双缓存模型以及传统缓存模型的仿真器。文中先分析了仿真器的系统结构,对每个模块的实现给出了较为详细的描述,并对所需参数的设置进行了说明。最后使用该仿真器证明了本文提出的预测双缓存模型,能够在点播人数逐渐增多的同时,提高节目内部数据的点播概率,有效缩短VCR操作的时间,提高点播系统的服务质量。
How to actualize resource storage and location effectively while the systematic entirety is kept is an important problem that requires to be solved in peer to peer video on demand. In server, proxy server and client of peer to peer video to demand, cache technology plays an important role on aspects of relieving network transmission pressure, balancing overall load, and reducing network bandwidth consumption. Design and selection of caching strategies can improve system performance.
This paper focuses on the new cache replacement policy that is fit for client and is proposed towards the fact that few researches on client cache technology have been made and is based on the video on demand with server structure P2P network environment. Later, this paper proposes the model of this strategy, elaborates the model, and analyze its advantages and disadvantages. Double predictive caching model is composed of four cache queries, three more than the traditional video on demand, aiming at increasing hit ratio of cache through caching more valuable streaming data, and then promoting system performance. Then, this paper makes a research on double predictive caching replacement algorithm, which has solved the problems such as cached copy distribution, cached copy probabilistic consistency and selection of threshold. Then, this paper also makes a deep discussion on the problem of data scheduling in cache, puts forward the data substitutions and scheduling algorithms of different caches, and also proposes the solutions for the data scheduling resulted from cache scheduling and VCR operation.
In order to analyze and compare the advantages and disadvantages of double predictive caching model proposed in this paper and the model in traditional video on demand, and to prove the feasibility and correctness of this model, this paper develops a simulator which is fit for both double predictive caching model and traditional cache model by using of VC based on the analysis of traditional simulator. This paper analyses the system structure of simulator firstly, gives a detailed description of actualization of each module and also makes an explanation of setting up of required parameter. Finally, the use of the stimulator has proved that the double predictive caching model proposed in this paper is capable of increasing order probability of inner data, effectively shortening time of VCR operation and promoting QoS of video on demand when the number of people who order is increased gradually.
引文
[1] FISHER D. Using Egocentric Networks to Understand Communication[J]. IEEE Internet Computing, 2005, 5(9): 20-28.
[2] BUSH R. FidoNet: Technology, Tools and History[J]. Communications of the ACM, 1993, 8(36): 31-35.
[3] MIURA K, etal. A Quorum-Based Protocol for Searching Objects in Peer-to-Peer Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 1(17): 25-37.
[4] DAVID P A, etal. SETI@home: an Experiment in Public-Resource Computing[J]. Communications of the ACM Archive, 2002, 11(45): 56-61.
[5]侯自强. P2P改变传媒世界-挑战,机遇和对策[C]. 2006中国宽频技术、业务与投资峰会,北京, 2006.
[6] GUO Y, etal. P2Cast: Peer-to-Peer Patching Scheme for VoD Service[C]. In Prm. WWW’03. Budapest. Hungary, 2003:301-309.
[7] SAROIU S, etal. Gribble. Measuring and Analyzing the Characteristics of Napster and Gnutella hosts[J]. Multimedia Systems Journal, 2003, 9(2):170-184.
[8] BURAGOHAIN C, etal. A game Theoretic Framework for Incentives in P2P systems[C]. In Proc. P2P, Sweden, 2003:48-56.
[9]谢珩,卢显良.基于Web的高性能瘦客户/服务器网络计算模式的实现[J].计算机应用研究, 2006,7:239-241.
[10] NOTTELMANN P, Fischer P. Search and Browse Services for Heterogeneous Collections with the Peer-to-Peer Network Pepper[C]. Information Processing and Management, 2007, 3(43): 624-642.
[11]陈大伟,张栋.混合P2P网络模型研究与设计[J].计算机与信息技术, 2006, 9:44-47.
[12] ROGERIO M, etal. A Polyharmonic Periodic Broadcasting Protocol for Clients with Bandwidth Limitation[C]. 2006 11th International Workshop on Computer-Aided Modeling, Analysis and Design of Communication Links and Networks, 2006: 54-58.
[13] TANCO L, etal. Pyramid Segmentation Algorithms Revisited[J]. Pattern Recognition, 2006, 8(39): 1430-1451.
[14] CYRIL B, etal. A New Sufficient Condition of Optimality for the Two-Machine Flowshop Problem[J]. European Journal of Operational Research, 2006, 3(169): 712-722.
[15]覃少华等.基于代理缓存的流媒体动态调度算法研究[J].计算机学报, 2005, 2(28):185-194.
[16] KWON J B, YEOM H Y. Adjustable Broadcast Protocol for Large-Scale Near Video on Demand Systems[C]. Computer Communications, 2005, 11(28): 1303-1316.
[17] SRDJAN P. Space-efficient FCFS Group Mutual Exclusion[J]. Information Processing Letters, 2005, 2(95): 343-350.
[18] RAI O H, Song H J. Scalable Proxy Caching Algorithm Minimizing Client's Buffer Size and Channel Bandwidth[J]. Journal of Visual Communication and Image Representation, 2006, 1(17):57-71.
[19] BATU S, Benjamin W. Speech and Network Adaptive Layered G. 729 Coder for Loss Concealments of Real-Time Voice Over IP[C]. Multimedia Signal Processing 2005 IEEE 7th Workshop on, 2005:1-4.
[20] HUI S C, Jack Y B. Playback-Adaptive Multi-Source Video Streaming[C]. Proc of the Fourth International Conference on Intelligent Multimedia Computing and Networking, 2005:819-822.
[21]向哲等.一种基于周期合并策略的流调度算法[J].软件学报, 2001, 8(12):1183-1189.
[22]单炜等.支持VCR功能的扩展流合并算法VCRSM的设计与实现[J].计算机科学, 2005, 3(32):88-94.
[23]胡银娥等.基于补丁算法的流媒体代理缓存的研究与实现[J]. 2007, 7(27):1817-1824.
[24] BASHAR Q, SARHAN N J. Towards Enhanced Resource Sharing in Video Streaming with Generalized Access Patterns[C]. Multimedia and Expo, 2007 IEEE International Conference on, 2007:1219-1222.
[25]覃少华等.流媒体点播的服务器通道调度方案综述[J].计算机科学, 2005, 1(32):101-105.
[26] CHI H C, ZHANG Q. Deadline-Aware Network Coding for Video on Demand Service Over P2P Networks[J]. Journal of Zhejiang University: Science, 2006, 5(7):755-763.
[27] GAO W, etal. Recent Advances in Peer-to-Peer Media Streaming Systems[J]. China Comminications, 2006, 5(13):52-57.
[28] JIN H, etal. Anysee: Multicast-Based Peer-to-Peer Media Streaming Service System[C]. 2005 Asia-Pacific Conference on Communications, 2005: 274-278.
[29] CHEN G, WU G X. A Client Peer Adjustment Policy for Peer to Peer Media Streaming[C]. Proceedings 2006 International Conference on Hybrid Information Technology, 2006,(1): 98-102.
[30] SASABE M, etal. Scalable and Continuous Media Streaming on Peer-to-Peer Networks[C]. Proceedings of P2P, 2003:92-99.
[31]金宏等.改进的最小空闲时间优先调度算法[J].软件学报, 2004, 8(15):1116-1123.
[32] ZHANG N, etal. Impact of Node Cheating on Gossip-Based Protocol[J]. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2006: 1068-1077.
[33] XIAO B, etal. A Gossip-Based Energy Conservation Protocol for Wireless Ad hoc and Sensor Networks[J]. Journal of Network and Systems Management, 2006, 3(14): 381-414.
[34] CSANAD I, VAN S R. More on Weighted Servers or FIFO is Better Than LRU[C]. Theoretical Computer Science, 2003, 1-3(306): 305-317.
[35] BOYAR J, etal. Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem[C]. WAOA , 2006: 95-107.
[36] LEONID B S. LFU-K:An Effective Buffer Management Replacement Algorithm[C]. DASFAA, 2004: 670-681.
[37] SMARAGDARKIS Y, etal. The EELRU Adaptive Replacement Algorithm[J]. Elsevier Science Performance Evaluation, 2003, 53(2): 93-123.
[38]田小波,陈蜀宇.基于最小效用的流媒体缓存替换算法[J].计算机应用, 2007, 3(27):733-736.
[39] CASTELLOTE M, ANDRADE C. Round-Robin Test on Methods for Determining Chloride Transport Parameters in Concrete[C]. Materials and Structures, 2006, 10(39): 955-990.
[40]马杰,樊建平. LittleDuck流媒体缓存模拟器[J].计算机工程, 2006, 14(32): 208-210.
[41]郑倩冰等.通用对等网络模拟器的设计与实现[J].计算机工程与科学, 2006,1(28):9-11.
[42] NYIK S T. A Generic Peer-to-Peer Network Simulator[R]. Proceedings of the 2002-2003 Grad Symposium, 2003:1-10.
[43]李旭峰等.通用P2P模拟器的构造技术研究[J].计算机应用研究, 2006, 5:16-18.
[44] JOSEPH S. NeuroGrid: Semantically Routing Queries in Peer-to-Peer Networks[C]. International Workshop on Peer-to-Peer Computing, 2002:78-90.
[45]赵枫等.基于DNS的防火墙渗透技术研究[J].信息安全与通信保密, 2006,2:47-49.
[46]谢红梅,王建东.一种匿名的E-Mail认证协议[J].信息安全与通信保密, 2006, 3:37-39.
[47] DETERS R, NYIK S T. Peer-to-peer Network Simulation[C]. ICEIS 2004 - Proceedings of the Sixth International Conference on Enterprise Information Systems, 2004, 84-91.
[48]霍英,施宜. NeuroGrid中Gnutella 0.6协议的扩展实现[J].微电子学与计算机, 2007, 6(24):126-129.
[49] LI R, etal. EMMP: A Highly Efficient Membership Management Protocol[J]. Frontiers of Computer Science in China, 2007, 2(1): 208-212.
[50] JáNOS I. Some Practical Aspects of Fitting and Testing the Zipf-Mandelbrot model[J]. Scientometrics, 2006, 1(67):107-120.
[2] BUSH R. FidoNet: Technology, Tools and History[J]. Communications of the ACM, 1993, 8(36): 31-35.
[3] MIURA K, etal. A Quorum-Based Protocol for Searching Objects in Peer-to-Peer Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 1(17): 25-37.
[4] DAVID P A, etal. SETI@home: an Experiment in Public-Resource Computing[J]. Communications of the ACM Archive, 2002, 11(45): 56-61.
[5]侯自强. P2P改变传媒世界-挑战,机遇和对策[C]. 2006中国宽频技术、业务与投资峰会,北京, 2006.
[6] GUO Y, etal. P2Cast: Peer-to-Peer Patching Scheme for VoD Service[C]. In Prm. WWW’03. Budapest. Hungary, 2003:301-309.
[7] SAROIU S, etal. Gribble. Measuring and Analyzing the Characteristics of Napster and Gnutella hosts[J]. Multimedia Systems Journal, 2003, 9(2):170-184.
[8] BURAGOHAIN C, etal. A game Theoretic Framework for Incentives in P2P systems[C]. In Proc. P2P, Sweden, 2003:48-56.
[9]谢珩,卢显良.基于Web的高性能瘦客户/服务器网络计算模式的实现[J].计算机应用研究, 2006,7:239-241.
[10] NOTTELMANN P, Fischer P. Search and Browse Services for Heterogeneous Collections with the Peer-to-Peer Network Pepper[C]. Information Processing and Management, 2007, 3(43): 624-642.
[11]陈大伟,张栋.混合P2P网络模型研究与设计[J].计算机与信息技术, 2006, 9:44-47.
[12] ROGERIO M, etal. A Polyharmonic Periodic Broadcasting Protocol for Clients with Bandwidth Limitation[C]. 2006 11th International Workshop on Computer-Aided Modeling, Analysis and Design of Communication Links and Networks, 2006: 54-58.
[13] TANCO L, etal. Pyramid Segmentation Algorithms Revisited[J]. Pattern Recognition, 2006, 8(39): 1430-1451.
[14] CYRIL B, etal. A New Sufficient Condition of Optimality for the Two-Machine Flowshop Problem[J]. European Journal of Operational Research, 2006, 3(169): 712-722.
[15]覃少华等.基于代理缓存的流媒体动态调度算法研究[J].计算机学报, 2005, 2(28):185-194.
[16] KWON J B, YEOM H Y. Adjustable Broadcast Protocol for Large-Scale Near Video on Demand Systems[C]. Computer Communications, 2005, 11(28): 1303-1316.
[17] SRDJAN P. Space-efficient FCFS Group Mutual Exclusion[J]. Information Processing Letters, 2005, 2(95): 343-350.
[18] RAI O H, Song H J. Scalable Proxy Caching Algorithm Minimizing Client's Buffer Size and Channel Bandwidth[J]. Journal of Visual Communication and Image Representation, 2006, 1(17):57-71.
[19] BATU S, Benjamin W. Speech and Network Adaptive Layered G. 729 Coder for Loss Concealments of Real-Time Voice Over IP[C]. Multimedia Signal Processing 2005 IEEE 7th Workshop on, 2005:1-4.
[20] HUI S C, Jack Y B. Playback-Adaptive Multi-Source Video Streaming[C]. Proc of the Fourth International Conference on Intelligent Multimedia Computing and Networking, 2005:819-822.
[21]向哲等.一种基于周期合并策略的流调度算法[J].软件学报, 2001, 8(12):1183-1189.
[22]单炜等.支持VCR功能的扩展流合并算法VCRSM的设计与实现[J].计算机科学, 2005, 3(32):88-94.
[23]胡银娥等.基于补丁算法的流媒体代理缓存的研究与实现[J]. 2007, 7(27):1817-1824.
[24] BASHAR Q, SARHAN N J. Towards Enhanced Resource Sharing in Video Streaming with Generalized Access Patterns[C]. Multimedia and Expo, 2007 IEEE International Conference on, 2007:1219-1222.
[25]覃少华等.流媒体点播的服务器通道调度方案综述[J].计算机科学, 2005, 1(32):101-105.
[26] CHI H C, ZHANG Q. Deadline-Aware Network Coding for Video on Demand Service Over P2P Networks[J]. Journal of Zhejiang University: Science, 2006, 5(7):755-763.
[27] GAO W, etal. Recent Advances in Peer-to-Peer Media Streaming Systems[J]. China Comminications, 2006, 5(13):52-57.
[28] JIN H, etal. Anysee: Multicast-Based Peer-to-Peer Media Streaming Service System[C]. 2005 Asia-Pacific Conference on Communications, 2005: 274-278.
[29] CHEN G, WU G X. A Client Peer Adjustment Policy for Peer to Peer Media Streaming[C]. Proceedings 2006 International Conference on Hybrid Information Technology, 2006,(1): 98-102.
[30] SASABE M, etal. Scalable and Continuous Media Streaming on Peer-to-Peer Networks[C]. Proceedings of P2P, 2003:92-99.
[31]金宏等.改进的最小空闲时间优先调度算法[J].软件学报, 2004, 8(15):1116-1123.
[32] ZHANG N, etal. Impact of Node Cheating on Gossip-Based Protocol[J]. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2006: 1068-1077.
[33] XIAO B, etal. A Gossip-Based Energy Conservation Protocol for Wireless Ad hoc and Sensor Networks[J]. Journal of Network and Systems Management, 2006, 3(14): 381-414.
[34] CSANAD I, VAN S R. More on Weighted Servers or FIFO is Better Than LRU[C]. Theoretical Computer Science, 2003, 1-3(306): 305-317.
[35] BOYAR J, etal. Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem[C]. WAOA , 2006: 95-107.
[36] LEONID B S. LFU-K:An Effective Buffer Management Replacement Algorithm[C]. DASFAA, 2004: 670-681.
[37] SMARAGDARKIS Y, etal. The EELRU Adaptive Replacement Algorithm[J]. Elsevier Science Performance Evaluation, 2003, 53(2): 93-123.
[38]田小波,陈蜀宇.基于最小效用的流媒体缓存替换算法[J].计算机应用, 2007, 3(27):733-736.
[39] CASTELLOTE M, ANDRADE C. Round-Robin Test on Methods for Determining Chloride Transport Parameters in Concrete[C]. Materials and Structures, 2006, 10(39): 955-990.
[40]马杰,樊建平. LittleDuck流媒体缓存模拟器[J].计算机工程, 2006, 14(32): 208-210.
[41]郑倩冰等.通用对等网络模拟器的设计与实现[J].计算机工程与科学, 2006,1(28):9-11.
[42] NYIK S T. A Generic Peer-to-Peer Network Simulator[R]. Proceedings of the 2002-2003 Grad Symposium, 2003:1-10.
[43]李旭峰等.通用P2P模拟器的构造技术研究[J].计算机应用研究, 2006, 5:16-18.
[44] JOSEPH S. NeuroGrid: Semantically Routing Queries in Peer-to-Peer Networks[C]. International Workshop on Peer-to-Peer Computing, 2002:78-90.
[45]赵枫等.基于DNS的防火墙渗透技术研究[J].信息安全与通信保密, 2006,2:47-49.
[46]谢红梅,王建东.一种匿名的E-Mail认证协议[J].信息安全与通信保密, 2006, 3:37-39.
[47] DETERS R, NYIK S T. Peer-to-peer Network Simulation[C]. ICEIS 2004 - Proceedings of the Sixth International Conference on Enterprise Information Systems, 2004, 84-91.
[48]霍英,施宜. NeuroGrid中Gnutella 0.6协议的扩展实现[J].微电子学与计算机, 2007, 6(24):126-129.
[49] LI R, etal. EMMP: A Highly Efficient Membership Management Protocol[J]. Frontiers of Computer Science in China, 2007, 2(1): 208-212.
[50] JáNOS I. Some Practical Aspects of Fitting and Testing the Zipf-Mandelbrot model[J]. Scientometrics, 2006, 1(67):107-120.