2022年非结构化PP系统Overlay优化技术综述 .pdf

《2022年非结构化PP系统Overlay优化技术综述 .pdf》由会员分享，可在线阅读，更多相关《2022年非结构化PP系统Overlay优化技术综述 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、小 型 微 型 计 算 机 系 统MINI MICROSYSTEMS 收稿日期： 2006-本文工作受国家 “ 九七三 ” 重点基础研究发展计划基金项目(2002CB312005)的资助 黄宇， 男， 1982 年生，博士研究生，研究方向为对等计算 , 移动计算； 金蓓弘， 女，1967 年生，博士，副研究员，研究方向为分布式计算, 软件工程技术；非结构化 P2P系统 Overlay 优化技术综述黄宇1,2, 金蓓弘21（中国科学技术大学计算机科学与技术系, 安徽 合肥 230027）2（中国科学院软件研究所 软件工程中心，北京 100080 ）E-mail ： 摘 要： 非结构化 P2P O

2、verlay 网络的结构松散 , 网络中资源的分布没有明确的限制, 这使得非结构化P2P Overlay 网络中的资源搜索在很大程度上依赖于通信开销巨大的泛洪法, 因而非结构化P2P 系统在伸缩性 , 可用性等方面 , 存在明显的不足 . 非结构化P2POverlay 网络的上述特点决定了非结构化P2P Overlay 优化技术的重要性 . 本文分四大类别 , 对非结构化 P2P Overlay 优化技术进行了介绍 , 分析比较了各类方法的优劣以及它们的适用场合, 并在此基础上对未来工作进行了展望.关键词： 非结构化 P2P系统； Overlay 优化中 图 分 类 号 ：文 献 标 识 码

3、：文章编号 ：A Survey of Overlay Optimization Techniques in Unstructured P2P SystemsHUANG Yu1,2，JIN Bei-hong21（Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China）2（Technology Center of Software Engineering, Institute of Software, Chinese Acade

4、my of Sciences Beijing 100080, China ）Abstract: Unstructured P2P systems have loose overlay structure and impose little control over the placement of resources in the overlay. Resource discovery in such systems mainly relies on flooding-based strategies, which greatly affects the system scalability

5、and resource availability. The overlay optimization techniques are thus of great importance to unstructured P2P systems, mainly due to the characteristics of unstructured P2P overlays discussed above. This paper presents a survey on existing overlay optimization techniques for unstructured P2P syste

6、ms. Detailed analysis of different overlay optimization techniques and comparison among the existing techniques are also presented. Based on the survey, this paper also outlines future research directions.Key words: Unstructured P2P Systems; Overlay Optimization 1P2P 计算和 Overlay 网络P2P 计算 (Peer-to-Pe

7、er Computing) 是指不同系统之间通过直接交换 ,实现计算资源的共享. P2P计算利用了网络边缘的资源 , 而不仅仅依赖于中央服务器. P2P 系统一般都具有内在的动态性 , Peer 可以动态地加入和离开网络1,2,3. P2P系统的运作依赖于Peer 之间的直接连接 . 各个 Peer 和系统中其它Peer 在网络体系结构的应用层中建立虚拟连接, 从而整个系统中的所有Peer 互连组成了一个应用层的, 逻辑上的虚拟网络 . 这一网络构建于底层物理网络之上, 依赖于底层物理网络的支持(比如底层 IP 网络的路由等 ), 并且它的构 建独立 于 底 层 物理 网 络(图1), 所以

8、我 们把 它 称 作Overlay 网络 4, 2,5. 根据 Overlay 网络的结构 , 我们可以把P2P 系统划分为结构化(structured)和非结构化 (unstructured)两种 6, 7. 构建 Overlay 网络的本质是让网络中的每个Peer分别存储自己与网络中部分Peer之间的路由信息, 通过 Peer间的合作转发来实现Overlay 网络中的路由 , 并以此为基础 , 为丰富多样的P2P 应用提供支持 . 构建 Overlay 网络的效率 , 对整个 P2P系统的运作 , 有着决定性的影响. Overlay 网络优化则是通过进一步改进每个Peer 记录的路由信息

9、, 来提升名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 黄宇 等：非结构化 P2P系统 Overlay 优化技术综述 2 Peer 间路由的效率 , 为上层的P2P 应用提供更为高效的支持. 图 1. 虚拟的覆盖网和底层的物理网络非结构化P2P 系统 (例如Gnutella8, Kazaa9 等)对Overlay 拓扑结构以及整个系统中资源的放置没有明确的限制. 该类系统中的目标搜索主要是通过Peer 间的协作消息转发 . 非

10、结构化 P2P系统协议简单 , 支持友好的基于关键字的搜索 , 搜索有多个拷贝存在的目标时, 性能很高 . 并且该类系统具有内在的高容错性, 能够很好地应对高度动态变化的 P2P网络 . 但是非结构化P2P系统的伸缩性 (Scalability), 可用性 (Availability) 和持久性 (Persistence)等方面有比较明显的缺陷 , 特别是在搜索稀少资源的时候2. 简单 , 松散的Overlay 构建方式是非结构化系统具有上述缺点的主要原因. 该类系统中的目标搜索一般都需要依赖于洪流法(flooding)或是基于洪流法的改进策略. 因而非结构化P2P 系统中的资源搜索往往会导致

11、大量冗余的通讯负载. 对 Overlay 网络进行优化 (Overlay Optimization), 可以在一定程度上解决上述问题. 合理的 Overlay 优化策略可以为目标搜索协议提供更有效的支持, 减少系统中冗余的通信负载 . Overlay 优化技术对非结构化P2P 系统更高效更广泛的应用 , 具有着重要的推动作用. 研究者已经对各类P2P系统进行了分析和比较. 在11 中 , 作者介绍了非结构化P2P系统中的 Overlay 优化技术 . 文中工作主要针对P2P系统中的拓扑失配(Topology Mismatching)问题 , 集中讨论了基于底层网络信息的(消除拓扑失配的)Ove

12、rlay 优化技术 . 在12中, 作者首先讨论了P2P系统的定义和性能衡量指标, 然后对各种 P2P体系结构 , P2P目标发现协议和P2P系统建模技术进行了介绍和分析. 51 中作者分别对结构化和非结构化 P2P系统进行了详细的介绍, 并对两类 P2P系统的优劣进行了分析比较 . 52 简单介绍了各类P2P 系统 , 并集中在结构化的 P2P系统及其应用 . 在2中, 作者对 P2P系统中的内容分发 (Content Distribution) 技术进行了综述. 作者从系统 的 伸 缩 性 (Scalability), 性 能 (Performance), 公 平 性(Fairness),

13、 安 全 性 (Security) 以 及 资 源 的 管 理 和 归 类(Resource Management and Grouping)这 5 个方面对各种类型的 P2P系统中的内容分发技术进行了考察. 本文分四大类别, 对非结构化 P2P系统中的 Overlay 优化技术进行了介绍和分析. 与11中的工作相比, 本文对各类非结构化Overlay 技术进行了更为全面的介绍和分析. 与12, 2, 51, 52 中针对各类P2P系统的介绍于分析相比, 本文集中关注非结构化的P2P 系统 , 对非结构化系统的Overlay优化技术 , 进行了深入的介绍. 本文其余部分组织方式如下. 本文首先

14、深入研究了P2P Overlay 优化问题和它对非结构化P2P系统的重要影响 (第 2 节). 然后对当前的Overlay 优化技术进行了逐类分析(第 36 节). 本文的最后是结论和未来研究的展望 .2Overlay 优化根据 Overlay 网络的结构 , 我们可以把P2P系统划分为结构化(structured)和非结构化(unstructured)两种 . 在结构化P2P系统中 (例如 Chord14, Pastry15 等), Overlay 拓扑结构以及资源的分布都受严格的控制, 由分布式哈希表决定系统中资源到位置的映射. 在结构化的Overlay 中, 路由效率很 高 , 系 统

15、伸 缩 性 很 好 . 但 是 维 护 高 度 结 构 化 的P2P Overlay 往往导致巨大的通信开销, 并且结构化P2P 系统面对 Peer 的动态加入 /离开 , 效率会受到明显的影响, 而 Peer的动态加入 /离开是P2P 系统的一个本质特征. 结构化P2P系统只能高效支持精确匹配的、单个目标的搜索 , 不能很好地支持基于关键字的、多目标的搜索 . 而目前 P2P系统中的搜索大部分是基于关键字的、针对多个目标的搜索16. 结构化 P2P 系统的不足还体现在该类系统中存在着两种重要的不匹配 : (1) 高度规则的Overlay 和底层物理网络之间的不匹配 ; (2)每个节点的责任和

16、它们能力之间的不匹配2. 非结构化P2P 系统对 Overlay 拓扑以及资源的位置都没有确定的要求 . 在一个非结构化P2P系统中 , 当一个新节点 加 入Overlay网 络 时 , 它 需 要 首 先 和 一 个 初 始 节 点(bootstrapping node)连接 , 并获得 Overlay 网络中其它节点的信息 . 然后新加入的节点可以通过Overlay 路由协议和网络中的其它节点进行通信, 并连接到 Overlay 网络 17. Peer 可以根据应用的需求更新自己的邻居表. 非结构化P2P 系统路由协议简单 , 搜索功能强 , 能高效支持基于关键字的多目标搜索 . 并且非结

17、构化P2P系统具有内在的高容错性. 充分比较两种Overlay 各自的特点 , 我们不难看到非结构化 P2P系统一些固有的缺点: (1) Overlay 结构的松散给其中的目标发现带来了相当的难度. 这使得非结构化P2P 系统中的目标搜索主要依靠泛洪法(flooding)或是基于泛洪法的改进策略 . 因而非结构化P2P 系统中往往存在着大量低效冗余请求. 这严重限制了非结构化系统的伸缩性; (2) Overlay 网络是处在应用层的, 逻辑上的虚拟网络, 现有的Overlay 构建往往忽略了底层基础设施的情况. 而 Overlay 网络中的通信又完全依赖底层基础设施的支持. 因而不受限制的 O

18、verlay 构建会给底层基础设施带来相当严重的通讯负载; (3) 非结构化 P2P 系统中现有的Overlay 构建策略往往忽略了网络中各个Peer之间的相异性 . Peer 在 Overlay 中的角色和自身能力之间的差异可以导致网络中出现多处性能瓶名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 黄宇 等：非结构化 P2P系统 Overlay 优化技术综述 3 颈, 妨碍整个网络的运作; (4) 在 P2P系统中共享的资源,

19、 往往不是在整个系统中随机分布的18, 19. 并且 , 每个 Peer对不同资源的请求一般也遵循特定的规律20, 18, 21, 22. 资源的分布以及Peer 的请求所具有的这些客观规律, 在Overlay 构建时 , 往往被忽略 . 这导致系统中存在大量低效的请求 , 增加了系统的负载, 妨碍了系统的高效运作. 在非结构化 P2P系统中对 Overlay 网络进行优化 , 从每个 Peer的角度来看 , 可以更迅速 , 更充分地响应用户的请求, 提高用户获得的服务质量; 从整个系统运作的角度来讲, 可以降低系统运行的开销,在同等条件下, 支持更大规模的P2P应用 . 针对非结构化P2P

20、Overlay的缺陷 , 研究者们提出了多种优化方法, 它们主要包括四类: (1) 基于拓扑特性的Overlay 优化; (2)基于底层网络信息的Overlay 优化 ; (3)基于Peer角色区分的 Overlay 优化 ; (4)基于被请求内容的Overlay优化 . 我们在后续四节中对这四类方法逐个进行分析.3基于拓扑特性的Overlay 优化Overlay 结构的松散给其中的目标发现带来了相当的难度, 这导致非结构化P2P 系统中的目标搜索在相当程度上依赖于通信开销巨大的泛洪法. 根据非结构化Overlay 的这一特点 , 一种可行的Overlay 优化方法是在Overlay 网络中维

21、护特殊的拓扑结构, 利用 Overlay 网络的拓扑性质, 来提升目标发现的效率. 23, 24, 25, 26, 27, 28提出了一类基于多播的Overlay优化方法 , 但是它们又有各自的不同. Yoid23, BTP24和Overcast25协议要求每个Peer 直接根据自己的邻居信息, 确定自己在多播树中的父节点和子节点. 这些系统中只有一棵针对单个源节点的多播树, 或者是有一个公共的多播树. 而 P2P 系统中 , 每个节点都可能成为源节点, 这限制了这一类方法的效率. 29 提出了多播树优化方法TMesh. TMesh 方法通过在已有Overlay 上再随机添加一些链接(Shor

22、tcut), 来提高通信效率, 进一步降低请求响应时间. TMesh 方法可以和任何已有的基于树形拓扑的多播算法结合使用 . 26和27改进了上述单一多播树的方法, 分两步来优化 Overlay 网络 . 首先 , Narada 和 Gossamer在系统中纯分布式地建立一个具有很高连通性的Mesh （2 维网格） , 并提供相应机制处理节点地加入和离开, 防止 Mesh 的分割与断连 . 然后 , 基于这个Mesh, 请求的发起节点可以再生成一棵多播树 , 将自己的请求多播给系统中其它节点. 基于Overlay网络中高连通性的Mesh, 和根据该Mesh 生成的多播树, Narada和 Go

23、ssamer能高效地将自己的请求多播给更多的节点, 并且面对动态P2P环境 , 具有一定的自组织性和自改进性. Kudos28 将分级优化Overlay 的想法又推进了一步, 它在 Overlay 中构建两个层次的Cluster, 并在每个层次上都使用类似 Narada的协议构建Overlay. 这一类方法最关键的问题在于 Overlay 的结构过于复杂 , 维护这样的结构往往需要非常大的开销 . 上述 Overlay 优化方法 , 利用了多播树的拓扑特性, 有效地控制了消息分发过程中的通信开销. 与基于多播树的方法不同 , 30 提出了一个基于连通支配集CDS(Connected Domin

24、ating Set) 的 Overlay 优化方法 . ( 在一个图G(V,E)中, 我们称集合D 为图 G 的支配集 , 如果 : (1) 集合 D 是点集 V的子集 ; (2) 任取点集 V 中的节点 a 满足 : aD, 或者存在点bV 且边 (a,b)边集 E. 如果图 G 的支配集 D 是点集 V 的连通子集 , 我们称 D 为图 G 的连通支配集 .) 使用基于连通支配集的方法时 , CDS 的构建仅仅依赖各Peer本地的 1-hop和 2-hop 邻居信息 . CDS的构建主要包括两个过程: 标记(marking) 和简化 (reduction). 首先在标记过程中, 各节点通过

25、比较自己邻居节点的邻居信息, 决定自己是否应该成为CDS 中的节点 . 通过标记过程 , CDS 在 Overlay 网络中被创建. 然后依据下面的两个规则, CDS中的冗余节点被剔除. 规则 (1): 如果 CDS 中的两个节点u 和 v 满足 : 邻居节点集合 N(v)N(u), 且 doc(v)doc(u), 则节点 v 被剔除出 CDS. (这里函数 doc(v)被定义为 : 节点 v 的 doc(v)值为节点 v存储的文件数目加上v 的邻居节点存储文件数目的最大值. 并且 , doc(v)函数通过每个节点全局唯一的ID 来保证任意两个节点的 doc函数值不等 ); 规则 (2): 如

26、果 CDS中的三个节点u, v, w 满足 : u,w 是 v 的邻居节点 , N(v)?N(u)N(w), 且 doc(v) = min(doc(v), doc(u), doc(w), 则节点 v 被剔除出 CDS. 30中的实验表明 , 基于经过优化的CDS 的支持 , 节点的请求能够被尽快地转发给足够多的节点, 并且请求被优先转发给拥有更多共享资源的节点. 在开销方面 , 创建和维护 CDS的代价要低于创建和维护路由索引的代价. ?这一类基于拓扑特性的Overlay 优化方法在基本原理上与设计结构化P2P Overlay 是共通的 . 它们都是通过加强Overlay 的拓扑性质 , 来获

27、得目标发现方面的效率. 基于这一原因 , 这类方法也不可避免地具有与结构化P2P 系统类似的缺点 . 首先在 Overlay 中维护特定的拓扑结构, 必然要付出相应的代价 . 例如在 Narada 中的通信负载与多播组的大小成正比 , 这就限制了Narada 机制在大规模P2P 系统中的应用 . 其次 , 面对动态的 P2P环境 , 要想维持 Overlay 的拓扑性质 , 同样需要付出相应的代价. Narada 中的 Mesh 和基于支配集方法中的CDS, 都面临着在Peer频繁离开 /加入的情况下如何还保持系统必须的连通性的问题. 基于支配集的方法还需要维持CDS 的支配性 . 基于上述的

28、原因, 单纯依赖 Overlay 拓扑特性的方法更适用于网络中节点相对稳定的情况 . 4基于底层网络信息的Overlay 优化由于 Peer之间的无序连接以及Peer的随机加入与退出, 同时 Peer间的协作忽略底层物理网络的拓扑结构, P2P系统一般都面临着拓扑失配(Topology Mismatching )问题 31, 32, 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 黄宇 等：非结构化 P2P系统 Overlay

29、优化技术综述 4 33, 34. 拓扑失配问题是指由于应用层Overlay 网络的拓扑结构和底层物理网络的拓扑结构之间存在不一致, 而使得应用层 Overlay 网络中的通信给底层物理网络带来很大的负载. 拓扑失配问题非常重要, 因为基于一个低效Overlay 的搜索会产生很多无效的通信负载, 给底层基础设施带来很大的负担 . 拓扑失配问题的高效解决可以增加非结构化P2P系统的伸缩性 , 使它能够更高效、更广泛地被使用. 解决拓扑失配问题还能使非结构化P2P 系统更合理地使用底层的基础设施 , 大大地降低网络运营商的开销35. 因为拓扑失配问题的存在和它的重要性, 根据底层网络的信息来优化Ov

30、erlay 网络, 减轻拓扑失配成为Overlay 优化的重要方法 . 36提出基于 IP 地址来获取底层物理网络信息的三种技术 GeoTrack, GeoPing和 GeoCluster. 它们都能根据网络层信息来推断物理网络的拓扑. GeoTRack 技术根据节点的DNS 信息和邻居节点的信息来推断物理网络的结构. GeoCluster技术通过 IP 地址和 BGP(Border Gateway Protocol)协议的前缀信息将节点分成cluster, 然后根据 cluster 中部分节点的位置信息 , 来推断整个cluster 的位置信息 . GeoPing技术则通过网络延迟来推断目标

31、节点的位置. GeoTrack 技术需要 DNS 的支持 , 而 GeoCluster技术需要 BGP的支持 . 这限制了它们在P2P系统中的应用 . 并且它们对物理位置的推断不够精确. 而 GeoPing采用的以网络延迟来衡量节点间相对位置的方法, 对 Overlay 的优化则有很大的意义 . 因为网络延迟本身对P2P系统中的 Peer来说 , 是非常重要的一个指标. 因而基于网络延迟, 可以比较有效地反映出底层物理网络的拓扑结构, 为拓扑失配问题的解决提供有效的支持 . 31, 32, 33, 34均采用以网络延迟来衡量节点间位置的思想,提出多种 Overlay 优化方法 . 31, 33

32、提出了自适应的连接建立方法ACE (Adaptive Connection Establishment), 来减少拓扑失配的负面影响. ACE 利用 Peer之间的网络延迟 , 作为衡量 Peer间相对位置与通信代价的标准. 使用 ACE 方法 , 每个 Peer首先建立一个邻居通信代价表. 然后根据邻居间通信的代价, 每个节点可以在自己和所有的邻居中建立一棵最小生成树. 最后 , Overlay 拓扑被进一步优化, 通信代价更多的邻居被通信代价少的邻居取代 . 通过考虑底层网络的信息, 优化 Overlay拓扑 , ACE 方法在不影响目标搜索效率的前提下, 使类Gnutella 系统中的通

33、信开销下降了65%. 37提出了基于2-hop 邻居信息的Overlay 优化方法THANCS(Two Hop Away Neighbor Comparison and Selection). THANCS 让每个 Peer收集自己的 2-hop 邻居信息 , 并且基于 Peer间通信延迟 , 对所有 2-hop 邻居进行比较和筛选, 实现优化Overlay 的目的 . THANCS 方法能够很好地和已有的路由算法结合. 实验表明 , 经过 THANCS 的优化 , Random walk38 和 Index Caching39 这两种搜索策略的响应时间和通信代价都有了明显的降低. 40和32

34、分别提出了自适应的Overlay 优化方法AOTO(Adaptive Overlay Topology Optimization)和基于位置信息的拓扑失配解决方法LTM(Location-aware Topology Matching). 这两种方法同样采用Peer间的通信延迟作为衡量节点位置远近的标准. 基于 Peer间的位置远近 , 在保证搜索效率的前提下 , Overlay 中长距离的低效连接被逐步剔除. 34提出的 SBO(Scalable Bipartite Overlay) 方法仍然采用衡量 Peer间通信延迟的方法来优化Overlay, 解决拓扑失配问题, 所不同的是它进一步采用

35、对节点染色的机制, 将Overlay 优化的代价分摊 . 这一类Overlay 优化方法的基础是节点间通信代价的获取 , 通信代价表的构建是一个关键的问题. 特别是在网络动态变化的时候. 很难在通信代价信息的及时性和获取通信代价所需开销之间作出很好的平衡. 并且 , 这一类方法仍然需要通过复杂的操作, 在 Overlay 中维护特定的拓扑结构. 这给系统带来不少通信负载. 同时 , 这一类Overlay 优化方法虽然对P2P 网络的动态性作了考虑, 但是由于该类方法所需操作的复杂性, 在实际使用中 , 它们还需要一个比较长的准备时间 , 才能实现对Overlay 的优化 , 发挥预期的作用 .

36、 Overlay 优化收敛速度的缓慢也限制了该类方法在动态P2P环境中的广泛使用. 另外 , LTM方法需要时钟同步, 这也限制了它在纯分布式环境中使用的效率. 5基于角色区分的Overlay 优化在 Internet 环境中 , P2P系统中的各个Peer之间往往具有显著的差别(heterogeneity). 这些差别一般体现在节点的处理能力、 网络带宽、 存储空间等方面 41. P2P 系统中往往还有节点因为防火墙的存在, 只具有受限制的可连接性. 42中的实验表明 , 在 eDonkey 和 Gnutella 系统中 , 有多达 36%的节点具有受限的可连接性, 它们只能对外发出请求,

37、却不能接收别的节点的请求. 虽然 Peer间的差异客观存在, 但是现有非结构化P2P系统中的 Overlay 构建策略却往往忽略了这一点 . Peer 在 Overlay 中的角色和自身能力的差异可以导致网络中出现多处性能瓶颈, 妨碍整个网络的高效运作. 基于上述原因 , 让 Overlay 网络的结构在整体上尽量符合更多节点的特征, 是一类重要的Overlay 优化方法 . 它能够让能力强的节点更多地为整个系统作贡献, 同时又能够避免能力弱或受限的节点成为整个网络的瓶颈. Kazaa9是最早利用节点间的相异性的系统之一. 根据43, 在 kazaa 系统中 , Peer 被划分为两类: 超级

38、节点(Super Node) 和普通节点 (Ordinary Node). 普通节点只和超级节点相连 , 而超级节点之间互相连接组成了Overlay 网络 . 超级节点维护所有子节点的文件信息, 并且负责向其它超级节点转发本地不能命中的请求. 虽然 Kazaa考虑了节点之间的相异性 , 但是其中的资源搜索在相当的程度上依赖于洪流法路由 . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 黄宇 等：非结构化 P2P系统 Overl

39、ay 优化技术综述 5 16 对 Gnutella8 系统进行改进, 提出了能动态调整Overlay 结构和路由策略的系统Gia. Gia 包括一个动态的拓扑调整协议 , 该拓扑调整协议保证了Overlay 拓扑中度数很高的节点 , 的确具有足够的处理能力, 能够处理更多的请求; 协议还保证了在Overlay 网络中 , 绝大部分节点都处在高处理能力节点的周围.Gia 采用的动态拓扑调整协议的核心思想是 : 首先 , 每个节点综合考虑自身的带宽, 处理能力 , 磁盘访问速度等因素, 来计算出自身的能力值Capacity(用单位时间能处理请求的数目来表征). 每个节点根据自己的Capacity和

40、现有的负载 , 计算出自己的饱和程度Satisfaction. 只有饱和 Satisfaction 小于 1, 即负载低于自身Capacity 的节点才能接纳新的节点作为自己的邻居; 同时 , Satisfaction大于 1 的节点 , 即过载的节点 , 会剔除多余邻居. Gia 还包括一个主动的流量控制协议, 用来避免通信负载过分集中于少数节点 . 流量控制协议通过令牌(Token)机制来实现. 每个节点为自己愿意接受的请求发放令牌, 只有获得令牌的节点才能够向该节点发送请求. 通过在设计Overlay 结构时 , 充分考虑各个节点的不同能力, Gia 对传统的 Gnutella 系统作出

41、了明显的改进. Gia系统具有更好的伸缩性, 更高的系统吞吐量 , 并同时保持了Gnutella 系统所具有的高容错性. 44 提出了e* 算法 , 来构建能感知节点可连接性的Overlay 网 络 . e* 算 法 首 先 对 网 络 中 的 节 点 进 行 分 簇(cluster), 并选择可连接性 , 处理能力 , 带宽等方面都满足要求的节点成为Cluster head. 第二步 , e* 算法将所有Cluster head连接起来 . 最后 e* 算法通过在Overlay 中在添加一些额外的边 , 来进一步提高系统在响应时间方面的性能. e*算法着重考虑Peer的可连接性 , 以此来对

42、 Overlay 进行优化 . 该算法能够明显提高系统在响应时间方面的表现. 实验表明, 使用e* 算法的系统 , 请求相应时间比其它同类系统降低了 28-61%. 该类方法通过考虑系统中Peer 之间的差异来优化Overlay 网络 . 通过调整了系统中负载的分配, 该类方法明显提高了整个系统的吞吐率. 但是这一类方法, 通过对某些Super-peer 角 色 的 提 升 , 使 系 统 中 局 部 地 出 现 了Client/Server 通信模式 . 因而这些方法也具有Client/Server模式共有的缺点 . 该类方法增强了系统对这些Super-peer的依赖 , 削弱了传统的非结构

43、化P2P系统优越的容错性, 增加了系统中发生单点失败的概率. 6基于被请求内容的Overlay 优化相关研究 45, 46, 47, 48表明 , 用户的多个请求之间具有高度的关联 . 在 P2P网络环境中 , 18, 19的实验表明 , 系统中的资源 , 一般不是在整个系统中随机分布, 而是具有一定的集中性(locality): 大部分的请求都是由少量内容丰富的节点提供的. 同时 , 系统中每个Peer 感兴趣的内容, 往往也表现出一定的集中性: Peer 一般只对某些主题的内容有兴趣 , 并且它的绝大部分请求, 都可以由少量跟该Peer有相同兴趣的Peer来满足 20, 18. 39 中的

44、实验表明 , Gnutella系 统 中 用 户 对 不 同 内 容 的 兴 趣 近 似 的 服 从Zipf-like 分布 . 被请求的内容以及Peer的需求所具有的客观规律 , 在现有的 Overlay 构建策略中往往被忽略. 这导致系统中存在大量盲目、 低效的请求 , 增加了系统的负载, 浪费了系统的资源 . 基于上述原因 , 我们可以对 Overlay 进行优化 , 利用系统中被请求内容的客观规律, 为更高效的目标搜索提供充分的支持. 基 于Peer 感 兴 趣 内 容 的 集 中 性 , 20提 出 了Interest-based shortcut方法 , 对 Gnutella 系统

45、进行了改进, 使得系统中大部分不必要的flood 能够被避免 , 因而使系统获得更好的伸缩性 . 该方法在Gnutella 系统的Overlay 之上 , 再增加一些特殊的连接(Interest-based Shortcut), 将具有类似兴趣的 Peer 连接在一起 . 由于 Peer 感兴趣内容集中性的存在 , 利用这些 Shortcut, Overlay 中的目标发现被明显加速.在 Shortcut 失效的时候 , Peer 仍然可以使用Gnutella 原有的Overlay 进行通信 . Interest-based shortcut 方法通过对感兴趣内容的本地性的发掘, 以合理的代价

46、 , 获得了内容发现效率的明显提升 . 18提出了CAC-SPIRP 方法 . 该方法包括两个部分. 第一部分 CAC(Content Abundant Cluster) 基于内容提供者的集中性 , 让具有丰富内容的Peer自组织成 Cluster. 该 Cluster包含了丰富的内容, 可以供系统中其它Peer频繁地请求 . 第二部 分SPIRP(Selectively Prefetching Indices from Responding Peers)让每个 Peer基于感兴趣内容的集中性, 选择出一组跟自己兴趣类似的Peer, 并预取这些Peer 提供内容的索引 . 实验表明 , CAC

47、-SPIRP 方法能够明显地请求的响应时间 , 并且同时降低了系统中的通信负载. 21提出了 Associative Overlay的概念 , 来对 Overlay进行优化 . 首先 , 系统需要根据资源的内容, 预定一些规则(guide rule), 并根据规则对系统中的资源进行分组. 相近主题的内容隶属于同一条规则. 然后 , 分别针对每一条规则, 具有该规则涵盖的资源的所有Peer 之间组成一个Overlay. 同一个Peer 可以具有不同主题的内容, 因而可以有针对不同规则的多组Overlay 邻居 . 基于这一机制 , Peer 的请求被限制在针对其所属规则的Overlay 中, 可

48、以更快地命中目标, 同时带来的通信负载, 与盲目的洪流法相比也明显减小. 22提出了基于兴趣组(Interest-Group) 的方法 , 来优化Overlay 网络 , 提高搜索效率. 首先 , 系统使用资源描述框架 RDF49 对系统中的资源进行描述. 然后 , 基于描述每个Peer所提供资源的元数据(Metadata), 以及不同 Peer间的兴趣比较机制MSW(Metadata Slide Window), 系统中的Peer依据它们各自的兴趣自组织成不同的Interest-Group, 资源的搜索首先在Interest-Group 之内进行 . 与21类似 , Peer 的请求被限制在

49、Interest Group 中, 可以更快地命中目标, 同时名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 黄宇 等：非结构化 P2P系统 Overlay 优化技术综述 6 带来的通信负载也明显减小. 50中 提 出 了 基 于 兴 趣 进 行 分 簇 的 方 法ICN(Interest-based Clustering Network). ICN方法采取了层次化的结构 , 对用户感兴趣的内容进行归类, 并根据该分类来聚合相近

50、兴趣的Peer, 对系统中的 Peer进行分簇 . 与21, 22中的工作类似 , 在基于兴趣分簇的P2P系统中 , Peer 的请求被限制在基于兴趣的Cluster 中, 通信效率得到了提高. 21, 22, 50中各自提出的三种方法, 在基本原理上是相同的 . 它们都根据各个节点的兴趣, 对节点进行归类. 这三种方法的区别在于它们各自使用了不同的机制来表述节点的兴趣 , 如自定义规则(guide rule), 资源的元数据描述(metadata)等. 这一类基于被请求内容的方法从一个不同的角度挖掘了 Overlay 优化的空间 . 提升了系统运作效率, 降低了通信负载 . 并且该类方法可以