（计算机应用技术专业论文）p4p路由算法的设计与研究.pdf

河南大学硕士研究生学位论文 摘要 随着p 2 p 应用，特别是p 2 p 流媒体应用的快速发展，p 2 p 的网络流量目前已占用 了i n t e r n e t 总体流量的大部分，并且这个比例还在不断增长。由于p 2 p 在选择节点 上的随意性，已经给承载网络带来了巨大的压力，由此造成的负面作用表现也越 来越大。p 2 p 应用在节点选择上的任意性是p 2 p 过度消耗网络资源的重要原因。这 种任意性主要来源于p 2 p 应用缺乏对网络底层的了解，结果导致p 2 p 重叠网和承载 网络的严重失配，引起很多p 2 p 网络流量频繁穿越运营商网络和骨干链路。美国耶 鲁大学提出了一种用于p 2 p 的网络优化技术p 4 p 。p 4 p 的主要思想是：在p 2 p 应用与 网络运营商之间开启显式的通信接口，p 2 p 客户( p e e r ) 可以调用该接口得到网络信 息，或请求承载网分配网络资源，从而能够更有效的利用网络资源，并提升p 2 p 应 用性能。 本文针对现有结构化p 2 p 路由算法存在物理位置和访问资源的局部性缺点，利 用p 4 p 技术方便感知网络拓扑信息特点，在结构化p 2 p 路由算法中找出一种相对比 较适用于p 4 p 下的路由算法- - p a s t r y 算法，以结构化拓扑结构为基础，采用p a s t r y 协议，提出了一种新的p 4 p 网络路由算法一p 4 p p a s t r y 路由算法。其基本思想： 对于拥有相同资源并且物理位置相近的节点进行聚类，在路由时优先考虑物理临 近并且通信成本较低的节点。在o v e r s i m 网络模拟平台上，对算法进行仿真分析。 实验表明该算法一方面可以提高本地化下载的比率，提高数据的交换速率，减少 了网络中不必要的跨域流量，减少骨干链路的负载。另一方面该算法可以帮助i s p 解决p 2 p 所引起的网络交通不可控制问题，于此同时还提高了p 2 p 应用程序的下载 速度，改善了互联网的性能，提高了整个网络的效率。使p 2 p 用户和i s p 实现了一 个双赢的目标。 关键词：p 2 p , p 4 p ；聚类；p a s t r y ；通信成本 河南大学硕士研究生学位论文第1 页 a b s t r a c t w i t hp 2 pa p p l i c a t i o n s ，e s p e c i a l l yp 2 ps t r e a m i n gm e d i aa p p l i c a t i o n s ，r a p i d d e v e l o p m e n t ，p 2 pn e t w o r kt r a f f i ci sn o wt a k i n gu pt h em a j o r i t yo fi n t e m e tt r a f f i ci n g e n e r a l ，a n dt h i sp e r c e n t a g ei sg r o w i n g a st h ep 2 pa r b i t r a r i n e s si nt h ec h o i c eo fn o d e s t h a th a sb r o u g h ta b o u ta i le n o r m o u sp r e s s u r eo nt h eb e a r e rn e t w o r k ，s or e s u l t i n g n e g a t i v e e f f e c t so fp e r f o r m a n c ei sm o r ea n dm o r es e v e r e p 2 pa p p l i c a t i o n s a r b i t r a r i l yc h o o s en o d ei s a l li m p o r t a n tr e a s o no fe x c e s s i v ec o n s 眦p t i o no fn e t w o r k r e s o u r c e s t h i si sm a i n l yd e r i v e df r o mt h ep 2 pa p p l i c a t i o n sa r el a c ko fu n d e r s t a n d i n go f t h eu n d e r l y i n gn e t w o r k ，r e s u l t i n gi no v e r l a p p i n gn e t w o r k sa n dp 2 pn e t w o r k sh a v ea s e r i o u sm i s m a t c h ，c a u s i n gal o to fp 2 pt r a f f i co f t e nt r a v e r s et h ei s pn e t w o r ka n d b a c k b o n el i n k y a l eu n i v e r s i t yh a sp r o p o s e dan e t w o r ko p t i m i z a t i o nt e c h n o l o g yf o rp 2 p , c a l l e dp 4 ep 4 p sm a i ni d e ai s ：p r o v i d i n ga ne x p l i c i tc o m m u n i c a t i o ni n t e r f a c eb e t w e e n p 2 pa p p l i c a t i o n sa n di s ep 2 pc l i e n t ( p e e r ) c a nc a l lt h ei n t e r f a c et or e c e i v en e t w o r k i n f o r m a t i o n ，o rr e q u e s tb e a r e rn e t w o r kt oa l l o c a t i o no fn e t w o r kr e s o u r c e s ，t h u sa l l o w i n g m o r ee f f i c i e n tu s eo fn e t w o r kr e s o u r c e sa n de n h a n c et h ep e r f o r m a n c eo fp 2 p a p p l i c a t i o n s t h i sp a p e ra i m i n ga tt h ec u r r e n ts t r u c t u r e dp 2 ps y s t e m sl o c a l i t yo fp h y s i c a l l o c a t i o na n da c c e s s i n gr e s o u r c e s b a s e do na d v a n t a g e st h a tp 4 pc a ns e n s en e t w o r k t o p o l o g ya n ds t a t u si n f o r m a t i o n w eh a v em a d ea r e f e r e n c et op 2 pr o u t i n gp r o t o c o l sa n d f i n da r e l a t i v e l ya p p l i c a b l er o u t i n ga l g o r i t h m ：p a s t r yi ns t r u c t u r e dp 2 pr o u t i n ga l g o r i t h m b yt h e u s eo fp 4 pt e c h n o l o g y , w er e s e a r c ha n dd e s i g no fap 4 pr o u t i n gp r o t o c o l p 4 p - p a s t r yi nw h i c hp e e r sp e r f o r m e dc l u s t e r i n gt ot h es a m er e s o u r c e sa n dt h ep r o x i m i t y o fp h y s i c a ll o c a t i o no fn o d e s w h e nr o u t i n g ，t h en o d er o u t e st ot h en o d e sw h i c ha r e p h y s i c a la d j a c e n tt oi ta n dh a v et h el o w e s tc o s to fc o m m u n i c a t i o n i no v e r s i m n e t w o r ks i m u l a t i o np l a t f o r m ，t h e o r ya n a l y s i sa n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a to n t h eo n eh a n d ，t h ea l g o r i t h mp r o p o s e di nt h i sp a p e rh a sr e a l i z e dl o c a l i z a t i o nd o w n l o a d a n dg r e a t l yr a i s e dt h ed a t at r a n s f e rr a t e ，r e d u c e dt h el o a di nb a c k b o n en e t w o r ka n d e n h a n c e dt h en e t w o r kp e r f o r m a n c e o nt h ea n o t h e rh a n d , t h ea l g o r i t h mc a nh e l pt h ei s p 第1i 页河南大学硕士研究生学位论文 t os o l v es e v e r a lp r o b l e m si np 2 pb u s i n e s s s u c ha st h en e t w o r kt r a f f i ci su n c o n t r o l l a b l e a n dr a i s i n go fl o c a l i z a t i o nd o w n l o a d ，d e c r e a s i n gi nt h et r a n s m i s s i o nd i s t a n c ea n d r e d u c i n gi nb a c k b o n en e t w o r kl o a d s oi tm a k e st h ei s pa n dn e t w o r ku s e r sa c h i e v ea w i n w i ns i t u a t i o n k e yw o r d s ：p 2 p , p 4 p , c l u s t e r , p a s t r y , c o m m u n i c a t i o nc o s t 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知。除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位申请人( 学位论文作者) 釜名： 垃章 2 0年 月 1 3 关于学位论文著作权使用授权书 本人经河南大学审核批准授子硕士学位。作为学住论文酌作者，本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 羝质文 本和电子文本) 以供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电于文本) 。 ( 涉及保密内睿的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名：拉 ：牢 2 0年月 目 学位论文指导教师釜名：童王垫垒 2 d年 月 日 河南大学硕士研究生学位论文第1 页 第一章绪论 目前，对等计算( p e e r t o p e e r ，简称p 2 p ) p 2 p 1 已经成为计算机界关注的 热门话题之一，财富杂志更将p 2 p 列为影响i n t e r n e t 未来的四项科技之一。 1 1 研究背景及意义 随着p 2 p 应用，特别是p 2 p 流媒体应用的快速发展，p 2 p 的网络流量目前已占用 了i n t e r n e t 总体流量的大部分，并且这个比例还在不断增长。由于p 2 p 在选择节点 上的随意性，已经给承载网络带来了巨大的压力，由此造成的负面作用表现也越 来越大。p 2 p 应用在节点选择上的任意性是p 2 p 过度消耗网络资源的重要原因。这 种任意性主要来源于p 2 p 应用缺乏对网络底层的了解，结果导致p 2 p 重叠网和承载 网络的严重失配，引起很多p 2 p 网络流量频繁穿越运营商网络和骨干链路。美国耶 鲁大学提出了一种用于p 2 p 的网络优化技术p 4 p 。p 4 p 的主要思想是：在p 2 p 应用与 网络运营商之间开启显式的通信接口，p 2 p 客户( p e e r ) 可以调用该接口得到网络信 息，或请求承载网分配网络资源，从而能够更有效的利用网络资源，并提升p 2 p 应 用性能。 p 4 p 技术的实质是一种网络资源的优化技术，通过网络的优化解决p 2 p 对资源 的耗费问题。p 4 p 的应用可以提高p 2 p 本地化下载的比率，提高数据的交换速率， 减少了网络中不必要的跨域流量，减少骨干链路的负载，让p 2 p 得到更大范围的商 业化应用逐步成为可能。文献 4 指出尽管美国有关部门已初步验证了p 4 p 带来的 好处并且成立了p 4 p 工作组，在美国，p 4 p 已经得到了部分网络运营商和p 2 p 软件商 的欢迎，但p 4 p 仍然面临着挑战，p 4 p 架构目前也尚未考虑如何以一种可扩展和高 效的方式实现。p 4 p 技术包括数据平面，管理平面和控制平面，但目前的主要研究 工作仍集中在控制平面，对数据平面、管理平面尚未涉及。 第2 页河南大学硕士研究生学位论文 目前由于p 4 p 自身的标准化还很不成熟，未来还有很多东西需要标准化，路由 查找算法在p 4 p 的实际应用中具有重要的作用和地位，它主要负责协调管理网络各 节点间的通信，路由查找算法的优劣直接关系至u p 4 p 系统的性能和可扩展性，路由 查找算法是网络交通管制的基础。路由查找算法可以减少网络消耗，有效地提高 网络的整体性能，对整个网络系统的性能有着重要影响并且可以为用户提供更好 的服务。目前基于p 4 p 技术的应用开发还很少，这些问题影响了p 4 p 的技术的实际 应用。为了加快p 4 p 技术的应用进程，必须设计开发适用于p 4 p 技术下路由协议， 从实现的复杂性考虑，改进已有的p 2 p 路由协议是最快捷的方式。本文正是基于p 4 p 能感知网络拓扑信息和状态信息这些特性，参考了p 2 p 下的路由协议，并在结构化 p 2 p 路由算法中找出一种相对比较适用于p 4 p 下的路由算法，利用p 4 p 的关键技术， 研究并设计了p 4 p 技术下的路由协议。 1 2 研究现状 p 4 p 技术 4 ：p 4 p ( p r o a c t i v en e t w o r kp r o v i d e rp a r t i c i p a t i o nf o rp 2 p ) 是 由y a l eu n i v e r s i t y 网络系统实验室提出的一种p 2 p 流量优化技术架构，p 4 p 技术架 构由隶属于分布式计算产业联盟( d i s t r i b u t e dc o m p u t a t i o ni n d u s t r i a l a s s o c i a t i o n ，d c i a ) 下的p 4 p 工作组( p 4 pw g ) 提出。p 4 p 工作组是由d c i a 的成员公 司p a n d o 2 2 n e t w o r k s 和v e r i z o n 在2 0 0 7 年7 月发起并且成立的，由d c i a 赞助，按 照同业公会方式运作。p a n d on e t w o r k s 和v e r i z o n 被选为共同主席。具体研究工作 主要由y a l eu n i v e r s i t y 承担。 p 4 p 技术思想：提出在i s p 和p 2 p 应用之间进行通信和协作来优化p 2 p 的网络流量 和性能。p 4 p 提出了明确的目标，即允许p 2 p 应用与i s p s 之间有效地进行合作，在 提高p 2 p 应用的高性能的条件下更加合理公平有效的利用网络资源。文献 5 指出 以往经验：网络服务提供商或者p 2 p 应用单方面提高网络效率的方法都不太有效， 并且认为纯粹基于本地化的链接也可能存在问题。文献 4 9 ，5 0 指出首先，本地化 河南大学硕士研究生学位论文第3 页 可能导致流量集中在某几条拥挤的骨干线路上。其次，在网络带宽差异较大的网 络中时，选择延时较短或路由跳数较小的网络节点可能也会导致跨域的连接。第 三，对于域间流量不可避免的情况( 比如有效内容分布在其它域) ，纯本地化方 式由于很少考虑代价问题，可能会导致用户选择昂贵的线路，因而产生较高的跨 域成本。p 4 p 架构提出在i s p 网络中部署一种称之i t r a c k e r 的设备，这种设备收集 i s p 的网络信息，并提供与p 2 p 应用交互通信的接口。这些接口包括静态网络策略、 反映网络状态的p 4 p 距离( p 4 p d i s t a n c e s ) 、网络能力( 如c a c h e 等) 。这些接口能够 支持外部应用程序获得i s p 网络的相关信息，与此同时保护了网络运营商的隐私， 从而实现了网络运营商和p 2 p 服务商联合优化他们各自的网络性能的目的。 p 4 p 技术 4 正处于发展阶段，目前的研究工作仍集中在控制平面，对数据平面、 管理平面尚未涉及。为了加快p 4 p 应用技术的前进步伐，必须设计开发适用于p 4 p 技术下的路由协议，从实现的复杂性考虑，改进已有的p 2 p 路由协议是最快捷的方 式，所以设计p 4 p 下的路由协议需要针对目前p 2 p 路由协议的研究现状所存在的问 题，根据p 4 p 控制面板中i t r a c k e r s 所提供的关键技术特点，来研究设计p 4 p 下的路 由协议。 p 2 p 1 ，4 7 路由协议研究现状 3 ：为了在p 2 p 网络中有效的发现资源，人们对 p 2 p 搜索技术做了大量的研究，资源搜索算法 5 4 是p 2 p 搜索技术的核心，对于系 统的性能往往有决定性的影响。从最初以n a p s t e r 5 5 为代表的有中央目录服务器 的集中式对等网络结构，发展到后来以g n u t e l l a 6 为代表的完全分布式的非结构 化对等网络f l o o d i n g 1 0 ，5 1 、r a n d o m w a l k 1 1 ，4 8 3 、s u p e r n o d e 1 2 ，再到以 c a n 2 ，5 2 、c h o r d 7 、p a s t r y 8 和t a p e s t r y 9 等为代表的基于分布式哈希表的 结构化对等网络。p 2 p 搜索算法与所采用的p 2 p 网络拓扑结构密切相关，拓扑结构 在很大程度上决定了它所采用的搜索算法。目前主要从p 2 p 网络的结构以及采用的 算法两方面进行研究。p 2 p 网络可分为两类：结构化网络和非结构化网络。对于结 第4 页河南大学硕士研究生学位论文 构化p 2 p 网络多采用基于分布式哈希表d h t 的单播方式的对象定位，对于非结构化 p 2 p 网络往往采用基于洪泛搜索 1 0 的机制。 在结构化网络中每个节点存储的信息与网络拓扑结构有关，通过映射完成，查 找采用基于d h t 分布式散列路由搜索算法。而非结构化网络则与网络拓扑无关，其 节点可任意存储信息，查找采用基于广度优先 4 8 的搜索算法及其改进算法。 结构化p 2 p 1 对等网络模型是一种采用纯分布式的消息传递机制和根据关键 字进行查找的定位服务模型，目前的主流方法是采用分布式哈希表d h t 2 技术。 这也是目前扩展性最好的p 2 p 路由方式之一。分布式哈希表d h t 是一个广域范围内 大量节点共同维护的巨大散列表。散列表被分割成不连续的块，每个节点被分配 给一个属于自己的散列块，并成为这个散列块的管理者。在d h t 技术中 5 3 ，网络 节点按照一定的方式分配一个唯一的节点标识符，资源对象通过散列运算产生一 个唯一的资源标识符。当需要查找该资源时，通过散列运算可定位到存储该资源 的节点p e e r 。这种机制的优点体现在： ( 1 ) 查找效率高、速度快。由于d h t 采用了确定性拓扑结构，可以提供精确、快 速的资源发现，只要目的结点存在于网络中，d h t 总能发现它： ( 2 ) 避免了单节点失效问题。出于冗余度以及延时的考虑，大部分d h t 总是在节 点的虚拟标识与关键字最接近的节点上复制备份冗余信息，这样也避免了单一节 点失效的问题。 它们克服了非结构化p 2 p 系统洪泛式查找的不足，提高了信息搜索效率。但因 为现有结构化p 2 p 系统以节点之间的逻辑关系构造拓扑结构，很少考虑节点的物理 邻接关系，所以存在物理位置局部性。节点进行资源定位时，查找与自己在逻辑 上相邻的节点，而它们在物理上并不一定相邻，虽然p 2 p 应用还可以采用自身的探 测技术和机制调整选择流量走向，但这种方式存在较大的弱点： ( 1 ) p 2 p 应用自身需要采用逆向流量工程推测( p r o b e ) 底层网络状态，比如发 出探测消息以推测目前拓扑信息、拥塞程度、链接开销等，它依赖网络测量技术， 河南大学硕士研究生学位论文第5 页 而目前的测量技术本身就耗费网络带宽资源，且不能完全反映网络真实状态，而 i s p 运营商的策略信息( 哪些1 i n k 昂贵不适合用p 2 p 应用，那些i s p 之间的l i n k 开销 便宜等) 逆向工程无法推测。因此，将导致整个网络的路由延迟 5 6 变大。 ( 2 ) 节点在访问资源时存在访问局部性，即总是多次访问相同资源，若在不 考虑该特性的情况下构造p 2 p 系统，就会降低其在延迟、拥塞等方面的性能。 本文针对现有结构化p 2 p 路由算法存在重叠网络和物理拓扑不匹配带来的搜 索效率低，过度消耗网络资源，物理位置和访问资源的局部性等缺点，利用p 4 p 技 术方便感知网络拓扑信息特点，在结构化p 2 p 路由算法中找出一种相对比较适用于 p 4 p 下的路由算法一p a s t r y 算法，以结构化拓扑结构为基础，采用p a s t r y 协议，提 出了一种新的p 4 p 路由算法一p 4 p - p a s t r y 路由算法。 1 3 研究内容 主要研究内容如下： 论述了p 2 p 的基本概念，介绍了p 4 p 技术及现状；论述了p 2 p 路由协议的发 展及路由算法。 一 详细论述了p 2 p 路由算法，分析了现有p 2 p 算法的优缺点，着重介绍p 4 p 技 术的研究内容和研究现状。 提出了基于p 4 p 技术的p a s t r y 路由算法，使p 4 p 下的p a s t r y 算法性能有所 提高，该算法提高了本地化下载的比率，提高数据的交换速率，减少了网络中不 必要的跨域流量，减少骨干链路的负载。 对现存的p a s t r y 进行分析比较，选择o v e r s i m 模拟器对算法进行模拟，通过 模拟结果进行分析比较。 第6 页河南大学硕士研究生学位论文 1 4 论文结构 论文的具体安排如下： 第一章是绪论，概要的介绍了课题来源、研究目的和意义、国内外研究现状、 本文的工作和本文的论述结构。 第二章介绍了p 2 p 网络的相关背景知识技术。在p 2 p 网络中，分析p 2 p 网络的 拓扑模型，资源搜索算法基本原理和发布技术，并介绍了目前几种比较流行的p 2 p 路由协议；然后介绍了结构化网络p 2 p 路由协议和非结构化p 2 p 路由协议的经典 案例，总结比较了两者的优缺点；重点介绍了p a s t r y 路由算法。 第三章重点介绍了p 4 p 技术产生的概念，介绍了p 4 p 的相关背景和知识技术。 在p 4 p 技术中，分析了p 4 p 技术的基本原理，p 4 p 技术的框架结构；然后详细介 绍了p 4 p 技术控制面板中的i t r a c k e r 接口内容，重点介绍了p 4 p 的核心构件 p 4 p - d i s t a n c e 接口以及该接口设计背后的理论基础；介绍了通过仿真实验和在 p l a n e t l a b 上真实的互联网实验，评估了p 4 p 效果。 第四章详细描述了一种基于p 4 p 网络技术的路由算法：p 4 p - p a s t r y 。结合第二 章对结构化p a s t r y 路由算法的分析以及第三章p 4 p 关键技术的优点，并在结构化 p 2 p 路由算法中找出一种相对比较适用于p 4 p 下的路由算法- - p a s t r y 算法，以结 构化拓扑结构为基础，采用p a s t r y 协议，提出了一种新的p 4 p 路由算法 p 4 p p a s t r y 路由算法，最后通过o v e r s i m 平台的对网络仿真进行模拟分析。 最后对论文的工作进行总结和展望。 本章小结 本章首先概要的介绍了课题来源、研究目的和意义，分析了国内外的研究现状， 最后介绍了本文的工作和论文的具体安排。 河南大学硕士研究生学位论文第7 页 2 1 p 2 p 概念 第二章p 2 p 路由协议分析 p 2 p ( p e e rt op e e r ) 从字面意思上可以理解为点对点或者是对等互联网络，从网络 上p 2 p 可以被定义为：它是在i n t e m e t 上通过各系统之间的直接交换来共享计算资源 和服务的一种应用模式。而这些资源通常指的是i n t e m e t 边界的存储、c p u 、信道、 内容和现场等。p 2 p 网络则是支撑这些应用，并且运行在不稳定连接、不可预知i p 地址和在域名服务器之外等环境下，具备有效自组织和独立生存能力的网络。p 2 p 网络打破了传统的c l i e n t s e r v e r ( c s ) 模式，在网络中的每个节点的地位都是对等 的。每个节点既能够充当服务器，向它节点提供网络服务，同时还能够享用其它 节点所提供的网络服务。 2 2p 2 p 路由协议 p 2 p 路由协议研究现状 1 】：为了在p 2 p 网络中更加有效的发现资源，国内外专 家学者对p 2 p 搜索技术做了大量深入的研究。目前主要从对等网络的拓扑结构特 点以及采用的算法两方面进行研究，对等网络可分为两种：无结构对等网络和基 于分布式哈希表的结构化对等网络。非结构化的p 2 p 网络则与网络拓扑无关，其 节点可任意存储信息，查找采用基于广度优先的搜索算法和其改进算法，非结构 化p 2 p 网络主要采用洪泛搜索机制，虽然可以支持灵活的查询，但可扩展性不好， 搜索效率低。在结构化p 2 p 网络中每个节点存储的信息与网络拓扑结构有关，通 过映射完成，查找采用基于d h t 分布式散列路由搜索算法。结构化p 2 p 网络被广 泛应用于大规模的分布式存储和信息检索领域，解决了非结构化网络的搜索效率 第8 页河南大学硕士研究生学位论文 低和扩展性不强等问题。但是结构化p 2 p 网络也存在重叠网络和物理拓扑不匹配 带来的查找延迟大和搜索效率低等缺点。 2 2 1 非结构化p 2 p 路由算法 洪泛算法 在网络中，每个节点都不知道其他节点的资源信息，当要查找某个文件时，把这 个查询信息传递给它相邻的网络节点。如果相邻的网络节点含有这个资源，就返回 一个q u e r y h i t 的信息给资源请求者。如果它相邻的网络节点都没有这个被查询文 件所想要的资源，就把这条消息转发给它相邻的网络节点。这种传播的方式像洪水 在网络中的各个节点流动一样所以称之f l o o d i n g 搜索。 随机漫步算法 由于洪泛机制带来大量的网络消息开销，一些研究者提出使用随机搜索技术来 进行文件搜索。标准的随机搜索是指网络中各节点将搜索消息转发给他们随机选 择的与其自身相邻的一个网络邻居。采用k 路随机转发机制，当开始搜索节点时，要 产生k 个搜索消息，然后发送给他们随机选择的k 个邻居，之后每个消息在网络中独 立地进行随机转发，并周期性地与初始结点联系以决定是否继续转发该消息。 超级节点思想算法 g n u t e l l a 2 6 建立超级节点( s u p e rn 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 的索引表中寻找：假如找 到了该文件，则直接根据该文件所存储的计算机的i p 地址建立连接：假如没有找到 该文件，则s u p e r n o d e 把这个查询请求消息发送给自己连接的其它超级节点，直到 s u p e r n o d e 得到想要的资源结束。 非结构化p 2 p 路由算法总结：由于非结构化p 2 p 网络将重叠网络认定为是一 个完全随机图，网络节点之间的链路没有按照某些事先定义的拓扑来进行构建。 河南大学硕士研究生学位论文第9 页 非结构化网络一般不能够提供性能保证，但此类系统支持复杂查询，容错性较好， 当节点频繁加入和退出系统时，非结构化网络所受的影响较小。但是查询速度较 慢，非结构化p 2 p 网络采用洪泛机制进行查询，对网络带宽的消耗非常大，并引 起可扩展性差问题。目前针对此类结构，研究主要集中于改进发现算法和复制策 略以提高发现的准确率和性能。 2 2 2 结构化p 2 p 路由算法 c a n 算法 c a n 是基于d 维笛卡儿空间来组织数据和查询数据。整个坐标空间动态地分配 给系统中的所有节点，每个网络节点和其它网络节点都拥有一块独立的互不相交 的区域。每个c a n 节点都保存一张坐标路由表，其中包括它的邻接节点的i p 地址 和虚拟坐标区域。每条c a n 消息都包括目的节点坐标。路由时网络节点只需要朝 着目标节点的方向把请求消息转发给自己的相邻的网络节点就行了。 c h o r d 算法 c h o r d 使用一致性哈希作为哈希算法，并对一致性哈希算法进行了优化。c h o r d 系统定义了一维的路由机制。系统中，所有的网络节点按照d h t 映射的i d 被分布 在一个环上( c h o r d 环) 。根据 关键字，k 的文件信息被存储在工d 为v 的节 点上假如该节点不存在，那么就存储在i d 号大于v 的最小的节点上此节点成 为v 节点的后继节点。当节点搜索网络资源时，根据 表得到v 的值节点 就向自己表中小于或者等于v 的最大值节点发送查找请求。接收请求的节点是v 的后继节点，就响应请求，并查找请求节点所需的网络资源，如果没有所需资源， 则以上面同样的方式处理查找请求消息。 p a s t r y 算法 p a s t r y 是微软和r i c e 大学共同发起的结构化p 2 p 算法。在该系统中，每个节 点有一个d h t 映射的标识号工d ，并且维护一个邻居集和一个叶子集和一个2 bn l o g 第10 页河南大学硕士研究生学位论文 行，2 b 一1 列的路由表。当进行查找时，首先在叶子集中查找，如果k e y 落入叶子 集中的i d 范围之内，查找消息就被转发到在数值上最近i d 的节点上，否则，从 路由表中选择一个比现有节点具有匹配更多共同前缀的节点号，并把该查找消息 转发给这个节点，进行一步的查询，假如仍然没有找到，则在邻居表寻找其一个 与其在查找节点物理上相近的节点，转发该消息。 t a p e s t r y 算法 t a p e s t r y 的思想来源于p l a x t o n 树，路由表第i 行记录n o d e l d 与自己前i - l 位相 同，第i 位不同且互不相同的2 6 1 个节点( n o d e l d 看作是基于2 6 的整数) 。在 p l a x t o n 中，节点使用自己所知道的邻近节点表，按照目的i d 来逐步传递消息。 t a p e s t r y 基于p l a x t o n 的思想，加入了容错机制，从而可适应p 2 p 的动态变化的特 点。t a p e s t r y 的路由机制和p l a x t o n 类似，它的查找复杂度为0 ( 1 0 9 n ) 。t a p e s t r y 中 每个节点还维护一张后向指针( b a c kp o i n t e r ) 列表指向把自己作为邻居的那些节点， 在节点退出算法中会用到这些指针。 结构化p 2 p 路由算法总结： 优点：结构化p 2 p 拓扑能够自适应节点的动态加入退出，并具有较好的容错 性，有着良好的可扩展性、被广泛应用于大规模的分布存储、信息检索领域。并 且由于重叠网络采用确定性拓扑结构，d h t 可以提供精确的发现。 缺点：d h t 这类结构最大的问题是d h t 的维护较为复杂和繁琐，尤其是因网 络中节点的频繁加入和退出造成的网络波动大大增加了维护的代价。除此之外， d h t 还不支持内容语义等复杂查询，仅支持精确关键词匹配查询。最关键的问题， 结构化p 2 p 网络是构建在于物理网络拓扑之上的一层o v e r l a y 网络不考虑物理网 络的拓扑结构，从而导致覆盖网与物理拓扑不匹配，导致了较大的网络延迟。 河南大学硕士研究生学位论文第11 页 2 3p a s t r y 路由协议原理 在p a s t r y 算法中，每个网络节点都拥有一个由d h t 映射的全局惟一的n o d e l d 。 而网络中的资源则由相同的机制映射成唯一的k e y 值。两者位于统一命名空间中。 在路由过程中，p a s t r y 把所要求的查询请求路由到与其键值最为接近的那个节点 上。具体说来，当网络节点收到查询资源的k e y 后，把消息转发到下一个n o d e l d 与k e y 更为匹配的网络节点上，也就是说和当前节点进行比较，至少有更长的1 位前缀与目标资源的k e y 相同的网络节点。如果这样的节点不存在，则当前网络 节点把消息发送到下一个n o d e l d 与目标资源k e y 匹配，如此不断递进，直到到达 目的节点为止。图2 - i 为p a s t r y 的路由算法示意图。为了实现路由，每个网络节 点保存一份路由表、一份邻近节点集和子叶集，其中子叶集保存的是在节点命名 空间上与当前网络节点相邻的网络节点。图2 - 2 为一个n o d e i d 号为1 0 2 3 3 1 0 2 的 网络节点的路由表，其中行数为l 0 9 2 ，列数为2 6 ，b 是系统配置参数，通常取3 或4 ；n 是所在p 2 p 网络的节点数。从图2 可知，路由表中的第n 行第m 列的元素 代表的是与当前网络节点的n o d e l d 拥有相同的n 个前缀字符，而第n + 1 个n o d e i d 字符为m 的节点。叶子集分为两个子部分，ilj 2 的节点的n o d e l d 在数值上小于 当前网络节点，fll 2 的节点的n o d e l d 在数值上大于当前网络节点。l 通常取值 为8 。 第1 2 页河南大学硕士研究生学位论文 图2 一lp a s t r y 的路由过稗 l 。；兰j 二 5 兰蔷爿；篓；b ll t c 3 j 二l “c 1 ：io ：t ：i 一l l 3 ，l1 ”l “：j j ：”i1 d ：j 】二j ：l h lc “l 二：= ：o ：l ：j 3 1 3 1 ：，；：0 ；1 n ：3 ，i ：3 0 3 1 3 - 0 2 ： 4 ：。3l * 7 3 2 ：n ：i2 l f - ；2 3 3 0 = l lo 0 ：3 _ | l o ：；o ：1日：l i 。o ：1e i ：二l - o o t ；t w 1 d ”。lj l l o ：3 j “o 1 i o ：3 一：，i o il i ) - o ii f 2 l 、e i # c ： i 尝蒹i 誊黑i 萎篆一鉴3i 图2 吧p a s t r y 的路由表 p a s t r y 算法与c h o r d 算法和c a n 算法相比，p a s t r y 算法引入了叶子节点和邻 居节点集合的概念。在应用层能够及时准确地获得这两个集合的节点信息时，可 以大大加快路由查找的速度，同时降低因路由引起的网络传输开销：在路由信息 正确的前提下，p a s t r y 路由算法的期望跳数为 1 0 9 ，因此p a s t r y 在控制路由跳 数上是高效的。并且p a s t r y 路由算法利用了成熟的最大掩码匹配算法，实现时可 以利用很多现成的软件算法和硬件框架，可以获得很好的效率。然而p a s t r y 算法 以节点之间的逻辑关系构造拓扑构，很少考虑节点的物理邻接关系，所以存在物 理位置局部性。当节点查找资源时，它们仅仅查找与他们逻辑相邻的节点，而不 考虑实际节点间的物理位置。因为p a s t r y 算法缺乏感知网络拓扑信息，所以无法 提供任何机制控制节点闻的距离跳数，然而，p 4 p 技术具备方便的感知网络拓扑信 息和计算节点间的通信成本等特点，p 4 p 技术的应用正好能弥补p a s t r y 感知网络 拓扑信息差这一缺陷。这是本文提出p 4 p 技术下p a s t r y 算法的着眼点。 河南大学硕士研究生学位论文第13 页 本章小结 目前流p 2 p 己经成为一种流行的网络技术，在许多领域得到了广泛的应用。本 章首先介绍了p 2 p 网络的相关背景知识技术。在p 2 p 网络中，分析p 2 p 网络的拓 扑模型，资源搜索算法基本原理和发布技术，并介绍了目前几种比较流行的p 2 p 路由协议；然后介绍了结构化网络p 2 p 路由协议和非结构化p 2 p 路由协议的经典 案例，总结比较了两者的优缺点，然后重点介绍了结构化p 2 p 下p a s t r y 路由算法； 第14 页河南大学硕士研究生学位论文 3 1p 4 p 引言 第三章p 4 p 介绍 现在我们着重关注于互联网上的交通管制问题，网络应用程序( 例如，网络资 源的用户) 如何公平有效地利用网络提供商提供的网络资源。这个问题尤其重要， 因为它在网络效率，网络经济学，应用程序性能方面有着至关重要的影响。 在目前的互联网，网络服务主要由网络提供商负责网络交通控制( 即互联网服 务供应商) 。应用程序仅仅明确说明网络交通的目的地址，网络提供商使用最佳 的网络交通工程学来确定路由，如实现高效路由或者负载平衡，以达到经济节能 的目的；网络提供商也可以通过控制网络反馈到t c p 来管制应用程序的网络传输 速率。 随着p 2 p 应用的兴起，然而，也对互联网交通控制带来了新的挑战。假设一个 p 2 p 客户端对一个资源数据感兴趣，他能够从一些资源节点下载资源，所以在选择 资源节点的时候有很大的灵活性。灵活性是p 2 p 点对点模式健壮性和可扩展性的 关键因素之一。 然而灵活性也从根本上改变了网络流量的控制问题：在传统的模式中，网络流 量控制问题通常是在给定的网络交通需求格局中完成的；在新的模式中，能满足 应用程序所需的资源有很多，因此存在多种下载方式，因此每一种下载方式产生 不同的需求模式，从而网络的效率可想而知。许多p 2 p 应用程序正被大量的网络 忽略，大量的p 2 p 应用程序可能引起网络效率的降低。 首先，对于域内，大量存在的p 2 p 应用程序可能会导致网络交通混乱，许多 p 2 p 应用程序可能频繁穿越i s p 的内部网络。例如，在我们所做的测试中，v e r i z o n 网络显示平均p 2 p 每传送1 位，进行5 5 跳，穿越1 0 0 0 公里，在p 4 p 的测试中， 我们在不降低应用程序性能的前提下，我们可以把相应跳数减少到0 8 9 跳。 河南大学硕士研究生学位论文第15 页 其次，对于域间，p 2 p 应用程序可能会产生大量的跨域传输 1 3 或在网络供应 商之间中继转发数量可观的数据流量 1 4 。在参考文献 1 3 中，k a r a g i a n n i s 等， 研究了b it t o r r e n t 在一所大学的使用状况。他们发现5 0 一9 0 大学生大量使用 p 2 p 进行资源下载。即使层层供应商不需要付费于网络供应商，但是p 2 p 网络交通 可能引起p 2 p 之间的网络流量失衡并导致潜在的违反对等协议。这种低效率的域 间流量可能会严重干扰i s p 的经济。 最后，p 2 p 的动态网络交通分配模式并不一定能够享有与网络流量工程的协同 共存 1 5 ，1 6 网络供应商会竭尽全力来估计交通模式，并决定以此为基础的 路由选择，但是所有这些努力可能会