（计算机应用技术专业论文）基于兴趣定位的对等网络搜索机制研究.pdf

摘蜚 摘要 由于计算机网络和电子技术的飞速发展，网络带宽和计算机的计算能力呈指 数式提升，这导致了一种全新的分布式计算模式对等计算的出现。相应的， 对等网络技术也r 益受到人们的重视。由于对等网络具有分散式控制、自组织、 自适应和良好朐扩展性等优点，这使得它非常适合用来处理因特网中海量主机资 源。对等网络面临的一个核一i i , 问题就是如何在众多的网络节点中查找到某个特定 数据，也就是资源定位问题。深入研究对等网络中的资源定位和路由问题是构建 可扩展、自适应、高容错对等网络的理论基础，资源定位和路由问题是本文的研 究对象。 由于在对等网络中节点访问具有文件关联性的特点，也就是说节点访问文件 具有倾向性，因此，被访问的文件之间也具有关联性，而现有的对等网络文件共 享系统【l 】对此并没有相关的研究。文件关联性会给资源定位和路由带来什么样 的影响呢? 我们是否可以将文件关联性用于路由以提高路由效率呢? 这种利用 文件关联性的资源定位又有何种应用，又怎样来实现这些应用昵? 本文试图对这 些问题做出回答，并介绍两种利用文件关跌性来进行资源定位和路出的方法。本 文做出如下几个方面的工作： l 、将文件关联性融入到c a n 系统中，提出一个结构化对等网络模型 m c a n ： 和非结构化对等网络相比，结构化对等网络c a n 具有更好的路由效率、更 好的可扩展性和容错性。但c a n 系统没有考虑文件关联性特点，所以路由效率 仍不高。m c a n 系统在c a n 系统的基础上进行改进，它利用文件关联性进行资 源定位和路出，提出种结构化对等网络上的基于兴趣定位方法。在实验仿真中， 利用查询负载、查询路径长度、查询范围和附加状态来衡量m c a n 和c a n 系统 的性能，从实验结果可以看出，m c a n 系统可以迸一步提高路由效率。 2 、将m c a n 系统应用到电子商务资源管理中，实现电子商务资源的分前j 式 管理、发布和查询： 结构化对等网络模型m c a n 用于电子商务资源管理中，可以克服集中式资 源管理带来的单点失败问题，更有效的管理资源、发布资源和查询资源。 中囝科学技术人学硕l 毕业论文 3 、提出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 的性能。从实验可得出，关联表可以提高g n u t e l l a 的路由效率具有良好的可扩展性和良好的负载分析i 能力。 关键词：对等网络，s u p e r 节点，基于兴趣定位方法，文件关联性，叠加层 摘望 a bs t r a c t t o d a y se x p o n e n t i a lg r o w t hi nn e t w o r kb a n d w i d t ha n dc o m p u t i n gc a p a c i t yh a s i n s p i r e d aw h o l en e wc l a s so fd i s t r i b u t e d a p p l i c a t i o n ，p e e r t o p e e ra p p l i c a t i o n i n f r a s t r u c t u r e s p e e r - t o p e e r s y s t e m sh a v em a n yi n t e r e s t i n gt e c h n i c a la s p e c t sl i k e d e c e n t r a l i z e dc o n t r o l ，s e l f - o r g a n i z a t i o n ，a d a p t a t i o na n ds c a l a b i l i t y , w h i c hm a k ei t a p r o m i s i n gc h o i c eo fh a r n e s s i n gt h eh u g er e s o u r c e so fv a s tn u m b e r so fi n t e m e th o s t s l i k eo t h e rd i s t r i b u t e ds y s t e m s ，t h ec o r eo p e r a t i o ni np e e r - t o p e e rs y s t e m si se f f i c i e n t l o c a t i o no fd a t ai t e r n si nd e c e n t r a l i z e dn e t w o r k s t h i sd i s s e r t a t i o nc o n c e n t r a t e so nt h e s t u d yo ne f f i c i e n tl o c a t i o na n dr o u t i n gi np e e r - t o p e e rn e t w o r k ，w h i c hi st h et h e o r y f o u n d a t i o nf o rc o n s t r u c t i n g s c a l a b l e ，s e l f - o r g a n i z i n ga n df a u l t t o r r e n tp e e r ，t o p e e r n e t w o r k i n p e e r - t o - p e e r n e t w o r k ，p e e ra c c e s s i n g f i l e s o ro t h e r p e e r s s h o wt h e c h a r a c t e r i s t i co ff i l er e l e v a n c y t no t h e r w o r d s ，p e e r sa r ea p tt oa c c e s ss o m ek i n do f f i l e s ，a n dt h e s ef i l e sa r er e l e v a n t m o s to fp e e r - t o p e e rs y s t e m sd on o tc o n s i d e rt h e c h a r a c t e r i s t i co ff i l e r e l e v a n c y , s ot h er o u t i n gp e r f o r m a n c eo ft h e s es y s t e m si sn o t e f f i c i e n te n o u g h w h a t i m p a c t w i l lf i l er e l e v a n c yt a k et or e s o u r c el o c a t i o na n d r o u t i n g i np e e r - t o p e e rs y s t e m s ? s h o u l dw eu s i n gt h ec h a r a c t e r i s t i c o ff i l e r e l e v a n c yt o p r o m o t et h er o u t i n gp e r f o r m a n c eo fp e e r - t o p e e rs y s t e m s ? w h a ta p p l i c a t i o nw i j i c o m ef o r t h ? a n dw ew i l lh o wt or e a l i z a t i o nt h e s ea p p l i c a t i o n s ? t h i sd i s s e r t a t i o nt r i e s t oa n s w e rt h e s eq u e s t i o n sa n di n t r o d u c e st w oe f f i c i e n tl o c a t i o nm e t h o d st h a tu s i n gt h e c h a r a c t e r i s t i co ff i l er e l e v a n c yt ol o c a t i o nd a t ai t e m s w ec a l l e dt h el o c a t i o nm e t h o d u s i n gt h ec h a r a c t e r i s t i co ff i l er e l e v a n c ya si n t e r e s t - b a s e dl o c a l i t y t h ed i s s e r t a t i o n t r i e st ou s ef i l e r e l e v a n c y t o p r o m o t e t h el o c a t i o na n d r o u t i n gp e r f o r m a n c eo f p e e r - t o p e e rs y s t e m s ，a n dm a k ec o n t r i b u t i o n sa st h ef o l l o w i n g ： 1 、i n t e g r a t i n gi n t e r e s t - b a s e dl o c a l i t yt ot h es t r u c t u r e dp e e r - t o p e e rs y s t e m ，c a n ，a n d p r e s e n t i n ga s t r u c t u r e dp e e r t o - p e e rn e t w o r k m o d e l ，m c a n ， s t r u c t u r e dp e e r - t o - p e e r n e t w o r k ，c a n ，h a sm a n ya t t r a c t i v ef e a t u r e s ，s u c ha s ， e f f i c i e n tr o u t i n gp e r f o r m a n c e ，g o o ds c a l a b i l i t ya n df a u l t t o r r e n t b u tc a n d o e sn o t t a k ef i l er e l e v a n c ei n t oa c c o u n t ；t h er o u t i n gp e r f o r m a n c eo fc a n i ss t i l lu n e f f i c i e n t 1 l l 中因科学技术人学彤! i 毕业论殳 m c a ni n t e g r a t e sf i l er e e v a n c ei n t oc a nt oi m p r o v er o u i i n gp e r f o r m a n c e ，w e e v a l u a t em c a n a n dc a n b yq u e r yl o a d ，t h el e n g t ho fr o u t i n gp a t h ( a p p l i c a t i o n l a y e r h o p s ) ，q u e r ys c o p ea n d a d d i t i o n a ls t a t e f r o mt h ee x p e r i e n c er e s u l t ，w ec a nl e a r nt h a t m c a nc a ni m p r o v et h er o u t i n gp e r f o r m a n c eg r e a t l y 2 、p r o p o s i n g a ne - b u s i n e s sr e s o u r c e m a n a g e m e n ts y s t e m ，r s m ，w h i c ha d o p t i n g s t r u c t u r e dp e e r - t o - p e e rs y s t e mm c a na st h er e s o u r c ep r o v i d i n gl a y e r r s mc a l l c o n q u e r t h es i n g l ep o i n tf a i l u r ep r o b l e m b yu s i n gd e c e n t r a l i z e ds y s t e mm c a n a s t h er e s o u r c ep r o v i d i n gl a y e r 3 、p r o p o s i n gr e l e v a n c y t a b l el o c a l i t y , w h i c hi sa no v e r l a yo ng n u t e l l as y s t e m r e l e v a n c y t a b l el o c a l i t yt r i e st ou s ei n t e r e s t b a s e dl o c a l i t yt op r o m o t et h er o u t i n g p e r f o r m a n c eo f g n u t e l l a w ee v a l u a t er e l e v a n c yt a b l el o c a l i t ya n do t h e ra l g o r i t h m s b ys u c c e s sr a t e ，q u e r yl o a d ，t h el e n g t ho fr o u t i n gp a t h ，q u e r ys c o p ea n da d d i t i o n a l s t a t e f r o mt h ee x p e r i e n c er e s u l t ，w ec o n c l u d et h a tr e l e v a n c yt a b l el o c a l i t y c a n p r o m o t e t h ep e r f o r m a n c eo f g n u t e l l a ，d i s t r i b u t eq u e r yl o a dw e l l ， k e y w o r d s ：p e e r - t o p e e rn e t w o r k ，s u p e rn o d e ，i n t e r e s t b a s e dl o c a l i t y , f i l er e l e v a n c l o v e r l a y v 瓣一带绪论 第一章绪论 证如摩尔定律指出的那样，“每十八个月处理器性能提高一倍，而价格降低 一半”，计算机的低廉价格让其使用越来越广泛。如何有效利用这些汁算机资源 也随之成为研究的热点问题之一。计算模式随着计算机性能及其网络速度的快速 增长经历了三个阶段 2 ：主从模式、客户机服务器模式( c i s ) 和对等计算模 式。 主从模式的系统构成以大型主机和哑终端为特征，它产生的客观条件是出于 在早期计算机是一种昂贵的奢侈品而且它们的功能相对较弱。这时的哑终端完全 依赖于大型主机，就像婴儿完全依赖于父母。 客户机服务器模式中，系统分成两大部分服务器和客户机，其基本工 作方式是客户机发出请求，服务器接受后，进行分析处理，然后将结果返回给客 户机。 对等计算模式也称为s e t - v e n t 模式，在此模式中每台机器既可以作为客户机 也可以作为服务器，每台机器通过对等网络( p e e r t o p e e r ，p 2 pn e t w o r k ) 3 】的 连接相互协作，从而达到拥有超强计算能力的网络环境，因而在高性能计算迅猛 发展的今天对等网络的研究也成为研究的热点。 1 1 研究动机 p 2 p 是英文“p e e r t o p e e r ”的缩写，称为对等网络或者点对点技术。p 2 p 足一种网络模型，在这种网络中所有的节点都是对等的( 称为对等节点) ，也就 是说每个节点即使客户机又是服务器，各个节点具有相同的责任与能力并协同完 成任务。对等节点之间通过互连贡献信息资源、处理器资源、存储资源甚至商速 缓存资源等，无需依赖集中处理器或资源就可以完成。p 2 p 的这种工作模式称为 s e r v e n t 模式它与当前广泛使用的客户端朋务器( c s ) 的掰络模式形成鲜明的 对比。c s 模式中的服务器是网络的控制核心，而s e r v e n t 模式没有任何集中控 制，因而具有很高的自治性、自适应性、随机性和良好的可扩展性等优点。 p 2 p 技术引起人们热切关注起源于n a p s t e r 4 】，g n u t e l l a 5 】，k a z a a 6 】， 中田科学技术人学坝i ：毕业论史 b i t t o r r e n t 7 等p 2 p 产品的应用。随着社会和网络的发展人们对数据存储和传 输有着迫切的需求，文件共享是日前p 2 p 最重要的一个应用，而如何有效的定位 资源又是文件共享的关键问题，所以对对等网络中的资源定位方法的研究是对等 网络研究的核心问题。对埘等网络中对等节点之问的数据访问的分析可以得出， 埘等节点上存储的数据之间具有一定的关联性，也就是节点访问文件的倾向性翮 文件之削的关联性。如果能将这些具有关联性的文件存放在某个集中的范围内， 那么对等网络系统的定位效率可以得到改善。但当前大多数的对等网络没有考虑 到文件关联性的特点，所以在本文中我们将基于文件关联性特点对对等网络进行 研究。 1 2 论文的研究背景 对等网络为大家所熟悉，得益于个叫做n a p s t e r 4 的文件共享系统的成功 运行，该系统主要用于m p 3 音乐文件的共享。随之又有g n u t e l i a 5 和f r e e n e t 8 1 等初级的对等网络应用系统的成功推出，对等网络受到了人们更加广泛的关注， 虽然大多数人关心的是由此引发的版权问题。由于对等网络具有分散控制、自组 织、自适应和良好的可扩展性等优点，使得人们对对等网络技术的研究投入越来 越多的关注。n a p s t e r 采用一神集中式的查找定位算法，具有一个集中的中央服 务器虽易于维护、查找效率高但存在可扩展性和单点失败的问题。g n u t e l l a 和 f r e e n e t 采用的是非结构化的分散查找定位方法，没有任何的中心服务器，具有 高度分散的特点，但它们存在着搜索效率不高的问题。针对g n u t e l l a 的这种不足 又出现了结构化的分散查找定位方法，如c h o r d 9 ，它提高了搜索效率具有更好 的可扩展性，但目前结构化对等网络的实际应用很少。 1 3 问题提出 如果对各个超级市场的数据仓库进行分析我们可以发现某些商品被购买时 存在着一定的联系，比如“人们在买黄油和牛奶的同时也买面包”。这种联系对 超市经营者有着很重要的意义，经营者希望将那些常常一起购买的商品摆放在一 起以增加销售，因而在现代的很多超市中许多往往被顾客同时购买的商品被摆放 在一起。在对等网络的文件共享系统中也有着类似的舰律存在：节点访问文件的 鳃一章结论 倾向性和文件之间的关联性。比如“节点a 所访问的文件大多是关于某一主题 ( 如影视) 的”或者“节点a 在访问文件d l 后很有可能再访问文件d 2 ”，这些 文件都有着一定的关联，它l r 3 ：i , p 有可能都要被某些节点访问。如果我们能将这些 棚关联的文件存放在一个节点上，那么就可以提高文件共享系统的效率，因为棚 关联文件被存放到一个节点上，当节点a 从节点b 获取文件d 1 后要获墩与文件 d l 相关联的文件d 2 只要直接访问节点b 就可以获得了，无需经过资源的搜索 定位节省了搜索定位时间和带宽。通过这种方式我们可以将一个节点上的所有文 件归结为类，它们之间都存在着某种关联( 同一主题) ，那么与这个节点有关 系的所有节点上存放的文件和该节点上的文件也就存在着关联，这些节点也就组 成了一个无形的类。我们将这种具有相同倾向( 主题) 和关联的文件特性称之为 文件关联性，而利用文件关联性特点进行搜索定位和路由的方法则称之为基于兴 趣定位方法。 但目前对等网络的所有文件共享系统并没有考虑到文件关联性的特点，因而 我们提出了以下几个问题。 问题1 ：这种利用文件关联性特点进行资源搜索定位的方法又有什么优势? 问题2 ：如何利用文件关联性特点来进行结构化对等网络资源的搜索定位? 目前许多对等网络的应用都是用于文件共享的，然面对等网络的应用并不只 限于文件共享。它还可以用于协同合作、边界服务、分布式计算 1 0 】、分布式代 理【1 1 】、主动网络【1 2 】、电子商务等领域。许多重要的研究领域，比如聚集计算 13 】、 网格计算 1 4 1 也可以借鉴对等网络中的思想。 阅题3 ：我们能将这种利用文件关联性的搜索定位方法用于什么样的应用呢? 问题4 ；如何将文件关联性特点融入到非结构化对等网络，非结构化对等网络的 陛能又会有什么样的改善昵? 本文对以上的问题一进行回答，并获得正确的结论。我们将利用文件关联 性的基于兴趣定位的搜索方法融入于结构化对等网络c a n 中，并将这种定位方 法应用于电子商务中的分布式注册服务中。 司时我们还将这种定位方法结合到 g n u t e l l a 系统中，看文件关联性定位方法对g n u t e l l a 系统有何作用。 中困l i 学技术人学碳f 毕业论业 1 4 文章组织 本文的组织结构如下所示： 第一章绪论 首先介绍研究动机和研究背景，然后根据文件相关性提出对等网络研究中的 问题，如何将文件相关性用于对等网络搜索提供搜索性能，最后是文章的组织结 丰 ：| 介绍。 第二章对等网络的研究现状 首先对对等网络的特征及其分类进行介绍；然后介绍n a p s t e r 4 】、g n u t e l l a 5 】、 k a z a a 6 、m o r p h e u s 1 5 、e d o n k e y 1 6 和b i t t o r r e n t 7 i 粼6 5 的非结构化对等 网络代表；其次是结构化对等网络t a p e s t r y 1 7 、p a s t r y 1 8 、c a n d 和c h o r d 的介绍；最后介绍了对等网络的一些应用。 第三章结构化对等网络模型m c a n 在结构化对等网络中利用文件关联性对资源进行定位，基于c a n 模型提出 基于兴趣定位的结构化对等网络模型m c a n 。对m c a n 系统进行仿真实验，本 文通过查询负载、查询范围、查询路径长度和附加状态这些衡量尺度来衡量 m c a n 的性能，并将m c a n 系统和c a n 系统进行比较。 第四章m c a n 技术应用研究 本章将第三章中提出的m c a n 对等网络模型应用于电子葡务的资源管理 中，提出基于m c a n 的电子商务资源管理系统模型r s m 。r s m 利用结构化对 等网络模型m c a n 作为资源提供层，克服了集中式资源管理系统带来的单点失 败问题，同时对资源进行完全分布的管理，利用m c a n 路由进行资源的有效定 位。 第五章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 作为下层资源定位机制，通过构造节点关联表在g n u t e l l a 系统上添加一个叠加 层a 本文通过成功率、查询负载、查询范围、查询路径长度和附加状态来衡量关 联表方法的性能，并将关联表方法和g n u t e l l a 的f l o o d i n g 方法进行比较。 第六章总结与展望 4 瓤一书埔论 总结全文并对将来继续进行的工作进行展望。 本文的总体结构如图1 i 所示。 图1 - 1 本文组织结构图 中用科学投术人学坝 j 毕业沦立 第二章对等网络的研究现状 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 等p 2 p 产品的应用。随着社会和网络的发展，人们对数据存储和传输、高性 能计算等有着迫切的需求，这些杀手级应用( k i l l e ra p p l i c a t i o n s ) 满足了人们快 速交换大容量数据的需求。p 2 p 技术避免了c s 结构带来的单点失效、性能胍 颈和网络拥塞等问题，p 2 p 技术不依赖或尽a i r , q , 依赖中央服务器，使得每个 p e e r 既能作为服务器，也可成为客户机。p 2 p 技术的核心思想就是将网络应用 的核心从中央服务器向网络边缘的终端设备扩散：这些终端设备可以是高性能 计算机，可以是p c 机，可以是手机，也可以是p d a 等等。 2 1 对等网络的特征及分类 随着计算机处理能力的进一步增强，当前市场上任一台新生产的计算机都 可作为服务器。p 2 p 的每个p e e r 既是客户机。又是服务器，还是路由器。p 2 p 的各个p e e r 因互为服务而共存，而不是依赖于特定的集中式机制；而且，各个 节点可以直接交互并可能随时离开对等网络。对等网络的以下特征使之与传统 系统相区别： a ) 每个节点既是客户机，又是服务器： b ) 节点之间通过直接建立连接，交互共享资源： c ) 资源分布在各个节点中，而不是集中在一个服务器中进行管理： d ) 节点具有动念性与即席性： e ) 有着极强的扩展性： f ) 纯p 2 p 系统没有任何集中控制机制，系统的各个节点运行的p 2 p 系统 软件功能相同。 p 2 p 根据其不同特性可以有不同的分类方法。本文介绍的是按照其，网络拓 扑结构和应用范围两种分类方法。 对等网络按结构的不用可分为结构化对等网络和非结构化对等网络。网络 拓扑结构是固定的，有规律的系统为结构化对等网络。c h o r d 、t a p e s t r v 、p a s t r v 靴_ 二帝对等m 络的研究耽状 车【ic a n 都属于结构化对等网络。这类网络提供了文件i d 和文件存储位冒之 间的映射关系，从而保证有效路山，并保证展终找到目标节点。而在非结构化 对等网络中( 如g n u t e l l a ，b i t t o r r e n t ) 中，对等节点连接任意其它对等节点构成 对等网络，数据放置与对等网络拓扑无关，网络拓扑是a dh o c 的。与非结构 化对等网络比较，结构化对等网络具有查找效率商和查找确定性等优点。路 算法是结构化对等网络的核心，路由算法的路由效率、可扩展性和容错性都直 接影响到结构化对等网络系统的资源定位效率、可扩展性和容错性。h a s h 算 法在结构化对等网络和非结构化对等网络系统中都有应用，分别是文件i d 和 文件存储位置之间的映射关系，以及生成文摘文件( 以保证文件的完整性和下 载安全性) 。m d 5 - h a s h 文件的数字文摘通过h a s h 函数计算得到。不管文件 长度如何，它的h a s h 函数计算结果是个固定长度的数字。与加密算法不同， h a s h 算法是一个不可逆的单向函数。采用安全性高的h a s h 算法，如m d 5 、 s h a 时，两个不同的文件几乎不可能得到相同的h a s h 结果。因此，一旦文件 被修改，就可检测出来。在2 2 和2 3 节分别介绍非结构化p 2 p 和结构化p 2 p 系统的例子。 p 2 p 系统按照应用范围来分类，可以分为：实时消息传递、管理和共享信 息、协作和分布式服务。 实时消息传递( i n s t a n tm e s s a g i n g ，i m ) 使得在线用户可以宣接的以实时方 式进行一对一的或成组的消息交流。通过使用i m 服务，用户安装系统客户端 软件并且登录中心服务嚣以后，服务器会将该用户设鬣为在线状态。这样，该 用户才能和其他用户建立直接的连接。i m 的产品有：腾i r q q 、i c q 和a i m 等。 由i m 衍生出来有交互式网络游戏，即通过网络节点进行的交互式在线游戏。 p 2 p 网络游戏有着广阔的市场前景，国内人气极旺的有联众、盛大网络等等。 管理和共享信息包含了文件共享、资源共享和分布式搜索引擎。文件共享， 比如g n u t e l l a 和k a z a a 不需要中心化的管理或控制机制就能实现文件共享。 资源共享是一种分句式的计算形式，即通过动态方式利用节点计算能力柬处理 一些过去只能有超级计算机才能处理的任务。而分布式搜索引擎是将创建为资 源检索结果的信息索引所需的功能扩展到有对等节点存在的网络边缘。它采用 了分丽治之的策略来定位信息并执行信息的实时搜索功能。 中圆科学技术人学坝f j 毕业沧文 p 2 p 分和式服务又分为分布式计算和分布式网络服务。分确i 式计算例子有 s e t i h o m e 项刚2 0 】，即利用节点空闲c p u 时间片断来计算寻找外星人程序。 分布式网络服务特点在于将网络流量局部化，这样不仅降低了网络丌= 销还缩短 了程序响应时问。c y t a q 公司丌发的d i s t r i b u t e dr e s o u r c en e t w o r k 2 ll 就是一个 p 2 p 分斫j 式网络服务的例子。它是一个由连接和集成了一个企业中的多种不同 信息源的资源路山器组成的网络，这些资源包含多种应用程序和数据库的信 息。多个信息源可以连接到一个资源路由器上或者一个信息源连接到多个资 源路由器上。 2 2 非结构化对等网络 非结构化对等网络有着广泛的应用，而且这些应用被人们所普遍接受。在 本节我们将介绍非结构化p 2 p 的几个比较成功的应用实例：n a p s t e r 、g n u t e l l a 、 e d o n k e y 和b i t t o r r e n t 。 2 2 1 n a p s t e r 算法 n a p s t e r 是一种用于音乐文件交换的对等网络应用软件，但它本身并不是 一个纯粹的对等网络系统。它具有一个中央服务器，里面保存了所有注册过的 音乐文件，所有查询工作由中央服务器完成；之后，各个节点采用点对点的方 式进行直接的通讯。很明显，n a p s t e r 采用这种集中服务器的方式共享音乐文 件很可能存在单点失败问题，它的可扩展性也不佳。 c l i e n tbc l i e n ta c l i e n tc 图2 1n a p s t e r 中集中式查询算法原理示意图 第一二帝对等刚络的研究现状 图2 1 描述了n a p s t c r 采用的集中式查询算法的原理。当某个客户( 比如 图中的c l i e n t a ) 要查询某个数据k ，它首先向服务器( 比如图中的s e r v e r a ) 提交查询请求，服务器查询它保存的注册过的文件信息返回查询结果( a n * 数 据k 存放于c l i e n tc 中) ，然后，两个客户机c l i e n ta 和c l i e n tc 进行直接的 通汛，c l i e n t a 从c l i e n t c i - 获取数据k 。 2 2 2g n u t e l l a 算法 g n u t e l l a 是非结构化对等网络中的一个杰出代表它吸取了n a p s t e r 的失 败教训，将p 2 p 的理念更推进一步：它不存在中枢目录服务器，用户只要安 装了该软件，立即变成一台能够提供完整目录和文件服务的服务器，并会自动 搜寻其它同类服务器，从而连成一台由无数p c 组成的网络超级服务器。 g n u t e l l a 采用完全分布的查询算法，它不依赖于任何的中央服务器，系统 中的每个节点都是同等的。它采用f l o o d i n g 算法来广播查询请求，每个接收 到查询请求的节点检查自己是否有满足查询的数据存在，如果有则返回结果， 并将接收到的查询消息广播给它的邻居节点。这种算法是完全分布的，有效的 避免了单点失败问题，但由于它采用了广播机制进行查询，所以其可扩展性不 好。 在第五章，我们将对g n u t e l l a 的f l o o d i n g 算法的原理进行详细的描述， 并在g n u t e l l a 上提出一种基于兴趣定位的定位方法关联表定位方法。 2 2 3e d o n k e y e d o n k e y 是由j e dm c c a l e b 在2 0 0 0 年创立起来的。最重要的是可以同时 从许多人那里下载同一个文件，它采用了“多源文件传输协议”( m f t p ，t h e m u l t i s o u r c ef i l et r a n s f e rp r o t o c 0 1 ) 。电驴的索引服务器并不集中在起，而是 各人私有的，遍布全世界，每一个人都可以运行电驴服务器，同时共享的文件 索引为被称为“e d 2 k q u i c k l i n k ”的连接，文件前缀为“e d 2 k ：”。同时，存 协议中，定义了一系列传输、压缩和扣包的标准甚至还定义了一套积分的标 准，用户上传的数据量越大，积分越高，下载的速度也越快。而且每个文件都 中田科学技术人学倾i j 毕业论义 有r o d 5 h a s h 的超级链接杯示，这使得该文件独一无二，并且在整个网络上都 可以追踪得到。 e d o n k e y 可以通过检索分段从多个j e | 户那晕下载文件，最终将下载的文件 片断拼成整个文件。而且，只要用户得到了一个文件片断，系统就会把这个片 断共享给大家，尽管通过选项的设置用户可以对上传速度做一些控制，但用户 无法关闭它。 当然，e d o n k e y 也存在些不足之处。比如其分段下载的机制存在一定负 面影响，一个大型文件分割成许多单元来下载，如果下载的过程中有一个单元 破损，整个文件就不能够使用了。而且更糟糕的是由于这种下载机制，在启动 下载任务时e d o n k e y 需要搜索该文件所有可以使用部分的来源，然后分析每 一个来源是搠有整个文件还是文件的一部分。再根据具体的情况来安排下载任 务，通常从启动下载任务到开始传输第一个字节，需要等待好几分钟的时间。 如果用户中途关闭程序，在下次启动继续下载时，除了得重新搜索和分析文件 来源，还需要分析e d o n k e y 用于存储已下载单元的缓存文件，这通常需要花 费更多的时间。 总之，g n u t e l l a 和e d o n k e y 以及e m u l e 代表了第二代p 2 p 无中心、纯分布 式系统的特点，它不再是简单的点到点通信，而是更高效、更复杂的网络通信： 再加上e d o n k e y 和e m u l e 引入的强制共享机制，在一定程度上避免了第一代 p 2 p ( n a p s t e r ) 纯个人服务器管理带来的随意性和低效率。 2 2 4b i t t o r r e n t b i t t o r r e n t ( 简称b t ) 引起人们的关注是在人们下载r e d h a t9 0 的时候。 通过b t ，在短短的几个小时内，全部3 张光盘镜像的5 0 0 份拷贝被下载，数 据总量达到了1 5 t b ，相当于2 0 0 0 多部高质量电影，最高速度达到了1 7 0 m b 秒。如此快捷、高效、自发而又有序的数据传播方式，在b t 出现以前几乎是 不可思议的事情。 b t 批判地继承了前辈产品的优点，将中心目录服务器的稳定性同优化的 分布式文件管理结合起来，从而在效率上远远超出了电驴这类产品。它要求提 供一个或多个统一的w e b 发布服务器，供网友此发布和搜寻资料。在客户端， 0 第一二窜对等叫绻的研究耽状 它通过一个i e 插件提供下载、上传管理。b t 把一份大文件切割成碎片，给每 一个碎片标上特殊标识，用户无需到一个固定地点( 例如传统网络的中心服务 器) 上下载完整的文件，系统会帮助用户自动寻找、随机下载具有相同标识的 文件碎片，将其加以整合成为完整的文件。 b t 不需要指定服务器，虽然在b t 罩面还是有服务器的概念，但使用b t 的人并不需要关心服务器在哪里，b t 的服务器称为t r a c k e r 。用b t 下载，需 要得到一个扩展名是t o r r e n t 的文件，这个文件很小，可以放在某个w e b 服务 器上，或者用f t p 和传统的p 2 p 束得到，甚至作为附件贴在论坛上。这个文 件翠面存放了对应的发布文件的描述信息、浚使用哪个t r a c k e r 、文件的校验 信息等，b t 用文件关联来对其进行处理。 使用b t 不用担心会下载到死档( 即无法下载完的文档) ，b t 把提供文件的 人称为种予( s e e d ) ，正在下载的人称为客户( c l i e n t ) ，某一个文件现在有多少 种子多少客户是可以看到的，只要有一个种子，就可以放心的下载。当然，种 子越多、客户越多的文件下载起来的速度会越快。如果传输中间断掉了，也没 有关系，再次打丌t o r r e n t 文件，b t 会自动的续传。 为了方便使用b t 技术，有人还专门开发了b t 的辅助工具，比如p t c 就 是一个非常完整的工具。它不仅可以查询下载信息，还可以做下载酊的侦察。 获得更多准备信息以决定是否下载。同时它还可以让用户随时制作并发布一 个t o r r e n t 。p t c 甚至可以使用一个脚本来读取r s s 的内容并搜索获得更多扩 展的共享资源。 2 3 结构化对等网络 对等网络的核心是路由算法，路由算法的可扩展性和容错性直接影响到对 等网络系统的性能，因此对等网络路由算法的研究具有重要的意义。结构化对 等网络路由算法由于查找可确定性、简单性和分布性等优点，j 下成为研究和应 用的焦点。本章介绍了几种有影响的结构化对等网络路由算法，如t a p e s t r y 、 p a s t r y 、c a n 和c h o r d ，这些算法都是基于分布式哈希表的【2 2 。 中国羊 学技术人学硕l ：毕业论文 2 3 1 t a p e s t r y 算法 t a p e s t r y 是伯克利的z h a o ，k u b i a t o w i c z 和j o s e p h 提出的一种用于在 o c e a n s t o r e 2 3 】中进行查找和路由工作的基础结构。它的工作机制来源于 p l a x t o n 2 4 方案，其命名、结构和核心查询和路出原理都类似于p l a x t o n ，但它 提供了自适应、容错性和自我优化等特性。 t a p e s t r y 算法中每个节点都需要维护一个邻居图( 路由表) 、反向指针 列表。对象位置指针和一些热点监视信息。路由表的大小为b x l o g s n ( b 行， l o g b n 列) ，每一项包含了网络中与当前节点最近的那些节点的信息，而且这 些节点标识号中与列数相应数目的后缀也要与当前节点相同( 即第i 列需要有 i 个后缀相同) 。每个节点还要维护一个指向其邻居的反向指针列表，主要用 于生成节点的路由表。对象位置指针采用拓扑形式 ，用于 在对象向服务器发送路由请求时提供帮助；热点监视信息采用如 这种形式的拓扑集合，这些信息用于帮助缓冲决定路由。 t a p e s t r y 的核心定位与路出机制类似予p l a x t o n 算法。首先，当前节点计 算自己的i d 与目的i d 的相同后缀的数目j ；然后，从路由表中选择一个中间 节点( 一般在j + 1 列) ，使得中间节点的i d 与目的劫夺的d 相同的后缀数 目大于等于j + l ，接着把查询请求任务转交给这个中间节点继续查询。这个过 程递归执行，知道找到目的i d 。可以看出每次任务转交，中间节点的i d 和目 的节点的i d 的相同后缀数据至少会增加1 ，如果将i d 作为字符串则串长为 l o g b n ，因此，t a p e s t r y 中，从任意一个节点开始查询，都能在l o g b n 跳内路由 到目的节点。 2 3 2p a s t r y 算法 p a s t r y 是m i c r o s o f t 和r i c e 大学共同发起的对等网络匿名存储系统中的定 位和路由算法，该算法与t a p e s t r y 有许多相似之处：使用匹配 缀或者后缀地 址的路出方法、插入和删除算法有类似的代价；它们在设计时都考虑了查询的 实际路径( 职) 路由和逻辑跳之间的关系，通过一定手段侵得相对延迟( r e l a t i v e d e l a yp e n a l t y ， r d p ) 2 5 尽可能少。p a s t r y 与t a p e s t r y 的区别在于：第一， 第一章对等刚络的研究现状 p a s t r y 中对象复制无需山所有者束控制，在对象的出版发布过程中，复s q j c , j - 象 被放到与对象编号最接近的多个节点上。第二，t a p