非结构化对等网络Gnutella搜索机制的改进

非结构化对等网络Gnutella搜索机制的改进张谢华1,2李士峰3（1徐州师范大学现代教育技术中心,江苏徐州221116）（2中国矿业大学信电学院,江苏徐州221008）（3中国矿业大学出版社,江苏徐州221008）摘要：本文介绍了非结构化对等网络Gnutella搜索机制的工作原理，分析其带来的可扩展性问题，提出一种动态拓扑调整的改进策略。仿真实验表明，该策略能够有效降低网络资源的消耗，优化节点间的负载均衡，进而提高网络的可扩展性和资源搜索效率。关键词：非结构化对等网络；Gnutella；搜索机制；拓扑调整InprovmentonGnutellaSearchingMechanisminUnstructedPeer-to-PeerNetworkZhangXiehua（MordenEducationTechnologyCenter，XuZhouNormalUniv，XuZhou，JiangSu，221116）Abstract:ThesearchingmechanismofGnutellaunstructedpeer-to-peernetworkanditsworkingprincipleareintroduced.Byanalyzingitspoorscalabilityproblem,thispaperproposesanewpolicywhichisusedtodynamicallyadjustthenetworktopology.Thesimulationresultsshowthatthepolicycaneffectivelyreducethenetworkresourcesconsumptionandoptimizetheload-balancebetweenpeers,andthenimprovethescalabilityofGnutellanetworkandtheefficiencyofresourcessearch.Keywords:unstructedPeer-to-PeerNetwork;Gnutella;searchingmechanism;topologyadjusting1引言构建高效的资源搜索机制是对等网络（Peer-to-Peer，P2P）研究的一个核心问题。Guntella网络作为非结构化P2P的一个典型代表，它利用洪泛（flooding）机制来搜索网络资源。该搜索机制算法灵活、网络维护代价较小且能够很好地适应节点高度动态的P2P环境，一直以来受到了广泛的关注。但随着网络规模的扩大，它造成了网络流量的急剧增加，导致一部分网络节点负载过重而失效，严重影响了网络的可扩展性和搜索查询的服务质量。本文在分析其缺陷的基础上，提出一种动态拓扑调整的改进策略，能够有效降低网络资源的消耗、优化节点间的负载均衡，进而提高网络的可扩展性和资源搜索的效率。2Gnutella网络搜索机制Gnutella网络中每一台联网的计算机既是客户机又是服务器，因此被称为对等机。资源搜索通过在对等机间扩散消息得以实现。而对等机间的通信遵循一种工作于TCP协议或PPP协议之上的应用层协议。该协议主要由一组消息集和相应的通信规则集组成。消息集中的Ping消息和Pong消息用于确认Guntella网络中对等机间的相邻连接，一个收到Ping消息的对等机会响应一个或多个Pong消息，其中包括本机地址和能提供的共享信息；Query消息和QueryHit消息用于实现资源的搜索查询，Query消息包含搜索请求、指明搜索内容是关键字或是文件，如果对等机本地的共享信息与其收到的Query搜索内容匹配，将会返回一个QueryHit消息，其中包括本机地址、端口号、传输速度、结果集及对等机标识符等；Push消息提供一种机制允许处于防火墙后的对等机向网络提供文件数据共享。对等机遵循的主要通信规则如表1所示。Gnutella网络中进行资源搜索的工作原理[1]：一台对等机通过访问某特殊站点提供的主机缓存服务，获得一台活动对等机地址并与之建立连接，加入到Gnutella网络，接着它通过Ping、Pong消息确定更多相邻对等机。当需要进行资源搜索时，向所有活动的相邻对等机都发送一个Query消息，其他对等机在接收到该消息后，根据情况决定是否返回一个QueryHit消息。无论本地是否存在符合查询请求的内容，其他对等机都会继续转发该查询消息，直到消息的TTL（TimeofLife）值减为0。一旦定位了响应对等机，将与之建立TCP连接并通过HTTP协议下载文件。表1Gnutella网络中的通信规则CommunicationrulesintheGnutellanetwork规则类型描述广播对等机自身产生的消息,将向其所有相邻对等机进行广播转发每个对等机会向除消息来源之外的所有相邻对等机转发接收到的消息（如Ping、Pong、Query、QueryHit等）丢弃在进行消息转发之前，首先检查其是否先前已经被处理过，如果是，就丢弃该消息不再进行转发；否则，将消息的TTL值减1，Hops值加1。一旦TTL值变成了0，则丢弃该消息响应应答消息仅能沿转发对应广播消息的源路径被发送返回，保证只有那些转发了广播消息的对等机才能看见应答消息3网络可扩展性问题扩散消息的洪泛机制使查询衍生到一定半径范围内的所有邻居。在网络规模不断扩大的情况下，网络中的消息按指数级进行增长，这些消息将极大耗费节点的处理时间吞噬网络带宽。因此针对有限的网络资源和无限的消息增长而言，必然会导致网络的过载和拥塞。而目前P2P网络中各节点在带宽处理能力等方面存在明显的差异，许多资源有限的节点难以承担更多的网络负载，节点用户被迫主动退出网络。当这部分节点因失效不能提供连通服务时，整个网络被隔离分片，这使得Gnutella网络的可扩展性和服务质量都受到了极大的影响。结合网络拓扑结构来进一步分析可扩展性问题。在高度动态的Gnutella网络环境下[2]，节点可以随时加入和离开网络，节点间的邻居连接并不固定和可靠，网络拓扑构造具有随意性。为了确认节点间的邻居关系，节点加入Gnutella网络后必须定期广播发送Ping消息给所有邻居和返回相应的Pong消息，从而保证有效的网络连接。随着网络中节点数量的不断增多，网络中的Ping消息和Pong消息将会随节点间连接的增加呈指数级增长。同时由于这种随意自由的拓扑连接，使得数据查询必须依靠广播扩散的搜索来完成，因而更多节点的加入会使网络产生更多的查询请求，所以广播转发的Query消息数量也将急剧增长。另外由于节点间存在复杂的邻居关系，造成网络中存在着大量重复转发的冗余消息。网络流量过大，网络节点负载过重。因此，系统的可扩展性受到了严重的限制。4动态拓扑调整的改进策略4.1基本思想由上述分析可知，洪泛机制下对等机任意选择邻居构建拓扑连接且将消息无限制地广播扩散到所有邻居节点的做法，造成网络过载和节点负载不均衡，引起较为严重的网络可扩展性问题。因而我们在充分考虑网络动态性和节点异构性的情况下，提出动态拓扑调整的改进策略[3]。根据节点所拥有的资源能力及时调整节点间的拓扑连接，使得查询向具有丰富资源的节点转发，节点可以自组织为相对有效的网络来解决可扩展性问题。简洁起见，本文将节点拥有的资源转换为在时间间隔T内最多能够连接的邻居节点个数（“度”数）。如果邻居节点的个数超过了资源限制，则调整节点间的连接关系。为了合理地加以调整，可以从Gnutella网络具有“幂规律”特性[4]的拓扑结构分布中得到启发。选择保留“度”数较高的邻居节点而重定向那些“度”数较低的邻居节点的邻居关系。因为“度”数较高的节点同其他节点的联系比较多，表明它们是稳定的而且资源比较丰富，查询消息到达较高聚集度的节点，就相当于遍历了较大范围的节点共享信息，从而获得较好的查询效率。把“度”数较低的邻居节点重定向给其他具有高空闲资源的邻居，能够减小过载节点的负载，如果找不到恰当的邻居节点，也就是说其他邻居节点的负载都接近其所拥有的资源，则直接断开节点与它们的连接。4.2算法描述为了实施动态拓扑调整的改进策略，Gnutella网络中的节点需要保存一个“邻居节点信息”列表（NeighborInformation列表），其作用是记录本节点的邻居节点信息。该列表通过在相邻节点之间周期性地交换消息包来进行刷新，或当对等机有新邻居节点加入时发消息包来进行添加。消息包包括邻居节点“度”数限制和其当前邻居的个数。在此基础之上，接下来具体描述动态拓扑调整的算法步骤：（1）节点n周期性检查自己当前的邻居个数numberneighborn是否超过资源“度”数限制resn。（2）如果过载，节点n尽力改变拓扑连接关系以减少邻居节点的个数。循环选择NeighborInformation列表中“度”数最低的邻居m，进行以下处理：判断节点m是否过载？如果resm-numberneighborm0，则直接断开节点n与m之间的邻居关系，删除节点m，n的NeighborInformation列表中相应信息；否则重定向m的邻居关系，实现以下操作：I、选择当前除m之外具有最高空闲资源的邻居节点k，即resk-numberneighbork0且值最大的邻居节点，具体做法为：a.求除m之外的各邻居节点的res-numberneighbor值，并得出最大值节点；b.如果这样的节点个数大于1，则判断其中res值最大的节点个数是否大于1。若等于1则它就是节点k；若大于1则取其中与节点m的IP地址最近的节点作为节点k。II、如果存在这样的节点k，则：a.将节点k的相关信息发送给节点m，断开节点n与节点m之间的邻居关系；b.建立节点m，k之间的邻居关系，在各自的NeighborInformation列表中添加相应信息。III、如果不存在具有空闲资源的邻居节点，则直接断开节点n与m之间的邻居关系。4.3算法实例分析设有节点i，资源限制可最多连接3个邻居，实际当前连接的邻居个数为5，即有resi=3，degreei=5。其邻居节点信息列表的内容为：neighborn1n2n3n4n5degree52324numberneighbor43224经过拓扑调整后内容修改为：neighborn1n3n5degree534numberneighbor524图1为采用该策略调整前后的节点拓扑。(a)拓扑调整前（b）拓扑调整后图1拓扑连接图5改进策略性能仿真和分析本文采用网络仿真软件NS2（NetworkSimulator2）[5]来模拟改进前后Gnutella网络的搜索过程。针对网络中每个节点所拥有的资源不同，模拟了5种等级的节点，分别为T1线路接入节点、专线接入节点、ADSL接入节点、LAN接入节点以及电话拨号接入节点。仿真拓扑规模分别为100、250、500、750、1000、1250，每种拓扑规模下都对改进前后的情形进行模拟，并采用搜索资源的查询响应时间为指标对其性能进行了具体分析，如图2所示。图2改进前后查询响应时间的比较查询响应时间（ms）节点个数001002505007501000125010203040506070改进后改进前n1n4n3in2n5n1n4n3in2n5由图2可以看出，开始查询响应时间较长，随着节点数目的增加可供使用的资源不断增多，因而查询响应时间相应缩短。但节点数目增加到一定程度后，网络中递增了大量消息，查询响应的过程变缓即查询响应时间又开始延长。采用改进策略之后，网络拓扑的调整使得部分节点减少了一定的邻居连接数量，有效降低了这部分节点的网络消耗，负载处于平衡状态；同时更多的查询被转发给了资源丰富的节点，得到了较快的处理，因而查询响应时间显著下降。6结语本文提出的改进策略基于节点的处理能力进行动态拓扑调整，在出现连接过载的情况下动态调整节点间的网络连接关系，较为理想地改善了Gnutella网络的拓扑结构及节点间的负载平衡，提高了网络的可扩展性和搜索的效率。参考文献：[1]Gnutella[EB/OL].