（计算机软件与理论专业论文）对等覆盖网络及其路由算法的研究与设计.pdf

摘要 摘要 近年来，一种基于对等结构( p e e r - t o p e e r ，简写为p 2 p ) 的大规模分布式 系统迅速发展起来，它所追求的目标是，为处于边缘网络上的终端用户建 立一个自由的互连互通网络环境，满足用户之问直接信息交流的需要。因 此如何建立这样一个对等覆盖网络，如何进行消息路由和资源发现就成为 该系统需要解决的基本问题，本文正是针对这一基本问题进行深入研究的。 首先，综述了p 2 p 技术的产生和发展状况，通过与传统的分布式系统 对比，指出了p 2 p 技术的新特点、应用方向以及研究意义。 其次，认真分析了现有的对等覆盖网络和相应的路由算法，以及它们 的优缺点，给出了改善这些算法的一些思路。另外还介绍了复杂网络理论 的相关内容，并重点介绍了复杂网络的小世界特性。 然后，遵循从社会学、组织学得到的启示并依掘复杂网络理论，紧紧 抓住对等网络具有小世界特性和幂律分布特性这一理论基础，设计了一种 基于社群的对等覆盖网络。实现了社群内路由算法，社群脚路由算法，解 决了社群的建立、初始化闯题以及节点路由表的建立和维护问题。还利用 数学手段对本文设计的覆盖网进行建模，从理论上验证了该网络具有较强 的“互连互通”性质。 随后，又针对覆盖网关键节点的选举问题展丌讨论。提出了基于加法 模运算的投标选举方法，并对该方法的公平性、正确性和成功概率进行理 论上的证明。又以该投标选举方法为基础，设汁了一个满足基于社群的覆 盖网络需要的多获胜者投标选举算法，从而解决了礼群关键节点的选举这 一关键闯题，也使德覆盖网的高效性和连通性德以保证。 最后，从上层应用系统开发和网络仿真两个方面对本文提出的基于社 群的覆盖网络及其路由算法进行论证和分析。 关键词p 2 p ；覆盖网络；路由算法：社群；投标选举算法；小世界特性 燕山大学。r 学硕十学能论文 a b s t r a c t p e e r - t o - p e e r s y s t e m s ( a b b r e v i a t e d t o “p 2 p s y s t e m s ，) h a v eb e i n g e x p e r i e n c i n gar a p i dg r o w t hi nt h ep a s ts e v e r a ly e a r s a n di t sg o a li st h a t ，t o c r e a t ea ni n t e r - c o n n e c t e dn e t w o r ke n v i r o n m e n tf o rt e r m i n a lu s e r sa tt h ee d g eo f n e t w o r k , i no r d e rt om e e tt h ed i r e c t c o m m u n i c a t i o na m o n gu s e r s s o ，t h eb a s i c p r o b l e m so fw h i c ha r eh o wt oc o n s t r u c ts u c ha no v e r l a yb a s e dp e e r - t o - p e e r t e c h n o l o g ya n dh o wt or o u t em e s s a g e so v e rt h i so v e r l a y i nt h i sd i s s e r t a t i o n ，w e j u s tf o c u so ns u c hp r o b l e m s m a i nc o n t r i b u t i o no ft h i sd i s s e r t a t i o ni sa sf o l l o w s f i r s t l y , t h ee m e r g e n c ea n dd e v e l o p m e n to fp e e r - t o p e e rt e c h n o l o g ya r e s u r v e y e d ，i nc o n t r a s tw i t ht h et r a d i t i o n a ld i s t r i b u t e ds y s t e m ，f l e wc h a r a c t e r i s t i c a n d a p p l i c a t i o nc a s ea n ds i g n i f i c a n c e o fr e s e a r c ho fp 2 pt e c h n o l o g ya r e p r e s e m e d s e n c o n d l y ，c u r r e n t l yp o p u l a r p 2 po v e r l a ya n di t sr e l e v a n tr o u t i n g a l g o r i t h ma r ep r e s e n t e da n da n a l i z e d t h e i rs h o r t c o m i n ga n ds t r o n g p o i n ta r c b m u g h to u t ，a n ds o m em e t h o d st oi m p r o v et h e ma r ep r o p o s e d i na d d i t i o n ， r e l e v a n tt h e o r yo fc o m p l e xn e t w o r k si si n t r o d u c e d ，e m p h a s e so np r o p e r t yo f s m a l lw o r l do f c o m p l e xn e t w o r k a f t e rt h i s ，a c c o r d i n ga ss o c i o l o g ya n dh i s t o l o g ya n dt h e o r yo fc o m p l e x n e t w o r k ，s e i z i n gt h e s m a l lw o r l dp r o p e r t ya n d p o w e r l a wp r o p e r t yo f p e e r - t o - p e e ro v e r l a yn e t w o r k ，ac o m m u n i t yb a s e dd i s t r i b u t e dr o u t i n g a l g o r i t h m ( c b d r ) i sp r o p o s e d t h em e t h o di ss i m p l e ，f u l l yd i s t r i b u t e d ， a p p l i c a b l e ，a n dp r o v a b l ec o r r e c t n e s s t h ec b d ra l g o r i t h mc o n s i s t s o f d e p e n d a b l er o u t i n gr u l e ，p e r f o r m a n c er o u t i n gr u l e ，p e e ra d d i n g ，p e e rd e l e t i n g ， c o m m u n i t yi n i t i a l i z i n g a n d r o u t i n g t a b l ei n f o r m a t i o n u p d a t i n g t h e c o r m e c t n e s so fc b d rn e t w o r ki sa l s op r o v e d ，b ym e t h o do fm o d e l i n gc b d r o v e r l a yu s i n gm a t h m a t i c s a n dt h e n ，p r o p o s i n gan e wb i d d i n g e l e c t i n ga l g o r i t h m 。aa d d i t i v em o d u l e a b s t r a c t b a s e db i d d i n g e l e c t i n gf u n c t i o n ，i sp r o p o s e d t h ef a i r n e s s ，c o r r e c t n e s sa n d p r o b a b i l i t yo fs u c c e s sa r ea r g u e d am u l t i w i n n e rb i d d i n g e l e c t i n ga l g o r i t h m s u i t a b l ef o rc b d ri sa l s od e s i g n e d t h i se l e c t i n ga l g o r i t h mi sb a s e do br i n g t o p o l o g ya n dc a nb eu s e dt oe l e c tm o r et h a no n ew i n n e r t h ed e t a i l sa b o u th o w t h i sa l g o r i t h mc a l lb eu s e di nc b d rt oe l e c tc o m m u n i t ye y e s ( c e ) a r ea l s o p r e s e n t e d f i n a l l y , s o m ea p p l i c a t i o ns y s t e ma n dn e t w o r ke m u l a t o ra r ed e s i g n e da n d i m p l e m e n t e d t h r o u g ht h ee x p e r i e n c ea n dd a t aa n a l y s i s ，t h ea p p l i c a b l ea n d v a l i d n e s so f c b d ri sp r o v e d k e y w o r d sp e e v w p e e r ；p 2 po v e r l a y ；r o u t i n ga l g o r i t h m ；c o m m u n i t y ； b i d d i n g e l e c t i n ga l g o r i t h m ；s m a l lw o r l dp r o p e r t y l i l 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文对等撞盖网络及其路由 算法的研究与设计，是本人在导师指导下，在燕山大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不 包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的 个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本 人承担。 作者签字 柄莴屿 同期：抛埤为f 炯 燕山大学硕士学位论文使用授权书 对等覆盖网络及其路由算法的研究与设计系本人在燕山大学攻读 硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕 山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。 本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并 向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人 授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布 论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密彭 ( 请在以上相应方框内打“”) 作者魏督高土乡隰助。毛年7 月h 导师签名： 夸禾必曲 f 1 期：洳e 年7 刖1 日 第1 章绪论 1 1 研究背景 第1 章绪论 自1 9 9 9 年n a p s t e r 的出现，一种被称为“对等系统”( p e e r - t o p e e rs y s t e m ，简称p 2 p 系统) 的新型大规模分布式系统迅速发展起来，并很快取代 w e b 成为i n t e r n e t 上占用带宽最多的应用系统。同时，研究界也对p 2 p 系 统抱以浓厚的兴趣，各著名大学和研究机构纷纷对p 2 p 网络展开大力研究， 在系统结构方向的各个项级国际会议和著名杂志上发表了许多针对p 2 p 系 统的研究成果。至今，p 2 p 系统的发展仍然方兴未艾，每年都有新的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 技术研究和开发新的应用，以适应和满足人们当前对网络的 需求，如当前在i n t e m e t 流行的大文件分发软件b i t t o r r e n t ，e m u l e 等。目前， p 2 p 技术发展以应用系统研究为主，从而带动p 2 p 系统基础设施的研究。 与传统的分布式系统相比，p 2 p 系统的节点是山处于边缘网络的用户终 端组成，所以p 2 p 系统具有许多新的特点，如节点数巨大，节点动态性、 异构性更强，地理范围分布更广等，这使p 2 p 系统研究和设计面l 临着很多 更严峻的问题，例如：节点的可用性较差，覆盖网拓扑结构的维护更难等 等”1 。 本文的研究和设计来源于一个实际的研究项目，即在广域网范围内， 为边缘网络上的终端用户搭建一个基于p 2 p 技术的多媒体数字平台，在该 基础平台之上，人们可以方便的交换文件，即时通信，进行流媒体的点播 燕山大学：i ：学硕十学位论文 和直播等等。 对该平台的研究涉及到p 2 p 技术、传统流媒体技术等多个技术领域， 需要研究的内容相当广泛。本文研究工作遵循以下指导思想：主要针对这 一平台中的基础问题进行研究，也就是说，研究那些平台必须解决，不解 决系统就不能f 常工作的问题，而对那些诸如提高系统性能等方面的问题 暂不做讨论。 对等覆盖网络及其路由是孤立的节点能够进行通信和交流的基础，本 文正是针对这一基础问题展开研讨。本文认真研究分析了现有的覆盖网络 及其路由算法，大胆借鉴社会学，组织学原则以及复杂网络理论，抓住对 等网络具有小世界特性和幂律分布特性这理论基础，研究和设计了一种 基于社群的覆盖网及其路由算法，提出了一些算法，着重从理论上论证网 络的合理性和可用性。 1 2p 2 p 技术概述 1 2 1 对等系统的定义 目前，在学术界、产业界对于“p 2 p 系统”这一概念尚未形成统一的权 威定义，下面列举几个常用的定义供参考1 2 , 3 1 ： 定义l ：p e e r - t o p e e ri sat y p eo fi n t e r a c tn e t w o r ka l l o w i n gag r o u po f c o m p u t e ru s e r sw i t ht h es a m en e t w o r k i n gp r o g r a mt oc o n n e c tw i t he a c ho t h e r f o rt h ep u r p o s e so f d i r e c t l ya c c e s s i n gf i l e sf r o mo n ea n o t h e f sh a r dd r i v e s 定义2 ：p e e r - t o - p e e rn e t w o r k i n g ( p 2 p ) i sa na p p l i c a t i o nt h a tr u n s o na p e r s o n a lc o m p u t e ra n ds h a r e sf i l e sw i t ho t h e ru s e r sa c r o s st h ei n t e m e t p 2 p n e t w o r k sw o r kb yc o n n e c t i n gi n d i v i d u a lc o m p u t e r st o g e t h e rt os h a r ef i l e s i n s t e a do f h a v i n gt og ot h r o u g hac e n t r a ls e r v e r 定义3 ：p 2 p 是一种分布式网络，网络的参与者共享他们所j 封j 有的一部 分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享资 源需要由网络提供服务和内容，能被其它对等节点( p e e r ) 直接访问而无需经 第1 章绪论 过中间实体。在此网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ， 又是资源( 服务和内容) 获取者( c l i e n t ) 。 随着人们对p 2 p 系统研究和认识的不断加深，对p 2 p 系统内涵的界定 及其定义将更加准确。但是从目前人们对p 2 p 系统的定义和已有的p 2 p 系 统来看，我们不难发现，至少以下两点是所有p 2 p 系统共有的核心特征： 其一，从用户的使用方式来看，系统中每个用户既向其他用户提供资 源，也从其他用户那里获取资源。换占之，每个结点既是服务器( s e r v e r ) 也 是客户端( c l i e n t ) 。这里所说的“资源”可以是一份文件、一块存储空问、 一定量的带宽，也可以是一段时间内保证质量的c p u 使用权限。总之，p 2 p 系统的精神是参与系统的所有结点互相合作、互利互惠。这与传统的一方 提供服务一方享受服务的c s 结构有着本质的不同。 其二，从体系结构来看，系统采甩无中一i = , ( d e c e n t r a l i z a t i o n ) 结构，没有 中心结点负责一致性控制、任务调度、决策仲裁等工作，而是通过参与系 统的结点之间充分合作以完成用户提交的任务。事实上，很多p 2 p 系统的 规模都非常大，往往有上百万结点丽时参与。在这种情况下，也很难有结 点能够有能力进行中心控制和全局管理。 除了以上两点之外，很多p 2 p 系统还具有结点数量大、动态性高、异 构性强、分布广泛、结点之间不互信等特点，这些都是传统的在集群( c l u s t e r ) 或者局域网( l a n ) 范围内实现的分布式系统所不曾面临的问题，也很大程度 上增加了p 2 p 系统设计与实现的难度。 i 2 2p 2 p 技术新特点 p 2 p 系统的精神是“结点合作”。因此，只要一个系统中没有管理者， 所有任务都是依靠结点之间的交换与配合完成，这个系统就可以认为是p 2 p 系统。 p 2 p 系统面临着很多在传统的分布式系统中没有的新问题： ( 1 ) 结点数量大很多p 2 p 系统已经达到上百月结点同时在线的规模， 这样大的规模导致的一个直接后果是不可能使用全连接的拓扑结构( 就是让 燕山大学t 学硕+ 学位论文 每个结点记录当前所有的其它结点) 。这样来，如果让结点知道更多其它 结点的信息并保证任意两个结点之间能够通信就成为一个棘手的问题。因 此，p 2 p 系统中的结点信息收集算法和覆盖网路由协议就成为p 2 p 研究的 一个重要方向。 ( 2 ) 结点动态性高对于用户来说，使用p 2 p 系统的一个标准模式是 “进入系统查找资源获得资源离丌系统”，这一过程通常时问不会很长， 因此p 2 p 系统的一个显著特点就是结点的平均在线时间短，实验测算，在 n a p s t c r 和g n u t e t l a 系统中结点的平均在线时间仅为2 个多小时。结点的高 动态性使得维护数据可用性的工作变得非常困难。 ( 3 ) 结点异构性强i n t e m e t 中结点的硬件能力不同、接入方式不同。这 就造成了参与p 2 p 系统的结点在存储能力、计算能力和带宽能力上都有很 大差异，如何利用这种异构性把所有结点的可用资源都充分利用起来以提 高系统各方面性能是p 2 p 系统必须仔细研究的问题。 ( 4 ) 结点分布广泛p 2 p 系统的结点在全球范围内分布，由于时区不同， 系统的不同部分会在不同时间处于繁忙状态。这对负载平衡、任务迁移、 复制策略等方面都提出了新的挑战。 ( 5 ) n 络异步性强传统分布式系统在集群或者局域网的范围内部署， 网络属于同步网( s y n c h r o n o u sn e t w o r k ) ，也就是说任意两个结点之间的通信 延迟总有上限。而p 2 p 系统部署在i n t e r n e t 这一异步网( a s y n c h r o n o u s n e t w o r k ) 中，由于网络经常发生阻塞、扰动、分裂等情况，不能保证系统中 任意两点的通信延迟有确定的上限。网络的异步性给一些需要严格语义的 应用造成了很大困难。例如：复制算法在异步网中就不能保证严格的线性 一致性( l i n e a r i z a b i l i t y ) 。那么如何在i n t e m e t 环境下对于各种操作保证尽量 强的可靠性和一致性就需要仔细的分析和研究。 ( 6 ) 结点之间不互信p 2 p 结点来自于不同的组织和用户，结点之间没 有天然的信任感，因此安全和隐私保密的工作就十分重要，如何在与别的 结点交换数据时保护好自己的隐私一直是p 2 p 研究的一个重要方向。 ( 7 ) 结点具有自私性很多理性用户总是试图多使用别人的资源，少贡 献自己的资源。实验测算，在g n u t e l l a 中有2 5 的结点从不共享数据给别 第1 章绪论 人，只从别人那是下载数据。并且有大量的用户( 大约占3 0 0 ) 低报自己的 带宽以降低其它用户下载其数据的意愿。如何激励用户多贡献自己的资源， 并且保证交换中的公平性也是受到很多研究者关注的热点方向之一。 ( 8 ) 系统全部暴露在公网中在传统的分布式系统中般只有负责与用 户交换的门户结点( p o r t a l ) 才可以直接从i n t e r a c t 访问，而p 2 p 系统的几乎全 部结点都可以直接从i n t e m e t 访问，这使得p 2 p 系统更容易受到攻击。尤其 对于一些允许结点自由加入的系统( 比如大多数p 2 p 文件共享系统) ，如何 防止联合攻击( c o n s p i r a c ya t t a c k ) 就显得更加重要。 正是p 2 p 系统的这些新特点使彳导p 2 p 系统从一出现就显得与传统的分 布式系统有着非常大的差别。这也是它之所以能够引起众多著名学者的研 究兴趣的原因之一。 1 2 3p 2 p 技术的应用研究 随着p 2 p 技术的发展，人们尝试着使用p 2 p 的方法解决各种问题，越 来越多的p 2 p 应用系统被提出并得到实践的检验，其中主要的包括： ( 1 ) 文件共享系统如n a p s t e r 、g n u t e l l a 、k a z a a 等一j 。 ( 2 ) 广域网分布式存储系统( p 2 p 存储系统) 分布式存储系统一直是分 布式系统的一个重要领域，p 2 p 技术出现后，人们试图把这些分布式存储系 统向更大范屡拓展，提出了在广域网中构建的分布式文件系统、对象存储 系统和数据库系统。目前p 2 p 存储系统研究比较广泛，如最早提出的p 2 p 存储系统o c e a n s t o r e 、典型的p 2 p 存储服务系统p a s t 和典型的p 2 p 存储 交换系统p a s t i c h e ，还有c f s 、t a n g l e r 、i v y 、p a n g a e a 、g r a n a r y 等等p 9 o 。 ( 3 ) 大文件分发系统大文件分发系统是通过结点之间互相传递数据以 减轻数据源处的压力，体系结构通常是树状结构或者网状结构。由于对实 时性、最低可按受带宽等要求不高，因此大文件分发系统能更充分的利用 带宽，获得更高的可扩展性。如b i t t o r r e n t 、e d o n k e y 、e m u l e 等。 ( 4 ) 视频组播系统视频组播的带宽要求很高，因此传统的c s 结构的 组播系统往往由于服务器出口带宽的限制而导致系统的可扩展性很差。在 燕山大学丁学硕十学位论文 基于p 2 p 结构的视频组播系统中，只有少数结点从服务器直接获驳数据， 更多的结点一方面从其它结点处获得数据，一方面也向其它结点提供数据。 整个系统的体系结构为树状结构或者网状结构。这种以对等方式构建的视 频组播系统充分利用了结点之间的可用带宽，使得系统的可扩展性大为提 高。如c o o l s t r e a m m i n g 、p p l i v e 等。 还有一些工作试图建立p 2 p 协同工作、p 2 p 搜索引掣”、利用p 2 p 系统 测量i n t e r n e t 链路状况、通过p 2 p 路由消除防火墙与网关的障碍、构建p 2 p 游戏系统等等，这里不再做更详细的介绍。 1 3 对等覆盖网络技术研究发展现状 1 9 9 9 年诞生的文件共享系统n a p s t e r 是最早的p 2 p 实用系统，它使用 了一个中心目录服务器，存放所有文件的元数据信息，从这个意义上说， n a s p t e r 并非一个纯粹的对等系统。n a p s t e r 第一次验证了p 2 p 思想在广域网 范围内的可行性。在n a p s t e r 因版权问题关闭之后，更多的p 2 p 文件共享系 统迅速崛起，成为i n t e m e t 发展的一股巨大浪潮，其中最著名的是g n u t e l l a 和k a z a a 。这些系统基本上都采用无中心结构，鲁棒性和可扩展性都得到 大幅度提高m 】。 同时，p 2 p 思想在文件共享应用系统的成功促使人们致力于在更多方面 开拓p 2 p 结构的应用。其中大文件分发系统b i t t o r r e n t 、e m u l e 和基于覆盖 网的i p 电话系统s k y p e 最为成功。 从国外公司对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 计 算技术的研究和开发工作。在2 0 0 0 年8 月，i n t e l 公司宣布成立p 2 p 工作组， 正式开展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 平台，任何个人和组织均可以加入该项目。因此，该项目不仅 6 第1 章绪论 吸引了大批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 应用i 。 在p 2 p 系统在产业界迅速发展的同时，研究界也及时跟进，对p 2 p 系 统展开了大规模的研究工作。自2 0 0 0 年起，在o s d i 、s o s p 、s i g c 0 m m 、 u s e n i x 、h 0 1 d s 等系统结构方向的项级会议上不断出现关于p 2 p 系统的 重要研究成果。 2 0 0 1 年，学界又召开了新的专门针对p 2 p 系统的学术会议i p t p s ，由 于该会议受到各著名院校和研究机构的广泛关注，很快成为p 2 p 研究领域 的高峰会议，发表了大量优秀论文，成为p 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 计算等相关的标准化工作。 从2 0 0 2 年开始，b e r k e l e y 、s t , a n f b r d 等著名大学相继开设了p 2 p 相关 的研究生课程，进一步推广了p 2 p 这一新兴的研究方向。 总的说来，研究界对于p 2 p 系统的主要贡献包括： ( 1 ) 提出了以分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 为代表的- - j = l t 新算法，使得p 2 p 系统的各方面性能得以改进： 2 ) 提出并实现了更多的基于p 2 p 结构的应用系统，扩展了p 2 p 的应用 领域； ( 3 ) 对p 2 p 系统进行了大量的测量与建模工作，更深刻的揭示了用户对 p 2 p 系统的使用方式和p 2 p 系统本身的工作规律，这些对于未来p 2 p 系统 的构建都有着重要的参考意义。 7 燕山大学t 学硕十学位论文 总之，这些研究工作使人们对于p 2 p 系统的规律和方法有了更深刻的 理解和认识，也为将来的p 2 p 系统设计奠定了更峰实的基础。 从国内的研究现状来看，还没有专门针对p 2 p 的研究机构和部门。从 2 0 0 3 年开始，国家8 6 3 计划和自然科学基金计划资助一些关于p 2 p 技术的 项目。目前在中国核心期刊上发表的有关p 2 p 的文章也甚少，而且多属综 述性文章【l o j 。 下面将简单介绍一下国内几个发展比较成熟的基于p 2 p 技术的应用软 件：m a z e ，g - r a n a r y , a n y s e e 。 m a z e 是北京大学网络实验室开发的一个中心控制与对等连接相融合的 对等计算文件共享系统，在结构上类似n a p s t e r ，对等计算搜索方法类似于 g n u t e l l a 。 网络上的一台计算机，不论是在内网还是外网，可以通过安装运行m a z e 的客户端软件自由加入和退出m a z e 系统。每个节点可以将自己的一个或多 个目录下的文件共享给系统的其他成员，也可以分享其他成员的资源。m a z e 支持基于关键字的资源检索，也可以通过好友关系直接获得。 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 。 a n y s e e 是华中科大设计研发的视频直播系统。它采用了一对多的服务 模式，支持部分n a t 和防火墙的穿越，提高了视频直播系统的可扩展性： 同时，它利用近播原则、分域调度的思想，使用l a n d m a r k 路标算法直接建 树的方式构建应用层上的组播树，克服了e s m 等一对多模式系统由联接图 的构造和维护带来的负载影响。 1 4 课题的研究内容和意义 本文研究工作遵循以下指导思想：主要针对p 2 p 系统的基础问题进行 研究，也就是说，研究那些绝大多数p 2 p 系统都必须解决，不解决系统就 不能正常工作的问题，而对那些诸如提高系统性能等方面的问题暂不做讨 8 第1 章绪论 论。本文研究的对等覆盖网络及其路由算法j f 是这样一类问题。 p 2 p 系统是利用边缘网络上的用户主机作为节点搭建覆盖网络，是一个 高度异构的、动态的环境，用户可以随时加入p 2 p 网络，也可以随意离开， 动态特性使得对等覆盖网络的拓扑结构难以维护，路由算法也将变得异常 复杂。 目前的覆盖网及其路由算法可以大致分为两类：一类是用于非结构化 覆盖网的以“洪泛”为代表的算法，这类算法的缺点是，消息路由的网络 消耗大，网络容易断裂，网络可扩展性不好等；另类是用于结构化覆盖 网的以分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 为代表的路由算法，现 有的d h t 算法过于注重理论的正确性，缺乏对实际应用的支持，而且由于 其对网络结构的严整性要求过于苛刻，面对高度动态的p 2 p 系统，d h t 算 法维护网络拓扑的开销很大。 在研究和设计思路上，本文主要遵循社会学，组织学原则和依据复杂 网络理论，紧紧抓住对等网络具有小世界特性和幂律分布特性这一理论基 础，来设计对等覆盖网络及其路由算法。具体研究内容如下： ( 1 ) 研究设计一种基于社群的覆盖网络拓扑模型，并在此覆盖网上设计 社群内路由算法，社群问路由算法，解决社群的建立，初始化以及节点路 由表的建立和维护等问题。保证该算法建立的覆盖网络是一个“互连互 通”的网络，不会出现严重断裂，并从理论上证明。 ( 2 ) 研究设计一个具有多获胜者的投标选举算法，解决社群领导( 关键节 点) 的公平选举问题。并对投标选举算法的公平性、j 下确性和成功概率进行 理论上的证明。 p 2 p 系统十分复杂，涉及到的研究领域也非常广泛，本文仅试图解决其 中比较基本的一些问题，而以下这些问题不在本文的研究范尉之内： ( 1 ) 覆盖网的安全性问题和路由最短路径的优化问题； ( 2 ) 如何利用设计的对等覆盖网络和路由协议搭建上层应用； ( 3 ) 对等覆盖网络小世界特性和幂律特性的验证。 事实上，在第5 章的提到的实验系统中对这些问题都有一定的研究， 并且其中的一些工作也取得了很好的成果，但本文不对这些问题进行深入 9 燕山大学t 学硕+ 学位论文 探讨。 1 5 论文组织及各章内容简介 本文共分5 章： 第1 章在对p 2 p 系统的定义、系统的新特点和主要应用等问题以及国 内外研究现状进行简单介绍之后，指出了本文的主要研究内容和意义。 第2 章在解释了几个重要的基本概念之后，对当前有关对等覆盖网络 的搭建以及相应的路由算法进行综述，分析了它们的优缺点，指出了改善 这些算法的思路。然后介绍了当前复杂网络理论的研究发展情况，重点介 绍当前复杂网络理论中有关网络拓扑建模、拓扑生成算法和已丌发的拓扑 生成器等内容。最后还重点介绍了小世界现象和小世界网络模型。 第3 章遵循从社会学、组织学得到的启示，依据复杂网络的一些理论， 设计了一种基于社群的对等覆盖网络，并在该覆盖网络上实现了社群内路 由算法，社群问路由算法。并解决了社群的建立、初始化叫题以及节点路 由表的建立和维护问题。指出了社群领导( 关键节点) 对覆盖网络以及路由效 率的重要性。最后，利用数学手段对本文设计的覆盖网进行建模，从理论 上验证了该网络具有较强的“互连互通”性质。 第4 章主要介绍覆盖网络关键节点的选举问题。提出了一种适用于基 于社群的覆盖网络的多获胜者投标选举算法。本算法利用基于加法模运算 的投标选举函数构造方法，并对投标选举算法的公平性，正确性和成功概 率进行理论上的证明。 第5 章从上层应用系统开发和网络仿真两个方向对本文提出的基于社 群的覆盖网络及其路由算法进行论证和分析。 最后，对本文的工作进行总结，并指出了工作的不足之处和进一步努力 的方向。 1 0 第2 章对等覆盖网络相关技术研究分析 第2 章对等覆盖网络相关技术研究分析 本章首先阐明覆盖网及其路由算法的内涵，然后着重分析了现有p 2 p 覆盖网及其路由算法的相关研究成果。 2 1 基本概念 2 1 1 覆盖网及其路由算法 在p 2 p 系统中，每个节点都与系统中的其他节点相连接，系统中所有节 点及其链接形成一个覆盖在物理网络上的虚拟网络，该虚拟网络成为一个 覆盖网( o v e r l a yn e t w o r k ) 。在覆盖网中任意两个节点问可以通信，消息通过 网络的边进行传播，节点之间完全平等。 覆盖网也通常被称为对等网络基础设施( p 2 po v e r l a yi n f r a s t r u c t u r e ) ，它 是p 2 p 节点得以相互协作的基础，一般指节点互连的拓扑结构和节点在与 相邻节点保持连接时的行为规范。覆盖网保证节点形成连通的图结构，并 在其上建立了特定的节点逻辑组织j 。 所谓路由算法，也常被称为搜索算法或发现算法，是指从一个节点出发， 沿着节点之间的连接进行消息转发，最终到达目标节点或实现路由目标( 如 搜索到所需数据) 过程的方法。覆盖网络和路由算法一般是一一对应的，特 定的覆盖网络决定了其上的路由特性和搜索性能i l “。 2 1 2 幂律分布 幂律( p o w e rl a w ) 分布1 1 3 l 又称为无标度( s c a l e f r e e ) 分布，也被人们通俗 的称为“长尾”分布、- - j k 定律，最早对幂律分布作出贡献的是哈佛语言 学专家z i p f 和意大利经济学家p a r e t o 。 燕山大学工学硕士学位论文 幂律分布的数学表达通式为： y = c x ” ( 2 - 1 ) 式中x ，y 是正的随机变量，c ，r 均为大于零的常数。 这种分布的共性是，绝大多数事件的规模较小，而只有很少的事件的 规模却相当大。 幂律分布表现出了一种很强的不公平性。统计物理学家习惯把服从幂 律分布的现象称为无尺度( s c a l e f r e e ) 现象，可以说，凡有生命的地方，有 进化、有竞争的地方都存在不同程度的无尺度现象。幂律分布广泛存在于 物理学、地球和行星科学、计算机科学、生物学、生态学、社会科学、经 济与金融学等众多领域中。 2 2 主要覆盖网络类型分析 从目前对覆盖网络的研究和应用系统的分析中，可以将覆盖网络按拓 扑结构，归纳为如下四种形式： ( 1 ) 中心化覆盖网络( c e n t r a l i z e do v e r l a y ) ； ( 2 ) 全分布式非结构化覆盖厩j ( d e c e n t r a l i z e du n s t r u c t u r e do v e r l a y ) ； ( 3 ) 全分布式结构化覆盖( d e c e n t r a l i z e ds t r u c t u r e do v e r l a y ) ； ( 4 ) 半结构化覆盖网( h y b r i ds t r u c t u r e do v e r l a y ) 。 覆盖网拓扑结构是指p 2 p 系统中各个节点之间的逻辑互联关系，覆盖 网拓扑结构一直是确定各种p 2 p 系统类型的重要依据。 p 2 p 系统一般要构造一个非中心化的覆盖网络，在构造过程中需要解决 系统中所包含的大量节点如何命名、组织以及确定节点的加入离丌方式、 出错恢复等问题。 2 2 1中心化覆盖网络 中心化覆盖网络最大的优点是维护简单，而且由于资源的发现和节点 间的路由依赖中心化的目录系统，发现和路由算法灵活高效并能够实现复 第2 章对等覆盖网络相关技术研究分析 杂查询。其最大的问题是，与传统客户机服务器结构类似容易造成单点 故障，这是第一代p 2 p 网络采用的结构模式，经典案例就是著名的m p 3 共 享软件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 系统，这种对等网络模型存在很多问题，主要表现为： 首先，中央服务器的瘫痪容易导致整个网络的崩馈，可靠性和安全性 较低；其次，随着网络规模的扩大，对中央索引服务器进行维护和更新的 费用将急剧增加，所需成本过高。 对小型网络而言，集中目录式模型在管理和控制方面占一定优势。但 鉴于其存在的种种缺陷，该模型并不适合大型网络应用。 2 2 2 全分布式非结构化覆盖网 全分布非结构化覆盖网没有中心服务器，足一种纯粹的p 2 p 系统，它 采用了随机图的组织方式，结点之间的链路没有遵循某些预先定义的拓扑 来构建，且结点度数服从“p o w e r - l a w ”规律，从而面对网络的动态变化体 现了较好的容错能力，受结点频繁加入和退出系统的影响小，因此具有较 好的可用性。同时可以支持复杂查询，如带有规则表达式的多关键词查询， 模糊查询等，最典型的案例是g n u t e l l a | ”j 。 但是，由于没有确定拓扑结构的支持，非结构化网络无法保证资源发 现的性能和效率。即使需要查找的目的结点存在，路由也有可能失败。 而且，目前的非结构化覆盖网多采用t t l ( t i m e t o l i v e ) 、洪泛 ( f l o o d i n g ) 、随机漫步或有选择转发路由算法，随着联网节点的不断增多， 网络规模不断扩大，通过以上几种方式的路由算法容易导致网络中部分低 带宽节点因网络资源过载而失效。所以在初期的g n u t e l l a 网络中，存在比 较严重的分区，断链现象。 也就是说，一个查询访问只能在网络