（计算机应用技术专业论文）一种基于p2p技术的通信算法研究.pdf

中文摘要 论文题麟：一种基于p 2 p 技术的通信算法研究 专业：计算机应用技术 硕士生：李皎( 签名)盔丝 指导教师：刘天时( 签名) 蛰叠三谷一 摘要 点对点( p e e rt op e e r ，p 2 p ) 网络具有自组织、非集中和节点交互直接等特点，是 计算机网络技术研究领域的一个热点。p 2 p 网络通信算法研究则是影响p 2 p 网络发展的一 个重要方面。一般来说，在计算枧潮络中，通信节点受场地分布和通信环境等一系列露 素影响，任意两节点的通信代价是不同的，也就是说通信节点之间的权值大小和通信时 间可能不同。通信时间是衡量通信效率的重要指标之一，在实际通信中越来越受到人们 蕊重视。本文以点对点技术为基础，研究了p 2 p 网络遗信算法，算法能够根搌通信权僮合 理布局网络节点，保证网络负载均衡，使得全部节点能在较短时间段内完成通信任务。 本文在深入分析p 2 p 通信技术和p 2 p 通信算法的基础上，提出了一种p 2 p 通信模式， 该模式能够合理布局潮络节点，有效提高数据传输效率。该通信模式的基本思想是引入 并发逶傣枫制，按照节点之间通信权值分布情况，给所有通信节点分配适量的通信任务， 达到缩短通信时间的目的。根据通信实际情况，给出通信网络中的节点之间通信权值的 估算方法。结合并发通信规则和通信权值的概念，给出通信树的有关定义和通信树的表 示方法。在此基础上，提出了两种p 2 p 模式不等权值通信树构造算法一k r u s k a l 通信 树算法和支路优先通信树算法。模拟结果表明，支路优先通信树算法的通信效率优于 k r u s k a l 通信树算法。文中将支路优先方法应用到蚁群算法中，从而进一步提高p 2 p 通 信效率。最后开发了p 2 p 网络通信算法测试软件，为深入分析研究p 2 p 通信算法提供方 便。 关键词：p 2 p 技术；并发机制；通信权值；通信树；通信时间 论文类型：基础研究 本文得到陕西省自然科学基金项目“点对点模式分布式数据库系统体系结构研究 ( 2 0 0 7 f 3 3 ) 和陕西省教育厅专项科研资助项目“点对点模式分布式数据库系统体系结构 研究( 0 7 j k 3 6 2 ) 大学科学研究资金的资助。 珏 英文摘要 s u h i e c t ：s t u d yo nac o m m u n i c a t i o na l g o r i t h mb a s e d o np 2 pt e c h n o l o g y s p e c i a l i t y ：c o m p u t e ra p p l i c a t i o nt e c h n i q u e n a m e ：l i j i a o ( s i g n a t u 他) ! 掣：丝 i n s t r u c t o r ：l i ut i a n s h i ( s i g n a t a r e ) 2 4 ：必i ：幽，2l 乏 a b s t r a c t 1 1 l ep e e rt op e e r ( p 2 p ) n e t w o r k w i t ht h ec h a r a c t e r i s t i c ss u c h 觞s e l f - g o v e r n m e n t ， n o n c e n t r a la n de x c h a n g i n gi n f o r m a t i o nd i r e c t l yb e t w e e nn o d e s ，h a sb e c o m eah o tr e s e a r c h d o m a i ni nc o m p u t e rn e t w o r k p 2 pn e t w o r kc o m m u n i c a t i o na l g o r i t h mi sa ni m p o r t a n ta s p e c t t oi n f l u e n c ep 2 pn e t w o r kd e v e l o p m e n t g e n e r a l l ys p e a k i n g ，i nc o m p u t e rn e t w o r k ，as e r i e so f f a c t o r s s u c h 嬲t h el o c m i o nd i s t r i b u t i o no fn o d e sa n dt h ec o m m u n i c a t i o ne n v i r o n m e n t ， i n f l u e n c et h ec o s ta n dt h ew e i g h to ft h ec o m m u n i c a t i o nb e t w e e nn o d e sw h i c hm a yb e d i f f e r e n tr e s p e c t i v e l y c o m m u n i c a t i o nt i m e ，o n eo fk e yi n d i c a t o r st om e a s u r ec o m m u n i c a t i o n e f f i c i e n c y , i sv e r yi m p o r t a n t i n a c t u a lc o m m u n i c a t i o n b a s e do np 2 pt e c h n o l o g y , t h e d i s s e r t a t i o ns t u d i e sap 2 pn e t w o r kc o m m u n i c a t i o na l g o r i t h m ，w h i c hc a nl a y o u t n o d e s r e a s o n a b l ya n db a l a n c et a s kf o rt h el o a d e dn o t e si nt h en e t w o r ki no r d e rt oc o m p l e t et h e c o m m u n i c a t i o nt a s kq u i c k l y f i r s t ，t h ed i s s e r t a t i o np r o p o s e sap 2 pc o m m u n i c a t i o nm o d e la f t e ra n a l y s i so fp 2 p c o m m u n i c a t i o nt e c h n o l o g y t h i sm o d e lc a nd i s t r i b u t en e t w o r kn o d e sr a t i o n a l l ya n di m p r o v e d a t at r a n s m i s s i o ne f f i c i e n c ye f f e c t i v e l y n 圮b a s i ci d e ao ft h em o d e li s t oi n t r o d u c ea c o n c u r r e n tc o m m u n i c a t i o nm e c h a n i s m ，a n dt oa s s i g np r o p e rc o m m u n i c a t i o nt a s kt oa l ln o d e s a c c o r d i n gt ot h ec o m m u n i c a t i o nw e i g h tb e t w e e nn o d e si no r d e rt os h o r t e nc o m m u n i c a t i o n t i m e 1 1 l ed i s s e r t a t i o na l s og i v e st h ew e i g h te s t i m a t i o nm e t h o d sa c c o r d i n gt oa c t u a ls i t u a t i o n f o r t h ec o m m u n i c a t i o n t h e ni tp r e s e n t st h ed e f i n i t i o no fc o m m u n i c a t i o nt r e ew i t hc o n c u r r e n t c o m m u n i c a t i o nm e c h a n i s ma n dp r o p o s e st w oc o m m u n i c a t i o na l g o r i t h m s ：o n ei sk r u s k a l c o m m u n i c a t i o nt r e ea l g o r i t h m a n dt h eo t h e ri sb r a n c hf i r s t ( b f i ) c o m m u n i c a t i o nt r e e a l g o r i t h m s i m u l a t i o nr e s u l t si n d i c a t et h a tb f ic o m m u n i c a t i o nt r e ea l g o r i t h mi ss u p e r i o rt o k r u s k a lc o m m u n i c a t i o nt r e ea l g o r i t h mi nc o m m u n i c a t i o ne f n c i e n c y 1 1 1 ea n tc o l o n y o p t i m i z a t i o n ( a c o ) a l g o r i t h ma p p l i e d t ob f ia l g o r i t h mc a ni m p r o v ec o m m u n i c a t i o n e 伍c i e n c yf u r t h e r f i n a l l y , t h ed i s s e r t a t i o nd e v e l o p s at e s ts o f h v a r et oa n a l y z ep 2 p c o m m u n i c a t i o na l g o r i t h m k e y w o r d s ：p 2 pt e c h n o l o g y ；c o n c u r r e n t m e c h a n i s m ；c o m m u n i c a t i o nw e i g h t ； c o m m u n i c a t i o nt r e e ；c o m m u n i c a t i o nt i m e t h e s i s ：f o u n d a t i o ns t u d y i i i 英文摘要 t h ed i s s e r t a t i o ni ss u p p o r t e db yn a t u r a l s c i e n c ef o u n d a t i o no fs h a a n x ip r o v i n c e d i s t r i b u t e dd a t a b a s es y s t e ma r c h i t e c t u r eb a s e do np 2 pm o d e ( 2 0 0 7 f 3 3 ) a n ds c i e n t i f i c r e s e a r c hf o u n d a t i o no fe d u c a t i o nb u r e a uo fs h a a n x ip r o v i n c e d i s t r i b u t e dd a t a b a s es y s t e m a r c h i t e c t u r eb a s e do np 2 pm o d e ”( 0 7 j k 3 6 2 ) i v 学位论文创新性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他 人已经发表或撰写过的研究成果；也不包含为获得西安石油大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做 了明确的说明并表示了谢意。 串请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：茎丝日期：跏矿，厂z o 学位论文使用授权的说明 本入完全了解西安石油大学有关保留和傻用学位论文麴规定，露：研究生在校攻读 学位期闯论文王作的知识产权单位属西安石油大学。学校享有以任何方法发表、复制、 公开阅览、借阅以及申请专利等权利，同时授权中国科学技术信息研究所将本论文收录 到中国学位论文全文数据库并通过网络向社会公众提供信息服务。本人离校后发表 或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为西安石油大 学。 论文作者签名： 导师签名： 日期： z q 否。( 善。 日期：1 p 驴。j 。w 注：如本论文涉密，请在使用授权的说明中指出( 含解密年限等) 。 第一章绪论 1 1 选题的背景及意义 第一章绪论 1 1 1 选题背景 点对点( p e e rt op e e r ，p 2 p ) 飘1 技术为网络的发展带来了深远的影响，它的理念使 得给i t 产业带来了无限的商机。目前，对于p 2 p 技术研究和探讨，一直是计算机网络领 域研究热点之一4 】，受到业界和学界人士的普遍关注。p 2 p 对人们产生最大的影响的， 并不是它的技术和功能，磊是它的理念。这种理念源于人们最初对互联网的向往与憧憬， 它使网络回归到i n t e r n e t 的本质，让共享与自由的思想充满整个网络世界。 在传统的客户机服务器( c l i e n t s e r v e r ，c s ) 模式巾瞄6 1 ，服务器为网络中各用 户提供服务并管理整个网络，是整个网络的核心。当服务器遇到故障时，整个网络将会 瘫痪。两p 2 p 模式使网络中静节点直接交换信息避免了这个翔题的产生。p 2 p 逶信指网 络中两个地位对等的节点之间的通信，节点之间信息的交换是直接的，不经过中间服务 器的转发。人们在实际通信过程中，比较重视通信时间，也就是通信效率，通信效率是 衡量算法性毙的重要指标，因此，p 2 p 透信算法麓研究对p 2 p 技术发展起着至关重要的 作用。 1 1 2 选题意义 随着经济的发展，企业规模不断扩大，企业向着跨地域方向发展。现有的信息数据 不能及时进行处理、分析，必须经过中间环节，各个场地之间的协调和合作困难，信息 不能直接交互导致工作效率较低等问题。点对点模式通信方式，为具有分布式需求的领 域或企事业单位提供了一种科学、方便、有效的工作模式，充分有效地利用了计算机逶 信网络资源，提高了数据通信效率。本文结合了p 2 p 的优点提嫩了一种点对点通信模式， 该模式给出了一种合理布局网络节点，有效提高数据传输效率的方法。该方法适合于多 播通信，为需要相嗣数据流的节点加入相同的组共享一条数据流提供了一葶申有效的数据 传输方法，同时也适合于网络数据群发。该遥信模型具有缀强的应用背景，对于有分布 式需求的企事业单位提供了一种新的数据传输模式。所以该通信模式的研究和实现会带 来广阔的发展前景和良好的经济效益。 1 2 研究现状 1 2 1 国外研究现状 p 2 p 看起来似乎缀新，但其实p 2 p 是互联网刚出现时应褥最广泛的一种技术。那时 并没有中心服务器、门户站点这样的概念，每一个网络用户都担当了服务器和客户机的 西安石油大学硕士学位论文 角色。但是每一个网络用户担当服务器和客户机的角色也带来了一些问题：信息遍布网 络各处，没有一个集中的存放地点，这样使得在潮络上寻找信息就好像大海捞针一样非 常困难。同时由于服务器的角色也是由网络用户担满，这样就使得网络上提供的各种服 务不稳定。以上种种原因使得互联网的元老p 2 p 逐渐的被人们遗忘。 p 2 p 基本技术的存在时闻和我们曾经熟悉的u s e n e t 、f i d o n e t 这两种菲鬻成功的分 布式对等网络技术几乎是闻时的，甚至更长些。u s e n e t 产生予1 9 7 9 年，f i d o n e t 剖建 1 9 8 4 年，它们都是一个分散、分布的信息交换系统。在最初的p 2 p 应用出现时，许多使 用该技术的人们甚至不会使用计算机。然两正是这种孕育着思想的网络技术为p 2 p 的出 现创造了坚实的基础。 1 9 9 8 年，n a p s t e r 公司1 9 岁的大学新生绍恩法宁开发的一款音乐共享软件 n a p s t e r 。该公司创造性地在互联网上推出了音乐交换服务，用户只需下载这款免费的软 件，就可以搜索到其它用户计算枫里存储的m p 3 文件，并从那里获得该文件，当然也可 以将自己拥有的m p 3 文件提供给其它用户，这种免费而方便的服务受到人们的普遍欢迎， 而这项服务开创的伙伴观念迅速使p 2 p 风靡全球。 n a p s t e r 实质上并习扛是纯粹的p 2 p 系统，它通过一个中央服务器保存所有n a p s t e r 用户上传的音乐文件索罨| 和存放位置的信息，实现了文件查谗与文件传输的分离，有效 地节省了中央服务器的带宽消耗，减少了系统的文件传输延时。这种方式的瓶颈在中央 服务器上，如果该服务器遇到故障，整个系统都会瘫痪。g n u t e l l a 是一个p 2 p 文件共享 系统，它是纯粹的p 2 p 系统，没有索零| 服务器，它采用了基予完全随机圈的洪泛 ( f l o o d i n g ) 发现和随机转发( r a n d o m w a l k e r ) 机制。随着联网节点的不断增多，网络 规模不断扩大，通过这种洪泛方式定位对等点的方法将造成网络流量急剧增加，从而导 致网络中部分低带宽节点因网络资源过载而失效。所以，解决g n u t e l l a 网络的可扩展性 对该网络的进一步发展至关重要。 1 2 2 国内研究现状 与国外的p 2 p 发展情况相院，中圜网络环境相对滞看，虽然嚣外的n a p s t e r 备受关 注，但国内上网用户数量很少，p 2 p 软件并没有条件使用，可以说p 2 p 技术在中国起步 晚、发展快。目前p 2 p 在即时通信、音乐共享与下载等方面的产品及商业p 2 p 软件也层 啦不穷，例如大家最熟悉的p p l i v e ，它是一款用于互联网上大规模视频直播的共享软件。 实现观看用户越多，播放越流畅的特性，整体服务质量大幄度提离。另外，在中国，p 2 p 电子商务的市场发展潜力无穷，在互联网实验室新近推出的( p 2 p 的现状及发展趋势研 究报告中有数据显示：到2 0 0 3 年底，中国的电子商务市场b 2 b 和b 2 c 的交易总额将可 能达到4 0 亿美元之巨，b 2 b 酶年均增速为1 9 4 ，瑟b 2 c 的年均增速是2 7 。唾，均呈 倍数增长。这样广阔的发展前景，势必为p 2 p 在电予商务领域的应用带来商机娜。中国 互联网协会秘书长黄澄清日前在2 0 0 7 年“中国i t 两会”之互联网年会上表示，中国已 2 第一章绪论 成为p 2 p 流媒体发展最快的国家。 m a z e 是北京大学网络实验室开发的一个中心索引与对等连接相融合的文件共享系 统，是市场上最大的非商业性、以科研为雷的系统。在用户管理、信息检索上采用集中 式控制，中心索引服务器提供基于关键字的搜索，同时，还可以基于节点之间友好关系 的搜索。网上的计算机无论是在网外网内，可以通过安装运行的客户端软件自由的加入 和退出该系统。另外有由华中科技大学开发的一个基于p 2 p 模式的视频点播系统软件 a n y s e e ，和清华大学自主开发的对等计算存储服务系统g r a n a r y 。 另外一种搜索方法是建立s u p e r n o d e ，它存储着离它最近的叶子节点的文件信息， 这些s u p e r n o d e ，再连通起来形成一个o v e r l a yn e t w o r k ，当叶子节点需要查询文件，它 首先从它连接的s u p e r n o d e 的索弓l 中寻找，如果找到了文件，则直接根据文件所存储的 机器的i p 地址建立连接，如果没有找到，则s u p e r n o d e 把这个查询请求发给它连接的其 它超级节点，直到得到想要的资源啉1 。 移动a g e n t 是一个能在异构网络中自主地从台主机迁移到另一台主机，并可与其 它a g e n t 或资源进行交互的程序。a g e n t 非常适合在网络环境中帮助用户完成信息检索 任务。 最薪的成果都是基于d h t ( d i s t r i b u t e dh a s ht a b l e s ) 的分布式发现和路由算法嘲。 这些算法都避免了类似n a p s t e r 的中央服务器，也不是像g n u t e l l a 那样基于广播进行查 找，而是通过分布式散列函数，将输入的关键字惟一映射到某个节点上，然后通过某些 路由算法同该节点建立连接。 文献 圭0 实现了一种高效的扩散路由算法l i g h t f l o o d i n g ，其优点是既可保持较高 的信息覆盖率，又可使冗余消息维持在一个适当的范围，以保持搜索的有效性。 文献 1 1 提出了基于a g e n t 的s u p e r p e e r s 网络结构。结合了n a p s t e r 和g n u t e l l a 的优点克服它们的不足之处。当溺络中的信息剧增，为了克服传统的关键字查找方法的 不精确性，a g e n t 采用元数据进行精确查找。每个节点的a g e n t 提供主动服务和智能搜 索功能。在p 2 p 搜索过程中，提出了一种解决双方都不在线情况下的基于元数据的查找 及下载所需信息的方法。 文献 1 2 给出了一种满足端到端酎延限翎的多播路由算法。该算法是基于通信网络 参数加权s t e i n e r 树的构造技术。当通信网络的目的节点集的时延不受限时，s t e i n e r 树就是p r i m 算法的最小生成树，而在时延受限的情况下，算法在给定目的节点集后，通 过改变费羽与时延的加权参数逼近最优解。透过现有算法蛉算例指出了现有算法的多攒 路由树构造中的问题，使s t e i n e r 树的最优性得到保障，实验模拟表明该算法在构造多 播树在优化和效率上都有了明显的提高。 文献 1 3 针对菲结构化对等鼹络中洪泛搜索机制的路由盲嚣性阀题，提出了一种利 用节点积累的经验指导节点传播查询的路由算法。在该路由舞法中，节点记录自己关注 的主题和满足主题的邻居节点，建立主题与邻居节点的对应关系表，当节点收到查询后 3 疆安石油大学硕士学位论文 就利用该表来指导节点选择查询路由，以便更快地找到查询结果。 文献 1 4 介绍了节点间密集的通信操作会极大地降低并行应用的性能，对于并行系 统来说，一个有效的通信操作库是极为重要的。常用的通信操作包括广播、多点播送、 路障同步、全对全通信等。文献 1 4 从通信操作中归结出四种基本动作类型，并从系统、 应用和算法三方面对通信算法进行深入探讨，找出了影响算法性能的关键因素，从而提 出一些使算法更加实用所需要考虑酶问题和解决措施。 文献 1 5 给出了通信树的构造算法，并对通信时间进行了分析。最后得出结论，对 于有n 个节点参与的通信，秃论是采用线形法、集中式方法，通信工作量均不低o ( n ) 阶， 褥采用分层结构等权值通信树算法，通信工作量为o ( 1 n n ) 阶。 以上是国内外研究的一些p 2 p 搜索通信算法，可以看出准确性和可扩展性是p 2 p 网 络面临的两个重要问题，所以对于网络搜索算法和网络通信算法的研究成为一个热点。 该论文将研究一种合理布局网络节点，有效提高数据传输效率的方法。 1 3 研究问题与研究思路 本文主要是在文献 1 5 的基础和启发下，研究一种p 2 p 网络透信算法。 文献 1 5 研究了一种分层式树形透信结构，并给撼了等权僮通信算法构造过程。文 献 1 5 将节点之间构成的数据通信称为通信树。用符号“ 表示取整操作，设数据通 信参与节点数为肛等权值通信树构造算法如下： s t e p l当节点数艇3 时，选其中一节点( 源节点) 作为树的根节点，其余节点终 为叶节点，通信树构造结束； s t e p 2当节点数n 3 时，将个节点分为两部分，将源节点放入第二部分，第一 部分由 ( 船1 ) 2 个节点构成树的第一个予树，它的父节点是第二部分舻 ( 船王) 2 个节 点构成的树的根节点； s t e p 3 对于子树内的构造转s t e p l ，直至构造结束。 ( 彭( 麓 图1 - 19 节点等权值通信树 图1 - 1 ( a ) 是按照上述算法构造的9 节点通信树。在图1 - 1 ( b ) 中，方框内数字表 4 第一章绪论 示相连两节点进行通信的时间段，例如，节点v 1 与节点吃间的方框数字为1 ，表示在第l 时闻段内节点强向节点殇发送数据。节点欹与节点毪闻的方框数字为4 ，表示在第4 时 间段内节点向节点k 发送数据。 文献 1 5 给出了节点分组方法与通信树构造方法，节点分组实际上是一个二分法， 即把源节点编号排在所有参与节点的最后，每组节点数为剩余节点数加l 后除2 ，通信 次数与节点分组数网一鳖级。接着推导出了并发通信时闻和累计通信时间的解析表达式， 并进行了理论证明，对推导结果进行分析和比较，结果显示二分法分层结构通信方法使 p 2 p 模式数据通信随节点数目的增加相对其它两种结构并发通信时间大幅度减少，前者 用时为0 ( 1 n n ) 量级，骶者为0 ( x ) 量级。焉且，二分法分层结构在实际应用中容易实施。 发送源节点将待发送数据和其它 ( n + 1 ) 2 个节点的节点信息发给其中的一个节点，再用 同样的方法处理剩余的n 一 ( n + i ) 2 个节点，然后，从发送数据路线的逆方向接收应答 状态。在实际应用中巍予受场地分布和通信条件等因素的影响，应尽可能将场地邻近的 节点分为一组，且优先选取通信速率高的节点，以缩短通信时间，降低通信费用。 另外，文献 1 5 引入并发通信机制，该通信机制相对于累计顺序通信通信效率明显 提高。本文也应用文献 1 5 所提出的并发通信机制。 然焉，在计算机通信网络中，通信节点受场地分布和通信环境等一系列因素的影响， 任意两节点的通信代价是不同的，也就是说通信节点之间的权值大小和通信时间不同。 因此本文在文献 1 5 所研究的等权值通信树的基础上，研究了不等权值通信树，给出了 不等权僮通信树的构造算法和树形调整算法，并对通信树的通信时闻进行评估。该通信 算法为企事业单位提供了一种通信过程简单、数据可靠、应用上经济实用的通信方法。 1 4 研究内容 本论文在深入分析等权值通信树构造方法的基础上，深入研究不等权值通信树的构 造方法，提出了两种不同的通信树构造方法，并通信时间进行了测试比较分析，最后开 发了相应的p 2 p 网络通信算法测试软件。 第一章“绪论 。首先介绍选题的背景和意义，然后分析了p 2 p 研究的现状，最后提 出了研究问题与研究思路以及研究内容及论文框架。 第二章“p 2 p 技术。本章介绍了p 2 p 技术的相关概念，对国内p 2 p 搜索算法进行分 析和对眈，并结合并发通信机制提出了一种分层式的p 2 p 通信结构。 第三章“通信规则与定义”。本章介绍了并发通信和通信权值的相关概念，并给出了 通信树的定义和通信树表示方法。 第四章“通信树算法。本章对通信时间进行了分析，并给如了k r u s k a l 通信树构造 算法和支路优先通信树算法，实验结果表明，支路优先通信树的通信效率明显优予 k r u s k a l 通信树的效率。最后将支路优先方法应用到蚁群算法，从而尽一步提高p 2 p 通 5 西安石油大学硕士学位论文 信效率。 第五章“p 2 p 网络通信算法测试软件 。本章编程实现了通信树算法，通过数据窗口 清楚的看出通信树通信时间及其相关参数，该p 2 p 网络通信算法测试软件为我们研究算 法提供方便。 第六章“结论与展望”。对本论文的研究内容进行了总结，提出了今后需要进一步进 行研究的内容和方向。 6 第二章p 2 p 技术 第二章p 2 p 技术 p 2 p 是p e e rt op e e r 的缩写，p e e r 在英语里有“( 地位、能力等) 同等者 、“同事 和“伙伴等意义。这样一来，p 2 p 也就可以理解为“伙伴对伙伴”的意恩，或称为对 等联网。p 2 p 技术让人们通过互联网直接交互。p 2 p 使得网络上酶沟通变得容易、更直接 共享和交互，真正地消除中间服务器。这种技术更适合现实中人们交流和沟通方式，它 是一种基于互联网环境的新的应用型技术，自从p 2 p 技术问世以来，网络上各种p 2 p 商 业软件层出不穷，p 2 p 软件用户也不断增多。随着p 2 p 技术的逐步完善，p 2 p 技术会有更 加广阔的发展空闻。 2 1p 2 p 技术概述 2 1 1p 2 p 特点 p 2 p 是一种分布式网络，对等节点( p e e r ) 之间直接访问而无需经过中间实体，以达 到共享计算机资源的目的，这些资源与服务包括信息交换、处理器时钟、缓存和磁盘空 间等。在此网络中的参与者既是资源提供者( s e r v e r ) ，又是资源获取者( c l i e n t ) 鞋秘。 从技术角度讲，p 2 p 技术并不是项新技术，它只是分布式计算在互联网上的应用， 另一方蕊，它是原始匮联网的回归，它反映了互联网的本质。 嚣翁对于p 2 p 没有确切的定义，但是p 2 p 有如下特点： 非中心化：网络中的资源和服务分散在所有节点上，信息的传输和服务的实现都直 接在节点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。p 2 p 的非中 心化基本特点，带来了其在可扩展性、健壮性等方面的优势。 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资 源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整个体系是全分布的， 不存在瓶颈。理论上其可扩展性几乎可以认为是无限的n6 i 。 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由予服务是分散在各个节点之间 进行的，部分节点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般在部分节点失效 时能够自动调整整体拓扑，保持其它节点的连通性。p 2 p 网络通常都是以自组织的方式建 立起来的，并允许节点自由地加入和离开。p 2 p 隧络还能够根据网络带宽、节点数、负载 等变化不断地做自适应式的调整雏朝。 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点，更好的实现了 整个网络的负载均衡转 。 7 两安石油大学硕士学位论文 图2 1p 2 p 系统的位置 2 1 2p 2 p 分类 如图2 1 所示，所有的计算机系统可分为集中式和分布式两类，分布式系统可进一步 划分为c s 系统和p 2 p 系统。p 2 p 系统可粗略的分为纯p 2 p 系统和混合p 2 p 系统。 纯p 2 p 系统：没有服务器的概念，所有的参与者都是对等者，存储、交换、搜索都是 在对等者上完成的。g n u t e l l a 系统就近似于纯p 2 p 系统。纯p 2 p 系统克服了c s 模式服务器 单点失效和瓶颈等问题，但一个节点的搜索请求要经过整个网络或者至少是一个很大的 范围才能得到结果，占用很多带宽，而且可能需要花费很长时间才能有返回结果。纯p 2 p 系统如图2 2 所示。 在纯p 2 p 系统中，网络节点之自j 的交互是直接的，节点的地位是平等的。节点可以提 供文件的下载服务，也可以提供文件的搜索服务。 图2 - 2 纯p 2 p 系统 混合p 2 p 系统：将分布式系统与集中式系统相结合，由位于网络中的服务器搜集相关 信息，作为索引节点，负责记录共享信息以及回答对这些信息的查询，对等者节点首先 向服务器发出请求，获得即将访问对等者的标识符( 即地址信息) ，然后直接和对等者交 换信息。系统n a p s t e r 就是这类系统的代表之一。这类系统中，要求服务器必须能够处理 第二章p 2 p 技术 大量的用户连接，拥有足够的内存和磁盘空间来维护和搜索文件列表，并可以连续运行。 混合p 2 p 系统如图2 3 所示。 混合p 2 p 系统是将整个p 2 p 网络分成两层，由超级节点和普通节点组成。一个超级节 点管理若干个普通节点，属于c s 结构。多个超级节点构成一个分布式网络。当然混合p 2 p 系统也可以是多层结构，把参与服务存储空间大、处理能力强、具有足够的网络带宽的 节点选作超级节点。超级节点管理普通节点，超级节点由更高一级的超级节点管理，构 成了层次化结构。有超级节点的p 2 p 网络易于管理、易于发现网络节点、搜索速度较快， 但是，当较高级别的超级节点失效时，对网络的影响比较大，严重的情况可能导致部分 网络的瘫痪。目前比较流行的网络电话s k y p e 就是采用了混合p 2 p 结构。 2 2p 2 p 与c s 技术比较 n o d c 图2 - 3 混合p 2 p 系统 在传统的客户机服务器( c 1 l e n t s e r v e r ，c s ) 模式中，服务器为网络中各用户提 供服务并管理整个网络，是整个网络的核心。当服务器遇到故障时，整个网络将会瘫痪。 而p 2 p 模式使网络中的节点直接交换信息避免了这个问题的产生。p 2 p 系统是自组织的、 非集中式的，各节点是自治的、对等的、动态的，节点之间的交互是直接的。p 2 p 打破 了传统的c s 模式，在对等网络中，每个节点的地位都是相同的，具备客户端和服务器 双重特性，可以作为服务使用者和服务提供者n8 | 。p 2 p 的优点在于，不但降低硬件设备 投入成本，而且还消除了中央服务器因信息转发而引起的瓶颈效应，同时，p 2 p 模式还 可提供机会利用大量对等节点的闲置资源n 引，如大量计算处理能力以及海量储存潜力， 在通过网络实现数据分配、控制及满足负载平衡请求等方面具有显著优势。p 2 p 模式在 数据发布、数据更新等方面要优于c s 模式。在p 2 p 模式与c s 模式中，节点之间的信 息交换方式如图2 4 所示。 9 西安石油大学硕士学位论文 对等者 用户 瓣 p 2 p 模式c s 模式 图2 4p 2 p 模式与c s 模式结构图 表2 - 1 给出了两种模式的技术毖较。c s 模式造成互联网络资源的集中，无论信息 资源还是成本资源均向同一方向集中，这样的模式符合一对多、强对弱的社会关系形式， 如政府对个人、对企业，大企业对小企业，学校对学生，企业对职工等等关系。所以c s 模式是符合市场需求的。p 2 p 方式将导致信息数量、成本资源都向互联网各点均匀分布， 也就是所谓“边缘纯的趋势。此模式符合“一对一的特点，以及彼此相当的社会关 系形式，如个人对个人，规模相当的企业之间等等，这也是符合市场需求的。所以这两 种模式会共存，有关p 2 p e o 将替代c s 模式的说法是不成立的。p 2 p 有其独特的市场空间， 是现有互联网应用的补充，这一点应该是毫无疑问昀。 2 3p 2 p 应用 表2 - 1p 2 p 与c s 技术比较 p 2 p 与c s 技术比较 p 2 pc s 数据发布好差 数据接受 孛 好 数据互动性好差 数据的传输速度好差 数据的安全 差 好 数据更凝好 差 数据质量中好 数据覆盖率和数量 差好 数据成本控制好差 数据管理方便性差好 2 3 。1p 2 p 应用领域 随着n a p s t e r 、g n u t e l l a 以及i c q 类p 2 p 系统等的出现，p 2 p 的技术优势以及它未来网 络中的应用价值逐渐体现出来，使它在工业界和学术界受到了高度的重视。许多著名的 公司先后投入对p 2 p 技术的研究之中。疆前，p 2 p 被广泛地应用于技术领域，极大地提高 了网络的信息、带宽和计算资源的利用率。网络上p 2 p 商业软件层出不穷，例如p p l i v e 是一款用于互联网上大规模视频直播的共享软件。实现观看用户越多，播放越流畅的特 l o 第二章p 2 p 技术 性，整体服务质量大幅度提高。大家最熟悉的代表性产品是各类b t ( b i tt o r r e n t ) 下载 软件，基本原理是利用p 2 p 技术，突破服务器与客户机概念，所有下载计算机也为其它下 载机器提供服务，好象在网络中有多台服务器，因此，下载入数越多，下载速度越快。 目前p 2 p 技术主要应用于以下几个领域n ： ( 1 ) 分布式存储：p 2 p 分布式存储系统是一个用于对等网络的数据存储系统，它可 以提供高效率的、负载平衡的文件存取功能。 ( 2 ) 文件共享：在传统的w e b 方式中，要实现文件交换需要服务器的参与，通过将 文件上传到某个特定的网站，用户再到某个网站搜索并下载需要的文件，而基于p 2 p ，两 个节点之闻可以直接交换信息。这种方式更符合人们信息交流的方式。 ( 3 ) 对等计算：采用p 2 p 技术的对等计算，可以把网络中的众多计算机暂时不用的 计算能力( 如处理器、存储器等) 等分散的资源积聚起来，宪成超级计算机的任务。如 应用于天气预报、动碱制作、基因组的研究等。p 2 p 技术使得这些需要大量数据处理的行 鲎十分受益。 ( 4 ) 协同工作：基于p 2 p 技术，在网络上任意两台计算机建立的共享虚拟空间中， 人们可以进行协同工作。 ( 5 ) 搜索弓| 擎：基于p 2 p 技术搜索文档、搜索深度要多予传统曩录式搜索琴| 擎的深 度。以g n u t e l l a 系统进行的搜索为例：一台p c 上的g n u t e l l a 软件可将用户的搜索请求同 时发给网络上另外1 0 台p c ，如果搜索请求未得到满足，这1 0 台p c 中的每一台都会把该搜 索请求转发给另外l o 台陀，这样，搜索范围将在几秒钟内以几何级数增长，几分钟内就 可搜索万台p c 上的信息资源。 ( 6 ) i c q 类的即时通信软件及游戏软件：两个或多个用户互相使用文字、语音或文 件进行交流，快速、直接，易于同非p c 网络设备( 如p d a 、手机) 通信。p 2 p 还可为开发 网络游戏提供一个越好平台。 2 3 2p 2 p 典型产品 说至o p 2 p ，就不能不提酲，大多数人把b t 与p 2 p 看成一组对等的概念，实际上b t 是一 个多点下载的p 2 p 软件。它不象f t p 那样只有一个发送源，b l 有多个发送点，当用户在下 载时，同时也在上传，使大家都处在同步传送的状态。应该说，b t 是当今p 2 p 最为成功的 一个应用。b t 的工作原理是将要下载的一个文件分为若干部分，用户甲在服务器随机下 载第n 部分，用户乙在随机下载第鹾部分，这样用户甲可就会去用户乙的机器上拿已经下 载好的m 部分，同样用户乙也可以去用户甲机器拿已经下载好的n 部分，这样可以减轻服 务器端的负荷，也可以提高用户的下载速度，原来到服务器下载可能才几k ，现在到其他 用户那里下载数据，传输速度明显提高。因此雕具有下载入越多，下载速度越快的优点。 配下载也充分体现了“我为人人，人人为我 的p 2 p 信息共享理念。 s k y p e 是采用p 2 p 技术的网络语音沟通工具。它可以免费高清晰与其它用户语音对话， 西安石油大学硕士学位论文 也可以拨打国内国际电话，还将传文件、文字聊天等功能集为一体。s k y p e 采用一种混合 p 2 p 模式的通信结构，它结合了集中式和分布式的特点，在网络的边缘节点采用集中式的 网络结构，而在超级节点之闻采用分布式的网络结构。s k y p e 是采用多层的网络结构，这 种结构利用超节点来实现网络中的每个节点可以获取所有其它可利用节点的资源，并将 这些节点资源动态组合，来参与流量分配、路径选择、信息处理和带宽增强等工作中， 面不是单纯依靠服务器来完成这些工作。 p p l i v e 基于p 2 p 的网络电视平台，是一款用于互联网上大规模视频直播的软件，采用 多点下载、网状模型的p 2 p 技术，有效解决了当前网络视频点播服务的带宽和负载有限的 问题，具有入越多，播放越流畅的特性。随着接入系统节点数囡不断增多，视频播放越 流畅、越稳定、效果越好，个别节点的退嵩又不影响整体性能。系统采用多点下载，动 态找到节点就近连接。p p l i v e 类似于b t 下载等p 2 p 软件，只有观看同一频道的人数达到一 定数量才能保证收视正常，建议用户多多作资源种子，大家一起共享视频资源。 2 4p 2 p 搜索算法 p 2 p 潮络规模大、节点分散且不稳定、数据种类多，因此，设计高效的接索机制，快 速而准确地找到所需要的数据，才能使p 2 p 网络得以广泛应用瞳们。国内外现有p 2 p 搜索算 法船u 可以分为两大类：盲目搜索和信息搜索。盲目搜索通过在网络中传播查询信息并且 把这些信息不断扩散给每个节点，直到搜索到想要的资源。而信息搜索在搜索的过程中 利用一些已有的信息来辅勘查找过程。下覆介绍几魏p 2 p 搜索算法。 在f l o o d i n g 方法中，每个节点都不知道其它节点的资源。这种搜索把消息传播给所 有的邻接点，它消耗了大量的网络带宽，使消息堵塞严重，效率比较低，扩展性不好。 另外一种搜索方法是建立超级节点s u p e r n o d e ，它存储着与它相邻的叶子节点的文件信 息，这些s u p e r n o d e 髯