（计算机应用技术专业论文）一种优化的p2p网络资源定位方法.pdf

南京邮电大学硕上研究生学位论文 摘要 摘要 随着i n t e r n e t 的发展，传统的c s 模式已不能满足新业务( 如实时业务和多媒体内容分 发等) 的需求。主要原因是c s 模式在信息资源共享方面，会导致中心失效和硬件资源不 能充分利用。为满足这些新业务的需求，出现了另一种网络模式- - p 2 p 。在p 2 p 中，网络中 的每个结点都是对等的，即每个结点既充当服务器，为其他结点提供服务；又充当客户端 享用其他结点提供的服务。 p 2 p 模式以其分布式管理、高效路由、容错性强和可扩展等优秀性能给信息社会带来 一股新的活力，但也存在着很多技术难点，如资源定位、负载均衡等。在资源定位方面， 当前主要有两种方法：泛洪算法( f l o o d i n g ) 和基于分布式哈希表( d h t 类) 的方法。其中 f l o o d i n g 算法随着节点数目的增长，系统开销呈指数倍增长，产生的广播数据将很快耗尽 网络资源。为解决这个问题，出现了多种流量控制的算法，但都未有突破性进展。因而很 多研究集中在d h t 方法上，其中m i t 提出的c h o r d 算法在网络拓扑结构频繁变动的环境中仍 然可以获得较好的性能。 结构化p 2 p 网络是构建于物理网络拓扑之上的一层o v e r l a y 网络，两者之间通过h a s h 散 列函数来映射。这种h a s h 关系使得节点的逻辑i d 号独立于节点的物理位置及节点的共享文 件。但经过h a s h 作用后，破坏了节点的位置信息，来自同一子网的节点可能会相距很远， 这不利于查询性能的优化。本文提出一种改进的分布式哈希表( d h t ) 资源定位技术，将非 结构化对等网络引入到结构化的c h o r d 网络中，每个节点保存少量的邻居节点和友元节点 信息，利用节点在物理网络上的邻近性和节点之间兴趣的相似度来提高查询效率。仿真结 果表明，该技术在路径长度和访问延迟方面的性能要优于原c h o r d 算法。 关键词：p 2 p ，c h o r d 算法，兴趣聚类，邻居聚类 南京邮电大学硕：l 研究生学位论文 a b s t r a c t a b s t r a c t w i mt h ed e v e l o p m e n to fi n t e r n e t ，t h e r ea p p e a rm a n yd r a w b a c k so fc sm o d e li n i n f o r m a t i o na n dr e s o b r c es h a r i n g a m o n gt h e m ，t h em o s tt y p i c a lp r o b l e m sa r ec e n t r a l i n v a l i d a t i o na n di n s u 伍c i e n tu t i l i z a t i o no fh a r d w a r er e s o u r c e o nt h eo t h e rh a n d ，m u l t i m e d i a b a s e di n t e m e tt r i g g e rt h ep r o l i f e r a t i o no fa n o t h e rn e t w o r km o d e lc a l l e dp 2 pm o d e l e v e r yn o d e i np 2 pm o d e li sp e e rt oa n yo t h e re l s e e a c ho n ec a nb et r e a t e da sas e r v e rt op r o v i d es e r v i c et o o t h e rn o d e sa n dg a i nt h es e r v i c ep r o v i d e db yo t h e r s p 2 pm o d e lm o t i v a t e st h ei n f o r m a t i o nn e t w o r kb yi t se x c e l l e n tp e r f o r m a n c es u c ha s d i s t r i b u t e dm a n a g e m e n t ，h i g hp e r f o r m a n c er o u t i n g , f a u l tt o l e r a n c ea n ds c a l a b i l i t y b u tt h e r e e x i s t sm a n yc h a l l e n g e ss u c ha sr e s o u r c el o c a t i o n , l o a db a l a n c i n g , e t c a l le x i s t i n gs e a r c h m e t h o dc a nb ec l a s s i f i e di n t ot w oc a t e g o r i e s ：f l o o d i n ga n dd h tb a s e d g n u t e l l ai sat y p i c a l f l o o d i n gp r o t o c 0 1 b u tb a n d w i d t hw o u l dq u i c k l ye x h a u s tb yb r o a d c a s td m a g r a mw i t ht h e g r o w t ho fi n t e r n e ta p p l i c a t i o n s a l t h o u g hm a n ye f f o r t sh a v eb e e np u to nc o n t r o l l i n gt h e b r o a d c a s tp a c k a g et os o l v et h ep r o b l e m ，i ti sv e r yd i f f i c u l tt ol i m i tt h ee x p o n e n t i a lg r o w t ho f o v e r h e a dl e a db yu s e ri n c e n s e m e n t s o ，m a n ys t u d i e st u r nt od h t c h o r dp r o p o s e db ym i ti s f e a t u r e dw i t hi t sh i 曲p e r f o r m a n c ei nt h ee n v i r o n m e n tw i t hl a r g eo s c i l l a t i o n s t r u c t u r e dp 2 pn e t w o r k sc r e a t eav i r t u a lt o p o l o g yo nt o po ft h ep h y s i c a lt o p o l o g y t h e o n l yr e l a t i o nb e t w e e nt h e mi st h eh a s h i n g , w h i c hm a k e st h en o d e sl o g i c a li di n d e p e n d e n to fi t s p h y s i c a ll o c a t i o na n ds h a r e df i l e s b u tt h i sh a s h i n gb r e a k st h en o d e sl o c a t i o ni n f o r m a t i o n ， w h i c hi sn o tc o n d u c i v et ot h eo p t i m i z a t i o no fq u e r yp e r f o r m a n c eb e c a u s et h en o d e si nt h es a m e s u b n e tw o d db ew i d ea p a r tf r o mo t h e r s t h i st h e s i sp r e s e n t sa na d v a n c e dd h tr e s o u r c e l o c a t i o nt e c h n i q u e e a c hp e e rm a i n t a i n si n f o r m a t i o no fas m a l ln u m b e ro fn e i g h b o r sa n df r i e n d s t h i sm e t h o di n t r o d u c e su n s t r u c t u r e dp 2 pt oc h o r d ，m a k i n gt h eb e s to ft h el o c a l i t yb o t hi nt h e u n d e r l y i n gp h y s i c a ln e t w o r ka n dt h ei n t e r e s ta m o n gp e e r s s i m u l a t i o nr e s u l t ss h o wt h a tt h i s s c h e m ei so u t p e r f o r mt h eo r i g i n a lc h o r di nt e r m so fp a t hl e n g t ha n da c c e s sl a t e n c y k e y w o r d s ：p 2 p , c h o r da l g o r i t h m ，i n t e r e s tc l u s t e r i n g , n e i g h b o rc l u s t e r i n g i i 南京邮电大学硕士研究生学位论文图表目录 图l l 图1 2 图l 一3 图l 一4 图1 5 图l 一6 图2 一l 图2 _ 2 图2 3 图2 4 图2 - 5 图2 6 图孓_ 1 图3 - 2 图 图3 一 图3 - 5 图 图3 7 图4 一l 图4 2 图4 3 图4 4 表l l 表2 一l 表2 2 表3 一l 表3 - 2 表3 - _ 3 图表目录 c s 模式2 p 2 p 模式一2 n a p s t e r 结构3 o n u t e l l a 泛洪示意图4 含s u p e m o d e 的半分布式结构5 度数和直径之间的渐进曲线关系9 h a s h 示例12 c h o r d 算法数据组织实例l3 节点加入后示意图1 4 c a n 算法坐标空间划分示例1 5 t a p e s t r y 算法中节点的邻居映射表1 8 p a s t r y 算法中节点数据结构示意图2 l 2 “个节点的饱和的网络2 8 饱和网络的c h o r d 算法查找过程2 9 不饱和网络示例一3 0 不饱和网络的杏询过程示例3 1 邻居节点个数和路由效率之间关系3 4 n 8 的友元节点和潜在的友元节点3 7 改进后查询过程一3 8 p l a n e t s i m 系统架构4 3 在不同规模的网络中友元节点命中率4 5 不同规模的网络中查询路径长度比较4 6 不同规模网络中查询时延比较4 6 四种不同结构p 2 p 系统性能一5 c h o r d 算法中指针表项含义1 3 五种d h t 算法的性能比较2 4 饱和网络中n 8 的f i n g e rt a b l e 2 9 不饱和网络中n 8 的f i n g e r t a b l e 3 0 改进后n 8 的f m g e rt a b l e 3 8 5 1 南京邮电学院学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研 究工作及取得的研究成果。尽我所知，除了中文特另t l d h 以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得南京邮电学院或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 研究生签名：塑螽蕴日期：皇! ! = 2 ：垒：! ! 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保 留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印 或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊 登) 授权南京邮电学院研究生部办理。 研究生签名：j 肆 日期：业 镌7 鼍 南京邮电大学硕士研究生学位论文第一章绪论 1 1 研究背景和意义 第一章绪论 随着i n t e m e t 的发展，c l i e n t s e r v e r ( c s ) 模式在信息资源共享方面的缺陷越来越明 显。中心失效和硬件资源得不到充分利用是目前c s 模式存在的两个严重的问题。由于 c s 模式存在着这两个缺陷促使了另一种网络模式p e e r - t o p e e r ( p 2 p ) 模式迅速发展。 p 2 p 是一个新名词，却也并不是一个全新的概念。1 9 6 9 年4 月7 日发布的第一份网 络互联标准文档r f c l 中讨论的网络应用就非常接近我们现在所谓的p 2 p 风格。而早在 因特网出现之前，u n i x 主机上广泛流行的u s e n e t 也是一个典型的p 2 p 结构。u s e n e t 产生于1 9 7 9 年，是一种分布式系统，能够为各个地方提供新闻组。u s e n e t 的最初雏 形是由两名研究生t o mt r u s c o t t 和j i me l l i s 实现的。当时文件都是通过电话线批量传送， 且常常选在长途费用比较低的夜间进行。如果采用集中式的控制管理方法将效率低下， 因此他们提出了一种分散、分布式的管理方法。这正是我们描述的p 2 p 模式。u s e n e t 非常成功，至今都还有着众多的用户。 早期p 2 p 应用另一个杰出的代表就是f i d o n e t ，它和u s e n e t 类似，也是一个分散、 分布的信息交换系统。t o mj e n n i n g s 于1 9 8 4 年创建 f i d o n e t 系统，让不同b b s 系统中 的用户互相交换信息。这种技术很好地满足了用户的需要，发展迅速，并一直沿用到 今天。 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源( 处理能 力、存储能力、网络连接能力、打印机等) ，这些共享资源需要由网络提供服务和内容， 能被其它对等节点( p e e r ) 直接访问而无需经过中间实体。在此网络中的参与者既是资源 ( 服务和内容) 提供者( s e r v e r ) ，又是资源( 服务和内容) 获取者( c l i e n t ) 。 p 2 p 打破了传统的c l i e n t s e r v e r ( c s ) 模式，在网络中的每个结点的地位都是对等 的。每个结点既充当服务器，为其他结点提供服务，同时也享用其他结点提供的服务 【l 】。p 2 p 与c s 模式的对比如图1 1 和图1 2 所示： 南京邮电大学顺士研究生学位论文 第一章绪论 围12p 2 p 模式 近儿年来对p 2 p 的研究迅速升温，各方面的应用层出不穷。特别是它提供无穷的 存储空间以及不受限制的传输容量，这是传统中央服务器所无法比拟的。p 2 p 的是 将网络中不同计算机连接在一起，并充分利用互联m 和w c b 站点中任何闲置资源。p 2 p 号称自身就等同于网络，新术语s c r v c n t ( s c r v e r + c l i e n t ) 正伴随着网络计算领域的新机遇 出现在我们面前。 从c s 模式至j p 2 p 模式的发展，i n t c m e t 上的共享行为被提升到了一个更高的层次。 这对我们解决很多难题都是一个良好契机，p 2 p 正在改变互联网中各成员问的能力平 衡，并使构成互联网的大多数计算机的能力得到发展，在分布计算、协同工作、搜索 引擘、文件交换等方面有着广泛的应用前景。 1 2p 2 p 资源定位方法的研究现状 由十p 2 p 技术蕴含着巨大的商业价值，许多学术机构和大公司投a n p 2 p 技术的研 南京邮电大学 藐士研究生学位论文蔓l 垡 究领域之中。在一个缺少集中化服务器的动态网络环境中，如何定位资源是p 2 p 技术 需要解决的首要问题。由于资源分散在p 2 p 网络中各个节点上，而节点又频繁的加入 或退出恤2 p 网络处于不断的变化之中；另外p 2 p 网络的规模一般都很大，而且会不 断扩展。因为p 2 p 网络内节点的动态性和巨大的网络规模，设计一个好的搜索方法比 较困难。为了在p 2 p l i 目络中有效地进行资源定位，国内外学者主要从两个方面来研究 p 2 p 搜索问题：一个是通过改变p 2 p 网络结构o 】【w 1 4 1 ，达到提高搜索效率的目的。另一 个是优化现有的一些搜索方法嗍嗍川。 1 2 1p 2 p 网络中的拓扑结构研究 拓扑结构是指分布式系统中各个计算单元之闻的物理或逻辑的互联关系，结点之 间的拓扑结构一直是确定系统类型的重要依据。p 2 p 系统一般要构造一个非集中式的 拓扑结构，在构造过程中需要解决系统中所包含的大量结点如何命名、组织以及确定 结点的加入离开方式、出错恢复等问题。 根据拓扑结构的关系可以将p 2 p 研究分为4 种形式埘：中心化拓扑( c e n t r a l i z e d t 0 p 0 1 0 科) ；全分布式非结构化拓扑( d e c e n t r a l i z e d u n s t r u c t u r e d t o p o l o g y ) ：全分布 式结构化拓扑( d e c e n t r a h z e ds t r u c t u r e d t o p o l o g y ，也称作d h t 网络) 和半分布式拓扑 ( p a r t i a l l y d c c c n t m l i z l t o p o l o g y ) 。 其中，中心化拓扑擐大的优点是维护简单发现效率高。在这种网络中，文件资源 存储在各个客户端上，而不是存储在服务器上。索引服务器存放了当前该共享网络中 所有共享文件资源的索引信息。由于资源的发现依赖中心化的目录系统，发现算法灵 活高效并能够实现复杂查询。最大的问题与传统客户机服务器结构类似，容易造成单 点故障，访问的“热点”现象和法律等相关问题，这是第一代p 2 p 网络采用的结构模 式，经典案例就是著名的m p 3 共享软件n a p s i 。 圈1 3n a p s t e r 结构 童塞竖里丕兰塑主堡塞竺兰竺丝三苎二皇堕丝 全分布非结构化网络中每个端点的功能和地位都是相等的，没有一个端点知道整 个网络的结构或者组成网络的每个端点的身份。采用了随机图的组织方式，结点度数 服从一p o w 仃- l a w ”规律，因此能够较快发现目的结点，面对网络的动态变化体现了较好 的容错能力，因此具有较好的可用性。同时可以支持复杂查询，如带有规则表达式的 多关键词查询，模糊查询等，最典型的案例是c m u t d l a ”i “l i t 2 j 。 幽l - 4g n u l e i l a 泛洪不恿凹 由于非结构化网络将重叠网络认为是一个完全随机图，这些系统一般不提供性能 保证，但容错性好，支持复杂的查询，并且受结点频繁加入和退出系统的影响小。但 是查询的结果可能不完全，查询速度较慢，采用广播查询的系统对网络带宽的消耗非 常大，并由此带来可扩展性差等问鹿。 目前对此类结构的研究主要集中于改进发现算法和复制策略以提高发现的准确率 和性能。 最新的研究成果体现在采用分布式散列表( d l 一l ，1 ) 的完全分布式结构化拓扑网 络。这些新的拓扑关系的基本原理是在d h t 表一维空间的基础上引入更多的拓扑结 构图来反映底层网络的结构。d h t 类结构能够自适应结点的动态加，u 退出有着良 好的可扩展性、鲁棒性、结点i d 分配的均匀性和自组织能力。在这种网络中，节点 之间具有结构化的拓扑关系，数据位置被精确的控制，这些都使得数据查询较为容易 实现，并且具有较高的效率。最经典的案例是p 一，t a p e s t r y l 阍， c a n l l 6 1 和 c h o r d 1 7 1 。 半分布式结构吸取了中心化结构和全分布式非结构化拓扑的优点，选择性能较高 ( 处理、存储、带宽等方面性能) 的结点作为超级点，超级节点只与本身的叶节点和 4 - 鋈熙萨、一一一， 南京邮电大学硕上研究生学位论文第一章绪论 其他超级节点相互相连。超级节点起到中心服务器的作用，它们存储了本身叶节点的 信息，所有的超级节点在p 2 p 网络中起到骨架作用。当一个超级节点收到从它叶节点 发来的搜索信息时，它首先在本地搜索，如果没有，再转发到其它的超级节点上去。 发现算法仅在超级点之间转发，所有超级点构成一个高速转发层。半分布式结构的优 点是性能、可扩展性较好，较容易管理，但对超级点依赖性大，易于受到攻击，容错 性也受到影响。最典型的案例就是k a z a a e l 8 】。 图1 5 含s u p c m o d e 的半分布式结构 1 2 2 四种不同结构的p 2 p 系统的比较 四种不同结构p 2 p 系统性能比较如表1 1 所示： 表1 一l四种不同结构p 2 p 系统性能 比较标准集中式结构分布式非结构化结构化d h t混合式结构 可扩展性差差好中 可靠性差好好中 可维护性最好最好 好 中 发现算法效率 最高中 高中 复杂查询支持支持 不支持支持 南京邮电大学硕士研究生学位论文 第一章绪论 1 3p 2 p 技术的特点 p 2 p 技术的特点主要体现在以下几个方面： 非中心化( d e c e n t r a l i z a t i o n ) ：网络中的资源和服务分散在所有结点上，信息的传 输和服务的实现都直接在结点之间进行，可以无需中间环节和服务器的介入，避 免了可能的瓶颈。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 2 p 网络中，由于信息的传输分散在各节点之间进行而无需经过某个 集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前解决 i n t e r n e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏在众多 的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖于某些中继 服务器节点。而在p 2 p 中，所有参与者都可以提供中继转发的功能，因而大大提高 了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少了对传统 c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点，更好 的实现了整个网络的负载均衡。 南京邮电大学硕士研究生学位论文 第一章绪论 1 4p 2 p 应用 人们己经将p 2 p 计算技术应用到很多不同的领域内，主要的应用包括：提供文 件和其它内容共享，对等计算能力和存储共享，协同处理，即时通讯交流，搜索引擎 技术。下面将从上述几个角度对p 2 p 技术的应用分别介绍。 1 提供文件和其它内容共享：例如n a p s t e r 、g n u t e l l a 1 9 1 、e d o n k e y 、e m u l e 、b i t t o r r e n t 虚 守； 网络资源文件共享的需求直接引发了p 2 p 技术热潮，在传统的c s 方式中，要 实现文件交换需要服务器的大力参与，通过将文件上传到某个特定的服务器上， 用户再到某个服务器上搜索需要的文件，然后下载，这种方式的不便之处不言而 喻，服务器经常成为这类系统的性能瓶颈所在。以n a p s t e r 为例，它用于在互联网 上共享m p 3 音乐文件，与传统的音乐共享技术不同的是n a p s t e r 把音乐文件存储在 客户节点上而不是存储在服务器节点上，中心服务器上存储的仅仅是用于文件的 索引信息，用户之间可以直接共享、传输音乐文件而不需要通过中心索引服务器。 采用这种方式来共享信息资源可以更加充分的利用网络中的带宽资源，从而提高 了系统数据通信的效率。 2 对等计算能力和存储共享：例女i s e t i h o m e 、a v a k i 、p o p u l a rp o w e r 等； 人们期望能够充分利用网络中的闲散c p u 空闲时间，内存空间，以及硬盘空 间来代替“超级计算机完成大量的计算任务。p 2 p 技术的对等计算，正是把网络中 众多计算机暂时不用的计算能力连结起来，使用积累的能力执行超级计算机的任 务。p 2 p 技术的存储共享技术就是将各个客户机的空闲存储空间是利用起来实现网 络存储，这些客户机之间通过通道联系，发挥了p 2 p 网上的全部直挂式存储能力， 数据存储也没有增加任何额外的开支，实在是一种不可多得的选择。 3 协同处理：例如必、m a g i 、g r o o v e 、n e tm ys e r v i c e 等； 共同的利益和目的是使用位于不同组织和区域内的工具的驱动力量。协同处 理提高了生产力，并且使得位于不同地域的团队能相互协调工作。协同处理还可 以将本地项目和信息存储在边缘设备上，减少对服务器存储方面的需求。一般应 用软件的协同应用包括：语音通讯，聊天室，文件共享等基本的功能，除了这些 基本的功能，用户之间还可以通过共享白板，协同写作进行视频会议等。 4 即时通讯交流：例如i c q 、o i c q 、y a h o om e s s e n g e r 等： p 2 p 的即时通讯软件可以即时知晓对方是否在线，另外通讯双方的交流完全是 7 南京邮电大学硕士研究生学位论文第一章绪论 点对点进行，不依赖服务器的性能和带宽。尽管目前的即时通讯技术一般还是要 用到中心服务器的，但是中心服务器仅仅是用于控制用户的认证信息等基本信息， 并且帮助完成节点之间的初始连接工作。 5 搜索引擎：例如g o o g l e ，b a i d u 等； 搜索引擎是目前人们在网络中进行搜索信息资源的主要工具，目前在使用的 都是集中式的搜索引擎，而且这类搜索引擎所搜索的主要媒体信息是超文本信息， 并没有对多媒体信息进行很好的支持。由于目前网络的信息数量成指数增长，搜 索引擎的增长速度已经不能有效的跟踪数据总量的增长，在j x t as e a r c h 中认为采 用p 2 p 的搜索技术可以有效的跟踪数据的更新速度，提高访问的有效性以及检索的 效率。 1 5 新技术对研究的影响 随着p 2 p 应用的蓬勃发展，作为p 2 p 应用中核心问题的发现技术除了遵循技术本身 的逻辑以外，也受到某些技术的发展趋势、需求趋势的深刻影响。 1 5 1 度数和直径的折衷关系( t r a d e o f f ) 对发现算法的影响 如上所述，d h t 发现技术完全建立在确定性拓扑结构的基础上，从而表现出对网络 中路由的指导性和网络中结点与数据管理的较强控制力。但是，对确定性结构的认识 又限制了发现算法效率的提升。研究分析了目前基于d h t 的发现算法，发现衡量发现算 法的两个重要参数度数( 表示邻居关系数、路由表的容量) 和链路长度( 发现算法的 平均路径长度) 之间存在渐进曲线陋3 的关系。 南京邮电大学硕士研究生学位论文第一章绪论 维护邻居数c 度) o ( 1 ) o ( 】0 9 n j i l o 咖g mo o o gn ) c ( n 1 嗣) o ( m ) 图l - - 6 度数和直径之间的渐进曲线关系 从图i - 6 渐进曲线关系可以看出，如果想获得更短的路径长度，必然导致度数的增 加；而网络实际连接状态的变化造成大度数邻居关系的维护复杂程度增加。另外，研 究者证明o ( 1 0 9 n ) 甚o ( 1 0 9 u l o g l o g n ) 的平均路径长度也不能满足状态变化剧烈的网 络应用的需求。新的发现算法受到这种折衷关系制约的根本原因在于d h t 对网络拓扑 结构的确定性认识。 1 5 2s m a l lw o r l d s m a l lw o r l d 特征和幂规律证明实际网络的拓扑结构既不是非结构化系统所认识的 一个完全随机图，也不是d h t 发现算法采用的确定性拓扑结构。实际网络体现的幂规 律分布的含义可以简单解释为在网络中有少数结点有较高的“度 ，多数结点的“度” 较低。度较高的结点同其他结点的联系比较多，通过它找到待查信息的概率较高。 s m a l l w o r l d 模型的特性：网络拓扑具有高聚集度和短链的特性。在符合s m a l l w o r l d 特性的网络模型中，可以根据结点的聚集度将结点划分为若干簇( c l u s t e r ) ，在每个簇 中至少存在一个度最高的结点为中心结点。大量研究证明了以g n u t e l l a 为代表的p 2 p 网 络符合s m a l l w o r l d 特征，也就是网络中存在大量高连通结点，部分结点之间存在“短 链现象。 因此，在p 2 p 的发现算法中如何缩短路径长度的问题变成了如何找到这些“短链 的问题【2 0 l 。尤其是在d h t 发现算法中，如何产生和找到“短链是发现算法设计的一 个新的思路。s m a l l w o r l d 特征的引入会对p 2 p 发现算法产生重大影响。 南京邮电大学硕士研究生学位论文第一章绪论 1 5 3 语义查询和d h t 的矛盾 基于d h t 的p 2 p 系统采用相容散列函数【2 3 】根据精确关键词进行对象的定位与发 现。散列函数总是试图保证生成的散列值均匀随机分布，结果两个内容相似度很高但 不完全相同的对象被生成了完全不同的散列值，存放到了完全随机的两个结点上。因 此，d h t 可以提供精确匹配查询，但是支持语义是非常困难的。 目前在d h t 基础上开展带有语义的资源管理技术【2 l 】的研究还非常少。由于d h t 的 精确关键词映射的特性决定了无法和信息检索等领域的研究成果结合 2 2 1 ，阻碍了基于 d h t 的p 2 p 系统的大规模应用 1 6 本文主要内容 通过比较全面地学习了p 2 p 网络相关知识后，本文针对如何在p 2 p 网络内进行资源 定位进行了研究。从优化搜索方法和改进p 2 p 网络搜索结构两个方面进行研究。 本文分5 部分： 第一章：介绍选题的背景，意义，和p 2 p 技术的应用领域以及p 2 p 网络资源定位方 法的研究现状。第二章：主要讲述了4 种结构化的d h t 的p 2 p 技术，并对不同搜索方法 进行比较并且分析其优缺点。第三章：对c h o r d 算法进行优化。第四章：对改进的算法 进行仿真并分析。第五章：总结全文，并指出改进方向。 南京邮电大学硕士研究生学位论文 第二章d h t 网络结构 2 1d h t 网络结构 第二章d h t 网络结构 基于d h t 的分布式发现和路由算法是通过分布式散列函数，将输入的关键字惟一映射 到某个结点上，然后通过某些路由算法同该结点建立连接。d h t 实际上是一个由广域范围 大量结点共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属 于自己的散列块，并成为这个散列块的管理者。当节点资源需要在对等网络中发布共享时， 采用分布式h a s h 2 3 1 方法对该资源的内容或相关信息进行h a s h 运算，生成资源的全局标识符 ( g u i d ) ，并按照一定方法，将资源存储到相应节点，从而在n o d e l d 和g u i d 之间建立某种 联系。节点需要查找资源时，向自己知晓的节点请求查询和定位。 d h t 类结构能够自适应结点的动态加入退出，有着良好的可扩展性、鲁棒性、结点i d 分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，d h t 可以提供精确的 发现。只要目标结点存在于网络中d h t 总能发现它，发现的准确性得到了保证。 d h t 类结构维护机制复杂，尤其在节点频繁加入或退出的情况下。另外，由于d h t 采用h a s h 方法对资源进行h a s h 计算，内容相近的资源可能h a s h 计算之后得到的结果相 差很远，所以d h t 只支持精确查询。 不同p 2 p 系统中的搜索策略采用不同的路由信息组织方式，伴随而来的是不同的侧重 性能和特点，以及不同的上层应用系统的组织方式、维护策略和系统性能。下面分别介绍 c a n ，p a s t r y ，c h o r d ，t a p e s t r y ，k a d e m l i a 【2 4 1 。 2 2c h o r d 算法 c h o r d 算法是由i o ns t o i c a 等人设计的一种较简单的结构化p 2 p 搜索策略。它的设计目标 是提供一个分布式、负载均衡的、可扩展的p 2 p 搜索策略，解决目前由中心控制的搜索策 略带来的扩展性能差、负载均衡差等限制问题。c h o r d 算法中每一个节点通过某哈希函数( 通 常是s h a 1 ) 计算出唯一的m 位的标示符( 节点i d ) ，标识该节点在c h o r d 系统中的位置。当节 点需要路由某一消息时，该消息也用哈希函数计算出消息i e y 值。消息的目标节点就是节 点i d 大于或者等于消息k e y 值的节点中节h i d 最小的一个，此节点称为这个消息的后继节 点( s u c c e s s o r ) 。在d h t 技术中，网络结点按照一定的方式分配一个唯一节点i d ，资源对 1 1 塑室塑皇奎堂堡主翌窒圭兰垡笙塞蔓三童里坚堕竺笙塑 象通过散列运算产生一个唯一的资源标识符( o b j e c t1 1 9 ) ，且该资源将存储在结点i d 与之相 等或者相近的结点上。需要查找该资源时，采用同样的方法可定位到存储该资源的结点。 因此，c h o r d 算法的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字( k e y ) 映射到对应的结点。从算法来看，c h o r d 是相容散列算法的变体。 图2 1 h a s h 示例 每个关键字k 标识符所对应的资源都保存在它的后继结点中，后继结点是结点标识符n 大于等于关键字k 标识符的第一个结点，我们将其记为s u c c e s s o r ( k ) 。由于关键字“l e t l t b e ” 的标识符为k 6 0 ，因此它被保存在n 9 0 结点中。如果标识符采用m 位二进制数表示，并且将 从0 到2 m - l 的数排列成一个圆圈，那么s u c c e s s o r ( k ) 就是从k 开始顺时针方向距离最近的结 点。 当结点n 加入网络时，为了保持相容哈希【2 3 1 映射，某些原来分配给n 的后继结点的关键 字将分配给n 。当结点n 离开网络时，所有分配给它的关键字将重新分配给n 的后继结点， 除此之外，网络没有其他变化。 2 2 1 路由查找策略 在c h o r d 算法中，每个结点维护少量的路由信息，通过这些路由信息，可以提高查询 的效率。如果m 是关键字和结点标识符的位数( 采用二进制表示) ，那么每个结点只需要维护 一张最多m 个表项的路由表，我们称之为指针表( f i n g e rt a b l e ) ，结点n 的查找表的第i 个表项 包括的是铲s u c c e s s ( n + 2 ) ，这里l = i = m 并且所有的计算都要进行m o d2 n ，s 称为结点n 的第i 个指针，我们用n f i n g e r i n o d e 表示，指针表中的其他项的含义如表2 1 所示。 1 2 南京邮电大学硕上研究生学位论文 第二章d h t 网络结构 表2 一lc h o r d 算法中指针表项含义 符号定义 f i n g e r k s t a r t ( n + 2 k 1 ) m o d2 m , 1 = k 嚆 后向 图2 _ - 5t a p e s t r y 算法中节点的邻居映射表 在t a p e s t r y 算法的容错处理中，检测正常操作过程中的链路和服务器失效，可以使用 t c p 连接超时机制。除此之外，每个t a p e s 仃y 系统中的结点都周期性的给后向指针指向的邻 居发送u d p 分组，把自己加入邻居映射表的结点。每个结点都n - - i 以根据自己收到的分组来 判断自己的邻居映射表中是否有结点失效。在邻居结点表中，除了主邻居结点( 最近的邻居) 之外，每个路由项还保存了两个备份的邻居结点，当检测到主邻居结点失效后，邻居结点 表将顺序选择备份邻居结点。 在t a p e s t r y 算法中，为每个对象分配多个根结点。具体的做法是在每个对象后面分别 加一个小的后缀( 比如1 ，2 ，3 ) ，然后对这些结果进行哈希运算得到多个根结点。在定位对象 时，执行同样的哈希操作以生成这组根结点。 南京邮电大学硕士研究生学位论文第二章d h t 网络结构 2 4 2 节点的加入和退出 t 印咖算法中结点的加入算法和p 嬲t 巧很类似。结点n 在h i l 入t a p e s t r y 系统之前，需要 已知一个已经在系统中的结点g 。然后n 通过g 发出路由自己的结点i d 的请求，根据经过的 结点的对应的邻居结点表构造自己的邻居结点表。构造过程中还需要进行一些优化工作， 构造完自己的数据结构后，结点n 将通知网络中的其他结点自己己经加入网络，通知只针 对在n 的邻居映射表中的主邻居结点和二级邻居结点进行。 t a p e s t r y 算法采用两种机制处理结点的退出。一种情况是结点从网络中自行消失( 主要 原因是结点失效) ，在这种情况下，它的邻居可以检测到它已经退出网络并可以相应的调整 路由表。另一种机制是结点在退出系统之前通过后向指针通知所有把它作为邻居的结点， 这些结点会相应调整路由表并通知对象服务器该结点己经退出网络。 t a p e s t r y 算法中的每个结点的邻居映射表都按照路由层次组织，每个层次都包括匹配 该层次对应的前缀并离该结点最近的一组结点。节点通过一次纠正一位的方式递交查找请 求，所以节点匹配自己标识符的每一个前缀而下一位不同的邻居信息。如一条可能的消息 传递路径可能是：木枣木4 木3 4 * 2 3 4 1 2 3 4 。其中宰号表示通配符。该路径从右向左解析，即 消息先传递到节点i d 为4 的节点，再分别依次传递到节点3 ，2 和l 。对于1 1 个节点的系统， 每个节点有o ( 1 0 9 n ) 个邻居，由于每跳纠正一位，所有路由路径长度为0 0 0 9 n ) # 8 。 2 5p a