（计算机软件与理论专业论文）对等网络有效资源搜索技术及其应用研究.pdf

山东师范大学硕士学位论文 摘要 对等网络( p e e rt op e e r ，p 2 p ) 的出现是对传统c s 网络架构的一次进化。由于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 d e n t i f y ，i d ) 而穿越了不同的自治域， 导致了较大的搜索延迟；另外，当前结构化p 2 p 的路由算法在设计时都假设节点有相同 的处理能力，然而实际中对等节点的处理能力是异构的，对等节点的负载存在着严重不 平衡的现象，影响了资源搜索算法的工作效率。 针对上述问题，本文的工作围绕结构化p 2 p 系统的资源定位和负载平衡展开研究， 主要成果可概括为以下两个方面： 第一，为了改善结构化p 2 p 系统的搜索性能，依据网络通信中的访问局部性( 包括 空间局部性和时间局部性) 原则，提出了l c h o r d 资源定位技术，并根据该技术设计了 一种文件共享系统p p f i l e 。 c h o r d 是一种环形拓扑的结构化对等网络结构，因其结构简洁，具有可扩展性而被 广泛采用。l c h o r d 资源搜索技术基于c h o r d 并对其进行了两个方面的改进： 1 ) l c h o r d 依据空间局部性对c h o r d 选择指针的方法进行改进，缩短了搜索的逐跳 延迟。c h o r d 根据指针表确定搜索请求的转发节点，c h o r d 中的节点在构造指针表时， 总是在逻辑空间中选择与构造者距离最近的节点作为指针，忽略了指针与构造者在物理 网络上的距离；l c h o r d 中的节点在构造指针表时，在保证c h o r d 原有的路由正确性的 前提下，选择与构造者在同一个自治域中的节点作为指针。由于节点所属的自治域基本 不发生变化，因此增加了指针表的稳定性，减小了系统和节点的开销，并且体现了网络 通信中的时间局部性，即与一个节点重复地通信。l c h o r d 中的节点依据改造后的指针 表转发搜索请求，避免了由于经过不同自治域而造成的高延迟，从而缩短了搜索请求在 路由过程中的逐跳延迟。 2 ) l c h o r d 使用基于相关性的搜索策略进行资源定位，缩短了搜索路径长度。具体 做法是：根据节点共享数据的相关性为节点建立兴趣社区，节点发出的请求首先与兴趣 社区中的节点进行匹配，若兴趣社区无法满足请求，再使用指针表转发请求。由于节点 山东师范大学硕士学位论文 在具有相似兴趣的节点处更有可能找到所需资源，而兴趣社区包含了与节点在兴趣上有 最大相似性的节点，因此l c h o r d 可以缩小搜索范围，缩短查询路径长度。节点每次发 出搜索请求时，兴趣社区是节点重复通信的对象，因此基于相关性的搜索策略体现了网 络通信中的时间局部性。 模拟实验结果表明，l c h o r d 与c h o r d 相比，缩小了搜索延迟，缩短了搜索路径长 度，从而提高了搜索效率。 最后，根据l c h o r d 搜索技术，本文结合x m l 技术设计了一种分布式文件共享系 统p p f i l e ，该系统可同时支持精确查找和模糊查找。 第二，针对结构化对等网络中负载平衡问题，提出了低开销的基于列表的负载平衡 技术( 1 0 wc o s t l i s t b a s e d l o a d b a l a n c i n g ，l c l l b ) ，该技术包括以下两个方面： 1 ) 使用一种新的虚拟节点选择方法c v s s ，减小了系统维护虚拟节点开销，并使系 统保持原有的容错性。传统的虚拟节点选择方法是在i d 空间中随机的选取，过多地增 加了系统维护开销，因此本文使用了一种在i d 空间中具有群聚性的虚拟节点选择方法 c v s s ，该方法在保持系统原有的容错性的前提下，考虑节点在容量上的差异为节点分 配适量的虚拟节点，并且使虚拟节点具有了群聚性，从而减小了系统的额外开销。 2 ) l c l l b 使用基于列表的负载平衡技术l l b ，减小了负载平衡的通信开销，实现 了可靠的负载平衡。l l b 利用c h o r d 为维护拓扑而在节点问进行的周期性通信交换负载 信息，并将收集到的负载信息分别存放于过载列表和轻载列表。节点根据负载量情况， 决定执行紧急负载平衡或周期负载平衡，将过载列表中的虚拟节点的负载转移到轻载列 表中的节点，实现负载均衡。 仿真实验表明，l c l l b 解决了由于文件在i d 空间分布不均而造成的负载失衡，并 且系统额外开销小，具有较好的可靠性。 关键词：对等网络；资源定位；访问局部性；负载平衡 i l 山东师范大学硕士学位论文 a b s t r a c t p e e rt op e e rn e t w o r k ( p 2 p ) i sar e v o l u t i o nt ot h et r a d i t i o n a lc l i e n t s e r v e rn e t w o r k a r c h i t e c t u r e e a c hn o d ei np 2 pc a l ls h a r eal a r g ea m o u n to fd a t aw i t ho t h e r s w i 廿lt h es c a l eo f t h ep 2 pn e t w o r kg r o w i n g ，i tc a l lr a p i d l ya c c u m u l a t ei n f l a t e di n f o r m m i o na n dp r o v i d ear i c h i n f o r m a t i o nw a r e h o u s ef o ru s e r s c o n s e q u e n t l y , a l le f f i c i e n ts e a r c hs c h e m ef o ru s e r st o r e t r i e v en e e d e dd a t aq u i c k l ya n da c c u r a t e l yi s r e q u i r e de m e r g e n t l y p r e s e n t r e s e a r c h c o n c e n t r a t e so ni m p r o v i n gl o c a t i o ne f f i c i e n c y , l o a db a l a n c e ，s c a l a b i l i t ya n de t c p 2 pn e t w o r k sc a nb ec l a s s i f i e di n t ou n s t r u c t u r e dp 2 pn e t w o r k sa n ds t r u c t u r e dp 2 p n e t w o r k s u n s t r u c t u r e dp 2 pn e t w o r k sa r ef i tf o rt h eh i g h l yd y n a m i cn e t w o r ke n v i r o n m e n t , f o r t h e ym a i n t a i nl o o s en e t w o r kt o p o l o g y b u tt h i sl 【i n do fp 2 pn e t w o r kh a sp o o rs c a l a b i l i t yo r c o n s u m e st o om u c hb a n d w i d t h s t r u c t u r e dp 2 pn e t w o r k se m p l o yas c a l a b l el o c a t i o ns c h e m e t og u a r a n t e es e a r c hs u c c e s s f u l l y , b u tt h en o d es e l e c t st h en e x th o pb a s e do nt h en o d ei d e n t i f i e r ( i d ) i nt h el o g i c a ls p a c i n g ，w h i c hp a s s i n gt h r o u g hd i f f e r e n ta u t o n o m ys y s t e m sr e s u l t i n gi n l o n gl a t e n c y a d d i t i o n a l l y , a l lo f t h el o c a t i o na l g o r i t h m sa s s u m et h a ta l ln o d e si nap 2 p s y s t e m h a v et h es a m ep r o c e s sc a p a c i t y h o w e v e r , t h ec a p a c i t yo ft h en o d e si nt h ep 2 pn e t w o r ki s e x t r e m e l yh e t e r o g e n e o u s ，w h i c hl e a d st ol o a di m b a l a n c ea n dr e d u c e st h ee f f i c i e n c yo ft h e l o c a t i o n a i m i n g a tt h e s ep r o b l e m sa b o v e ，t h i sp a p e rs t u d i e so nr e s o u r c el o c a t i o na n dl o a d b a l a n c i n gi ns t r u c t u r e dp 2 pa n dm a k e s t h ef o l l o w i n gt w oc o n t r i b u t i o n s ： 1 i no r d e rt oi m p r o v es e a r c hp e r f o r m a n c eo fs t r u c t u r e ds y s t e m s ，t h i sd i s s e r t a t i o np u t s f o r w a r dl c h o r da c c o r d i n gt ot h el o c a l i t yo fr e f e r e n c e ( i n c l u d e ss p a t i a la n dt e m p o r a ll o c a l i t y ) i nn e t w o r kc o m m u n i c a t i o n u s i n gx m l t e c h n o l o g y , w ec o n s t r u c t saf i l es h a r i n gs y s t e r n _ p p f i l eb a s e do nl c h o r d c h o r di sas t r u c t u r e dp 2 po fc i r c l et o p o l o g y a si th a st h en e a ts t r u c t u r ea n db e t t e r s c a l a b i l i t y , c h o r di su s e dw i d e l y l c h o r d ，w h i c hi sb a s e do nc h o r d ，m a k e si m p r o v e m e n ti n t h ef o l l o w i n gt w oa s p e c t s ： f i r s t l y , l c h o r di m p r o v e st h ef i n g e rs e l e c t i o na c c o r d i n gt ot h es p a t i a ll o c a l i t ya n dt h u s r e d u c e ss e a r c hl a t e n c yi ne a c hh o p p e e r si nc h o r df o r w a r dr e q u e s t sa c c o r d i n gt ot h e i rf i n g e r l i s t a sc o n s t r u c t i n gt h ef m g e rl i s t ，ap e e ri nc h o r ds e l e c t st h en e a r e s to n ei nt h ei ds p a c ea s i t sf i n g e ra n dn e g l e c t st h ed i s t a n c ei np h y s i c a ln e t w o r k w h i l ei nl c h o r d ，ap e e rs e l e c t st h e o n ew h i c hi si nt h es a m ea u t o n o m ys y s t e m ( a s ) a si t sf i n g e ri nt h ec o n d i t i o no fk e e p i n g r o u t i n gc o r r e c t n e s s a st h ea s o f ap e e rs e l d o mc h a n g e s ，i te n h a n c e st h es t a b i l i t yo f t h ef i n g e r l i s ta n dt h u sr e d u c e ss y s t e mc o s t s t 1 1 i ss e l e c t i o na l s oe m b o d i e st h et e m p o r a ll o c a l i t yi n l i i 山东师范大学硕士学位论文 n e t w o r kc o m m u n i c a t i o n ，i e k e e p i n gc o m m u n i c a t i o nw i t ht h es a m en o d e p e e r si nl c h o r d f o r w a r dr e q u e s t sa c c o r d i n gt ot h ei m p r o v e df i n g e ri i s ta n dt h u sa c q u i r el o w l a t e n c y s e c o n d l y , l c h o r du s e sal o c a t i o na l g o r i t h mb a s e do nd a t ar e l a t i v i t y ，s oi th a sas h o r t e r s e a r c hp a t h l c h o r dc r e a t e sa l li n t e r e s t - b a s e dc o m m u n i t yf o re a c hn o d ea c c o r d i n gt ot h e r e l a t i v i t yo fs h a r ed a t a w h e ni n i t i a t i n gar e q u e s t ，t h ep e e rf i r s ts e a r c h e si nt h ec o m m u n i t y i f t h ec o m m u n i t yc a n tm a t c ht h er e q u e s t ，t h ep e e rt h e nf o r w a r d si ta c c o r d i n gt ot h ef i n g e rl i s t a sp e e r sa l w a y ss t o r ef i l e st h a tt h e ya r ei n t e r e s t e di na n dm a yf i n dd a t an e e d e do nt h eo n e s t h a ts h a r ec o m m o ni n t e r e s t s ，l c h o r dl e s s e n st h es e a r c hs c o p ea n ds h o a e n ss e a r c hp a t h w h e n i ti n i t i a t e sar e q u e s t ，t h ep e e rc h e c k si t sc o m m u n i t ya n dt h ec o m m u n i t yb e c o m e st h eo b j e c t i o n t h a ti tc o m m u n i c a t e sw i t h r e p e a t e d l y , w h i c hs h o w st h et e m p o r a ll o c a l i t yo fn e t w o r k c o m m u n i c a t i o n 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 tl c h o r dh a sal o w e rl a t e n c ya n ds h o r t e rs e a r c hp a t ht h a n c h o r d t h i sp a p e r , u s i n gx m lt e c h n o l o g y , p r e s e n t sap 2 pf i l e s h a r i n gs y s t e mb a s e do n l c h o r d p p f i l e w h i c hs u p p o r t se x a c t - m a t c hl o o k u pa n df u z z ys e a r c hs i m u l t a n e o u s l y 2 a i m e da ti m p r o v i n gt h ed e g r e eo fl o a di m b a l a n c ei ns t r u c t u r e dp 2 p , t h i sd i s s e r t a t i o n p r e s e n t sal o wc o s tl i s t - b a s e dl o a db a l a n c i n ga l g o r i t h m ( l c l l b ) l c l l bm a i n l yi n c l u d e st h e f o l l o w i n gt w oc o m p o n e n t s ： f i r s t ，i nc o n d i t i o no fk e e pt h ef a u l tt o l e r a n c e ，l c l l bu s e sac l u s t e r i n gv i f t ：i i a ls e r v e r s e l e c t i o n ( c v s s ) a l g o r i t h mt or e d u c et h ec o s t so f m a i n t a i n i n gv i r t u a ls e r v e r s t r a d i t i o u a l l y , a s v i r t u a ls e r v e r sa r es e l e c t e dr a n d o m l yi ni ds p a c e ，i tr e s u l t sa ne x c e s sc o s t c v s st a k e st h e c a p a c i t yh e t e r o g e n e i t yo fp e e r si n t oc o n s i d e r a t i o nt oa l l o c a t ea p p r o p r i a t en u m b e ro fv i r t u a l s e r v e r sf o re a c hp e e ra n dh a st h e s ev i r t u a ls e r v e r sc l u s t e r e di nas e c t i o ni nt h ei ds p a c e ，s oi t r e d u c e st h es y s t e m se x t r ac o s t s e c o n d ，l c l l bu s e sl i s t e d b a s e dl o a db a l a n c i n g ( l l b ) a l g o r i t h mt or e d u c et h e c o m m u n i c a t i o ns p e n d i n ga n dk e e pr e l i a b l el o a db a l a n c i n g l l bt a k e sa d v a n t a g eo ft h e p e r i o d i c a lc o m m u n i c a t i o na m o n gp e e r st h a tk e e p st h et o p o l o g yo fs t r u c t u r e dp 2 p t oe x c h a n g e l o a di n f o r m a t i o n t h i si n f o r m a t i o ni ss t o r e di nh e a v yn o d el i s t ( h n l ) o rl i g h tn o d el i s t ( l n l ) a c c o r d i n gt ot h en o d eu t i l i z a t i o n n o d e sp e r f o r me m e r g e n c yl o a db a l a n c i n go rp e r i o d i c a ll o a d b a l a n c i n ga c c o r d i n gt ot h e i ru t i l i z a t i o nt om o v ev i r t u a ls e r v e r si nh n l t op e e r si nl n l t h u s ， l l be s t a b l i s h e sl o a db a l a n c i n gi nt h es y s t e m s i m u l a t i o nr e s u l t ss h o wt h a tl c l l bc a np r o v i d er e l i a b l el o a db a l a n c i n ga n dl o we x t r a c o s t i n g ，w h i c hm e a n sb e t t e rp r a c t i c a b i l i t y k e y w o r d s ：p e e r - t o p e e r ；r e s o u r c el o c a t i o n ；l o c a l i t yo f r e f e r e n c e ；l o a db a l a n c i n g 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明 的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：王芳导师签字： 学位论文版权使用授权书 一月冬 本学位论文作者完全了解! 墩有关保留、使用学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许沦文被查阅和借阅。本人授权生! 撞可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：王芳 导师签字：z8 拉月和导师签字：级8 拉a l 等 签字日期：2 0 0 6 年f 月g 日签字日期：2 0 0 6 年j 月8 日 山东师范大学硕士学位论文 第1 章绪论 网络技术的飞速发展与迅速普及使其成为数据通信的重要手段，网络的发展大大超 出了网络的提出者以及早期的建立者的构想。在传统的客户机服务器网络中，以一些大 的网站为中心，不同地域的客户端通过连接服务器进行信息的浏览和下载。随着网络规 模的扩大，服务器已难以满足日益增加的客户端的需求，一旦服务器不堪重负而崩溃， 整个网络也会随之崩溃。另外，联入网络中的设备以及计算单元的数量和种类也越来越 多，然而这些设备以及计算单元并没有得到充分的利用。如果能够将这些设备以及计算 单元的处理器计算能力、磁盘存储能力以及网络带宽资源等进行充分利用，将会有效缓 解目前互联网所面临的一些问题。 p 2 p ( p e e rt op e e r ) 计算技术的出现目的就是希望能够分担或免除服务器的压力， 并充分利用互联网中所蕴含的潜在计算资源。p 2 p 中文称为对等网络，是一种具有较高 扩展性的分布式系统结构，由互相连接的计算机( 以下称为节点) 构成，为了实现共享 资源( 如文件、c p u 运算能力、存储空间和带宽) 节点自组织成网络，能够自适应节点 或网络的失败和节点数量的变化，确保可以接受的连通性和性能。对等网络中其对等概 念是指网络中的物理节点在逻辑上具有相同的地位，而并非处理能力的对等。相对于传 统的集中式客户j j 务器( c s ) 模型，p 2 p 弱化了服务器的概念，系统中的各个节点不再 区分服务器和客户端的角色关系，每个节点既可请求服务，也可提供服务，节点之间可 以直接进行数据通信而不需要通过中间的服务器。 1 1 研究背景 1 1 1c l i e n t s e r v e r 资源共享模式的不足 最早的大规模分布式应用都采用c l i e n t s e r v e r 模型，该模型通过c l i e n t s e r v e r 模式 构建了最早的资源共享网络。该模式包括客户机，文件服务器两层c s 、多层c s 、以及 浏览器h i 务器等几种类别。在c s 模式中，客户机具备一定的计算能力，但主要工作还 是依赖于服务器来完成，其基本工作方式是客户机发出请求，服务器接收请求并进行分 析处理，然后将处理结果返回给客户机。c l i e n t s e r v e r 模型特点是系统中的共享资源集 中存储在服务器上，这样不存在并发性、数据一致性等问题，需要维护的节点少。在 c l i e n t s e r v e r 模型中只有一个服务器节点需要进行保护，就可以保证系统的安全性，便 于管理。 山东师范大学硕士学位论文 在c l i e n t s e r v e r 共享模式下，资源的查找很简单，只要客户知道存放共享资源的服 务器i p 地址或者域名，就可以在i n t e m e t 上实现资源的共享。c l i e n t s e r v e r 模式中，一 般都是由客户端进行初始化，发送建立连接请求，根据应用的特点建立t c p 或者u d p 的连接。连接建立之后，客户选择应用层不同的应用服务( 一般采用w e l l k n o w n 端口 来识别不同的的应用) 发出请求信息，然后进行数据的传送和处理。 c l i e n t s e r v e r 模型网络资源共享存在很多缺点： ( 1 )在c s 模式下，由客户机提交请求，服务器同时为多台客户机提供服务并处理客 户机的请求。要构建c l i e n t s e r v e r 模型需要性能较好的服务器，服务器的性能越好，其 价格越贵，使得构建网络的造价提高。 ( 2 )可扩展性差：服务器的处理能力决定了系统的最大工作负载，随着客户的不断增 加，服务器性能也需要不断的扩展，而服务器的处理能力很难有效扩展，因此服务器仍 是性能瓶颈。 ( 3 )容错性差：服务器的i p 地址或域名对客户而言都是己知的，这样给服务器带来 了很多不安全因素。服务器一旦受到攻击将导致服务瘫痪，使服务器成为单点故障点 ( 4 )缺乏灵活性：用于客户机和服务器通信的协议是硬编码的，客户和服务器之间的 角色分配在设计时就已经决定，系统的功能很难扩展和升级；并且不同的应用需要服务 器和客户端运行不同的软件。 为了解决c l i e n t s e r v e r 模式中容易产生的单点失效，即克服一旦服务器失效整个系 统就会垮掉的缺点，人们提出了服务器群集中式管理方案：将一个服务器由服务器群替 换，服务器群对客户的请求进行响应。服务器群由一个宿主进行管理，宿主主机决定对 客户请求进行应答的服务器，因此这种结构仍然是比较容易进行管理和控制一致性、安 全性的。与传统的c l i e n t s e r v e r 模型相比，服务器群集中式管理结构并没有带来过多的 复杂性，只是增强了单个服务器的安生性，当单个服务器出现超载或失效情况，可以由 其他服务器接管任务进行处理，保证系统可用性。 在改进的c l i e n t s e r v e r 网络结构中有一个集中式的管理中心，负责拦截和分发数据 包给后台服务器群。用服务器群替换单个服务器节点的最大好处是服务器具有容错功 能、可扩展性，人们可以使用主备份( p d m a r y - b a c k u p ) 技术和负载平衡技术在服务器 之间同步。但实践证明，这样的模型中管理中心可能成为性能的瓶颈，管理中心一旦失 败，其余的服务器都无法工作。 1 1 2 对等网络模式 随着网络规模的扩大，单个服务器越来越难以应付全世界范围百万计用户的请求， 出现了服务器超载、远距离服务高延时等问题，甚至查询失效率猛增。尽管人们不断地 2 山东师范大学硕士学位论文 对c l i e n t s e r v e r 模式进行改进，使用不同的技术增强c l i e n t s e r v e r 模型在现实应用中的 可用性，但不能从根本上解决以上问题。另一方面，计算机的计算能力正按照摩尔定律 在飞速增长，计算机芯片的集成和计算机c p u 的处理速度大约1 8 个月翻一番，现在客 户端可以执行更多更复杂的任务，例如图形操作，数据处理等等，而不仅仅是转发用户 的请求。随着计算机处理能力的进一步增强，当前市场上任一台新生产的计算机都可作 为服务器。在这样的背景下，共享模式从客户服务器模式逐步演变到对等网络模式。 对等网络的概念其实很早就有，最早根源于七十年代中期很流行的l a n 文件共享。 许多多媒体游戏也建立在对等网络的模型之上，一些早期的分布式系统例如u u c p f 9 1 和 交换网络i l0 j 就采用了和对等网络相似的模型。但直到近年来随着i n t e r n e t 的飞速发展， 网络带宽的成倍增加以及计算机计算能力的大大提高，对等网络又以一种新的形式引起 了人们的关注。以i n t e m e t 上的信息查找为例，i n t e m e t 上的各种信息呈爆炸性增长， 但利用现有的任何搜索引擎或者门户网站都很难找到实时信息，因为无论是利用 c r a w l e r 搜寻、i n t e r n e t 的搜索引擎、还是对i n t e m e t 内容进行分类的门户网站，都无法 以实时的方式处理不断变化和增长的i n t e m e t 。利用对等网络可以建立一种分布式的搜 索引擎，每个提供信息服务的节点都对自己保存的信息编制索引并回答其他节点的查询 请求，实现实时查询。 虽然近年来网络带宽成倍增长，但热门站点仍然越来越不堪重负，而处于网络边缘 的客户机的空闲链路带宽被白白浪费。利用对等网络提供的分布式结构可以有效均衡负 载，充分利用带宽。目前以g n u t e l l a 软件为代表的对等网络技术其实质在于将互联网的 集中管理模式引向分散管理模式，将共享内容从中央单一节点引向网络的边缘，从而充 分利用互联网中众多终端节点所蕴涵的处理能力和潜在资源。 对等网络模型打破了传统的客户，服务器模式，它以用户为中心，节点不再严格的划 分为客户机或服务器，每个节点的地位都是相同的，既充当服务器为其他节点提供服务， 同时也充当客户机享用其他节点提供的服务。对等网络系统中的各个节点因为互为服务 而共存，而不是依赖与特定的集中式机制，而且各个节点可以直接交互并可以随时离开 对等网络。与传统的客户服务器模式相比，对等网络模式有如下优势： ( 1 )负载均衡对等网络环境下可以根据策略灵活分布信息，负载均衡模块可以监控 各种信息的流量和请求率，然后重新分布这些信息以减轻单个节点的负载。 ( 2 )丰富的信息资源任何对等网络用户能够扫描活动节点搜索需要的信息，然后直 接从节点上下载。用户可以把下载的信息进行共享，这样，请求率高的文件能够很快在 许多节点上扩散开来。当网络增长的时候，共享信息的数量和范围都将随之增长。在一 个开放的网络环境下，对等网络能够很快积累相当丰富的信息。 ( 3 )冗余和容错对等网络的多个节点问的信息复制导致高度冗余，其直接结果是提 高了信息的可用性，使之服务更多的用户。另外，冗余使得网络不会产生“单点失效” 山东师范大学硕士学位论文 问题。 1 2 问题提出 对等网络系统最大的特点就是用户之间直接共享资源，其核心技术就是分布式资源 定位机制，即查询对象存储位置的请求在对等网络中的路由问题，这也是提高网络可扩 展性、解决网络带宽被吞噬的关键所在。 目前对等网络系统的资源定位技术基本上可以分为三类。第一类基于中央服务器 ( 或服务器群) ，如n a p s t e r 系统，中央服务器维护系统中所有共享资源的位置索引，由 中央索引服务器提供查询和定位。该技术的优点是高效、易于实现，但存在单一故障点、 可扩展性差等问题。 另外两种技术将共享资源的索引分散在系统中的节点上，根据资源定位机制是否依 赖特定的系统拓扑结构，分为非结构化和结构化定位技术。非结构化定位技术，如 g n u t e l l a ，以洪泛( f l o o d i n g ) 方式将定位请求发送给自己的邻居节点，直到满足查询或超 时，其优点是没有单一故障点，但存在带宽消耗大、可扩展性差等问题。 结构化定位技术基于分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) ，这种方法利用哈希 函数为搜索空间建立索引，将杂乱的信息有序化，然后将信息按照一定的规律组织，进 而抽象出高效的查询算法完成准确查询定位。由于每个节点都保存一张拥有其他少数节 点的索引信息的路由表，所以这种算法也被称为分布路由算法。分布路由算法摒弃了上 述两种定位机制的弊端，是新一代规模可扩展的路由算法，现在已经有t a p e s t r y ，c h o r d 、 c a n 等较成功的范例。 分布路由算法的重点主要集中在提高查询效率、负载平衡、网络的扩展性、降低带 宽占用率等方面。由于分布式哈希的路由算法是网络逻辑层上的算法，在逻辑网络很难 考虑节点在物理网络拓扑上的关系和数据之间的逻辑联系，所以出现了虽然逻辑上高 效，而实际效率极低的问题。而且，在分布式哈希表的搜索机制中，对共享资源也进行 哈希，节点根据哈希标识存储相应的资源，忽略了节点在能力上的差异，造成了负载分 配不均衡，影响路由算法的效率。 1 3 论文的主要内容及组织 论文针对当前p 2 p 网络模型的研究现状、存在的问题进行了分析研究，以现有的 p 2 p 系统结构、搜索方法为主要研究对象，重点研究了结构化对等网络的资源定位技术 和负载平衡方法。论文首先提出一种基于访问局部性的资源定位技术l c h o r d ，该技术 不仅考虑节点在物理网络上的邻近关系，而且兼顾了数据之间内在的逻辑联系，减少资 4 山东师范大学硕士学位论文 源定位的逐跳时延和路径长度，提高了查询效率。然后，结合x m l 技术和l c h o r d 搜 索技术提出了一种文件共享系统模型p p f i l e ，并给出了系统关键功能实现的伪代码。对 于结构化对等网络的负载平衡问题，本文提出一种具有群聚性的虚拟节点方法c v s s ， 减小系统维护虚拟节点的额外开销。利用c v s s 的目录负载平衡d l b 算法，将分布式 的负载平衡问题转化为目录内节点问的负载平衡问题，减小了负载平衡算法的复杂度， 使其具有实用性。 论文的研究内容组织如下： 第一章介绍了论文的研究背景，分析了对等网络的优势和面临的问题，指出了本论 文的研究意义。 第二章介绍了经典的对等网络模型，分析说明了各种对等网络的资源定位技术的优 点和存在的问题。本章中介绍的结构化对等网络c h o r d 是本文的研究对象。 第三章基于结构化对等网络结构c h o r d ，提出了基于访问局部性的资源定位技术 l c h o r d 。本章详细介绍了l c h o r d 的设计思想和实现方法，并在l c h o r d 的基础上应用 x m l 技术设计了一种基于结构化p 2 p 的文件共享系统p p f i l e 。 l c h o r d 资源搜索技术基于c h o r d 并对其进行了以下两个方面的改进： 首先，l c h o r d 依据空间局部性对c h o r d 选择指针的方法进行改进，缩短了搜索的 逐跳延迟。c h o r d 根据指针表确定搜索请求的转发节点，c h o r d 中的节点在构造指针表 时，总是在逻辑空间中选择与构造者距离最近的节点作为指针，忽略了指针与构造者在 物理网络上的距离，导致搜索请求在路由过程中无谓地经过多个自治域而使实际搜索产 生高延迟；l c h o r d 中的节点在构造指针表时，在保证c h o r d 原有的路由正确性的前提 下，选择与构造者在同一个自治域中的节点作为指针。由于节点所属的自治域基本不发 生变化，因此增加了指针表的稳定性，减小了系统和节点的开销，并且体现了网络通信 的时间局部性，即与一个节点重复地通信。l c h o r d 中的节点依据改造后的指针表转发 搜索请求，避免了由于经过不同自治域而造成的高延迟，从而缩短了搜索请求在路由过 程中的逐跳延迟。 其次，l c h o r d 使用基于相关性的搜索策略进行资源定位，缩短了搜索路径长度。 具体做法是：根据节点共享数据的相关性为节点建立兴趣社区，节点发出的请求首先与 兴趣社区中的节点进行匹配，若兴趣社区无法满足请求，再使用指针表转发请求。由于 节点在具有相似兴趣的节点处更有可能找到所需资源，而兴趣社区包含了与节点在兴趣 上有最大相似性的节点，因此l c h o r d 可以缩小搜索范围，缩短查询路径长度。节点每 次发出搜索请求时，兴趣社区成为节点的重复通信对象，因此基于相关性的搜索策略体 现了网络通信中的时间局部性。 模拟实验结果表明，l c h o r d 与c h o r d 相比，缩小了搜索延迟，缩短了搜索路径长 度，从而提高了搜索效率。同时，由于l c h o r d 中节点的兴趣社区随着网络规模指数级 山东师范大学硕士学位论文 增长，且l c h o r d 没有改变c h o r d 的关键字分配原则，因此l c h o r d 继承了c h o r d 的可扩 展性、容错性等优点。 最后，根据l c h o r d 搜索技术，结合x m l 技术设计了一种分布式文件共享系统 p p f i l e ，该系统可同时支持精确查找和模糊查找。 第四章分析了结构化对等网络中负载平衡问题，提出了一种低开销的负载平衡技术 l c l l b 。 首先，从c h o r d 中节点所负责的i d 空间和节点能力两个方面，阐述了结构化对等 网络中存在的负载不均衡问题。 然后，提出了一种低开销的基于列表的负负载平衡技术l c l l b 。针对传统的虚拟 节点选择方法过多增加了系统维护开销的问题，l c l l b 使用一种在i d 空间中具有群聚 性的虚拟节点选择方法c v s s ，该方法在保持系统原有的容错性的前提下，考虑节点在 容量上的差异为节点分配适量的虚拟节点，并且使虚拟节点具有了群聚性，减小了系统 的额外开销。为了减小为实现负载平衡而引入的通信开销，l c l l b 使用基于列表的负 载平衡技术l l b 。l l b 利用c h o r d 为维护拓扑而在节点间进行的周期性通信交换负载信 息，并将收集到的负载信息分别存放于过载列表和轻载列表。节点根据负载量情况，决 定执行紧急负载平衡或周期负载平衡，将过载列表中的虚拟节点的负载转移到轻载列表 中的节点，实现负载均衡。 最后，对l c l l b 技术进行实验模拟，实验结果表明，l c l l b 负载平衡技术