（计算机应用技术专业论文）基于对等网的文件共享技术研究.pdf

哈尔滨t 程大学硕十学位论文 摘要 随着对等网( p 2 p ) 的广泛应用，人们对p 2 p 应用模式的需求也越来越大。 相对于传统的c s 模式，p 2 p 具有非中心化、扩展性好、性价比高、健壮性 强以及负载均衡等优点。因此，越来越多的组织和个人将p 2 p 技术应用于互 联网文件共享领域。但是要更好地在文件共享领域发挥作用，p 2 p 技术仍然 需要在搜索技术、数据传输技术( n a t 穿透) 、安全机制以及激励机制等方面 作进一步的改进。 目前，在p 2 p 搜索技术方面的研究主要有基于现有的非结构化搜索算法 ( 如泛洪式搜索算法) 的改进研究以及结构化搜索算法的创新研究。本文主 要针对非结构化p 2 p 搜索技术进行了阐述和研究，找出了泛洪式算法的冗余 消息产生规律，并提出了减少冗余消息数量的改进算法。数据传输技术( n a t 穿透) 也是p 2 p 文件共享领域亟待解决的关键技术之一。通过对现有的n a t 设备端口映射机制的分析和研究，提出了基于软件方法的n a t 穿透方案，解 决了锥型n a t 的u d p t c p 穿透问题。 最后，对b i t t o r r e n t 文件共享系统的工作原理、相关协议与算法进行了 详细分析和研究。研究发现，现有的b i t t o r r e n t 文件共享系统所采用的随机 邻节点选择算法很容易导致跨i s p 网络流量的增长，易引起网络阻塞。另外， b i t t o r r e n t 网络中存在大量的n a t 节点，这些节点之间不能够相互共享数据。 针对b i t t o r r e n t 文件共享系统的以上不足，本文分别提出了有规则的邻节点 选择算法与u d p t c p 穿透n a t 的软件解决方案对b i t t o r r e n t 文件共享系统进 行了改进设计。 关键词：对等网( p 2 p ) ；搜索；数据传输；网络地址转换；b i t t o r r e n t ； 哈尔滨丁程大学硕士学位论文 a b s t r a c t a sp e e r - t o p e e r ( p 2 p ) a p p l i c a t i o n sa w i d e l ya p p l i e d ，t h ed e m a n df o rp 2 p a p p l i c a t i o nm o d e li sa l s og r o w i n g c o m p a r e dt ot r a d i t i o n a lc l i e n t s e r v e r ( c s ) m o d e l ，p 2 pi so f f - c e n t e r , s c a l a b i l i t y , h i g hp e r f o r m a n c e - p r i c er a t i o ，s t r o n g r o b u s t n e s s ，l o a db a l a n c i n g ，a n ds oo n t h u s ，m o r ea n dm o l eo r g a n i z a t i o n sa n d p e r s o n sa r ea p p l y i n gp 2 pt e c h n o l o g yi n t of i l es h a r i n gf i e l d h o w e v e r , t ob em o i e i n f l u e n t i a li nt h i sf i e l d , p 2 ps t i l lh a st ob ei m p r o v e di ns o m ea 印e c 协s u c ha s l e s o u r c e s e a r c h , d a t au a s f e r ( n a tt r a v e r s a l ) ，t h es e c u r i t y a n di n c e n t i v e m e c h a n i s m a tp r e s e n t , t h er e s e a r c ho f p 2 ps e a r c hm a i n l yf o c u s e so i lt h ei m p r o v e m e n to f t h ee x i s t i n gu n s t r u c t u r e ds e a r c ha l g o r i t h m ( c g ：f l o o d i n g ) a n dt h es t u d yo fn e w s e a r c ha l g o r i t h m s t h i st h e s i sf o c u s e so nu n s t r u c t u r e dp 2 ps e a r c ha l g o r i t h m f l o o d i n gw i l lb es t u d i e di n - d e p t ht of i n do u ti t si n h e r e n tl a w s d a t at r a n s m i s s i o n t e c h n o l o g y ( n a tt m v e r s a l ) i so t l eo f t h ek e yi s s u e so f p 2 pf i l e s h a r i n gs y s t e m t o b er e s o l v e d n a tm a p p i n go ft h ee x i s t i n gp o r tf a c i l i t i e st h r o u g ht h em e c h a n i s m o fr e s e a r c ha n da n a l y s i s t h i st h e s i sp r o p o s e sas o f t w a r em e t h o dt os o l v et h e p r o b l e m eo fp e e r - t o - p e e r c o m m u n i c f i o na c r o s sn e t w o r ka d d r e s st r a n s l a t o r s ( n a t ) a tl a s t , t h ep r i n c i p l e ，r e l a t e dp r o t o c o l sa n ds o m ea l g o r i t h m so f b i t t o r r e n ta r e a n a l y s e da n ds t u d i e d a n dt h er e s u l ts h o w st h a tt h ea d j a c e n tn o d e sr a n d o m l y s e l e c t i o na l g o r i t h mo f b i t t o r r e n tc a ne a s i l yc a u s ea c r o s s - i s p 仃a 位cg r o w t ha n d n e t w o r kc o n g e s t i o n i na d d i t i o n , t h e r ea r eal o to f n a t e dn o d e si nb i t t o r r e n t n e t w o r k t h e yc a nn o ts h a r ed a t ae a c ho t h e r , b e c a u s eo f n a t i no r d e rt oi m p r o v e t h ep e r f o r m a n c eo f b i t t o r r e n t , t h i st h e s i sp r o p o s e so n en e wa 由a c e n tn o d e s s e l e c t i o na l g o r i t h ma n das o f t w a r es o l u t i o nf o rn a tp r o b l e m k e y w o r d s ：p e e r - t o - p e e r ( p 2 p ) ，s e a r c h d a t at r a n s f e r , n a t , b i t t o r r e n t 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：生垒盆 日期：川年3 月厂日 哈尔滨_ 下程大学硕+ 学付论文 第1 章绪论 1 1 课题的背景、目的与意义 随着互联网技术的迅速发展，互联网已经深入到世界的各个角落，影响 着世界经济、政治以及文化的发展。据研究咨询公司e t f o r e c a s t 的研究数据， 2 0 0 5 年全球互联网用户总数为1 0 8 亿，比2 0 0 4 年增加了1 5 亿。同时，该 研究机构还预测未来五年内全球互联网用户数将再增一倍，达到2 0 亿。互联 网用户数量的急剧上升极大地推动了互联网技术的发展以及业界对互联网应 用技术的研究步伐。 人类进入2 1 世纪，信息化技术的广泛应用成为这个世纪的重要特征之 一。人们对信息的需求达到了有史以来的颠峰时期。然而，人们的信息交换 大多是依赖于网络技术进行的。目前，大多数网络服务都是基于客户端服 务器( 以下简称：c s ) 模式的。在互联网发展过程中，c s 模式发挥了极其 重要的作用。我们所熟知的v r p 、w 胛等应用都是基于c s 模式构建的。近年 来，互联网带宽和计算能力增长速度与人们日益增长的对带宽和计算能力的 进一步需要之间的矛盾对这种模式提出了严峻的挑战。在c s 模式中，客户 端数量的迅速增加很容易导致服务器在带宽、计算力以及存储力等方面产生 瓶颈。相对于此，对等网技术( p e e r - t o - p e e r ，以下简称p 2 p ) 模式在解决服 务器带宽、降低服务器压力以及提高资源利用率等方面具有突出的优势。 p 2 p 是一种分布式网络，网络的参与者共享它们所拥有的一部分资源( 处 理能力、存储能力、网络连接能力、打印机等) ，这些共享资源需要由网络 提供服务和内容，能被其它对等点( p e e r ) 直接访问而不用经过中问实体的 参与。在此网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ，又 是资源( 服务和内容) 获取者( c l i e n t ) m 。p 2 p 模式是传统的c s 模式的技 术突破。与c s 模式相比，p 2 p 模式的主要优点体现在以下几个方面： ( 1 ) 非中心化：网络中的资源和服务分散在所有结点上，信息的传输和服 务的实现都直接在结点之间进行，可以无需中间环节和服务器的介入，避免 了可能的瓶颈。p 2 p 的非中心化特点带来了其在可扩展性、健壮性等方面的 哈尔滨丁程大学硕十学位论文 优势。 ( 2 ) 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了， 系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需 要。整个体系是全分布的，不存在瓶颈。理论上其可扩展性可被认为是无限 的。 ( 3 ) 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散 在各个结点之间进行的，部分结点或网络遭到破坏对其它部分的影响很小。 p 2 p 网络一般在部分结点失效时能够自动调整整体拓扑，保持其它结点的连 通性。p 2 p 网络通常都是以自组织的方式建立起来的，并允许结点自由地加 入和退出。p 2 p 网络还能够根据网络带宽、结点数，负载等变化不断地做自 适应式的调整。 ( 4 ) 高性能价格比：性能优势是p 2 p 被广泛关注的一个重要原因。随着 硬件技术的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩 尔定理高速增长。采用p 2 p 架构可以有效地利用互联网中散布的大量普通结 点，将计算任务或存储资料分布到所有结点上。利用其中闲置的计算能力或 存储空间达到高性能计算和海量存储的目的。通过利用网络中的大量空闲资 源，可以用更低的成本提供更高的计算和存储能力。 ( 5 ) 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减 少了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布 在多个节点，更好的实现了整个网络的负载均衡。 由于以上优点，p 2 p 技术在互联网中的应用也越来越广泛。如今，p 2 p 技术已被广泛应用于文件共享、对等计算、网络存储以及虚拟社区等领域“1 。 尤其在文件共享领域，p 2 p 技术正发挥着越来越大的作用。然而，应用的扩 大与需求的增加对p 2 p 技术提出了更加严峻的挑战。为了满足新的应用需求 以及解决现有的互联网信息共享技术，研究p 2 p 文件共享技术具有非常积极 的意义。 本课题主要来源于与黑龙江省电子信息产品监督检验院的合作项目“黑 龙江省农村党员干部现代远程教育综合应用系统”中的课件下载系统设计。 哈尔滨工程大学硕士学t i ) ：论文 1 2 国内外研究现状 近年来，国内外有许多著名的研究机构和企业参与了p 2 p 技术的应用与 研究。国内的研究机构主要有：北京大学、清华大学、华中科技大学以及上 海聚力传媒等。他们研发了基于p 2 p 技术的文件共享系统、网络存储系统以 及流媒体直播系统等。此外，一些著名的跨国企业和大学，如：微软、i 删、 i n t e l 、s u n 、m i t 等都成立了各自的研究机构专门从事p 2 p 技术的应用与研 究。 1 2 1p 2 p 拓扑结构的研究 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关 系，节点之间的拓扑结构一直是判断系统类型的重要依据。目前互联网中广 泛使用集中式、层次式等拓扑结构。互联网本身是世界上最大的非集中式的 互联网络，但是九十年代所建立的一些网络应用系统却是完全集中式的，很多 w e b 应用都是运行在集中式的服务器系统上。集中式拓扑结构系统目前面临 着过量存储负载、d o s 攻击等一些难以解决的问题。 p 2 p 系统一般构造一个非集中式的拓扑结构，在构造过程中需要解决系 统中所包含的大量节点如何命名、组织以及确定节点的加入退出方式、失效 恢复等问题。 p 2 p 的网络拓扑结构可大致分为四类：中心化拓扑、全分布式非结构化 拓扑、全分布式结构化拓扑和半分布式拓扑m ，。 其中，中心化拓扑最大的优点是维护简单并且发现效率高。由于资源的 发现依赖中心化的目录系统，发现算法灵活高效并能够实现复杂查询。它的 最大问题与传统客户机服务器结构类似，容易造成单点故障，访问的热点现 象和法律等相关问题，这是第一代p 2 p 网络采用的拓扑结构模式。 全分布非结构化拓扑采用了随机图的组织方式，节点度数服从 “p o w e r - l a w ”规律，从而能够较快发现目的节点。相对于网络的动态变化， 它体现了较好的容错能力，因此可用性较强。同时它还可以支持复杂查询， 如：多关键词查询和模糊查询等“，。 最近两年，研究学者们将研究重心偏移到采用分布式散列表( d 盯) 的完 全分布式结构化拓扑网络m 。这种拓扑结构由于采用了d h t 技术，支持精确定 3 哈尔滨工程大学硕十学位论文 位查找等资源定位算法。但是节点的频繁加入退出会大大增加系统用于维护 网络拓扑的资源开销，而且它不支持模糊查询功能以及内容语义等复杂查询 o 半分布式拓扑结构吸取了中心化结构和全分布式非结构化拓扑的优点， 它选择性能较高( 处理器和带宽) 的节点作为超级节点，各个超级节点存储 了系统中其它部分节点的信息。在这种拓扑网络中，资源查询消息仅仅在超 级节点之间转发，超级节点再将查询请求转发给适当的叶子节点。半分布式 结构也是一个层次式结构，超级节点之间构成了一个高速转发层，超级节点 和所负责的普通节点构成若干层次。它的主要优点是可扩展性较好，较容易 管理，但对超级节点依赖性大，存在“局部单点故障”等问题，容易受到攻 击。 1 2 2p 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 搜索技术主要有集中式搜索、泛洪式搜索、随机 漫步搜索以及基于这两种基本算法的变种m m 。结构化p 2 p 搜索技术主要有基 于分布式哈希表的资源搜索技术。本文第三章将会详细阐述和分析现有的非 结构化搜索技术。 1 2 3p 2 p 安全机制研究 安全问题一直以来都是网络技术中一个非常重要的问题。p 2 p 领域的安 全技术研究还处于初期，目前还没有一套完整的安全解决方案。目前在p 2 p 领域存在的安全问题主要有d o s 攻击、安全认证与病毒“”。一旦网络中某一 节点遭受病毒入侵，那么在短时间内网内的所有节点都将遭受同样的入侵， 其危害是巨大的。因此如何构建一个安全、可靠的p 2 p 网络模型也是该领域 的研究重点之一。 1 2 4p 2 p 应用研究 随着p 2 p 技术在文件共享领域的良好应用，全世界的研究学者与工程师 都在考虑一个重要问题，如何把p 2 p 技术应用到实际工程中为社会经济与文 4 哈尔滨t 程大学硕十学伊论文 化的发展服务。近年来，人们在这方面取得了突出的成就，先后将p 2 p 技术 应用到协同计算、文件共享、网络存储、网络电话、网络流媒体等领域。但 是在这些应用领域中，都存在着或多或少的技术难题，需要研究学者们进一 步研究与解决。 1 3 本文的主要工作 本文的主要工作包括： 。 ( 1 ) 分析了现有的对等网络模型，对各种网络模型的特点进行了详尽的阐 述和比较。 ( 2 ) 对非结构化p 2 p 资源搜索技术进行了阐述和分析，研究了泛洪式搜索 算法的内在规律与特征，并提出了基于树状覆盖子网的改进方法，另外还介 绍了集中式搜索算法和随机漫步搜索算法的基本原理及相关改进。 ( 3 ) 分析了现有的n a t 类型以及相关的端口映射方式，然后提出了针对锥 型n a t 的点到点的u d p t c p 穿透n a t 的软件解决方案，并对穿透协议进行了 详细的解释与分析。 ( 4 ) 详细地分析和研究了b i t t o r r e n t 文件共享系统的相关协议和算法， 并针对邻节点选择算法和网络连通性的不足之处提出了相应的改进设计方 案。 1 4 本文的章节安排 本文的章节安排如下： 第一章是绪论，介绍了课题的背景、目的及意义，以及国内外研究现状、 论文工作内容和章节安排。 第二章研究了p 2 p 文件共享系统的发展状况，然后对每种模型的工作原 理以及各自的特点进行了分析和比较。 第三章介绍了p 2 p 资源搜索技术的现状，研究了非结构化资源搜索技术， 简述了集中式搜索算法和随机漫步算法的原理和特征，并深入研究了泛洪式 搜索算法的冗余消息产生规律，同时提出了基于树状覆盖子网的改进方法。 第四章是本文的重点之一，详细地分析了现有的锥型n a t 和s y m e t r i c 哈尔滨下程大学硕十学位论文 n a t 的端口映射方式，然后分别提出了点到点的u d p t c p 穿透锥型n a t 的协 议，并且对协议进行了详细的分析和解释，为p 2 p 文件共享系统中的数据传 输难题提供了软件解决方案。 第五章在前几章的基础之上，把文件共享技术的研究点归结到了 b i t t o r r e n t 文件共享模型之上，对b i t t o r r e n t 文件共享系统的相关协议和 算法进行了详细的阐述和分析，最后针对现有的b i t t o r r e n t 文件共享系统在 邻节点选择算法和网络连通性上的不足提出了两点改进设计方案。 结论部分对本文的工作进行了总结，同时指出了还有待进一步研究的一 些问题。 6 哈尔滨t 程大学硕十学位论文 第2 章对等网文件共享系统模型 从第一个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 模型、k a z a a 模型、盯模型以及以c h o r d 为代表的结构化p 2 p 文件共享系统 模型。它们都是p 2 p 文件共享系统发展过程中非常杰出的代表。p 2 p 文件共 享系统的发展状况如图2 1 。 时间轴 i 1 9 9 9 2 0 0 0 2 0 0 12 0 0 2现在 圈匹四匝圆 叵困匝函蕊固 回叵亟五 重垂 图2 1p 2 p 文件共享系统发展概况 2 1 n a p s t e r 模型 n a p s t e r 是最早出现的p 2 p 文件共享系统之一，并在短期内迅速成长起 来。n a p s t e r 实质上并不是纯粹的p 2 p 系统，它由一群高性能的中央服务器 保存着网络中所有节点共享资源的目录信息。当需要查询某个文件时，节点 会向中央服务器发出文件查询请求。中央服务器进行相应的检索和查询后， 会返回符合查询请求的节点地址信息列表。查询发起节点接收到应答后，会 根据网络流量和延迟等信息进行选择，与合适的节点建立连接，并开始文件 传输。n a p s t e r 文件共享系统的工作原理如图2 2 。 7 哈尔滨t 程大学硕士学位论文 ：s c l r e l r ：r c s p o n o ：州咖 d：f i l ed o w n l o a d 图2 2n a p s t e r 模型工作原理图 n a p s t e r 率先实现了文件查询与文件传输的分离，有效地节省了中央服 务器的带宽消耗，减少了系统的文件传输延时。这种方式最大的隐患在中央 服务器上，如果该服务器失效，整个系统就会瘫痪。当用户数量增加到1 0 5 或 更高时，n a p s t e r 的系统性能会大大下降。另一个问题在于安全性上，n a p s t e r 并没有提供有效的安全机制。 n a p s t e r 模型是第一代p 2 p 网络模型。它打破了传统c s 和b s 的资源 共享方式，使得用户之间可以相互直接共享数据，可以说是文件共享技术领 域里一次技术飞跃。n a p s t e r 模型的诞生和应用具有积极的意义。但是这种 网络模型在后来的应用中，也出现了很多的问题，主要表现为： ( 1 ) 存在严重的单点故障，即：中央服务器的瘫痪容易导致整个网络的崩 溃，可靠性和安全性较低。 ( 2 ) 系统可扩展性差，即：随着网络规模的扩大，对中央索引服务器进行 维护和更新的费用将急剧增加，所需成本较高。 ( 3 ) 存在法律和版权纠纷，i l p 中央服务器的存在引起共享资源在版权问 题上的纠纷。 第一代p 2 p 网络模型在小型系统中能够发挥其最佳性能，但该模型对于 大型系统并不适用。 2 2g n u t c l l a 模型 g n u t e l l a 模型是第二代p 2 p 网络模型，它和n a p s t e r 最大的区别在于 g n u t e l l a 是纯粹的p 2 p 系统，没有索引服务器，它采用了基于完全随机图的 8 哈尔滨_ t 程大学硕十学位论文 泛洪发现和随机转发机制m ”，。为了控制搜索消息的传输，泛洪发现机制通过 搜索消息的订l 减值来实现。在g n u t e l l a 分布式对等网络模型中，每一个联 网计算机在功能上都是对等的，既是客户机又是服务器，所以又被称为对等 机。 ， 随着联网节点的不断增多，网络规模不断扩大，通过这种泛洪方式进行 资源定位的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点 因网络资源过载而失效。所以在初期的g n u t e l l a 网络中，存在比较严重的分 区，断链现象。也就是说，一个查询访问只能在网络的很小一部分进行，因 此网络的可扩展性不好。所以，解决g n u t e l l a 网络的可扩展性对该网络的进 一步发展至关重要。 g n u t e l l a 模型的应用非常广泛，它是非结构化p 2 p 网络模型的典范。在 原始g n u t e l l a 模型之上，许多学者和工程师都致力于增加g n u t e l l a 可扩展 性方面的研究，对其资源定位算法进行改进“m 。同时，业界出现了许多基于 g n u t e l l a 模型的应用系统，这些改进后的系统在可扩展性方面明显得到了提 高，网络冗余流量也得到了不同程度的减少。 图2 3c j n u t e l l a 模型工作原理图 g n u t e l l a 模型解决t n a p s t e r 模型的某些缺陷，省去了索引服务器，功能 简洁，资源搜索能力极强。但是，它也存在很多弊端，主要表现在以下方面： ( 1 ) 网络中对等点的查找和定位比较复杂。 ( 2 ) 随着网络规模的扩大，通过广播方式定位对等点的方法将造成网络流 量急剧增加，从而导致网络拥塞。 ( 3 ) 安全性不高，易遭受恶意攻击，如攻击者发送垃圾查询信息，造成网 络拥塞等。 鉴于以上缺点和不足，广播式对等网络模型也不适合于大型网络应用。 9 哈尔滨_ t 程大学硕十学位论文 必须对其资源搜索算法进行改进才能适应新的应用需求，本文将在第3 章对 p 2 p 网络资源搜索技术进行详细的阐述和研究。 2 3k a z a a 模型 k a z a a 模型是p 2 p 混合模型的典型代表( 见图2 4 ) ，它在g n u t e l l a 模型 基础上引入了超级节点的概念，综合了n a p s t e r 模型快速查找和g n u t e l l a 模型去中心化的优势。k a z a a 模型将节点按能力不同( 计算能力、内存大小、 连接带宽、网络滞留时间等) 区分为普通节点和超级节点两类。其中超级节点 与其临近的若干普通节点之问构成一个自治的簇，簇内采用基于集中目录式 的p 2 p 模式，而整个p 2 p 网络中各个不同的簇之间再通过纯p 2 p 的模式将超 级节点相连起来，甚至也可以在各个超级节点之间再次选取性能最优的节点， 或者另外引入一新的性能最优的节点作为索引节点来保存整个网络中可以利 用的超级节点信息，并且负责维护整个网络的结构“一。 吵m t o 一” 图2 4k a z a a 模型工作原理图 由于普通节点的文件搜索先在本地所属的簇内进行，只有查询结果不充 分的时候，再通过超级节点之间进行有限的泛洪。这样就有效地消除了 g n u t e l l a 结构中使用泛洪算法带来的网络拥塞、搜索迟缓等不利影响。同时， 由于每个簇中的超级节点监控着所有普通节点的行为，这也能确保一些恶意 的攻击行为能在网络局部得到控制，并且超级节点的存在也能在一定程度上 l o 哈尔滨丁程大学硕+ 学位论文 提高整个网络的负载均衡。但是也是由于超级节点的存在，网内存在“局部 单点故障”，一旦某超级节点失效，那么与之相关的普通节点都会受到影响 b i t t o r r e n t 是近年来使用最为广泛，影响最大的p 2 p 文件共享系统，因 此可以将b i t t o r r e n t 确定为一种p 2 p 文件共享系统模型，并对它进行研究。 根据英国网络分析公司c a c h e l o g i c 的调查研究，b i t t o r r e n t 所带来的流量 已经占据了互联网总流量的3 5 这比其它所有基于对等网技术应用系 统所产生的数据流量总和还多。 由于b i t t o r r e n t 模型在文件共享系统领域的重要地位与影响，本文将在 第五章详细分析b i t t o r r e n t 模型的工作原理、协议、相关算法、目前存在的 缺点和针对这些缺点所提出的改进设计。 2 5 结构化p 2 p 文件共享系统模型 所谓结构化与非结构化模型的根本区别在于每个节点所维护的邻居节点 是否能够按照某种全局方式组织起来以利于快速查找。结构化p 2 p 模式是一 种采用纯分布式的消息传递机制和根据关键字进行查找的定位服务，目前的 主流方法是采用分布式哈希表( d h t ) 技术，这也是目前扩展性最好的p 2 p 资源 搜索方式之一。由于d h t 各节点并不需要维护整个网络的信息，只在节点中 存储其临近的后继节点信息，因此较少的路由信息就可以有效地实现到达目 标节点，同时又取消了泛洪算法。该类模型有效地减少了节点信息的发送数 量，从而增强了p 2 p 网络的扩展性。同时，出于冗余度以及延时的考虑，大 部分d h t 总是在节点的虚拟标识与关键字最接近的节点上复制备份冗余信 息，这样也避免了单一节点失效的问题“”。 目前基于d h t 的代表性的研究项目主要包括加州大学伯克利分校的c a n 项目和t a p e s t r y 项目，麻省理工学院的c h o r d 项目、i r i s 项目，以及微软 研究院的p a s t r y 项目等。这些系统一般都假定节点具有相同的能力，这对于 哈尔滨工程大学硕十学位论文 规模较小的系统较为有效。但这种假设并不适合大规模的i n t e r n e t 部署。同 时基于d h t 的拓扑维护和修复算法也比g n u t e l l a 模型和k a z a a 模型等无结构 的系统要复杂得多，甚至在c h o r d 项目中产生了“绕路”的问题。事实上， 目前大量实际应用还大都是基于无结构的拓扑和泛洪广播机制，现在大多采 用i ) t t t 方式的p 2 p 系统缺乏在i n t e r n e t 中大规模真实部署的实例，成功应用 还比较少见。 2 6 本章小结 本章首先简述了p 2 p 文件共享系统的发展状况，然后分别针对n a p s t e r 模型、g n u t e l l a 模型、k a z a a 模型以及b i t t o r r e n t 模型的工作原理和各自的 优缺点进行了研究和分析。 1 2 哈尔滨工程大学硕十学位论文 第3 章对等网资源搜索技术 资源搜索技术是p 2 p 计算领域的关键技术之一。本章着重于p 2 p 的资源 搜索技术进行阐述和研究。资源搜索意指对想要寻找的数据进行定位。大多 数现有的p 2 p 系统都支持通过关键字或标识符进行的对象查询。有些p 2 p 系 统甚至还可以处理更复杂的关键字查询。在同一个p 2 p 系统中，一份文件可 能有多份拷贝，它们分布在网络的多个节点里。当某些节点需要获取该文件 时，它们可以通过该文件所对应的关键字在网内进行查找。一般而言，一份 文件可以具有多个不同的关键字，不同的p 2 p 系统对关键字的设置规则也是 不同的。 现有的大多数资源搜索技术都是基于消息转发机制的。一般而言，一条 查询消息起源于请求节点，然后该查询消息被一个节点转发给另一个节点， 直到被查询的资源被找到或查询生命期结束为止。为了转发查询消息，每个 节点必须维护它的邻居节点的一些信息。对于某节点而言，它所有的邻居节 点的信息就组成了该节点的路由表，资源的查找均需要依靠该路由表进行。 这就是常见的基于消息转发机制的非结构化p 2 p 资源搜索技术n 。此外，最 新研究成果提出了基于分布式哈希表( o h t ) 的结构化搜索技术，该技术根据 设定的哈希函数进行资源的精确定位与查找，但该技术不能支持模糊查询， 而且节点的加入与退出对于整个p 2 p 系统的影响相当大。 为了对p 2 p 资源搜索算法评价和比较不同的的，定义一个评价指标是有 必要的。现有的评价指标可被归纳为以下三点。 ( 1 ) 扩展性 扩展性是指资源搜索算法在网络规模不断扩大的情况仍然能够有效地进 行资源的搜索，即能够满足大规模p 2 p 网的需要。一般而言，给定一个查询， 如果在搜索过程中影响的无关节点( 不满足查询条件的节点) 越多( 如： 泛洪算法) ；为了实现搜索所需要交换的节点信息越多；节点加入离开 网络对其它节点的影响越大( t n 基于d h t 的结构化p 2 p 网络) ；那么算法的 扩展性就越差。 ( 2 ) 查询命中率 。 一般而言，发起查询的节点被称为请求者，拥有满足该查询条件的资源 1 3 哈尔滨t 稗大学硕十学 i 7 ：论文 的节点被称为提供者。有三种出错情况会影响查询命中率：提供者发生异 常( 突然退出p 2 p 网络) ；查询传递过程中的通讯错误( 连接错误、中转 节点错误) ；路由错误( 路由算法失败) 。 其中前两点错误与具体网络和节点机器状况相关，这种类型的错误可不 予考虑。本文重点考虑路由算法失败带来的错误，为了更加清晰地说明，信 息检索领域的两个重要评价指标准确率和召回率被引入进来，定义如下： 对于查询q ，其查询准确率定义为： p r e c i s i o n ( q ) = n c o r r e c tnn c o m p u t e ( 3 1 ) 式中： p r e c i s i o n 一查询准确率； n c o r r e c t 一 满足查询q 的节点的集合； n c o m p u t e 一一 资源搜索算法搜索到的满足查询q 的节点的集合。 对于查询q ，其查询召回率定义为： r e c a l l ( q ) = n c o r r e c tnn c o m p u t e ( 3 2 ) 式中： r e c a l l 表示召回率： n c o r r e c t 一一 满足查询q 的节点的集合； n c o m p u t e 资源搜索算法搜索到的满足查询q 的节点的集合。 ( 3 ) 查询效率 。 查询效率是由平均查询消息数和平均查询路径长度决定的。式( 3 3 ) 和 ( 3 - 4 ) 分别定义了平均查询消息数和平均查询路径长度。 其中，平均查询消息数量肘的定义为： 面= 粤 ( 3 3 ) 却 式中。 吖平均消息数； 岛一次查询所产生的总的消息数； 昂网络中的节点总数。 其中，平均查询路径长度的定义为： 1 4 哈尔滨丁程大学硕士学位论文 一厶 工= 上l 一 ( 3 4 ) 式中： 上平均查询路径长度； 厶第i 条查询路径的长度； 总的查询路径数。 一个优秀的资源搜索算法能使平均查询消息数m 和平均查询路径长度 尽可能小。但是这两者之间往往会相互影响，提升一项往往以牺牲另一项 为代价。例如基于泛洪算法的资源搜索方法比随机漫步的资源搜索方法产生 的查询消息多，但平均查询路径却往往比后者短。 本章分析和研究了不同类型的p 2 p 系统中的搜索技术，重点偏向于非结 构化p 2 p 系统。对于结构化p 2 p 搜索技术，本章将不予分析与阐述。有关结 构化p 2 p 搜索算法请参考文献 3 2 。 3 1 集中式搜索算法 集中式搜索算法是最早出现的p 2 p 资源搜索算法。在该搜索算法中，p 2 p 系统会对网络中的全部共享资源建立索引，如n a p s t e r 、e m u l e 等。这种系统 的架构如图3 1 所示。 图3 1 集中式搜索算法示意图 如图3 1 所示，节点a 首先把它自身共享的文件索引上传到中心索引服 务器( r ) 。当节点b 对a 所共享的文件感兴趣时，它就会向索引服务器( r ) 哈尔滨工程大学硕十学位论文 提出查询请求。当索引服务器检索到该文件的信息时，r 就会把存储该文件 的节点a 的地址( i p + 端口) 发送给节点b 。此时，节点b 就可以与节点a 建 立连接，开始下载该文件。 集中式搜索算法与后面将要提到的分布式搜索算法各有优势，集中式检 索速度较快并且保证能够找到全部文件，而分布式仅仅能保证查找到大部分 共享资源，但它的查询效率和可扩展性远远高于集中式搜索算法。 3 2 泛洪式搜索算法及改进 在泛洪算法中，当节点想要搜索某个资源文件时，它就会生成一条查询 消息，然后将该消息复制成n 份拷贝( n 为其邻节点个数) 并分别将这些消 息转发给它的所有邻节点。当它的邻节点接收到该消息时，这些邻节点又将 该消息进行复制，然后转发给它自身的所有邻居节点( 除了消息的上级转发 者) 。每条查询消息都有一个唯一的消息i d 。当一个节点接收到一条查询消 息时，该节点将会做出判断，确认该消息是否已被接收过。如果是，那么节 点就将该消息作为冗余消息而丢弃，反之，就进入下一步处理( 如：转发操 作) 。这种方式像洪水在网络中各个节点流动一样，所以叫做泛洪式 ( f l o o d i n g ) 搜索w 。由于这种搜索策略是首先遍历自己的邻接点，然后再 向下传播，所以又称为宽度优先搜索方法( b f s ) 。如图3 2 所示：搜索的节 点一开始t t l = 3 ，每向前广播一次t t l 减1 ，如果t t l 减到0 还没有搜索到资 源，则停止。如果搜索到资源则返回目标机器的相关信息以便于建立连接。 在搜索过程中可能出现循环，但是由于有t t l 控制，所以这个循环不会永远 进行下去，当t t l = o 的时候自然结束。一条查询消息到达它的生命终点有两 种可能：一是它被判断是冗余消息，二是它的t t l 值减为0 。一般而言，可 以称一条消息的前半段生命期为“低跳”，后半段生命期为“高跳”。 1 6 哈尔滨下程大学硕士学位论文 图3 2 泛洪式资源搜索算法示意图 泛洪式搜索算法具有回应时间短、覆盖范围广以及可靠性高等优点。2 0 0 1 年，相关机构研究表明在g n u t e l l a 系统中，当t t l = 7 时，网内9 5 以上的节 点都可以被覆盖到m ，。这是因为随着跳距越大，越多的节点将参与进来，对 查询消息进行转发，这种增长方式是成指数上升的。另外，在采用泛洪式搜 索算法的p 2 p 系统中，节点的加入、离开以及失效等行为对整个系统的消息 转发与信息交换能力所带来的负面影响非常小，因为所有的节点都担任着相 似的角色。 由于以上因素，泛洪算法被广泛应用到p 2 p 系统中。然而，随着p 2 p 系 统流行度的不断提升，以及系统规模迅速扩张，泛洪式算法的一些负面特征 也逐步显现出来。被大量冗余消息所导致的过量的网络流量增加了互联网的 运营负担。这个问题在高连通度的网络中尤为突出。当同一条查询消息的多 份拷贝通过某节点的邻节点传达给该节点时，除了最先到达的消息是可用的 之外，后续到达的消息都是冗余消息。这些冗余消息增加了网络带宽消耗和 节点的处理负担，但它们并没有扩大搜索的范围。2 0 0 0 年1 2 月，u s 互联 网研究中心做了一次统计，统计表明：一个具有5 0 0 0 0 个节点的g n u t e l l a 系统用于资源搜索而产生的网络流量占互联网总流量的1 7 。该结果表明大 量冗余消息的存在对g n u t e l l a 系统的发展和扩展产生了巨大的阻碍。 近年来，非结构化搜索算法的研究也大多基于对原始泛洪式搜索算法的 改进之上m 。为了进一步对泛洪算法进行改进，研究其内在规律和特征是非 常必要的。根据网络连通度的不同，本文分别选取了3 种连通度的6 n u t e l l a 1 7 哈尔滨_ t 稃大学硕+ 学位论文 网络模型进行实验，以寻求泛洪搜索技术的节点覆盖率以及冗余消息产生规 律。 实验对象的参数情况如表3 1 ， 表3 1 泛洪式搜索特征统计实验对象基本参数情况 连通度平均连通度节点总数 低 3 53 8 9 7 2 由 4 8 12 5 4 7 9 高 6 1 02 1 0 8 9 实验结果如下： 2 5 薄2 0 娄1 5 蠢1 0 鬈5 0 t 0 譬6 0 匿5 0 丑4 0 釉 瞎1 0 0 第猫第猷第碱第黜第雠第磷 瞵数 图3 3 泛洪节点覆盖增长率变化情况( 初始t t l = 7 ) 第磷第鳓，5 僦第嘲第戳第僦 磷数 图3 4 泛洪冗余消息分布情况( 初始t t l = 7 ) 根据以上实验结果，3 种连通度的p 2 p 网络在消息泛洪过程中，其节点 的覆盖增长率在低跳段( 6 t t l 3 ) 非常高，但在高跳段( 2 t t l o ) 非 i s 哈尔滨工程大学硕士学位论文 常低。再根据图3 4 的实验结果，其冗余消息的产生比例正好在低跳段较低， 而在高跳段较高。 在对纯粹的泛洪式搜索算法进行深入研究和分析之后，本文提出一种改 进方法，用于弥补现有的缺陷。如果查询消息是在一个树状结构的网络中广 播，那么上述所有的冗余消息将不会存在，如图3 5 。对于一个象g n u t e l l a 这样的具有高连通度的网络，它尽管在消息广播开销方面具有明显的优势， 但试图达到树状结构无冗余消息产生的效果是不可能的，这是由其拓扑和自 身的特点决定的。研究表明，在6 n u t e l l a 网络中，查询消息经过7 跳就可以覆 盖网内9 5 以上的节点，而对于随机构建的树状网络达到相同的效果需要经过 3 0 2 j h 。另外，断链或节点失效在树状网络中的可能导致网络部分瘫痪。然而， 如果查询消息起源于健壮性较强且子节点数较多的节点，那么这样的问题便 可以消除。 图3 5 树状网络无冗余消息广播示意图 纯泛洪式搜索在低跳段( 即泛洪的初始阶段) 具有较少的冗余消息数和 较高的节点覆盖增长率，处于低跳段的节点能够达到树状网络消息广播的优 点，同时能够最大限度地减少系统开销，明显优越于树状网络。在以上的分 析和研究的基础之上，本文提出一种纯泛洪式搜索算法的改进方法，称为基 于树状覆盖子网的泛洪式搜索。该改进方法结合了纯泛洪式搜索算法和树状 网络消息广播的优点。基本思想是：一条查询消息在初始若干跳段内采用纯 泛洪式搜索进行广