（计算机应用技术专业论文）基于dht的p2p资源定位模型研究.pdf

西华大学硕十学位论文 基于d h t 的p 2 p 资源定位模型研究 计算机应用技术 研究生王晓光指导教师刘克剑 p 2 p ( p e e r - t o p e e r ) 技术作为i n t e r n e t 的重要技术之一，近些年来受到了计算 机业界越来越多的关注。由于p 2 p 具有大规模性、动态性、分布性等特点， 在这种环境中如何有效的查询资源，就成了一个十分具有挑战性的问题。目 前，最受研究者们关注的是基于d r r r ( 分布式哈希表1 的分布式结构化定位模 型。c h o r d 是结构化f 2 p 系统的一个典型代表，但它没有考虑逻辑网络拓扑 和物理网络拓扑的匹配，而导致路由效率低下；并且忽略了节点异构性，把 所有节点都看成是能力相同的。 本文对c h o r d 系统存在的一些问题，结合混合式p 2 p 网络的优点，提出 了改进方案：一种分层的结构化c h o r d 模型。该系统分为两层，主干网层和 子网层，它们均使用c h o r d 协议进行资源定位。同时针对c h o r d 路由表结构 具有一定的冗余信息，定位效率不高。本文提出了基于优化路由表的改进算 法，优化c h o r d 路由表除去冗余信息。 主干网由超级节点组成，子网由超级节点、普通节点和备份节点组成。超 级节点能力比普通节点强，稳定性高。备份节点用于备份超级节点的信息， 当超级节点失效时，备份节点会接替超级节点的工作。子网普通节点进行资 源定位时，首先在本地子网内用c h o r d 协议查询，只有查询失败时，才到主 干网上查询。系统按照节点的物理距离进行子网划分，子网节点在获取外网 资源后，在本地子网中重新发布，同时超级节点对查询请求进行查询缓冲。 这样，充分利用了查询和数据的时间和空间局部性，资源定位速度快，数据 传输效率高。 最后通过仿真试验表明，改进后查询策略在系统中的平均查询路径长度和 平均查询延时，比标准c h o r d 系统，d u a l c h o r d 和双向c h o r d 更加优良。 关键词：资源定位，分布式哈希表，c h o r d ，分层模型，超级节点 西华大学硕士学位论文 r e s e a r c ho nt h er e s o u r c e sl o c a t i n gm o d e l so fp 2 p s y s t e mb a s e d o nd h t c o m p u t e ra p p l i c a t i o nt e c h n i q u e s m d c a n d i d a t e ：w a n gx i a o g u a n gs u p e r v i s o r ：l i uk e j i a n a so n eo ft h ei m p o r t a n tt e c h n o l o g i e so ft h ei n t e r n e t ，t h ep 2 p ( p e e r - t o p e e r ) t e c h n o l o g yh a sb e e np a i dm o r ea n dm o r ea t t e n t i o nf o rr e c e n ty e a r si nt h ec o m p u t e r f i e l d s i n c ep 2 ph a v es o m es p e c i a lc h a r a c t e r i s t i c s ，s u c ha sl a r g e s c a l e ，d y n a m i c s t a t ea n dd i s t r i b u t e de t c ，t h e r e f o r e ，h o wt or e t r i e v ei n f o r m a t i o ne f f e c t i v e l yi nt h e s y s t e mi sac h a l l e n g i n gp r o b l e m ad h t - b a s e dd e c e n t r a l i z e ds t r u c t u r e dm o d e l ， w h i c ha v o i d sc e n t r a lm a n a g i n ga n db r o a d c a s tq u e r y i n g ，h a sb e c o m eaf o c u si nt h e r e s e a r c ha r e a c h o r di sat y p i c a ld h t - b a s e ds y s t e m h o w e v e r , a st h el o g i c k e y w o r ds p a c e i si s o l a t e df r o mt h er e a lp h y s i c a lt o p o l o g yo ft h en e t w o r k ，i t w e a k e n st h ed a t al o c a l i t ya n dt h en o d e si np h y s i c a ln e i g h b o r h o o dm a yd i s t r i b u t e d f a ra p a r ti nl o g i cr i n go fc h o r d a sar e s u l t ，t h es y s t e mm a yh a v eal a r g el a t e n c y a n dd o w n l o a d i n gs p e e d b e s i d e s ，i ti sr e g a r d l e s st h ep e e r sh e t e r o g e n e i t y i nt h et h e s i s ，w ep u tf o r w a r dah i e r a r c h i c a lp 2 pr e s o u r c e s l o c a t i n gm o d e lb a s e d o nc h o r d t h em o d e lc o n s i s t so ft w ot i n g s ：t h em a i nr i n ga n dt h es u br i n g m o r e o v e rc h o r dh a sap o o rp e r f o r m a n c eb e c a u s eo fr e d u n d a n ti n f o r m a t i o ni nt h e f i n g e rt a l e i nt h i st h e s i s ，a ni m p r o v e df i n g e rs t r u c t u r ei sp r e s e n t e df o rr e m o v i n g r e d u n d a n c y t h em a i nr i n gi sb u i l tu pw i t hs u p e rp e e r sw h i l et h es u br i n gc o n s i s t so fn o r m a l p e e r s ，s u p e rp e e r sa n db a c k u pp e e r s t h es u p e rp e e r s ，w h i c hh e l pt h e ms e a r c h r e s o u r c e si nt h em a i nr i n g ，a r em o r ep o w e r f u la n ds t a b l e b a c k u pp e e r sb a c k u pt h e d a t ao ns u p e rp e e r s ，a n dt h e yw i l lt a k ec h a 唱et h em a i nr i n gw h e ns u p e rp e e r sf a i l t ow o r k t h e yb e g i nt h e i rw o r ka sf o l l o w s ：f i r s t ，an o r m a lp e e ri nas p e c i f i cs u b r i n gl a u n c h e sar e s o u r c eq u e r yr e q u i r e m e n t ，w h i c hw i l lb er o u t e di nt h es u br i n g a c c o r d i n gt ot h ec h o r dp r o t o c 0 1 o n l yi nt h ec a s et h a tt h er e q u i r e m e n ti sn o t m e t d o e st h er e q u i r e m e n tb es e n tt os u p e rp e e r sw i t h i nt h es u br i n ga n db er e - l o c a t e di n t h em a i nr i n g t h e r e f 6 r c ，f o rt h eb e n e f i to fh i g he f f i c i e n c yi nd a t al o c a t i n ga n d t r a n s p o r t i n g ，p e e r si np h y s i c a ln e i g h b o r h o o da l ed i s t r i b u t e di n t h es a m es u br i n g a n de x t e m a lr e s o u r c e sa r er e p u b l i s h e di nt h el o c a ls u br i n ga f t e rd o w n l o a d e df r o m e x t e r n a ln e t w o r k t h es i m u l a t i o nr e s u l ts h o w st h a t t h en e wa l g o r i t h md o e sb r i n gb e t t e r p e r f o r m a n c e i n r o u t i n gd e l a ya n dh o p s o fn e t w o r kt h a nt h eo r i g i n a lc h o r d d u a l c h o r da n dt w o w a yc h o r d k e y w o r d s ：r e s o u r c el o c a t i n g ，d h t , c h o r d ，h i e r a r c h i c a lm o d e l ，s u p e rp e e r i i l _ 西华人学硕十学位论文 8 声明 本人声明所呈交的学位论文是本人在导师的指导下进行的研究工作及取 得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确地说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 作者签名：互蚴 汐7 年歹月矽日 导师签名：易1 嘭夕象f 叠年s 月z 乡日 两华大学硕十学位论文 9 授权书 西华大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，西华大学可以将本论文的全部或部分 态容编入有关数据库进行检索，可以采用影印、缩印或扫描等复印 手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书； 2 、不保盔匝适用本授权书。 ( 请在以上口内划) 学位语文作者签冬：互助 日期：伊7 乒2 夕 钫 钆 ；硝；l 、哆孓 名 譬 签钆 纂 o d 教： 导期指日 西华大学硕士学位论文 l 绪论 1 1p 2 p 技术简介 1 - 1 1p 2 p 的概念及发展 p 2 p 是一种分布式技术，不同于c l i e n t s e r v e r ，b r o w s e r s e r v e r 和s l a v e m a s t e r 等传统模式，它抛开了应用服务器的束缚，使得网络中的节点以一种对等的方 式共享这些节点的存储空间、处理器计算能力、网络带宽等资源1 。一方面节 点间可以直接进行交互，不再需要服务器作为媒介来进行中转，从而使交流更 直接，效率更高；另一方面节点不再依赖中央服务器，从而解决了因服务器能力 不足而引起的性能瓶颈问题，增强了系统的可伸缩性，同时也避免了因中央服 务器的失败而导致的整个系统无法工作的可能性，使得系统的可靠性更强。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 模式与c s 模式相比有以下特点： ( 1 ) p 2 p 模式高度的资源利用率。能充分共享任何位置的资源，系统的边缘结 点由被动转为主动，使它们所拥有的丰富资源被共享。 ( 2 ) 它消除了中心服务器的瓶颈问题，系统更可靠( r e l i a b l e ) ，更易于扩展。 ( 3 ) 其中各节点高度自治，可以在任意时刻随意地加入或离开系统。 ( 4 ) 采用基于内容的寻址方式，信息定位更准确。 以下图1 - 1 ，图1 2 分别表示了p 2 p 模式和c s 模式。 两华大学硕十学位论文 f i g1 - 1t h ep 2 pm o d e l 图1 - 1p 2 p 模式 f i g1 - 2t h ec sm o d e l 图1 - 2c s 模式 到目前为止，p 2 p 研究已经涉及非常广泛的方面，主要包括：网络拓扑构 造、安全与可靠性、分布式数据存储、大规模并行计算等。p 2 p 的应用更是涵 盖诸多领域，商业和民用领域的文件和数据共享和存储、科研领域的协同工作 和并行计算、军事领域的士兵协作和战场网络( b a t t l e f i e l dn e t w o r k ) 构造等。 p 2 p 网络系统虽然会随着应用的不同而具有不同的功能、形式和特点，同 时也会在底层机制、系统目标及研究问题上也会有所侧重。但对于一般的p 2 p 网络，大都以信息共享为核心，且许多p 2 p 网络都需要以信息共享为基础， 信息共享也是目前研究的最为广泛的一类p 2 p 系统；另外，无论是在信息共 享p 2 p 系统中，还是在其它p 2 p 系统中，搜索问题一直是研究的重点问题， 这是因为许多其它问题的研究都直接或间接的依赖于搜索机制，比如信任管理 得出的节点可信度需和搜索机制相结合才能发挥信任管理的目标。此外，搜索 机制也是影响p 2 p 网络性能的关键因素，它不仅决定了系统的可用性，如用 2 西华人学硕士学位论文 户应答时间，服务质量等；同时它也会决定系统本身的性能，包括系统的通讯 负载、可扩展性等。 1 1 2p 2 p 技术的应用 p 2 p 引导网络计算模式从集中式向分布式偏移，也就是说网络应用的核心 从中央服务器向网络边缘的终端设备扩散，目前人们从很多不同的角度来应用 p 2 p 计算技术，主要应用的角度包括信息资源共享、对等计算、协同工作、搜 索引擎等i 刁。下面将从这几个角度分别进行一个简单的介绍。 ( 1 ) 文件交换 以p 2 p 模式实现了自由的文件交换体系，从而引发了网络的p 2 p 技术革 命。一种是“中心文件目录分布式文件系统 ，交换数据时是通过中央服务器 来进行目录管理的。n a p s t e r 就属于此类。由于采用集中式目录管理，所以不 可避免地存在单点瓶颈的问题。另外一种属于完全的p 2 p ，这类系统没有中间 服务器。g n u t c l l a 和f r e e n e t 是这方面两个典型的应用。第三类系统是上面两 类系统的折衷有中间服务器，但文件目录是分布的，如w o r k s l i n k 。在这 方面，m a z e 同时也是国内具有代表性的p 2 p 应用软件。 ( 2 ) 对等计算 采用p 2 p 技术的对等计算，把网络中的众多计算机暂时不用的计算能力联 结起来，使用积累的能力执行超级计算机的任务。任何需要大量数据处理的行 业都可以从对等计算中获利，如天气预报、动画制作、基因组的研究等。 s e t i h o m e 是b e r k e l e y 大学启动的对等计算的研究项目，目前大约吸引了 一百万台计算机参与研究。该项目是利用该大学的空间科学实验室开发的屏幕 保护程序来使用计算机的空闲机时，该屏幕保护程序在运行时分析在外星系文 明研究项目中所获得的无线电信号，程序运行节点从中心服务器节点下载数据 进行计算然后，再将计算结果上载到该实验室的中心服务器上。 对等计算可以帮助企业完成大规模的数据处理，参与计算的计算机之间可 以直接共享计算中的中间结果。通过整合这些以前尚未使用的闲散计算能力和 资源，可以将企业的计算能力相比以前得到很大的提升，同时因为利用了多个 节点上的计算能力使得计算任务可以高效廉价的完成。g r i d 是研究对等计算 的典型代表，i b m 公司也启动了自组织计算计划来研究对等计算。 3 西华大学硕十学位论文 ( 3 ) 搜索引擎 搜索引擎是目前人们在网络中搜索信息的主要工具。目前的搜索引擎如： g o o g l e 、b a i d u 等都是集中式的搜索引擎。即使是g o o g l e 这个目前最出色的 全中文搜索引擎只能搜索到2 0 - 3 0 的网络资源。p 2 p 网络模式中节点之间 动念而又对等的互联关系使得搜索可以在对等点之间直接地、实时地进行，既 可以保证搜索的实时性，又可以达到传统目录式搜索引擎无可比拟的深度( 理 论上将包括网络上所有开放的信息资源) 。p 2 p 为互联网的信息搜索提供了全 新的解决之道。 ( 4 ) 实时通信技术 实时通信技术是网络中重要的通信技术，成功的实时通信技术吸引了数以 万计的在线用户。目前的实时通信技术一般也采用一个中心服务器控制着用户 的认证等基本的信息，节点之间直接进行数据通信。i c q ，o i c q , a m ，m s n 等是 典型的实时通信系统，这些系统也包含好友列表等基本功能。是一个开放源码 的实时通信平台，j a b b e r 提出了一个采用x m l 表示的在不兼容的各种实时通 信平台之间进行消息交换的协议。 ( 5 ) 网络游戏 很多基于广域网络的游戏也是基于p 2 p 技术的，例如2 a m 、c e b t e r s p a n 等。采用p 2 p 技术建立起来的分布式小组服务模型，配以动态分配的技术，每 个服务器的承载人数将在数量级上超过传统的服务器模式，这将大大提高目前 多人在线交互游戏的性能；同时每个游戏用户成为一个对等节点，各个节点可 以进行大量的点对点通讯，从而减少服务器的通讯任务，提高性能。 如此以来，一方面p 2 p 技术应用得越来越广泛，p 2 p 网络上的资源同益丰 富和庞大，而另一方面p 2 p 网络上的用户节点的频繁加入和离开，p 2 p 应用占 用的网络资源也越来越多，这些都使得p 2 p 网络资源的管理和发现技术显得极 为重要，而结构化的p 2 p 网络因为有高可扩展性的特点，基于d h t ( d i s t r i b u t e d h a s ht a b l e ，即分布式哈希表) 资源发现技术所以成为了现在研究的重中之重。 1 2p 2 p 网络的分类 p 2 p 系统自产生至今得到了广泛的研究和应用，种类繁多，很多研究人员 4 、 两华大学硕十学位论文 按照不同的标准，从不同的角度对它们进行了分类，如按对等节点之间数据传 送方式，可以分为基于点对点方式的p 2 p 系统和基于多点多元方式的p 2 p 系统； 按照应用分类，可以分为实时通讯、文件共享、分布式计算等。本节主要从p 2 p 网络发展历程和其网络拓扑结构来对其进行分类。 网络拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联 关系，节点之问的拓扑结构一直是确定系统类型的重要依据。根据拓扑结构的 关系可以将研究分为四种形式如图1 3 所示。 ( 1 ) 集中目录式：例如n a p s t e r l3 1 。采用集中式的查找策略。 ( 2 ) 分布式非结构化：例如g n u t e l l a l 4 1 ，采用“广播泛洪的查找策略。 ( 3 ) 混合式：例如k a z a a 副。采用中心化拓扑和全分布式非结构化拓扑相结合 的查找策略，并且k a z a a 采用设置超级结点的一种分层结构。 ( 4 ) 分布式结构化：主要是指基于d h t 的分布式结构化网络。例如c h o r d ， c a n ，t a p e s t r y 和p a s t r y 。采用分布式散列表( d h t ) 进行查找。 f i g1 - 3t h ec l a s s i f i c a t i o no fp 2 p n e t w o r k 图1 - 3 p 2 p 系统分类 5 两华人学硕+ 学位论文 1 3p 2 p 技术的国内外研究现状 国外开展p 2 p 研究的学术团体主要包括p 2 p 工作组( p 2 p w g ) 和全球网格论 坛( g l o b a lg r i df o r u m ，g g f ) 。p 2 p 工作组成立的主要目的是希望加速p 2 p 计算 基础设施的建立和相应的标准化工作。p 2 p w g 成立之后，对p 2 p 计算中的术 语进行了统一，也形成相关的草案，但是在标准化工作方面工作进展缓慢。目 前p 2 p w g 已经和g g f 合并，由该论坛管理p 2 p 计算相关的工作。g g f 负责 网格计算和p 2 p 计算等相关的标准化工作。 从国外公司对p 2 p 计算的支持力度来看，m i c r o s o f t 公司、s u n 公司和i n t e l 公司投入较大。m i c r o s o f t 公司成立了p a s t r y 项目组，主要负责p 2 p 计算技术的 研究和开发工作。目前m i c r o s o f t 公司已经发布了基于p a s t r y 的软件包 s i m p a s t r y v i s p a s t r y 。在p a s t r y 的基础之上，r i c e 大学也发布了f r e e p a s t r y l 7 1 软 件包。 2 0 0 0 年8 月，i n t e l 公司宣布成立p 2 p 工作组，负责开发p 2 p 应用平台。2 0 0 2 年i n t e l 发布了n e t 基础架构之上的a c c e l e r a t o rk i t ( p 2 p 加速工具包) 和p 2 p 安 全a p i 软件包，从而使得微软n e t 开发人员能够迅速地建立p 2 p 安全w e b 应 用程序。 s u n 公司利用j a v a 技术，开展了j x t a 项削酬。j x t a 是基于的j a v a 开源 p 2 p 平台，任何个人和组织均可以加入该项目。因此，该项目不仅吸引了大批p 2 p 研究人员和开发人员，而且已经发布了基于j x t a 的即时聊天软件包。j x t a 定义了一组核心业务：认证、资源发现和管理。在安全方面，j x t a 加入了加 密软件包，允许使用该加密包进行数据加密，从而保证消息的隐私、可认证性 和完整性。在j x t a 核心之上，还定义了包括内容管理、信息搜索以及服务管 理在内的各种其它可选j x t a 服务。在核心服务和可选服务基础上，用户可以 开发各种j x t a 平台上的p 2 p 应用。 国内知名研究p 2 p 技术的学术机构如下： ( 1 ) 北京大学m a z c m a z e 是北京大学网络实验室开发的一个中心控制与对等连接相融合的对 等计算文件共享系统，在结构上类似n a p e s t e r ，对等计算搜索方法类似于 g n u t e l l a 网络上的一台计算机，不论是在内网还是外网，可以通过安装运行m a z e 6 两华人学硕士学位论文 的客户端软件自由加入和退出系统。每个节点可以将自己的一个或多个目录下 的文件共享给系统的其他成员，也可以分享其他成员的资源。m a z e 支持基于关 键字的资源检索，也可以通过好友关系直接获得资源。 但) 清华大学g r a n a r y g r a n a r y 是清华大学自主开发的对等计算存储服务系统。它以对象格式存储 数据。另外，g r a n a r y 设计了专门的节点信息收集算法p e e r w i n d o w 的结构化覆 盖网络路由协议t o u r i s t 。 ( 3 ) 华中科技大学- a n y s e e a n y s e e 是华中科大设计研发的视频直播系统。它采用了一对多的服务模 式，支持部分n a t 和防火墙的穿越，提高了视频直播系统的可扩展性同时，它 利用近播原则、分域调度的思想，使用l a n d m a r k 路标算法直接建树的方式构 建应用层上的组播树，克服了e s m 等一对多模式系统由联接图的构造和维护 带来的负载影响。 随着p 2 p 技术的不断发展，各种p 2 p 网络模型也暴露出很多问题。如p a s t r y 等结构化的路由网络模型无法支持模糊查询，节点频繁地加入或退出也增大了 网络的维护开销。另外在纯p 2 p 的网络模型中，洪泛式的搜索方法也会造成网 络流量的急剧增加，对网络节点造成过重的负担，容易导致节点的失效。同时， p 2 p 模式的网络也极易造成病毒的广泛传播，还存在着网络管理等诸多方面的 问题待解决，很多研究者也都致力于对底层p 2 p 模型的研究来试图解决其中的 难点，提高p 2 p 网络的效率。 1 4 结构化p 2 p 网络资源发现技术的研究 由于非结构化p 2 p 网络的拓扑图是随机图，资源分布没有很强的规律性， 资源搜索技术主要采用的是泛洪搜索和简单启发式搜索，资源搜索过程时间比 较长，通信量比较大，耗费大量的网络开销，因此，系统的可扩展性受到严重 限制，后来提出了结构化p 2 p 网络。结构化p 2 p 网络是基于确定的拓扑图，主 要是采用了分布式哈希( d r r r ) 路由技术，这也是目前扩展性最好的p 2 p 路由方 式之一，是当前研究领域的热点i 剐。由于d h t 各节点并不需要维护整个网络的 信息，只在节点中存储其l 临近的后继节点信息，因此较少的路由信息就可以有 7 两华大学硕士学位论文 效地实现到达目标节点，同时又取消了泛洪算法。该模型有效地减少了节点信 息的发送数量，从而增强了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 项目、中国科技大学的p p o c e a n 项目等。这些系统一般都假定节点具有相同 的能力，这对于规模较小的系统较为有效。但这种假设并不适合大规模的 i n t e r a c t 部署。d h t 类结构最大的问题是d h t 的维护机制较为复杂，尤其是节 点频繁加入退出造成的网络波动( c h u m ) 会极大增加d h t 的维护代价。同时基 于d h t 的拓扑维护和修复算法也比g n u t e l l a 模型和k a z a a 模型等无结构的系 统要复杂得多，甚至在项目中产生了“绕路”的问题。d h t 所面临的另外一个 问题是d h t 仅支持精确关键词匹配查询，无法支持内容语义等复杂查询。 1 5 问题的提出 p 2 p 引导网络计算模式从集中式向分布式偏移，也就是说网络应用的核心 从中央服务器向网络边缘的终端设备扩散：服务器到服务器、服务器到p c 机、 p c 机到p c 机，p c 机到w a p 手机所有网络节点上的设备都可以建立p 2 p 对话。这使人们在上的共享行为被提到了一个更高的层次，使人们以更主动深 刻的方式参与到网络中去。p 2 p 网络模型打破了c s 模式的架构，摒弃了中心 服务器这个中一t l , 节点 9 1 。p 2 p 系统要在一个大规模的动态环境中实现网络资源 的共享，交换和查询。但是在这样一个没有中心节点的模型中，如何高效的进 行资源定位和查询，提高资源搜索的效率成为了p 2 p 系统的关键问题。 由于现在p 2 p 网络节点数量庞大，资源丰富，结构化p 2 p 网络虽然具有高 可扩展性、查询的准确性和比非结构化p 2 p 网络高的查询速度，但是结构化p 2 p 网络资源搜索技术还是有许多需要解决的问题，如前文提到的由于没有考虑物 理网络拓扑结构而出现的“绕路 问题，节点路由表信息冗余问题等，都影响 了结构化p 2 p 网络资源搜索效率。 8 两华大学硕士学位论文 1 6 论文的主要贡献和创新点 对等网络技术的核心是资源搜索定位，资源搜索定位方法的优劣直接关 系到p 2 p 系统的性能和可扩展性，结构化对等网络的资源定位机制由于其查找 可确定性、简单性和分布性等优点正越来越成为研究和应用的焦点，结构化 p 2 p 系统很好地解决了系统的可扩展性问题，但其路由机制主要是从对等点逻 辑上的相邻性进行设计，对网络拓扑的实际结构欠缺考虑【1 0 l 。在路由中，虽然 从源对等点到目标对等点的路由跳数，能有效地控制在某一范围内，但却不能 保证每一跳之间距离的合理性。也就是说，在逻辑上相邻的一跳，在物理网络 中有可能经过很多跳数，甚至好多个自治区域，这样就造成了相当大的网络延 迟。结构化c h o r d 路由算法的期望跳数为o ( 1 0 9 n ) ，因此，c h o r d 的覆盖网络 的路由跳数是比较高效的。但是c h o r d 缺乏对物理网络拓扑信息的利用。 本文针对c h o r d 资源定位模型忽略节点地理位置信息，忽略网络节点间 异构性的缺点，提出了一种分为双层的c h o r d 模型，主干网层由超级节点组成， 每个超级节点负责管理一个子网，并将物理距离较近的节点分到统一个子网 内。按照节点的能力将节点分为普通节点，超级节点，备份节点。充分利用节 点的计算力和存储能力。同时，针对c h o r d 路由表结构具有一定的冗余信息， 除去冗余信息，添加节点有效路由信息，使网络整体效率明显提高。 1 7 论文的组织 本文讨论了p 2 p 网络资源定位相关模型和方法，根据研究过程所涉及的内 容和系统仿真的步骤，本文分为以下几个部分 第一章介绍p 2 p 的概念和发展，国内外研究状况 第二章结构化p 2 p 网络的资源定位模型 第三章改进的c h o r d 资源定位模型 第四章改进模型的仿真与性能分析 第五章总结与展望 9 西华人学硕十学位论文 2 结构化p 2 p 网络资源定位模型 从最初以n a p s t e r 为代表的有着中央目录服务器的对等网络结构，发展到 后来以g n u t e l l a 为代表的，完全分布式无结构对等网络，和提供节点匿名发布 和获取文档的f r e e n e t ，再到以c a n 、c h o r d 、p a s t r y 和t a p e s t r y 等为代表的基 于分布式哈希表的结构化对等网络i l ，对等网络的发展历经了大致三个阶段， 分别采用了不同的资源定位和路由模型。本章重点对结构化的对等网络模型加 以介绍，描述它们所采用的搜索机制以及现有机制存在的不足。 为了解决网络资源快速定位的问题，人们丌始运用d h t 技术来构建结构 化的p 2 p 网络。在结构化p 2 p 网络中，每个节点只存储特定的信息或特定信息 的索引。当用户需要在系统中获取信息时，他们必须知道这些信息或索引可能 存在于哪些节点中。由于用户预先知道应该搜索哪些节点，避免了非结构化系 统中使用的洪泛式查找，因此提高了信息搜索的效率。 结构化p 2 p 网络的整个网络具有相对稳定而规则的拓扑结构，每个节点 所维护的邻居能够按照某种全局方式组织起来，每个节点都有固定的地址。结 构化p 2 p 网络采用的是纯分布式的消息传递机制和根据关键字进行查找的定位 服务，目前采用的最多的是分布式哈希表( d h t ) 技术，即依据拓扑结构，可以 用h a s h 函数给网络的每个节点指定一个逻辑地址，并把地址和节点的位置对 应起来，每个节点都保存一张路由表进行路由，所以结构化p 2 p 网络又称为 d h t 网络。 像c h o r d ，p a s t r y , c a n ，t a p e s t r y 等都是属于结构化p 2 p 网络，它们都具有 高可扩展性、查询精确度高、查询速度比较快，对于给定的某个地址，拓扑结 构保证只需要通过0 ( 1 0 9 n ) 跳就能路由到具有相应资源的节点上去，n 为网络 中的节点数，但是在语义查询、多关键字查询等复杂查询存在固有的一些问题。 2 1d h t 路由原理 结构化p 2 p 网络中，网络中的客户端主机称为节点，数据项目成为对象。 名字空间指系统的一个名字域，在这个名字域中所有的名字都是独一无二的。 名字用来标识节点，一个节点可以有几个名字，每个名字基于不同的尺度。但 总的来说，每个节点在一个名字空间中只能有一个名字。对于一个节点来说典 1 0 西华大学硕十学位论文 型的名字就是它的i n t e r n e ti p 地址。标识符是指在某个整数名字空间中的独一 无二的整数。在系统中，标识符可以通过对一个节点的名字进行散列来获得， 一般是对节点的口地址进行散列，例如标识符p = h a s h ( i p ) 。 关键字( k e y ) 是对一个对象独一无二的标识符，它可以通过对对象名进行散 列来获得，k = h a s h ( v ) ，其中v 为某对象名字。 散列函数可以将i p 或者k e y 映射到整数，通常可以在一个更小的值集合 上获得一个离散分布。散列函数是不可逆的。散列表( h a s ht a b l e ) 是一个字典， 在这个字典中k e y 通过一个散列函数被映射到一个数组的位置上。如果有多个 k e y 被映射到一个位置上则被称为是冲突。完美的散列函数是一个没有冲突的 散列函数，每个不同的k e y 都被映射到不同的整数上。使用完美的散列函数的 散列表没有冲突。最小的完美散列函数映射每个不同的k e y 到不同的整数并且 可能的整数的数目和可能的k e y 数目相同。 d h t 实际上是一个由广域范围大量节点共同维护的巨大散列表。散列表被 分割成不连续的块，每个节点被分配给一个属于自己的散列块，并成为这个散 列块的管理者。 d h t 的节点既是动态的，节点数量也是巨大的，因此非中心化和原子自组 织成为两个设计的重要目标。通过加密散列函数，一个对象的名字或关键词被 映射为1 2 8 位或1 6 0 位的散列值。一个采用d h t 的系统内所有节点被映射到 一个空间l = 【0 ，1 ) ，如果散列函数映射一个h 位的名字到一个散列值h ，则有 h 2 h l 。在分布式散列表中，对于同一个k e y 发生冲突的可能性很少。 在基于d h t 的p 2 p 系统中，文件被关联到k e y ( 1 ： i 文件名的散列产生) ；系 统中的每个节点拥有一部分散列空间，负责保存某个范围的k e y 。在对一个k e y 进行查询后，系统将返回一个保存具有k e y 的对象的节点的标识符。d h t 的功 能允许节点基于文件的k e y 来存入和取出文件，这已经被证明是在分布式系统 中的一种有用的底层基础。 基于d h t 的搜索实现主要包括4 个关键剧1 2 】，如下： ( 1 ) 散列表的建立 散列值的产生使用一个基本的散列函数，比如s h a - 1 ；节点的标识符采用节 点的名字( 如节点的口地址) 的散列值；对象的标识符采用对象名的散列值；每个 节点存储一张散列表，存储节点标识符与节点物理地址的映射。 两华大学硕士学位论文 ( 2 ) 内容的查找 内容的查找通过 对来查找，k e y 在这里对应着对象标识符， v a l u e 在这罩对应文件的名称、所在的节点的地址等信息。、 ( 3 ) 定位关键字所在的节点 将各个节点所具有的 对保存在与对象标识符相近的节点标识 符的机器中，使搜索关键字代表的对象和节点地址关联上。 ( 4 ) 对的维护 当有新节点或新的 对出现时，将对应的 对转移到对 应的节点上当j 日节点离开时，将其存储的 对转移到相邻的节点上。 2 2 发现算法中的度数和直径折中关系 d h t 发现技术完全建立在确定性拓扑结构的基础上，从而表现出对网络中 路由的指导性和网络中节点与数据管理的较强控制力。但是，对确定性结构的 认识又限制了发现算法效率的提升。研究分析了目前基于d h t 的发现算法， 发现衡量发现算法的两个重要参数，度数( 表示邻居关系数、路由表的容量) 和 链路长度( 发现算法的平均路径长度) 之间存在渐进曲线的关系，如图2 - 1 所示。 维护邻居数( 度) d f i g2 - 1t h eg r a d u a lc i i i v eb e t w e e nd e g r e e sa n dd i a m e t e r 图2 - 1 度数和直径之间的渐进曲线关系 1 2 状态 西华人学硕士学位论文 在n 个节点网络中，图中直观显示出当度数为n 时，发现算法的直径为 o ( 1 ) ，当每个节点仅维护一个邻居时，发现算法的直径为o ( 。这是度数和直 径关系的两种极端情况。 从渐进曲线关系可以看出，如果想获得更短的路径长度，必然导致度数的 增加；而网络实际连接状态的变化造成大度数邻居关系的维护复杂程度增加。另 外，研究者证明o ( 1 0 9 聊甚至o ( 1 0 9 n l o g ( 1 0 9 n ) ) 的平均路径长度也不能满足状态 变化剧烈的网络应用的需求。新的发现算法受到这种折衷关系制约的根本原因 在于d i w 对网络拓扑结构的确定性认识。 2 3 哈希函数 哈希函数是一种产生认证码的方法【1 3 】，例如m d 5 ，s h a - 1 ，它用于数据 的加密和信息安全。哈希函数的主要特点是单向性，通过给定x 可容易找到y 使得y = h ( x ) 成立，但由y 找到x 使得y = h ( 1 日很难得到满足，一般在计算上 不可行1 1 7 】。这样就保证使用哈希函数应用的安全性。哈希函数可表示为 y = h ( x ) ，一般要求哈希函数h 可作用于任何大小的数据且产生的输出长度固 定。即给定任意一个数据x ，可以通过h ( 殉计算出等长的字符串输出。如果哈 希函数h ( x ) 设计的好，h ( x ) 能够实现快速计算和查找。 2 4d h t 分布式哈希表 d h t 是d i s t r i b u t e dh a s ht a b l e 的简称，即分布式哈希表，它是在p 2 p 网络 应用层和网络路由层之间，加入单独的d h t 层来进行p 2 p 网络资源定位和查 询。基于d h t 的资源定位模型，采用哈希函数加速了查询速度和安全性，管 理和使用都很方便。此外，d h t 算法不会像泛洪算法那样占用太多的网络带宽。 因此，基于d h t 的定位模型比前面的几种资源定位模型要好的多。 和无结构对等网络相比，结构化对等网络对文档在系统中的存放位置有严 格的控制并且节点之间的关系比较紧凑。结构化对等网络的最大优点在于它可 以在0 0 0 9 ( 其中n 是系统中节点的数目) 的跳数之内完成文档的路由和定位。 结构化对等网络的主要特点是自组织、可扩展、负载均衡、以及较好的容错性。 和无结构对等网络主要用于文件共享领域不同，结构化对等网络的这些优良特 1 3 两华大学硕十学位论文 性使得它可以应用在对可靠性和扩展性要求比较高的场合，如下图2 2d h t 技 术示意图。 l e v e n tn o l i 胁t i o nn e t w o r ks t o r a g e o t h e r a p p l i c a t i o n 以p - 妇幻n b ” d h t n w t iv p t 一一一，一一 1 r n e t w o r kl a y e r t c p i p f i g2 - 2d h t t e c h n i c a ld i a g r a m 图2 2d h t 技术示意图 简单的理解，结构化对等网络中每个文档对应一个m 比特长的唯一标识 符，可以将文档的这个唯一标识符理解为一个虚拟空间中的地址【1 4 1 。整个虚拟 空间被划分为很多个区域，每个区域包含了若干连续的虚拟地址，系统中的每 个节点负责这些区域中的一个或多个。文档被存储在负责它的虚拟地址所在区 域的节点中，对文档的插入和查找操作的路由通过文档的虚拟地址进行。虚拟 空间中区域的划分和负责每个区域节点的选择都是动态的，每次节点加入或者 离开系统都会导致动态的调整。文档的唯一标识符通过对文档内容或u