（计算机软件与理论专业论文）对等网中chord协议及算法的研究及改进.pdf

哈尔滨t 程大学硕十学位论文 摘要 对等网应用所面临的一个关键问题是如何有效定位存储特定资源的结 点。不同的对等网查找算法采用不同的策略，其查询效率也有所不同。 本文分析了一种分布式查找算法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 算法的不足，本文提出了f u l l c h o r d 算法。f u l l - c h o r d 算 法主要改进了c h o r d 算法的指针表，将原来计算指针表的公式扩展为两个， 这样可以在顺时针和逆时针两个方向上同时进行。f u l 卜c h o r d 算法在查询开 始时，就能将查询限制在半个c h o r d 环上，这样便能更接近目标结点，提高 查询效率。通过理论分析，f u l l c h o r d 算法的查询效率明显优于c h o r d 算法。 对等网中结点加入和离开是很平常的，因此必需考虑对等网的自适应性。 关于这个方面，本文做了大量研究，提出了为每个结点再建立一张拥有r 个 后继结点的后继列表的设想，很好地解决了这个问题。 本文还借鉴了s m a l 卜w o r l d 领域的研究成果，扩展了c h o r d 算法。通过 对结点度数的分析，提出“超级结点”的概念。并且参考g o o g l e 的网页搜索 技术p a g e r a n k ，给出了计算结点级别的公式n o d e r a n g e ，从而能很好地确定 超级结点。通过超级结点，可以更加有效地定位资源，提高查询效率。 最后，通过仿真测试表明，f u l 卜c h o r d 算法在平均查找路径长度和平均 查询时间这两个方面的性能明显优于原始c h o r d 算法。 关键词：对等网；分布式散列表；相容散列；s m a l l - w o r l d ；c h o r d 哈尔滨t 程大学硕十学位论文 a b s t r a c t o n eo ff u n d a m e n t a lp r o b l e m sc o n f r o n t e db yp e e r - t o - p e e r ( p 2 p ) a p p l i c a t i o n s i sh o wt oe m c i e n t l yl o c a t et h en o d et h a ts t o r e sa p a r t i c u l a rd a t ai t e m d i f f e r e n t s t r a t e g i e sa r ea d o p t e db yd i f f e r e n tp 2 ps e a r c ha l g o r i t h m s ，i nw h i c ht h ee f f i c i e n c y i sd i f r e f e m o n eo fd i s t r i b u t e ds e a r c ha l g o r i t h m s ，n a m e dc h o r dw a sa n a l y s e d a st h e s e c o n dg e n e r a t i o no fp 2 pa l g o r i t h m ，d i s t r i b u t e dh a s ht a b l ei sa d o p t e db yc h o r da s t h es e a r c hs t r a t e g y c h o r di ss e a l a b l e w i t hc o m m u n i c a t i o nc o s ta n dt h es t a t e m a i n t a i n e db ye a c hn o d es e a l i n gl o g a r i t h m i c a l l yw i t ht h en u m b e ro fc h o r dn o d e s m a n ya d v a n t a g e sa r ch o l db yc h o r da l g o r i t h m ，s u c h 嬲b a l a n c el o a d ，r e l i a b i l i t y , e x p a n s i b i l i t ya n ds oo n , b u tt h es e a r c he m c i e n c yo f c h o r di sl o w n 圮f u l l - c h o r da l g o r i t h mw h i c ha d d r e s s e dt h ed i s a d v a n t a g eo fc h o r dw a s p r e s e n t e d 1 1 圮f i n g e rt a b l eo fc h o r dw a si m p r o v e db yf u l l c h o r da l g o r i t h m t h e f o r m u l aw h i c hc a l c u l a t e dt h ef i n g e rt a b l ew a se x t e n d e di n t ot w o ，s ot h a tt h e c a l c u l a t i n gp r o c e d u r ec o u l db ec o n d u c t e di nb o t ho fc l o c k w i s ea n da n t i - c l o c k w i s e d i r e c t i o n s a tt h eb e g i n n i n go f t h es e a r c hp r o c e d u r e ，t h er a n g eo f t h es e a r c hc o u l d b er e s t r i c t e di nah a l fc h o r d - c i r c l eb yf u l l - c h o r d i ns u c haw a y , t h et a r g e tn o d e c o u l db ea p p r o a c h e dm o r e e a s i l ya n dt h es e a r c he 伍c i e n c ya l s oc o u l db ei m p r o v e d t h e o r e t i c a la n a l y s e sh a ds h o w e dt h a tt h ee m c i e n c yo ff u l l c h o r da l g o r i t h mi s c l e a r l ys u p e r i o rt oo r i g h l a dc h o r da l g o r i t h m ni sv e r yc o m m o nt oi n s e r to rd e l e t ean o d ei nap 2 pn e t w o r k , a n d 也e r e f o r e t h ea d a p t a b i l i t yo fp 2 pn e t w o r km u s tb ec o n s i d e r e d t h r o u g hl o t so fw o r ki nt h i s a s p e c t ，a na s s u m p t i o no fc r e a t i n gat a b l eh a v i n grs u c c e s s o r sf o re a c hn o d ew a s p r e s e n t e da n dt h i sw i l ls o l v et h ep r o b l e mb e t t e r t h er e s e a r c hr e s u l t si ns m a l l w o r l df i e l dw e r ea l s ou s e df o rr e f e r e n c et o e x t e n dc h o r da l g o r i t h m t h r o u g ht h ea n a l y s i so ft h en o d ed e g r e e ，ac o n c e p t w h i c hi sc a l l e d s u p e rn o d e ”w a sp r e s e n t e d r e f e r e n c i n gt ot h es e a r c ht e c h n o l o g y o fg o o g l ec a l l e dp a g e r a n k , af o r m u l aw h i c hc a nc a l c u l a t et h en o d er a n g ec a l l e d n o d c r a n g ew a sf o u n da n dt h es u p e rn o d ec a nb ed e t e r m i n e de a s i l yt h r o u g ht h i s f o r m u l a t h er e s o u r c ec o u l db ee m c i e n t l y1 0 e a t e db ys u p e rn o d e a n dt h es e a r c h e 仿c i e n c ya l s oc o u l db ei m p r o v e d f i n a l l y t h es i m u l a t e dt e s t i n g sh a ds h o w e dt h a tt h ee m c i e n c yo ff u l l c h o r d 哈尔滨t 程大学硕十学位论文 i sc l e a r l ys u p e r i o rt ot h eo r i g i n a lc h o r di nt w oa s p e c t so fa v e r a g es e a r c hp a t h l e n g t ha n da v e r a g es e a r c ht i m e k e yw o r d s ：p e e rt op e e r ( p 2 p ) ；d i s t r i b u t e dh a s ht a b l e ( d h t ) ；c o n s i s t e n t h a s h i n g ；s m a l l w o r l d ；c h o r d 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献等的引用已在文中指出，并与参考文献相对应。除文中 已经注明引用的内容外，本论文不包含任何其他个人或集 体已经公开发表的作品成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 作者。签铋墨盒：丝 日 期：q 年湖7 日 哈尔滨_ t 程大学硕士学位论文 1 1 引言 第1 章绪论 对等网是目前非常热门的应用，自1 9 9 9 年以来，对等网的研究一直是国 外知名学府( 如美国麻省理工学院、加州大学伯克利分校和莱斯大学等) 以 及知名企业的研发机构( 如微软、诺基亚的研究院) 关注的重点。它甚至被 美国财富杂志称为改变i n t e r n e t 发展的四大新技术之一，被认为是代表 无线宽带互联网未来的关键技术。 对等网最根本的思想，同时也是它与c s 最显著的区别在于，网络中的 结点既可以获取其它结点的资源或服务同时又是资源或服务的提供者，即兼 具c 1 i e n t 和s e r v e r 的双重身份。 对等网的关键问题是查找，也就是如何在一个动态的( 结点的加入和退 出非常频繁) 环境中查找一个对象。由于对等网有几种不同的拓扑结构，所 以它们对应的查找策略也不同。根据拓扑结构可以将对等网分为以下四种形 式： ( 1 ) 集中式( 中心化) 拓扑：例如n a p s t e r t “。采用集中式的查找策略。 ( 2 ) 全分布式非结构化拓扑：例如g n u t e l l a m 。采用“广播泛洪”的查找 策略。 ( 3 ) 全分布式结构化拓扑；例如c h o r d “1 、c a n “、t a p e s t r y ”1 和p a s t r y 。 采用分布式散列表( d h t ) 进行查找。 ( 4 ) 半分布式结构：例如k a z a a m ，。采用中心化拓扑和全分布式非结构化拓 扑相结合的查找策略，并且k a z a a 采用设置超级结点的一种分层结构。 在以上四种形式中，由于全分布式结构化拓扑结构的可扩展性、可靠性、 可维护性和发现算法效率高等特点，所以成为目前研究的热点。美国m i t 大学 的c h o r d 系统就是其中的典型代表之一。 1 2c h o r d 算法概述及其优缺点 c h o r d 算法是m i t 大学在2 0 0 1 年提出的一种基于d h t 的结构化分布式查 找算法，它具有简单性、可验证性、可扩展性等优点，是一种较为成功的对 等网查找算法。 哈尔滨工程大学硕士学位论文 作为第二代对等网查找算法，c h o r d 算法虽然具有很多优点，但由于d h t 本身的局限性，其无法避免存在一些问题。主要表现在以下几点： ( 1 ) c h o r d 算法的查找效率有待提高。原始c h o r d 算法在n 个结点的网络 中完成查找操作平均需要l o g n 跳，最多需要l o g n 跳。这种查找效率在实 z 时性要求较高的场合是无法满足需求的。 ( 2 ) c h o r d 算法构造的逻辑覆盖网与底层实际的物理网络拓扑完全脱离， 地理位置相近的两个结点在c h o r d 环上可能相距很远。这就导致了c h o r d 算 法扩展到存在地理异构性的大规模广域网环境时，查找效率低下。 ( 3 ) c h o r d 算法指针表信息冗余。由于原始c h o r d 算法构造指针表的公式 和c h o r d 环自身的特点，信息冗余在指针表中是不可避免的。这样，不仅影 响了查找效率，而且使得指针表占用内存空间增大。当有结点加入和退出 c h o r d 环时，需要更新的无用信息增多。 ( 4 ) c h o r d 算法没有考虑结点之间的差异。虽然对等网的理念提出结点之 间是平等的，但在实际环境中。完全平等的结点是不存在的，结点之间或多 或少存在差异。有的结点保存的信息经常被查询，像这样的结点和其它结点 是有区别的，路由它的指针应该被更多的结点知道。 ( 5 ) c h o r d 算法作为一种资源组织与发现技术必须支持复杂的查询，如关 键词、内容查询等。尽管信息检索和数据挖掘领域提供了大量成熟的语义查 询技术，由于d h t 精确关键词映射的特性阻碍了d h t 在复杂查询方面的应用。 1 3c h o r d 算法的研究及改进现状 如何改进c h o r d 算法的指针表以提高查询效率，这是一个关键问题。针 对这个问题，国内外学者提出了许多改进c h o r d 算法的思想。 在这其中具有代表性的有：s t a n f o r d 大学p r a s a n n ag a n e s a n 和g u r m e e t s i n g hm a n k u 提出的最优化路由算法m ，它的基本思想是，从当前结点开始， 沿不同方向、按照不同公式构造指针表。虽然该算法将平均查找路径长度缩 1 短到三l o g n ，但同时增大了指针表的容量。该算法在结点占用内存和提高查 3 询效率之间没有达到很好的平衡。g c o r d a s c o ，l g a r g a n o ，m h a m a r 等人提 出的f - c h o r d ( a ) 优化算法，该算法继承了原始c h o r d 算法的优点，还是在 维护对数级结点数的情况下，将平均查找路径长度缩短到0 ( 1 0 9 n l 0 9 1 0 9 n ) 级别。另外还有高阶c h o r d 算法。该算法指出原始c h o r d 算法相当于2 阶的 c h o r d ，并讨论了一种更为一般化的资源查找策略：高阶c h o r d 。根据高阶 2 哈尔滨工程大学硕士学位论文 c h o r d 的结构，算法可以构造出阶数大于2 的任何阶c h o r d 。高阶c h o r d 将会 使查询请求更快地转发到目标结点，但是为此结点必须维护更大的指针表。 相比于减少转发次数带来的收益，维护指针表的代价是比较低的。因此，可 以通过高阶c h o r d 算法为对等网提供一种更为有效的查找策略。除此之外， 还有h - f - c h o r d ( q ) 、d u a l c h o r d 等改进算法。 经过几年的发展，c h o r d 算法的研究已在理论和实践方面取得很大进展。 不仅出现了上面提到的各种改进算法，而且还有了许多c h o r d 算法的仿真系 统，比如：p 2 p s i m 、p e e r s i m 、f r e e p a s t r y 等。 p 2 p s i m 是m i t 大学计算机科学和人工智能实验室推出的对等网协议仿真 软件，它可以直接仿真目前非常流行的对等网协议，比如：c h o r d 、c a n 、 t a p e s t r y 和p a s t r y 等。另外，通过修改p 2 p s i m 的源代码，还可以仿真任何 改进后的对等网协议。本文提出的f u l l - c h o r d 算法，就是通过p 2 p s i m 来仿 真的。 p e e r s i m 是用j a v a 实现、基于组件技术的仿真器，更好地支持了对等网 的可扩展性和动态性。它使用两种模型，一种是基于环的模型，另一种是基 于事件的模型。它支持基于对象的有标准组件的编程，实现同一接口的组件 可以很容易地替代其它组件。 f r e e p a s t r y 仿真器是一个采用j a v a 的p a s t r y 协议的开源应用的仿真 器。仿真器变量的设置，如节点的个数、生成事件的数量等，依靠启动本地 仿真器时的命令行输入。 1 4 论文的研究目的和意义 本文研究的主要目的是要解决c h o r d 算法查找效率低下的问题。因此，本 文应该首先分析c h o r d 算法的查找策略相容散列，研究可扩展c h o r d 算法 的查找原理。在此基础上，本文提出建立双向路由的f u l l - c h o r d 算法。通过 ， 理论和仿真的分析，f u l l - c h o r d 算法的平均查找路径长度是( 1 0 9 ；+ 1 ) ， 珥z 相比原始的c h o r d 算法，查找效率明显提高。 资源查找成功与否的关键在于指针表中的各项有正确的后继指针。本文 创造性地提出在为每个结点建立指针表的同时，再建立一张拥有r 个后继的后 继列表，这为解决这个关键问题提供了契机。 通过作者分析，发现对等网具有小世界( s m a l 卜w o r l d ) 特征。本文用 s m a l l - _ w o r l d 理论分析了c h o r d 算法，并参考g o o g l e 的网页搜索技术p a g e r a n k ， 在此基础上提出了“超级结点”的概念，给出了计算结点级别的公式 哈尔滨丁程大学硕七学位论文 n o d e r a n g e 。通过s m a l l - w o r l d 理论，能很好地解决地理异构问题( 可以把地 理位置相近的结点放在一起，再设置一个超级结点和一个备用超级结点) 。 通过本课题的研究，解决了c h o r d 模型中的许多问题，在降低资源消耗的 同时很好地提高了查询效率。 1 5 论文的组织结构 本文主要对c h o r d 路由算法做了详细的分析与研究，并在此基础上对 c h o r d 路由算法进行了改进，在结构上本文共分为下面6 章，各个章节的内 容组织如下： 第一章介绍c h o r d 算法的研究及改进现状和本文的研究目的和意义。 第二章简单介绍了对等网的特点、应用及面临的问题，并重点阐述了各 种类型的对等网系统和多种主流的d h t 协议。 第三章首先介绍了c h o r d 算法的基础散列函数，然后在此基础上引出 c h o r d 路由协议( 包括：相容散列，简单的关键字查找和可扩展的关键字查 找) 。 第四章是本文的核心，提出了对可扩展c h o r d 路由算法的改进算法 f u l l c h o r d ，并通过具体实例比较分析了改进后的算法和原算法的性能差异。 然后对结点的加入和稳定、结点加入对查询的影响等各方面进行了分析。 第五章用s m a l l - w o r l d 理论分析如何改进c h o r d 路由算法。 第六章通过仿真比较分析了原始的c h o r d 路由算法和改进后的 f u l l - c h o r d 算法在平均查找长度和平均查询延迟时间上的差异。 4 哈尔滨_ t 程大学硕+ 学位论文 第2 章对等网相关技术介绍 2 1 分布对象的定位机制 分布式计算环境中，对象是通过对象引用来标识的。分布式计算主流技 术c o r b ar m 规范中，规定对象引用包括对象所在的主机名、端口号以及对象标 识等信息。在分布式系统中，客户端必须获取服务器端具体对象的对象引用， 明确对象在网络中的具体物理地址信息之后，才能访问该对象。由于对象引 用由服务器端自动产生，不便于理解和使用，在分布式系统中提供了多种对 象定位机制，使得用户可以通过这些机制来实现对对象的透明访问。分布对 象定位机制是研究如何在分布式计算环境中有效地发布、定位对象的方法。 定位对象的模型包括三个步骤，如图2 1 所示。其中对象目录负责存储 对象定位信息，包括对象名、对象引用和一些与引用相关联的可选择性的描 述性数据( 如属性、功能名等) 。在分布对象计算主流技术c o r 队中，c o r b a 命名服务是基于集中式的对象定位信息目录服务，c o r b a 命名服务规范中的 联邦机制使其可以层次化管理对象目录。c o r b a 交易服务实质上是定义了基 于属性值匹配的一种命名服务，同时还提供了一层与通用目录服务( l d a p ) 的 接口，使得该对象定位机制可以实现基于l d a p 的层次式的对象定位机制。 图2 1 对象定位模型 c o r b a 命名服务是基于集中式的对象定位机制，当整个分布式系统中对 象数目大量增加时，运行命名服务进程的主机将承担很重的名字维护和名字 解析工作，太多的i o 操作使得命名服务器成为分布式系统的瓶颈，任何时 候命名服务器的网络不可达都将导致整个系统的崩溃。交易服务是基于层次 5 哈尔滨工程大学硕十学位论文 式的对象定位机制，其父结点的瓶颈也导致了可扩展性、可用性的不足。当 前c o r b a 在局域网中应用较多，而在整个i n t e r n e t 上的应用很少的一个主要 原因就是其服务发现定位机制的局限。针对大规模分布式系统，基于对等网 的完全分布对象定位机制模型是个很好的选择。 该模型充分考虑对等网系统本身的优势，即将整个分布式系统中所有对 象定位信息不再集中发布在命名服务器上，而是分散到网络中的每台机器上， 同时利用对等网系统所特有的语义路由的功能，实现大规模分布式系统中的 对象定位信息的发布、查询和维护工作。对应于图2 1 的目录服务，亦可描 述为大规模分布式环境中的分布式散列表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 。 2 2 对等网技术的概述 2 2 1 对等网的定义 目前，在学术界、工业界对于对等网没有一个统一的定义，下面列举几 个常用的定义供参考“： p e e r t o p e e ri sat y p eo fi n t e r n e 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 h o t h e rf o rt h ep u r p o s e so fd 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 r s h a r dd r i v e s 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 so 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 r n e t p 2 pn 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 e f i l e si n s t e a do fh a v i n gt og ot h r o u g hac e n t r a ls e r v e r 对等网是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件 资源( 处理能力、存储能力、网络连接能力、打印机等) 。这些共享资源需 要由网络提供服务和内容，能被其它对等结点( p e e r ) 直接访问而无需经过 中间实体。在此网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ， 又是资源( 服务和内容) 获取者( e l i e n t ) 。 虽然上述定义稍有不同，但共同点都是对等网打破了传统的c s 模式， 在网络中的每个结点的地位都是对等的。每个结点既充当服务器，为其它结 点提供服务，同时也享用其它结点提供的服务。 6 哈尔滨下程大学硕+ 学位论文 2 2 2 对等网技术的特点 与其它网络模型相比，对等网具有以下特点： ( 1 ) 非中心化 网络中的资源和服务分散在所有结点上，信息的传输和服务的实现都直 接在结点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。 对等网的非中心化基本特点，带来了其在可扩展性、健壮性等方面的优势。 ( 2 ) 可扩展性 在对等网中，随着用户的加入，不仅服务的需求增加了，系统整体的资 源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整个体系 是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 ( 3 ) 健壮性 对等网架构天生具有耐攻击、高容错的优点。由于服务是分散在各个结 点上进行的，部分结点或网络遭到破坏对其它部分的影响很小。对等网一般 在部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。对等网 通常都是以自组织的方式建立起来的，并允许结点自由地加入和离开。对等 网还能够根据网络带宽、结点数、负载等的变化不断地做自适应式的调整。 ( 4 ) 高性能价格比 性能优势是对等网被广泛关注的一个重要原因。随着硬件技术的发展， 个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。 采用对等网架构可以有效地利用互联网中散布的大量普通结点，将计算任务 或存储资料分布到所有结点上。利用其中闲置的计算能力或存储空间，达到 高性能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更 低的成本提供更高的计算和存储能力。 ( 5 ) 隐私保护 在对等网中，由于信息的传输分散在各结点之间进行而无需经过某个集 中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前解决 i n t e r n e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏 在众多的网络实体之中。在一些传统的匿名通信系统中，实现这一机制依赖 于某些中继服务器结点。而在对等网中，所有参与者都可以提供中继转发的 功能，因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的 隐私保护。 ( 6 ) 负载均衡 对等网环境下由于每个结点既是服务器又是客户机，减少了对传统c s 7 哈尔滨丁程大学硕七学位论文 结构服务器计算能力、存储能力的要求。同时因为资源分布在多个结点，更 好的实现了整个网络的负载均衡。 2 2 3 对等网的应用 对等网的特点充分显示出了其强大的技术优势。从应用角度来看，目前 对等网技术主要涉及到以下几个领域：文件交换、对等计算、搜索引擎、协 同工作和实时通信。 ( 1 ) 文件交换 在传统的w e b 方式中，将文件上传到某个特定的网站，用户再到该网站上 搜索需要的文件，然后下载。这种方式离不开服务器的参与，对用户而言非 常不方便。对等网技术使得i n t e r n e t 上的任意两台计算机之间可以直接共享 文档、多媒体和其它文件。利用对等网技术进行文件交换时，客户不再需要 将文件先传到服务器，而只需在自己的硬盘上开辟共享区，就可以在客户间 进行交换。n a p s t e r 就是一个很好的文件交换软件，它提供用户在互联网上共 享m p 3 音乐文件的对等网服务。n a p s t e r 把音乐文件存储在客户结点上，中心 服务器上存储的仅仅是文件的索引信息，用户之间可以直接共享、传输音乐 文件而无需通过中心索引服务器。 ( 2 ) 对等计算 一般的家庭计算机很多都只是用来处理文字、上网浏览，真正做事的很 少。为了能充分利用这些闲置的中央处理器、内存以及磁盘空间等，科学家 提出了对等计算。采用对等网技术的对等计算，就是把网络中众多计算机暂 时不用的计算能力连接起来，执行超级计算机的任务，通过众多计算机来完 成超级计算机的功能。在对等计算中，大型的计算任务被分解成很多个小的 工作单元，分别分配给网络中的结点独立执行。当结点完成了工作之后就将 结果传送给服务器，然后进行下一个工作单元。其典型代表是s e t i h o m e 系统， s e t i h o m e 是旨在利用连入i n t e r n e t 的成千上万台计算机的闲置能力搜寻外 星文明的大型试验系统。它可以将连入i n t e r n e t 的计算机在闲置时的处理运 算能力整合起来，形成一个超级计算机，并且通过这个超级计算机对由巨型a r e c i b o 望远镜搜集的来自外太空的无线电磁波数据进行分析。据统计，在不 到两年的时间里，这种计算方法已经完成了单台计算机需要3 4 5 0 0 0 年的计算 量。 ( 3 ) 搜索引擎 对等网文件共享首先要解决文件定位的问题。但无论是现在的目录式搜 索引擎，还是l y c o s 和国内百度的智能搜索引擎，其搜索都要依靠服务器来完 8 哈尔滨工程大学硕士学位论文 成。而利用对等网技术的搜索引擎，则完全不需要服务器，用户就能够深度 搜索文档，可达到传统目录式搜索引擎( 只能搜索到2 0 9 6 3 0 的网络资源) 无可 比拟的深度( 理论上将包括网络上的所有开放的信息资源) 。以g n u t e l l a 进行 的搜索为例：一台p c 上的g n u t e l l a 软件可将用户的搜索请求同时发给网络上 多台p c 。如果搜索请求未得到满足，这多台p c 中的每一台都会把该搜索请求 转发给另外多台p c 。理论上，搜索范围将在几秒钟内以凡何级数增长，几分 钟内就可搜遍几百万台p c 上的信息资源。当然实际环境中还需要考虑网络带 宽以及路由优化方面的问题。对等网为互联网的信息搜索提供了一个全新的 解决之道。 ( 4 ) 协同工作 对等网技术一旦用于协同工作，可以使企业内部分散的各部门之间、企 业和关键客户以及合作伙伴之间，建立起安全的网上工作和联系的环境。 g r o o v e 是协同工作的一个例子。它是一个平台，软件开发商可以利用该平台 构建协同环境。g r o o v e 演示了一种对等网的“协同空间”。当用户及其小组 成员在p c 上安装了g r o o v e 后，该小组就创建了一个“虚拟空间”。在这个虚 拟空间中，用户可以实时地与小组成员交互并进行项目协同。除此以外， g r o o v e 还提供了添加新工具和管理小组的规范。 ( 5 ) 实时通信 目前的实时通信技术一般采用一个中心服务器控制着用户的认证等基本 信息，结点之间直接进行数据通信的模式。i c q 、o i c q 、a i m 等是典型的实时 通信系统。j a b b e r 是下一代的实时通信平台，在该平台上可以创建许多应用 程序，包括那些人与人或人与应用程序通信的程序，或者是应用程序之间通 信的程序。 2 2 4 对等网技术所面临的典型问题 ( 1 ) 资源定位问题 在典型的对等网中，数据资源分布在各个独立的结点上，如何高效地索 引、查找、定位以及访问这些数据信息资源是一个重要问题。在分布式系统 中，这些问题同样也是正在研究的热点问题。一般来说在对等网共享应用中 所采用的检索方式是采用键值来查询自己所需的信息资源，同时人们也期望 能够将数据资源的索引信息存放在系统中的每一个结点上，而不是像n a p s t e r 那样存储在中心服务器上。在数据的访问过程中则期望能够采用流水、并行 或者选择传输路径的方式来加快数据的访问速度。 如何在对等网中进行资源定位是首先要解决的问题。一般有以下三种方 9 哈尔滨t 程大学硕十学位论文 式： 集中目录模型 每一个结点将自身能够提供的共享内容注册到一个或几个集中式的目录 服务器中。查找资源时首先通过服务器定位，然后两个结点之间再直接通讯。 例如早期的n a p s t e r ，这类网络实现简单，但往往需要大的目录服务器的支持， 并且系统的健壮性不好。 泛洪请求模型 没有任何索引信息，内容提交与内容查找都通过相邻接结点直接广播传 递，例如g n u t e l l a 。一般情况下，采取这种方式的对等网络对参与结点的带 宽要求比较高。 动态散列表方式 动态散列表( d h t ) “”是大多数对等网所采取的资源定位方式。首先为网 络中的每一个结点分配虚拟地址( r i d ) ，同时用一个键值( k e y ) 来表示其 可提供的共享内容。取一个散列函数，这个函数可以将k e y 转换成一个散列值 i t ( k e y ) 。网络中结点相邻的定义是散列值相邻。发布信息的时候就把( k e y ，r i d ) 二元组发布到具有和h ( k e y ) 相近地址的结点上去，其中r i d 指出了文档的存储 位置。资源定位的时候，就可以快速根据h ( v i d ) 到相近的结点上获取二元组 ( k e y 。r i d ) ，从而获得文档的存储位置。不同的d h t 算法决定了对等网的逻辑 拓扑，比如c a n 就是一个n 维向量空间，而c h o r d 是一个环形拓扑，t a p e s t r y 则 是一个网状的拓扑。 上述的资源定位方式可以依据不同的对等网应用环境来进行选择，但是 d h t 作为第二代资源定位方式，具有更大的技术优势。基于3 h t 的对等网在一 定程度上可以直接实现内容的定位。但该方式存在的一个矛盾是：如果一个 结点提供共享的内容表示越复杂，则散列函数越不好选择；相应的，网络的 拓扑结构就越复杂。而如果内容表示简单，则又达不到真正实现依据内容定 位的能力。目前大多数d h t 方式的对等网对结点所提供共享内容的表示都很简 单，一般仅仅为文件名。 ( 2 ) 安全问题 从集中式转变到全分布式模型面临的另外一个问题就是安全问题。集中 控制可以解决目前网络中多数安全问题，而分布式环境中，安全问题变得更 加复杂。许多对等网应用程序会提供用户信息和服务的直接访问，大多数对 等设备都是个人计算机，而这些计算机都是属于其他用户并由这些用户控制 的。这些用户并不是安全专家，而且对等网应用程序也可能存在安全漏洞， 同时不合理的管理会制造安全漏洞。因此，安全问题值得用户关注。与目前 的c s 模型中面临的安全问题相似，对等网技术中的主要安全问题包括：用户 l o 哈尔滨t 程大学硕+ 学位论文 认证问题、数据加密与解密问题、路由安全问题、存储与访问安全问题、恶 意破坏问题、故意欺骗问题、应用安全问题和个人隐私问题，还有一个重要 的问题亟待解决：在对等网中普遍存在的知识产权保护问题m m m ”。 2 3 对等网中拓t l 、结构研究 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的关系，结 点之间的拓扑结构一直是确定系统类型的重要依据。目前互联网中广泛使用 集中式、层次式等拓扑结构，i n t e r n e t 本身是世界上最大的非集中式的互联 网络。但是1 9 9 0 年代所建立的一些网络应用系统却是完全集中式的系统，很 多w e b 应用都是运行在集中式的服务器系统上。集中式拓扑结构系统目前面临 着存储负载过量、d o s 攻击等一些难以解决的问题。 对等网系统一般要构造一个非集中式的拓扑结构，在构造过程中需要解 决系统中所包含的大量结点如何命名、组织以及确定结点的加入离开方式、 出错恢复等问题。 下面具体介绍在引言中提到的四种拓扑结构。 2 3 1 中心化拓扑 中心化拓扑最大的优点是维护简单、发现效率高。由于资源的发现依赖 中心化的目录系统，发现算法灵活高效并能够实现复杂查询。最大的问题与 传统c s 结构类似，容易造成单点故障、访问的“热点”现象和法律等相关问 题，这是第一代对等网采用的结构模式，经典案例就是著名的m p 3 共享软件 n a p s t e r 。 n a p s t e r 是最早出现的对等网系统之一，并在短期内迅速成长起来。 n a p s t e r 实质上并非是纯粹的对等网系统，它通过一个中央服务器保存所有 n a p s t e r 用户上传的音乐文件索引和存放位置的信息。当某个用户需要某个音 乐文件时，首先连接至l j n 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 模型中，一群高性能的中央服务器保存着网络中所有活动对等 哈尔滨工程大学硕士学位论文 计算机共享资源的目录信息。当需要查询某个文件时，对等机会向一台中央 服务器发出文件查询请求。中央服务器进行相应的检索和查询后，会返回符 合查询要求的对等机地址信息列表。查询发起对等机接收到应答后，会根据 网络流量和延迟等信息进行选择，与合适的对等机建立连接，从而开始文件 传输。 这种对等网络模型存在很多问题，主要表现为： ( 1 ) 中央服务器的瘫痪容易导致整个网络的崩馈，可靠性和安全性较低。 ( 2 ) 随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急 剧增加，所需成本过高。 ( 3 ) 中央服务器的存在引起共享资源在版权问题上的纠纷，并因此被认为 非纯粹意义上的对等网模型。对小型网络而言，集中目录式模型在管理和控 制方面占一定优势。但鉴于其存在的种种缺陷，该模型并不适合大型网络应 用。 2 3 2 全分布式非结构化拓扑 全分布非结构化网络采用了随机图的组织方式，结点度数服从幂律，从 而能够较快发现目的结点。面对网络的动态变化体现了较好的容错能力，因 此具有较好的可用性。同时可以支持复杂查询，如带有规则表达式的多关键 词查询、模糊查询等，最典型的案例是g n u t e l l a 。 g n u t e l l a 是一个对等网文件共享系统，它和n a p s t e r 最大的区别在于 g n u t e l l a 是纯粹的对等网系统，没有索引服务器。它采用了基于完全随机图 的洪泛发现和随机转发机制。为了控制搜索消息的传输，通过t t l ( t i m et o l i v e ) 的减值来实现。 在g n u t e l l a 分布式对等网络模型中，每一个联网计算机在功能上都是对 等的，既是客户机同时又是服务器，所以被称为对等机( s e r v e n t ，s e r v e r + c l i e n t 的组合) 。 随着联网结点的不断增多，网络规模不断扩大，通过这种洪泛方式定位 对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽结点因 网络资源过载而失效。所以在初期的g n u t e l l a 网络中，存在比较严重的分区、 断链现象。也就是说，一个查询访问只能在网络的很小一部分进行，因此网 络的可扩展性不好。所以，解决g n u t e l l a 网络的可扩展性对该网络的进一步 发展至关重要。 由于没有确定拓扑结构的支持，非结构化网络无法保证资源发现的效率。 即使需要查找的目的结点存在，发现也有可能失败。由于采用t t l 、洪泛、随 1 2 哈尔滨1 = 程大学硕七学位论文 机漫步或有选择转发算法，因此直径不可控，可扩展性较差。 因此发现的准确性和可扩展性是非结构化网络面临的两个重要问题。目 前对此类结构的研究主要集中于改进发现算法和复制策略以提高发现的准确 率和性能。 由于非结构化网络将重叠网络认为是一个完全随机图，结点之间的链路 没有遵循某些预先定义的拓扑来构建，所以这些系统一般