用户名: 密码: 验证码:
P2P网络的动力学建模与算法研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
随着信息技术的飞速发展,各种新颖的基于计算机网络的应用层出不穷,P2P网络就是其中典型的代表。虽然以往的研究也提出了许多P2P网络模型和关键技术,但对P2P网络动力学建模方面的研究却为数不多。同时,在P2P网络的应用领域目前存在着大量的问题,而其中很多问题可以在现有的应用支撑环境下采用现代控制理论和系统分析的方法获得解决。本论文旨在面向P2P网络这样一个应用广泛的对象,研究其动力学建模和一些关键算法,以便为实际网络系统的应用提供有效的解决方案和指导性建议。
     本文的主要工作和创新性表现在以下几个方面:
     1.研究了P2P文件共享系统的动力学建模和一些关键算法。我们以节点之间待传输的数据量作为系统的状态,提出了一种用确定性微分方程组来描述系统状态变化的动力学模型。该模型不仅考虑了影响节点数据传输速率的网络带宽,拷贝份数,存储空间,还考虑了P2P网络中节点选择算法,带宽分配算法,激励算法等因素。通过分析P2P文件共享系统中的算法对节点状态的影响,我们导出了方程的具体形式。实验结果表明该模型能够反映P2P文件共享系统的本质特征,从而为设计高性能P2P网络,改进现有算法,以及研究P2P网络的稳定性提供了理论基础。
     2.运用经济学中的市场机制原理,为P2P网络建立了一种基于动态价格的激励模型(Dynamic price-based incentive model, DPIM),有效地提高了P2P网络的可用性。在此模型基础之上,我们主要研究了其中的激励算法。仿真和分析结果表明,此种供求关系决定带宽价格的激励模型可以充分利用市场自主调节的功能,促使节点增加上传带宽和共享资源,避免了搭便车行为,提高了系统效率,打击了作弊行为。
     3.研究了媒体分发网络MDN(Media Delivery Network)系统中对等节点PN(Peer Node)的关键算法。在P2P文件共享系统的动力学模型基础上,定义了MDN的系统状态,并为MDN系统建立了动力学模型。该模型考虑了PN上传速率,PN存储空间大小,PN节点的部署算法,节点选择算法,带宽分配算法等因素对状态的影响。为了提高MDN系统的服务性能,我们还提出了基于状态的改进算法。仿真结果表明,所建立的模型能够准确反映MDN系统的本质特征,为系统的性能优化提供了一种方法。
With the development of information technology, many novel applications of computer networks have appeared. P2P is one of the most important applications. Although there were many models for P2P networks, few have addressed the model of dynamic behaviors. Meanwhile, P2P networks have a lot of problems, but modern control theory and system analysis methods provide a new perspective in solving these problems under existed application support environment. To this end, we study the dynamical modeling for P2P networks and some key algorithms. Then, we provide effective solutions and some advances for actual P2P networks.
     The main works and innovation are as follows:
     1. We propose a dynamical model for P2P file sharing systems and study some key algorithms. States of peers are defined as the amount of data which will be transmitted. We formulate a set of deterministic differential equations to describe the evolution of systems states by taking network physical characteristics (the physical upload, download bandwidth, storage space, etc) and software protocols (bandwidth allocation algorithm, peer selection algorithm, peer incentive mechanism, etc) into consideration. Then according to particular algorithms, we give the corresponding concrete models. Experiments show that the proposed model can adapt to different P2P file sharing systems. Therefore it provides a theoretical basis for designing high-performance P2P networks, improving existing P2P algorithms and researching stability of the P2P systems.
     2. We study the market mechanisms of economic principles and utilize it to model P2P file sharing systems. We name it as dynamic price-based incentive model (DPIM). Then, we study the incentive algorithm of DPIM. The results of simulation and analysis indicate the model can reduce free riding in P2P networks, punish cheating behaviors, and enhance file sharing efficiency and service quality.
     3. We study some key algorithms in the P2P-based Media Delivery Network (MDN). Based on the dynamical model of P2P, we define the states for the MDN and provide a novel dynamic model to character the behaviors of MDN systems. PN upload bandwidth, storage space, storage allocation algorithm, bandwidth allocation algorithm and PN selection algorithm are considered in the model. In order to improve the performance, some state-based algorithms are proposed. The results of simulation show that the model captures the characteristics of MDN in a more accurate way and provides a method for dynamic optimization of the system.
引文
陈贵海,李振华.2007.对等网络:结构、应用与设计[M].北京:清华大学出版社.
    方阳.2008.媒体分发网络中的对等节点的设计与实现[D]:硕士.合肥:中国科学技术大学.
    郭春茂.2007.P2P媒体分发网络实时数据分发调度算法[D]:硕士.合肥:中国科学技术大学.
    郭东,郑烇,殷保群,王嵩.2008.基于P2P媒体内容分发网络中分布式节点的设计和实现[J].电信科学,24(8):45-49.
    高鸿业.2007.西方经济学:微观部分[M].北京:中国人民大学出版社.
    李靖.2009.流媒体服务系统接入控制与缓存策略的研究[D]:博士.合肥:中国科学技术大学.
    孔柏汉.2008.基于P2P的可运营媒体内容分发网络的设计与实现[J].电信科学,24(8):33-37.
    芦珊.2010.基于P2P的媒体分发网络接入控制研究[D]:硕士.合肥:中国科学技术大学.
    邵祖华.2001.美国的个人信用制度及其启示[J].中国信用卡,1:38-43.
    王颖,顾铁成,张阳,陆桑璐,谢立.2005.一种基于分布式异构服务器机群VOD系统的数据分布算法[J].小型微型计算机系统,26(9):1611-1616.
    万健,郑若艇,徐向华.2007.P2P网络中激励机制研究[J].计算机应用,27(9):2202-2205.
    徐锦.2008.P2P媒体分发网络分发存储策略研究[D]:硕士.合肥:中国科学技术大学.
    余一娇,金海.2008.对等网络中的搭便车行为分析与抑制机制综述[J].计算机学报,31(1):1-15.
    路卫娜,杨寿保,郭磊涛.2008.P2P流媒体系统中积分检测相结合的激励机制.中国科学院研究生院学报,25(1):61-78.
    钟玉琢,向哲,沈洪.2003.流媒体和视频服务器[M].北京:清华大学出版社.
    张增斌,陈阳,邓北星等.2007.基于邻近原则的BitTorrent实验研究[J].厦门大学学报,46:213-215,
    Ben Strulo, AlanSmith, Jeff Farr.2003. An Architecture for Peer-to-Peer Economies[C], Proceedings of the 3rd International Conference on Peer-to-Peer Computing, September: 208-215.
    Bartolini N, Presti F L, Petrioli C.2003. Optimal dynamic replica placement in content delivery networks [C]. Proc. Of IEEE Int. Conf. on Networking, Sydney, Australia:125-130.
    Biersack E W, Carra D, Cigno R L, et al.2007. Overlay architectures for file distribution: Fundamental performance analysis for homogeneous and heterogeneous cases. Computer Networks:901-917.
    Chan C, Su T, Huang S, et al.2002. Cooperative proxy scheme for large-scale VoD systems[C]:404-409.
    Chan C L, Huang S Y, Wang J S.2007. Performance Analysis of Proxy Caching for VOD Services With Heterogeneous Clients[J]. IEEE Transactions on Communications,55(11): 2142-2151.
    Deshpande, Hrishikesh, Bawa, et al.2008. Streaming Live Media over Peers (latest version) [Online]. Available:http://infolab.stanford.edu/peers/(URL).
    Eytan A, Bernardo A H.2000. Free riding on gnutella[J]. First Monday,5(10):42-68.
    Flup E W, Of M, Reininger Daniel, et al.1998. Paying for Qos:An Optimal Distributed Algorithm for Pricing Network Resources[C]. Proceedings of the IEEE Sixth International Workshop on Quality of Service:75-84.
    Flup E W.1999. Resource Allocation and Pricing for QoS Management in Computer Networks[D]. PhD. Thesis, North Carolina State University.
    Fudenberg D, Tirole J.1991. Game Theory[M]. MIT press, Cambridge MR.
    Ge Z, Figueiredo D R, Jaiswal S, et al.2003. Modeling Peer-Peer File Sharing Systems[C]. In Proc. Of Joint Conf. of the IEEE Computer and Communic ations(INFOCOM 03): 2188-2198.
    Guo L, Chen S Q, Xiao Z, et al.2007. A Performance Study of BitTorrent-like Peer-to-Peer Systems[J]. In IEEE Journal on Selected Areas in Communications (JSAC 07),25:155-169.
    Gaeta R, Gribaudo M, Manini D, et al.2006. Analysis of Resource Transfers in Peer-to-Peer File Sharing Applications using Fluid Models[J]. Performance Evaluation.63(3):149-174.
    Gupta R, Somani A K.2004.Pricing strategy for incentive selfish nodes to share resources in Peer-to-Peer(P2P) networks[C]. Proceedings of the 12th IEEE International Conference on Networks, Singapore:624-629.
    Gummadi P K, Saroiu S, Gribble S D.2002. A Measurement Study of Peer-to-Peer File Sharing Systems[J]. In Proc. MMCN, San Jose, CA, USA, Jan:270-284.
    Huang J, Yin B Q, Guo D, et al.2010. An Evolution Model for P2P File-Sharing Networks[C]. ICCMS, Second International Conference on Computer Modeling and Simulation,2: 361-365.
    Hausheer D, Liebau N C, Mauthe A, Steinmetz R, Stiller B.2003. Token-Based accounting and distributed pricing to introduce market mechanisms in a peer-to-peer file sharing scenario[C]. In:Proc. of the 3rd Int'l onf. on Peer-to-Peer Computing,3:200-201.
    Izal M, Keller G U, Biersack E, et al.2004. Dissecting BitTorrent:Five Months in a Torrent's Lifetime[C]. In Proc. of Passive & Active Measurement Workshop, Apr.3015,1-11.
    Jiang Q, Xi H S, Yin B Q.2009. Dynamic File Grouping for Load Balancing in Streaming Media Clustered Server Systems[J], International Journal of Control, Automation, and Systems,7(4):630-637.
    Jonathan S K, Victor O K, Lui K S.2005. Scheduling Algorithms for Peer-to-Peer Collaborative File Distribution[C]. In Proc. on Collaborative Computing:Networking, Applications and Worksharing:210-220.
    Kangasharju, Jussi A T.2002. Internet Content Distribution. PhD thesis(D).
    Kumar R, Liu Y, Ross K.2007. Stochastic Fluid Theory for P2P Streaming Systems[C]. In IEEE INFOCOM, Anchorage, Alaska, USA, May:113-121.
    Kant K.2003. An Analytic Model for Peer to Peer File Sharing Networks [C]. InProc. International Communications Conference, Anchorage, AL, USA, May:801-805.
    Krit Wongrujira, Aruna Seneviratne.2005. Monetary incentive with reputation for virtual market-place based P2P[C]. Proceedings of the 2005 ACM conference on Emerging network experiment and technology.Toulouse.France.Oct:135-145.
    Lazar I, Terrill W.2001. Exploring content delivery networking[J]. IT Professional,3(4): 47-49.
    Lai K, Feldman, Stoica M, et al.2003. Incentives for cooperation in peer-to-peer networks[C]. In Proceedings of the Workshop on Economics of Peer-to-Peer Systems. Berkeley, CA: 205-211.
    Liu Hongtao, Bai Yun, Qiu Yuhui.2007. An Incentive Mechanism for Peer-to-Peer File Sharing[J]. Fuzzy Information and Engineering(ICFIE), ASC 40:442-447.
    Li Jun, Zhang Shunyi.2006. Modeling and Analyzing Peer-to-Peer File-sharing System[C]. Proceedings of the 2006 IEEE/WIC/ACM international conference on Web Intelligence and Intelligent Agent Technology,2006:433-436.
    Li K H, Xu C Q, Zhang Y H, Wu Z M.2008. Optimal Prefix Caching and Data Sharing Strategy[C]. In:Proc. of IEEE Conf. on Multimedia and Expo, Hannover, Germany: 465-468.
    Lee C H, Gui Y Q, Jung I B, et al.2006. A Peer to Peer Prefix Patching Scheme for VOD Servers[C]. In:Proc. of the International Conf. on Information Technology:New Generations, Las Vegas, Nevada, USA:530-534.
    Lang K R, Vragov R.2005. A pricing mechanism for digital content distribution over Peer-to-Peer networks[C]. Proceeding of the 38th Annual Hawaii International Conference on System Sciences. Hawaii:211-221.
    Feldman M, Papadimitriou C, Chuang J, Stoica I.2004. Free-riding and whitewashing in peer-to-peer systems[C]. Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, Portland, Oregon, USA: 331-341.
    Feldman M, Lai K, Stoica I, et al.2004. Robust incentive techniques for peer-to-peer networks[C]. Proceedings of the 5th ACM conference on Electronic commerce, New York, NY.US.May:1010-1019.
    Ma T, Lee C, Lui J C S, et al.2006. Incentive and service differentiation in P2P networks:A game theoretic approach, IEEE/ACM Transactions on Networking,14 (5):978-991.
    Ma R T B, Lee C M, Liu J C S, et al.2003. Incentive P2P Networks:A Protocol to Encourage Information Sharing and Contribution [J]. SIGMETRICS Perfonnance Evaluation Review, 31(2):23-25.
    Manini D, Gribaudo M.2006. Modelling Search, Availability, and Parallel Download in P2P File Sharing Applications with Fluid Model[C]. Proceedings of the 14th International Conference on Advanced Computing and Communication, ADCOM:449-454.
    Misra V, Gong W, Towsley D.2000. Fluid-based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED[C]. Proceedings of ACM SIGCOMM: 151-160.
    Oram A.2001.Peer-to-Peer:Harnessing the Power of Disruptive Technologies[M]. Sebastopol, CA, USA:O'Reilly & Associates.
    Pouwelse J, Garbacki P, Epema D, Sips H.2005. The BitTorrent P2P File-Sharing System: Measurements and Analysis[C]. InProc. Of International Workshop on Peer-to-Peer Systems, Feb:206-216.
    Philippe Golle, Kevin Leyton Brown, Ilya Mironov.2001. Incentives for sharing in peer-to-peer networks[C]. Proceedings of the 3rd ACM conference on Electronic Commerce, October 14-17, Tampa, Florida, USA:264-267.
    Qiu D Y, Sang W Q.2008. Global Stability of Peer-to-Peer File Sharing Systems[J]. Computer Communications,31:212-219.
    Qiu D Y, Srikant R.2004. Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks[C]. In Proc. ACM, SIGCOMM, Portland, Oregon, Sep:367-377.
    Rosenberg C, Pons P, Xu D.2004. Policy-Driven Multi-File Distribution, Quality of Service[C]. IWQOS 2004. Twelfth IEEE International Workshop on:193-197.
    Simon G M Koo, Catherine Rosenberg.2003. Analysis of Parallel Downloading for Large File Distribution[C]. Proceedings of the The Ninth IEEE Workshop on Future Trends of Distributed Computing Systems,2003:301-330.
    Saroiu S, Gummadi K P.2003. Gribble.Measuring and Analyzing the Characteristics of Napster and Gnutella Hosts[J]. Multimedia Syst,9(2):170-184.
    Sepandar D, Kamvar, MarioT, Schlosser, Hector GarciaMolina.2003. The Eigentrust algorithm for reputation management in P2P networks[C], Proceedings of the 12th international conference on World Wide Web, May 20-24, Budapest, Hungary:640-651.
    StruloB Smitha, Farrj.2003. Achitecture for peer to peer economices[C]. Proceedings of the 3rd International Conference on Peer to Peer Computing. Linkoping:208-209.
    Turker M A.2004. Content delivery networks and their roles in elearning[C]. Signal Processing and Comminications Applications Conference:359-362.
    Vishnumurthy V, Chandrakumar S, Sirer E G.2005. Karma:A secure economic framework for P2P resource sharing [C]. Proceedings of the 2005 Conf. of the Centre for Advanced Studies on Collaborative research, IBM Press:85-199.
    Veciana G D, Yang X Y.2003. Fairness Incentives and Performance in Peer-to-Peer Networks [C]. In Pro. Forty-first Annual Allerton Conf. Communication, Control and Computing, Monticello, IL, Oct:749-758.
    Varian H R.1992. Microeconomic Analysis[M]. New York:W.Norton&Company.
    Wang X F, Chen G R.2002. Pinning control of scale-free dynamical networks[J]. Physica A, 310:521-531.
    Xu D Y, Rulkarniz S S, Rosenbergz C, et al.2004. A CDN-P2P Hybrib Architecture for Cost-Effective Streaming Media Distribution[J]. Computer Networks,44(3):353-382.
    Yang X Y, Veciana G D.2004. Service Capacity of Peer to Peer Networks[C]. In Proc. IEEE INFOCOM,4:2242-2252.
    Yue Y. Lin C, Tan Z.2006. Analyzing the performance and fairness of BitTorrent-like networks using a general fluid model[C]. Computer Communications:3946-3956.
    Zhang Z B, Chen Y, Deng B X, et al.2007. Experimental Study on Network Coordinate Based Locality-aware BitTorrent[J], Xiamen University,46(2):213-215.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700