博士论文开题报告基于gossip的P2P网络拓扑优化技术研究.doc

《博士论文开题报告基于gossip的P2P网络拓扑优化技术研究.doc》由会员分享，可在线阅读，更多相关《博士论文开题报告基于gossip的P2P网络拓扑优化技术研究.doc（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、. . . . 研究生学位论文开题报告登记表学 院：专 业：学 号：姓 名：导师：导师职称：教授（博导） 0000年 00 月 00 日71 / 75目 录1. 立论依据11.1 选题的研究意义11.2 选题的应用价值31.3 国外研究现状51.3.1 基于gossip的P2P网络拓扑管理技术61.3.1.1 拓扑管理71.3.1.2 负载均衡程度的评价方法111.3.2 基于gossip的分层P2P拓扑构造技术111.3.3 基于gossip的组播信息分发技术151.3.4 技术难点191.4 国外专利分析201.4.1 专利查询说明201.4.2 相关专利容分析221.4.3 专利分析总结

2、252. 论文工作实施292.1 论文研究容292.2 拟解决关键问题312.3 研究与工作目标312.4 研究方案322.5 技术路线332.5.1 基于gossip的P2P网络拓扑管理协议LBTMP342.5.2 基于gossip的自适应分层P2P网络拓扑Firas392.5.3 基于gossip的分层P2P组播分发协议DouLaCast452.5.4 基于gossip机制的互联网影像分发系统502.6 实验系统522.6.1 实验系统设计与原理图522.6.2 实验环境与测试条件532.6.3 实验测试容542.6.4 测试表格设计542.6.5 结果预测与分析原则552.7 可行性分析

3、562.7.1 原理可行性分析562.7.2 研究方法可行性分析562.7.3 初期实验可行性分析572.7.3.1 基于gossip的P2P网络拓扑管理协议的实验可行性分析572.7.3.2 基于gossip的自适应分层P2P拓扑构造协议实验可行性分析582.7.3.3 基于gossip的分层P2P拓扑组播分发算法的实验可行性分析592.8 论文的创新之处602.9 研究计划602.10 预期可完成的研究成果613. 论文工作基础和开题要求对照表633.1 论文研究基础633.2 开题要求完成情况对照表654. 参考文献与出处67附：参考文献分布情况分析71结尾72开题报告1. 立论依据（要

4、求：基础研究需结合科学研究发展趋势来论述科学意义；应用研究需结合国民经济和社会发展中迫切需要解决的关键科技问题（牢扣可扩展性与可靠性）来论述其应用前景。）1.1 选题的研究意义从上世纪50年代计算机网络产生至今，通过网络进行信息传播已经对人类的工作与生活产生了巨大影响。国务院新闻办公室主任王晨在2010年5月1日提到，中国网民人数达到4.04亿，互联网普与率达到28.9%，超过世界平均水平，使用手机上网的网民达到2.33亿人。艾瑞咨询分析认为，中国互联网现阶段正处于快速扩时期，并将持续较长的一段时间，在此期间中国网民总数将保持持续的稳定增长。其中视频分享等高带宽业务由2009年4月的1.8亿上

5、升到2010年3月的2.4亿。以上说明中国互联网用户规模增长迅速，互联网用户对诸如流媒体播放等高带宽业务的需求明显增加，这为互联网服务商发展并推广新的互联网业务带来增长点。随着在线游戏，文件共享传输，网络存储，流媒体直播，交互式网络电视等新业务的不断发展，对互联网服务商的服务质量提出了更高的要求，也给网络技术的发展提出了新挑战。近年来，对等网络（Peer-to-Peer）1作为一种高效的分布式网络，受到越来越多的关注。其主要特征在于去中心化，服务不再由单一的服务器提供，网络节点之间呈现对等特性，发展趋势如图1.1.1所示。中国电信总工程师韦乐平在2010年5月6日透露，目前的互联网流量的主要增

6、长点为P2P和网络视频，其中P2P的流量占比高达70%。图1.1.1 P2P的发展历史与趋势但是自Napster2诞生以来传统的P2P网络模型给现有的通信技术提出了诸多挑战。其中最重要的便是通信规模的扩引起的可扩展性与可靠性的问题。P2P网络作为一个开放的分布式通信系统，其规模已从小规模向大规模甚至海量规模过渡。但由于P2P节点的构成主要为廉价的PC客户端，自身硬件可靠性差、存在较强的资源异构性特征，并且用户可以随意加入或离开P2P网络。故大规模的P2P网络具有较强的动态性与较低的可靠性，使得P2P网络不能为上层应用提供稳定可靠的服务来保证上层业务的持续顺利运行，降低了P2P网络的可用性。可见

7、大规模与动态性的特点对当前P2P网络的可扩展性与可靠性造成了影响。Chawathe7与Yang83分别在SIGCOMM03（文献7被引971次）与ICDE03（文献83被引874次）的会议中指出目前主流的P2P模型存在如下主要问题：1）高度中心化的拓扑结构如Napster2网络存在单点崩溃现象，无法承受大规模的访问压力。2）全分布式的拓扑结构如Gnutella网络3采用洪泛查询方式提供资源搜索服务，导致网络查询半径较大，重复请求连接较多，限制了P2P网络的可扩展性。3）DHT结构的Chord4，Pastry5，Kademelia6等结构化P2P网络在网络扰动（network churn）时查询

8、路径树的频繁重构将导致较大开销7，引起查询效率低下。此外DHT不支持模糊查询与语义查询8。需要构建一种可以适应网络规模增长、鲁棒性强的P2P网络模型来保证P2P网络的稳定运行，为上层应用提供可靠的服务。Gossip技术作为一种简单有效的信息传播方式，可应用于构建鲁棒性的大规模自适应P2P网络。Gossip协议利用流言在人群中的传播特点进行信息传播，每个gossip节点无需感知全局拓扑结构，只需要根据自己的本地邻居表进行gossip目标节点的选择然后进行信息发送（也可为双向交互过程）即可完成一次gossip传输，过程简单。SPYROS在其博士论文8中指出了基于gossip的P2P网络具有以下特点

9、： 1）自配置性：采用简单的管理模式对全网进行分布式管理，对于诸如加入离开或其他支撑上层应用的操作原语可以自行配置完成，无需大量其他节点或具有中心化管理功能的服务器支持，具有即时生效的特点。同时系统服务能力可以随系统规模增大而增强，呈现比例关系，具有良好的扩展性。2）自组织特性：能够快速适应系统的动态变化，并能持续容忍这种变化发生。即在动态网络环境中模型可以有效抵抗节点或者链路失效，具有自我修复的能力。可以看出，基于gossip机制的P2P网络的自配置性使得网络具有分布式管理的能力，无需引入中心服务器对网络进行集中控管，不存在单点崩溃导致网络崩溃的可能性，且系统服务性能不会随网络规模增大而呈现

10、停滞甚至下降，网络具有良好的扩展性，并有利于将底层的服务支撑与上层应用分开进行层次化的应用系统设计；自组织性使网络可以具有一定的弹性，可以从网络扰动中快速恢复，保持持续的服务能力。 目前基于gossip技术的网络应用尚处于初期，本文拟采用gossip机制的协议来解决并优化P2P网络的拓扑管理，分层拓扑构造，组播分发等方面存在的问题。具体的问题如下：u P2P拓扑管理中负载分布不均衡导致网络服务不公平的问题在P2P网络中为用户公平的网络服务是促进P2P网络健康发展所面临的关键所在。即P2P节点所承担的负载与其服务能力成正比，服务节点的选择不应该总是偏向少数节点，而是应该从全局角度有一个均衡化的考

11、量。拓扑管理作为一个基础服务，其主要作用之一是向上层应用提供节点选择服务。传统拓扑管理技术采用基于随机选择的策略进行拓扑信息交换与融合，部分考虑了服务节点选择的均衡性问题，同时采用节点入度方差作为描述网络整体负载均衡程度的指标。但P2P网络的一个显著特点便是节点服务能力异构，由于传统方法没有考虑节点的服务能力差异性与负载动态变化的特性，导致节点选择服务提供盲目随机的节点选择，致使网络负载可能继续偏向少数重负载节点，进一步恶化网络公平性，降低用户参与P2P网络的意愿。同时，盲目随机的节点选择增加了服务节点的误选机率达20%-30%，导致必须重新进行节点选择，增加了用户进行P2P应用的服务等待时间

12、。u 分层P2P拓扑中超级节点比例不可控导致服务效率低下的问题2005年，IEEE高级会员Liu等人34在国际权威期刊TPDS中发表论文指出，分层P2P拓扑如果不能保证可控的超级节点比例，系统服务性能难以达到最优。而目前的分层P2P网络在构造拓扑时不能根据网络规模的变化提供一种灵活的控制机制来保证合适的超级节点比例。实验表明：传统的固定阈值划分法不具有自适应性，而传统的自适应分层拓扑在节点规模增加100%时超级节点规模仅增加大约44%。不可控的超级节点比例将导致分层P2P网络中超级节点过多或叶节点过多的现象，降低P2P网络服务性能。u P2P拓扑中组播分发可靠性与冗余开销导致延时增加与浪费带宽

13、的问题当前的P2P拓扑中的组播分发主要依赖构建组播分发树或采用类似洪泛的纯分布式概率转发方式。组播分发树效率较高但当应用于频繁出现网络扰动的大规模P2P网络时，组播树需要频繁重建，导致分发可靠性降低；而纯分布式的概率转发没有考虑节点服务能力的差异性，导致盲目的中继转发节点选择引发大量低服务能力节点参与组播，使得组播的原子可靠性低于90%。同时大量低服务能力节点参与组播将增加冗余数据传输，延缓了组播的收敛时间，最终降低了组播分发的可用性。本文拟开展以下研究：在拓扑管理中引入新的负载评价模型来对网络整体负载分布进行实时的评估，改进拓扑管理的节点选择模式，降低节点选择的误选概率并提高网络的负载均衡程

14、度，最终提高P2P网络的整体服务性能；构建一种自适应的分层拓扑来改进拓扑的构造模式，使其具有稳定可控的超级节点比例，能适应网络环境的变化；构造一种高可靠低冗余的组播分发协议，在可控的分层P2P拓扑上利用优化的缓存机制和负载感知机制来提高组播的可靠性，并降低冗余消息的转发。以上改进有利于增强P2P网络的服务性能，对提升P2P网络的综合性能具有极高的参考价值。为此，本文的研究结合gossip协议的原理与P2P网络的特性进行P2P网络拓扑优化与相关应用的研究，通过对P2P网络进行拓扑管理、拓扑优化与组播分发技术的改进来提高P2P网络的可靠性与可扩展性。本研究以构造可靠的大规模P2P网络平台为目的，为

15、将来大规模的P2P网络应用平台提供了理论支持，具有较重要的理论意义与应用价值。1.2 选题的应用价值本文研究的容包括无结构P2P网络中的拓扑管理策略，自适应的半结构化拓扑构造以与高效可靠的信息分发技术。研究成果可推广应用于众多领域，主要应用包括以下方面：一、应用于P2P的流媒体视频直播基于P2P方式的流媒体已经成为P2P的主要应用方式之一。典型的应用如PPLive与PPStream。据PPLive官方统计16，PPLive的用户规模已经达到1.2亿，同时在线观看人数突破500万。庞大的用户规模必然给P2P流媒体领域的发展带来广阔的商业前景。 节点选择：目前的P2P流媒体网络在进行节点选择时是通

16、过底层的gossip过程随机选择一些邻居作为服务节点提供给上层的应用，没有充分考虑被选择的服务节点是否有能力承载上层应用的服务请求，导致节点选择的误选率增加，而且没有从全局的角度考虑负载均衡，影响了最终节点选择的性能。本研究提出的LBTMP协议兼顾负载均衡与节点选择的随机性，可以改进P2P节点选择方式，起到均衡网络负载的功效。LBTMP采用了新的负载描述模型描述节点的服务能力与实时负载。通过改进拓扑信息交换策略与节点选择策略优先将剩余负载能力高的节点作为备选节点提供给上层应用，降低了节点误选机率，并起到了均衡负载分布的作用。 分层拓扑构造：大规模网络化是目前P2P流媒体网络的的趋势发展，但是海

17、量的用户规模必然给流媒体服务器的访问带来巨大压力。本研究提出的自适应分层P2P拓扑构造技术可以构造一个以终端节点为组成单元的自适应分层P2P网络，然后由超级节点向视频服务器请时数据流，而叶节点通过超级节点的转发来获取数据流。该拓扑可以有效利用终端用户的网络资源，从而减少对视频服务器的访问压力，节约了服务器资源并提高系统稳定性。同时在分层拓扑维护过程中视频节点可以根据自身的负载变化实现自适应的角色转换来适应网络环境变化。二、大规模在线网络游戏光纤到户的普与和3G时代的来临意味着用户终端可以通过有线或无线接入方式享受高速网络接入，类似于大型3D在线游戏以与互动式社交平台等高带宽应用需求具有了合适的

18、硬件平台。据eNet游戏先锋网统计，2009年第一季度中国的网游市场规模达到55.14亿元，环比增长8.3%。网游产业的巨大发展前景必然带来相关技术的革新，研究大规模在线网络游戏的网络支撑平台具有重要的应用价值。 组播消息分发：大规模网络游戏的用户规模庞大，可以形成万人同时在线甚至十万级别规模。应用程序需要定期分发更新消息来更新应用的状态，如在线游戏中虚拟人物的位置坐标，以与游戏对象所持有的各种游戏参数等信息。目前的C/S模式通过游戏服务器向用户定期分发，当终端用户规模庞大且存在异构接入时将导致较长的队列等待，使得游戏延时较大甚至不能响应，降低了用户体验质量。本研究提出的分层P2P组播分发技术

19、利用用户自组织成的分层P2P网络进行游戏中的参数信息分发，无需服务器介入，降低了部署成本。同时相对纯分布式的组播分发，具有较短的分发延时和冗余附加开销，改善网游支撑平台的服务质量。综上所述，本文的研究成果可应用于大规模P2P网络以与宽带无线网络中的面向业务特征的底层业务服务平台构造以与海量数据分发。本文将以基于gossip的P2P服务网络的构建与相关技术作为研究的应用背景，拟通过本文的理论分析与创新思想指导设计实现一种基于gossip机制的P2P基础网络服务平台，并在该服务平台上实现相应的海量信息分发，以期推动在P2P网络与相关技术的发展。同时本文的成果也将为基于gossip机制的P2P网络中

20、的分布式拓扑管理、负载均衡的节点选择、分层拓扑构造、分层拓扑中的组播数据分发等关键技术提供了应用支撑。随着将来研究的进一步深入，这些理论成果将逐步应用到P2P网络的具体实践中，具有重要的研究意义和应用价值。1.3 国外研究现状（要求：国外达到的水平，已取得的主要进展与存在的问题与不足。对国外有关研究现状进行分析和文献综述，提出并明确需要研究的主要问题。）基于gossip机制的协议9（也称为epidemic协议）利用流言在人群中传播的特点进行信息传播，具有简单可靠，灵活性高的特点（gossip过程见图1.2.1）。1987年，Alan19等人第一次将gossip技术应用于数据库站点的复制中，使得

21、gossip技术在分布式网络应用中得到成功的推广。2008年，Alberto在文献11中指出，目前学术界18对于gossip的定义不明确，或宽泛（任何基于消息的协议都纳入gossip畴），或狭隘（针对某个应用的gossip解决方案）。如果不考虑任何特定细节简单来讲，gossip协议中每个gossip节点持有一个邻居表集合，包含全部或部分的P2P节点。每个gossip节点定期从自己的邻居集合中选择一个或若干个随机节点进行连接，然后二者进行数据的交换。根据gossip协议理论的权威人士Guerraoui与Kermarrec等的分析9，这样的信息交换方式使得任意节点很容易以较高概率将信息分发到全网围

22、。如果在上述信息交换方式中节点交换的是各自的邻居集合中的邻居节点信息，则在一次gossip交换过程后，节点将会接收其他节点的邻居信息，并更新自己的邻居表。通过这种持续的gossip交换过程，P2P网络的拓扑演化成为一个动态变化的拓扑，演化规律以与最终形成的拓扑形成与gossip过程中的具体实现细节有关8。可见gossip通信需要具备以下特点：1）节点的选择需要具有随机性或部分随机性，不能总是选择同一个节点；2）节点仅仅了解本地拓扑信息；3）通信方式是周期性的。图1.2.1 gossip过程的示意图这使得基于gossip协议的P2P网络具有以下优点8：1）可扩展性与弹性：gossip协议的可扩展

23、性来自于协议的执行流程依赖于每个节点在相对固定的时间间隔后执行一组固定的操作。每个节点不需要任何中心化的节点进行控制与管理，不存在中心管理单元的管理压力，系统规模可以自由扩展。整个P2P网络的资源与全局负载成比例关系，当节点给网络带来负载时也向网络在贡献自身的资源。网络规模增大的同时，资源与负载都在增加，表现出良好的弹性。2）鲁棒性与容错性：gossip协议中没有中心化的控制管理单元，单个节点失效不会对全网造成影响。持续的gossip过程产生了一个随时间变化的动态拓扑。失效的节点与链路会在交换邻居节点信息的过程中被探测到并自动丢弃，新加入的节点通过交换邻居信息可以快速获取到全网围的节点信息。单

24、个节点的拓扑信息将被多个邻居持有并在全网进行分发扩散，具有冗余特性。这种持续的动态成员关系使得基于gossip的P2P网络可以有效抵御节点失效与网络扰动。3）自组织与自管理：由于没有中心化管理单元，全网的组织管理为分布式的管理控制，通过控制每个节点的gossip过程中目标gossip节点的选择、发送邻居策略以与最终的邻居表更新策略可以实现不同特性的拓扑结构，使得全网可以自组织的成为具有某个特性的拓扑，并采用分布式的管理方式对拓扑进行管理控制。Gossip协议在P2P网络方面具有多项应用11，如节点采样服务12作为一种基本的服务可以为其他的各类gossip应用提供一个全局的节点选择方式；分布式的

25、全局参数聚集13利用gossip协议可以将每个节点的某个参数做聚集函数（平均，极值，方差等）运算，使得每个节点可以感知全局的参数信息；负载均衡的数据迁移策略11可以帮助过载节点将负载数据迁移到未过载节点上；基于特征值的分组排序算法14根据节点的特征值（如带宽、存等资源）将节点分成若干集合供上层应用程序使用；分布式的拓扑管理协议15采用偏好排序的方式构造结构化或具有一定特征的拓扑。本文研究基于大规模P2P网络信息服务平台的应用，着重研究拓扑管理、分层拓扑构造与组播信息分发三个方面。下面分别从这三个方面进行阐述：1.3.1 基于gossip的P2P网络拓扑管理技术拓扑管理技术是对整个网络的成员关系

26、进行管理与控制，使得成员关系达到某种预定结果。一般拓扑管理不直接针对某类应用，而是为上层的其他应用提供服务支撑。例如拓扑管理作为服务提供给上层应用的基本功能是节点选择服务。即通过对成员关系的管理控制，为上层应用提供合适的节点，供上层应用使用。拓扑管理作为一种基础的P2P网络服务，是当前P2P网络领域的热点研究问题之一，下面从具体的拓扑管理过程与管理控制结果来进行阐述。1.3.1.1 拓扑管理大规模P2P网络中的拓扑管理技术分为两大类：基于随机游走方式的拓扑管理与基于gossip方式的拓扑管理。基于gossip的拓扑管理主要包含拓扑维护与节点选择两个方面的技术。拓扑维护主要实现对拓扑的管理控制，

27、保证拓扑在动态的P2P环境中具有抗扰动、容错等特性；节点选择主要是面向上层应用提供满足应用需求的节点选择服务。图1.3.2 拓扑管理技术分类示意图2003年，Spyros和Marteen20提出了一种在大规模P2P网络中基于gossip的路由表管理算法。该方法是一种单目标的随机成员管理方式，即利用gossip进行成员关系的交换：每隔一个固定的时间间隔节点便从自己的邻居表中随机选择一个目标gossip节点，然后将自身的邻居表中的邻居地址信息全部发给目标gossip节点，同时也从目标gossip节点处接收其返回的邻居成员地址信息，最后保留最新的c（c为邻居表大小）个邻居地址信息，并删除其余的节点地

28、址信息。通过这种成员关系的管理来收集全局围的节点地址信息。然后根据节点ID的取值围对收集的节点地址信息进行筛选，并将筛选结果通过随机选择的方式置入路由表中的相应项。该方法通过动态改变P2P网络的成员关系，实现了一个鲁棒的连接拓扑，可以有效抵御网络扰动，并且具有高可扩展性。但是该方法也存在不足：节点使用基于时间戳的更新方式对邻居表进行更新，对于新加入到网络中的节点，从全局围考虑，其地址信息在网络中只有少量拷贝，将以较低概率被选为服务节点提供给上层应用，难以有效平衡网络负载24，即最终筛选出的路由表项可能是“热点”，引起P2P网络的负载不均衡。同样在2003年，Ganesh与Kermarrec等人

29、提出了一种多目标的成员管理协议SCAMP21。该方法认为邻居表的大小是一个动态变化的值，随网络规模增大而增大，只要可以保证定义了一个参数c用于决定每次gossip过程中选择重复给目标节点进行邻居信息交换。当一个节点s需要加入到网络中时，它会首先找到一个contact节点并发送加入的消息，然后contact节点将向自己的邻居表中每个邻居节点转发加入消息。为了保证s的加入过程的可靠性，contact节点会从邻居表中随机选择c个对象重复转发加入消息。而收到加入消息的节点将以概率p保留s在自己的邻居表中或将消息继续转发。这种针对多目标发送gossip消息的成员管理方式具有高可靠性，但是也带来了冗余数据

30、的转发。SCAMP本质上是在构造一个随机拓扑连接，由于是多目标的gossip过程，需要有良好的时间同步机制与时间间隔控制机制来避免gossip过程的异步与大量冗余数据转发导致的网络拥塞，使得SCAMP的控制比较复杂，不易于在大规模P2P网络环境中进行部署。2004年，Angelos等人提出了PROOFS22，PROOFS也是一种单目标的随机成员管理方式，即在用户终端之间构造了一个随时间变化的随机连接覆盖网络，以此平衡对网络中“热点”对象的搜索请求负载。PROOFS构造的随机拓扑为有向图拓扑，在一次shuffle（随机重连）过程中，节点首先从邻居表中选择一个大小为c的邻居子集V，然后从V中选择一

31、个邻居S作为shuffle对象，向这个邻居S发起连接，并将V发给S，同时接收来自S的邻居子集，最后从自身的邻居集合中删除V，并接受来自S的邻居子集。在shuffle过程完毕后，S将源节点作为自己的邻居节点。该方法通过构造随机连接降低了网络局部对“热点”对象的访问频次，提高了鲁棒性，具有负载均衡的特性。但是该方法也存在不足：即Angelos假设用户终端为同构性质的终端，但实际P2P网络中的用户终端多为异构终端，而随机选择的节点本身不一定能担任搜索请求转发的任务。即对“热点”对象的负载访问虽然可以转移，但转移的目标节点具有盲目性，导致搜索转发任务不能正常完成。2005年，Spyros在PROOFS

32、的工作上做出了改进，提出了CYCLON23，CYCLON作为一种无结构P2P网络的拓扑管理协议，主要在PROOFS的基础上对节点的描述加入了时间戳属性，当进行shuffle过程的目标节点选择时，CYCLON不是随机选择而是选择时间戳最大的节点。由于时间戳较大的节点是那些已长时间存在于网络中的节点，此时可能已经成为失效节点。故这样可以加快对失效节点的检测，使得从网络中尽早删除失效节点以与指向失效节点的连接。通过实验证明，CYCLON在节点入度的均匀分布程度与删除失效节点以与指向失效节点的连接等方面均优于PROOFS。但是CYCLON在进行邻居子集的选择时仍然采用的是PROOFS那种随机选择的方式

33、，对于异构的P2P网络而言仍然具有盲目性，难以实现良好的负载均衡。同时基于时间戳的选择方式与20存在同样的缺陷，即导致全网中新加入节点的地址信息拷贝较少，降低了新加入节点去平衡负载的可能性。2007年，Mark等人24在权威期刊TOCS（IF3，被引177次）上提出了一种拓扑管理的服务框架模型，明确将拓扑管理分为拓扑维护与节点选择（peer sampling）两部分。并使用实验对基于gossip模式的拓扑管理进行了详尽的分析。模型中定义了gossip过程中的两个关键参数H，S；针对这两个参数的不同选择将会导致不同的结果：参数H本质上是基于时间戳原则对邻居表进行更新，H值越大，则将从邻居表中删除

34、更多的时间戳较大的节点信息，这有助于从网络中删除失效节点以与指向失效节点的连接，以实现对网络的快速修复，使得P2P覆盖网络具有较好的容错性；参数S则是控制两个节点在gossip过程的邻居交换长度，S越大，则使得一次gossip过程中邻居表的更新程度更高，拓扑的随机性更好，具有更好的负载均衡特性25。在节点选择模块中，Mark等人提出的是一种随机选择服务节点的方式向上层应用提供服务，认为随机性选择的节点不易产生热点集中的现象，可以均衡上层应用的负载。但该文章提出的服务框架模型仍然存在一些问题：虽然在拓扑维护模块中结合了基于时间戳与基于随机方式进行邻居成员的关系管理，但不能针对网络中那些轻负载节点

35、的信息作出有针对性的快速传播与扩散，使得负载较轻的节点信息被快速扩散用于给上层应用提供服务。同时节点的选择基于随机方式，存在与前述2223同样的问题，即被选节点不一定能满足上层应用的服务需求。同年，Neils等人提出了ARRG26，一种在真实网络环境中的运行的gossip协议。作者认为以前的工作没有考虑真实网络环境中诸如防火墙、NAT地址转换等问题，另外Mark24等的工作认为一次gossip过程中节点发送信息与接收目标gossip节点的信息是一个不可拆分的原子过程，而在真实网络环境中存在网络延时与丢包，gossip过程不可能是一个原子过程，这使得gossip协议仅仅停留在模拟实验层次上。AR

36、RG采用了Fallback缓存策略来改进真实网络环境中的网络连通性问题。每进行一次成功的gossip信息交换过程，节点就将可以成功建立连接的目标gossip节点存入Fallback缓存，这样Fallback缓存中存储的节点地址信息都是可以连通的节点。当在其他的gossip过程中遇到不可连通的节点，就从Fallback缓存中取出一个节点替代当前节点重新建立gossip连接。由于Fallback缓存中的节点是可以连通的节点，所以采用Fallback缓存可以提高可靠性，增强ARRG协议的鲁棒性。但ARRG仍然采用随机方式进行目标gossip节点的选择以与邻居表的更新策略，虽然加入了Fallback缓

37、存用于解决容错，但本质上没有考虑上层应用的负载均衡需求，来进行拓扑的维护与节点选择。2009年，Elth等人提出了Eddy27，Eddy作为一种基于gossip的拓扑管理协议可以最小化选择出的节点序列之间的时间关联性与空间关联性，以此来改进每个节点地址信息在全网围的均衡分布。Eddy在节点加入过程中采用了类似SCAMP的做法，收到加入消息的节点会将消息转发，直至消息的TTL值为0，则新节点被最后一个收到加入消息的节点置入自己的邻居表中。在交换邻居信息的gossip过程中，Eddy无论发送邻居信息与更新邻居表均采用的是随机方式，其最终目的在于维持一个随机均匀的节点地址信息分布。但Eddy加入了一

38、种邻居表大小平衡机制，即通过比较自身邻居表与源gossip节点的邻居表大小来决定向源gossip节点发送多少个邻居地址信息条目。虽然Eddy的一系列改进通过模拟实验证明了可以起到平衡节点地址信息拷贝个数在全网围的均衡分布，但Eddy本质上还是一种基于随机gossip的拓扑管理方式，通过Eddy选择的节点不一定能满足上层应用需求，并达到负载均衡的效果。与gossip方式相对的一类协议是是基于随机游走（Random Walk）的协议。2009年Daniel等提出了MRWB28，一种基于随机游走的节点选择策略。MRWB认为在动态的无结构P2P系统中进行服务节点的选择存在明显的偏向性，容易引起“热点”

39、的产生。MRWB将网络看作一个具有时间索引特征的图，设定一个动态变化的时间窗口，然后在时间窗口随机选择节点。这种随机选择的方式与上述的gossip方式一样，不能根据应用需求做出恰当的节点选择。同年，符永铨等人29提出了SMARW，一种可扩展的无偏随机游走节点选择算法。SMARW通过考察相邻节点之间的消息转发比例与节点度来确定消息的转发是否继续进行，当消息不再转发时，消息停留的节点就是最终被选择的节点。SMARW可以实现大规模无结构P2P网络的无偏采样选择，并且可以均衡消息转发所产生的负载开销。但是SMARW是基于静态拓扑实现的节点选择方式，不能适应负载动态变化的网络环境，同时基于无偏的选择也不

40、能为上层应用提供合适的节点选择服务。另外基于随机游走的拓扑管理在抖动性较强的网络环境中普遍存在收敛时间过长的问题，影响了节点选择的服务质量。另外Vishnumurthy30等人在2006年提出了一种针对无结构化异构P2P网络的拓扑管理方法，该方法定义了一个关键参数：用户的期望负载。用于调节网络异构性产生的负载不均衡现象。具体为构造随机图时不是构造常数度的随机图，而是节点根据自身的期望负载选择与多少个随机节点建立连接，能力强的节点可以连接较多的邻居以形成较大的连接出度。这种非常数度的连接方式对负载起到了一种均衡的作用。但最终形成的拓扑是一种静态的随机拓扑，不能很好的对大规模P2P网络的变化以与抖

41、动做出自适应的改变。而在2005年Ming31等人提出了一种无结构P2P环境中的非均匀的随机拓扑管理策略，是一种偏好性的拓扑管理策略。作者认为在很多应用场景中采用偏好的节点选择使得P2P网络的服务更加高效，并将提出的方法应用于在DHT网络中进行距离偏好的节点选择，节点选择充分考虑了节点之间的延时，将选择延时较小的节点作为服务节点。但是该方法没有考虑大规模P2P网络存在较强的扰动特性，根据Chawathe 7的观点，随机游走在在扰动性较强的网络环境中需要重新构建游走路径，导致收敛时间较长，不适合动态的网络环境。综上所述：传统的P2P网络中的拓扑管理技术存在盲目进行节点选择导致选择的服务节点不能满

42、足上层应用的现象。问题在于采用随机方式选择目标gossip节点以与需要交换的邻居节点信息，以构建一个随机化的拓扑结构来提高网络的鲁棒性，避免出现“热点”发生。但该方法没有没有考虑节点的服务能力与负载承受状况，也忽略了节点的实时负载随时间变化的特性，在负载持续增加时导致20%-30%的服务节点选择不能满足上层应用需求，增加了重新进行节点选择的几率与成本，降低了P2P网络的性能。需要一种负载均衡的拓扑管理服务来为P2P网路的上层应用提供合适的节点选择，保证上层应用的正常运行。1.3.1.2 负载均衡程度的评价方法判断一个P2P网络的负载均衡程度，可以帮助网络管理员了解网络的运行状态，以便在负载不均

43、衡导致网络性能严重下降的情况下介入并监管网络，使其可以稳定运行来保证服务质量。Vishnumurthy30在2006年的INFOCOM会议中描述了负载分布的状态图，指出了负载的分布具有正态分布的特性，即大部分节点的负载位于一个合适的负载围，而承受极少与极多负载的节点是少数。但他没有提出一种衡量负载均衡程度的方法来对P2P网络的负载分布的均衡性做出客观评价。2004年-2007年，gossip通信领域的权威人士Voulgaris23、Jelasity24与Ogston27分别使用节点入度方差来衡量网络的负载均衡程度。节点入度代表一个覆盖网络中这个节点被多少节点置入自己的邻居表中，从而知道这个节点

44、的存在。在进行节点选择时入度高的节点被选为服务节点的概率较高。所以P2P网络中的节点入度方差表征了所有节点被选择为服务节点概率的差异性。这种差异性在一定程度上反映了网络节点可以承受负载的差异性。但存在以下问题：1）节点可以承受负载的能力（节点入度）不等同于节点已经承受的负载，负载均衡程度的衡量应该将节点实际承受的负载纳入考量围；2）P2P网络是一个异构的覆盖网络，节点之间具有不同的硬件配置资源与接入带宽，不同的节点也就具有了不同的服务能力，如果按照一个统一标准要求每个节点都承受一样的负载，可能导致对于服务能力较弱的节点来说负载过重，对于服务能力较强的节点负载过轻，这并不是一种真正的负载均衡。3

45、）仅仅按照连接度来描述负载的分配是不精确的，因为当前的P2P网络多提供尽力而为的服务模式82。当一个节点作为服务节点为其他多个节点提供服务时，其他节点施加的负载并不是均匀的。如果采用基于节点入度的评价，则可以认为每个“度”给节点带来的不一定是一样的负载，这使得基于连接个数的衡量方式不能准确描述网络中的负载分布。综上所述：现有的P2P网络负载均衡程度的评价方法存在粗略不精确的现象，问题在于传统评价方法采用节点入度表示节点被选择作为服务节点的机率，将所有节点的入度方差作为描述网络整体负载均衡程度的指标。该方法忽略了P2P网络中节点自有的异构特性与实际环境中节点实时负载变化的因素，欠缺合理性与精确性

46、，故节点入度方差不适合作为P2P网络负载均衡程度的评价指标。需要一种精确客观的负载均衡量化方法来衡量实际应用中的网络负载，以帮助网络管理员对P2P网络的负载分布作出客观的评价。1.3.2 基于gossip的分层P2P拓扑构造技术在纯粹平坦式（flat）的大规模无结构化P2P网络中，由于节点地理位置分布的不均衡性和节点能力的异构性导致节点之间可能存在较大的延时以与弱能力节点不能满足应用需求的问题，因此造成了在平坦式的无结构化P2P网络上运行的如文件共享、流媒体传输、即时通讯等应用的效率下降。为了解决该问题，国外学者提出了一系列构造分层P2P拓扑的技术来改进平坦式拓扑结构的不足。分层P2P拓扑构造

47、技术的分类图如图1.4所示。图1.3.3：分层P2P拓扑构造技术分类图现有的分层P2P拓扑构造技术主要分为以下几类：2002年，Gnutella协议开发组推出Gnutella协议0.6版82，在这个版本中提出Ultrapeer与leafpeer的概念，即超级节点与叶节点。协议将网络分为二层结构，上层为超级节点通过随机方式连接构成，下层为叶节点，叶节点只维持对少量超级节点的连接。超级节点将作为叶节点的代理服务器帮助叶节点完成诸如查询请求转发以与消息处理等工作。这种结构考虑到了节点之间存在的异构性特点，有效提高了Gnutella网络的灵活性，降低了消息处理与路由过程中参与的节点个数以与节点之间传输

48、数据的流量，提高了网络的性能。但是该方法也存在明显的不足，对于超级节点的选择通过预先定义的节点带宽阈值进行选择，使得超级节点的选择缺乏灵活性，当网络带宽存在物理升级与变化，难以控制超级节点所占比例；超级节点不能实现与叶节点的灵活角色互换，导致不能适应动态的网络环境变化。2003年，Yatin等人提出了GIA7，一种基于无结构P2P模型Gnutella而改进的分层P2P拓扑。GIA用于解决并发查询给节点带来的负载过重的问题。在进行超级节点的选择时，GIA将网络中节点可以处理查询请求的速率作为超级节点选择的指标，认为网络中的节点按照处理查询请求速率进行划分具有几个不同级别，高于1000x速率的节点即为超级节点。这种方法源自固定阈值划分，即将节点按照某种能力划分为若干级别，达到一定级别的可视为超级节点，方法简单有效。但是该方法不具有自适应性。需要预先对级别做出定