分布非结构化P2P网络资源定位研究

２００７，４３（６）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用基金项目：国家重点基础研究发展规划（９７３）（ｔｈｅＮａｔｉｏｎａｌＧｒａｎｄＦｕｎｄａｍｅｎｔａｌＲｅｓｅａｒｃｈ９７３ＰｒｏｇｒａｍｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．２００４ＣＢ３１８００３）。

作者简介：李运娣，硕士研究生，研究方向：计算机网络与分布式系统；冯勇，研究员，博士生导师，研究方向：分布式计算与混合计算。

１引言Ｐ２Ｐ（Ｐｅｅｒ－ｔｏ－Ｐｅｅｒ）即对等网技术，近年来随着许多Ｐ２Ｐ系统的成功应用引起了人们对Ｐ２Ｐ技术的研究的热潮。

Ｐ２Ｐ网络是没有任何集中控制的分布式系统，系统中每个结点既是客户机又是服务器，它们在功能上是等同的。

与传统的客户机／服务器模型不同，Ｐ２Ｐ系统中的文件不是存储在集中的服务器上而是存储在分散的终端结点上，文件直接在终端结点间进行传输。

由于文件是在终端节点间分布保存的，并且没有一个集中的索引目录，因此如何有效地对资源进行搜索定位成为Ｐ２Ｐ系统研究的核心问题。

２问题描述及目前研究目前Ｐ２Ｐ系统共有３类模型：非完全分布式的（以Ｎａｐｓｔｅｒ为代表）、分布非结构化的（以Ｇｎｕｔｅｌｌａ）为代表、基于ＤＨＴ的分布结构化的（ＣＡＮ、Ｃｈｏｒｄ等）。

由于分布非结构化系统设计简单，节点的频繁加入和离开对系统的影响比较小，同时支持目前流行的关键字搜索。

因此，将来对于Ｐ２Ｐ大规模的应用来说，改进分布非结构化系统的搜索算法，提高非结构化系统的可扩展性是一个比较好的选择。

分布非结构化网络的典型代表Ｇｎｕｔｅｌｌａ设计思想简单，它采用洪泛式的搜索机制，也就是每个节点在查找的过程中将接收到的请求信息转发到所有的邻居节点。

这种搜索方法只能搜索到源节点周围的一个小范围，并且把请求转发到所有的邻居节点会产生大量的消息，从而吞噬大量的带宽而使得系统极不可扩展。

在文献［２］中提出了迭代深入的方法，它是一种逐步进行的宽度优先搜索。

如果能在比较小的深度中找到满意的结果，就可以减少网络中的消息传播量。

在文献［３］中给出了一种前向学习的方法，在这种方法中建议每个节点包含的元数据可以给出哪个节点可能含有应答信息的隐含信息，依据此隐含信息可以来选择节点转发请求信息。

在文献［５］中提出了Ｇｎｕｔｅｌｌａ具有Ｐｏｗｅｒ－ｌａｗ特性，依据这种特性提出了将请求转发到度数较高的节点，度数较高的节点指向更多的节点，包含了较多的信息。

在文献［６］运用本地索引方法，在这种方法中，每个节点不但可以处理本节点，而且可以处理周围一跳或几跳的节点的信息，减少了请求处理的次数。

根据对以上改进算法的学习，考虑Ｐ２Ｐ网络与神经网络的一些相似性，借鉴反馈神经网络的学习，给出了一种灵活的基于语义路由的前向学习算法。

此算法能动态适应网络变化，提高搜索的效率。

下面对算法进行详细的介绍。

３算法描述由于Ｇｎｕｔｅｌｌａ的应答信息是沿请求路径反向传递的，运用其应答信息来建立路由信息表。

在路由信息表中保存着请求信息与应答节点的对应关系，路由表随着节点不停的转发请求信息和得到应答信息而更新。

根据路由表信息，在查找的过程中来动态调整网络的拓扑结构，使得源请求节点向目标节点靠拢。

也就是在查找的过程中，先依照关键字与应答节点的关系库进行查找，如果找到，就开辟相应的新的连接。

这样，整个网络就成为一个依据请求分布的、动态的、灵活的Ｐ２Ｐ网络。

随着网络的动态调整，使网络中的节点都向着最有利于发现请求分布非结构化Ｐ２Ｐ网络资源定位研究李运娣，冯勇ＬＩＹｕｎ－ｄｉ，ＦＥＮＧＹｏｎｇ中国科学院成都分院计算所自动推理实验室，成都６１００４１ＣｈｅｎｇｄｕＩｎｓｔｉｔｕｔｅｏｆＣｏｍｐｕｔｅＡｐｐｌｉｃａｔｉｏｎＡｃａｄｅｍｉａＳｉｎｉｃａ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｃｈｅｎｇｄｕ６１００４１，ＣｈｉｎａＥ－ｍａｉｌ：ｌｉｙｕｎｄｉ＠ｍａｉｌｓ．ｇｕｃａｓ．ａｃ．ｃｎＬＩＹｕｎ－ｄｉ，ＦＥＮＧＹｏｎｇ．ＳｔｕｄｙｏｆｄａｔａｌｏｃａｔｉｏｎｉｎｕｎｓｔｒｕｃｔｕｒｅｄＰ２Ｐｎｅｔｗｏｒｋｓ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（６）：１５６－１５８．Ａｂｓｔｒａｃｔ：ＴｈｅＰ２Ｐｓｙｓｔｅｍｉｓａｄｉｓｔｒｉｂｕｔｅｄｓｙｓｔｅｍ．ＳｏｈｏｗｔｏｌｏｃａｔｅｔｈｅｒｅｓｏｕｒｃｅｉｓａｎｉｍｐｏｒｔａｎｔｐｒｏｂｌｅｍｉｎｔｈｅＰ２Ｐｎｅｔｗｏｒｋｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｓｔｕｄｙｔｈｅｕｎｓｔｒｕｃｔｕｒｅｄＰ２Ｐｓｙｓｔｅｍｓ’ｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍａｎｄｔｈｅｒｅｌａｔｉｖｅｒｅｓｅａｒｃｈ，ａｎｄｇｉｖｅａｓｅｍａｎｔｉｃａｌｇｏｒｉｔｈｍ．Ａｔｌａｓｔｔｈｅｓｉｍｕｌａｔｉｏｎｉｓｇｉｖｅｎ．Ｋｅｙｗｏｒｄｓ：Ｐ２Ｐ；Ｇｎｕｔｅｌｌａ；ｓｅａｒｃｈｉｎｇｍｅｃｈａｎｉｓｍ；ｓｃａｌａｂｉｌｉｔｙ摘要：Ｐ２Ｐ系统是一个分布式系统，其中的资源如何进行定位是一个重要的问题。

通过对分布非结构化Ｐ２Ｐ系统的搜索机制以及现有的改进方法的研究，给出了一种基于语义路由改进算法，并对此算法进行了模拟仿真。

关键词：Ｐ２Ｐ；Ｇｎｕｔｅｌｌａ；搜索机制；可扩展性文章编号：１００２－８３３１（２００７）０６－０１５６－０３文献标识码：Ａ中图分类号：ＴＰ３９３１５６２００７，４３（６）标记（ｍａｒｋ）０１…０节点信息Ｇｎ１ＩＰＧｎ２ＩＰ…ＧｎｋＩＰ关键字ｋｅｙｗｏｒｄｓ１…ｋｅｙｗｏｒｄｓｋｋｅｙｗｏｒｄｓ１…ｋｅｙｗｏｒｄｓｋ………ｋｅｙｗｏｒｄｓ１…ｋｅｙｗｏｒｄｓｋ表１本地路由信息表结果的节点靠近。

因此，如果初次路由失败或没找到足够的结果，将按迭代深度优先的策略进行查找，以便能在较小的几跳中找到满意的结果。

３．１路由信息表的建立在算法中，每个节点维护着一个如表１所示的路由表，路由表中存储着请求关键字与节点的联系信息。

其中标记（ｍａｒｋ）信息用来表示该节点最近有没有被访问过，或说该节点最近有没有对请求信息进行了应答，此标记信息是用来作为信息表更新的依据。

在节点信息中保存有节点ＩＤ（Ｇｎｋ节点在Ｇｎｕｔｅｌｌａ网络中的唯一标示符）和ＩＰ信息，此信息可用来开辟新的连接，以便动态的调整网络结构，使得请求节点向有利于目标的节点进行调整。

关键字存储着通过此节点以前访问的相应的请求信息。

在这里运用了前向学习的方法来建立本地的路由信息表，节点根据对以前转发的请求信息的应答情况来建立自己的路由表。

因为Ｇｎｕｔｅｌｌａ中对每个请求，当在网络中的某个节点中找到适合的结果时，该节点就会对源请求节点发送应答信息，并且应答信息是逆着请求信息被转发的路径而反向传递的。

因此，依据这一特性，对每个应答信息，在它被向源请求信息进行转发的路径上的每个节点中记录下请求信息与应答节点的对应关系。

也就是，当一个查找成功时，源请求节点和请求信息成功被应答路径上的所有节点通过在路由信息表中增加请求信息与远程应答节点对应关系来建立路由表。

对于新节点的加入，采用最简单的办法，就是直接根据它加入网络后的邻居节点的信息来建立自己的本地路由信息表。

当一个节点要对某文件进行查找时，节点首先检查自己的路由信息表，在路由表中查找关键字最相接近的节点，然后直接与这些节点建立连接，之后把请求转发到这些节点。

接收到请求信息的节点以同样的方式来转发请求信息。

在路由表中寻找关键字最接近的节点来转发请求信息，这里的关键字最接近是依照匹配度来进行的，把请求转发到匹配度最高的节点。

例如，假定给定这样一个查询，要对关键字Ａ、Ｂ和Ｃ进行查找，如果某个节点中只含有Ａ或只含Ｂ或只含Ｃ则说该节点的匹配度为１，如果含有ＡＢ或ＡＣ或ＢＣ则说节点的匹配度为２，如果同时含有ＡＢＣ则说节点的匹配度为３。

先对本地路由信息表中保存有的关键字进行查找，找到匹配度高的节点来进行查询。

在图１中给出了查找过程。

在查找的过程中，选择了直接开辟连接来进行，这样可以使请求信息根据以前的应答情况跳过一些不大有可能包含有用信息的节点，减少请求信息被转发处理的次数。

请求节点不断的与远程节点建立直接的连接会增加网络中的连接数，但是这些连接是基于过去一段时间内反映请求信息的分布而建立起来的。

这些动态的连接调整，使节点更倾向于向那些网络中比较稳定的和提供信息比较多的节点来建立连接。

这样的网络拓扑结构调整更有利于下一步查询，提高查找的效率。

这样，随着请求的转发，新的连接的建立，网络也会变成一个动态、灵活的Ｐ２Ｐ网络。

３．２负载平衡控制为了避免在请求过程中某些节点由于开辟连接过多而超载，采用文献［９］中的主动流控制（ａｃｔｉｖｅｆｌｏｗｃｏｎｔｒｏｌ）方法来控制请求过程中新连接的开辟。

在此策略中，仅当被请求建立连接的节点根据自己的状态表示愿意从此请求节点接受请求信息时，新的连接才被建立。

为了更好地进行信息流控制，每个节点中都保有一定的流控制令牌（ｆｌｏｗ－ｃｏｎｔｒｏｌｔｏｋｅｎｓ），每个令牌表示节点愿意接受信息这一简单的信息，当一个节点向另一个节点请求建立新的连接时，被请求的节点首先检查自己的流控制令牌，如果仍然有流控制令牌，则允许此次连接的建立，同时令牌个数减１，如果流控制令牌个数为０，则拒绝此次连接的建立。

这样就可以避免节点由于接受了过多的连接而超负载的问题。

节点以它能处理消息的速率产生令牌，如果它收到信息的速率大于它传送信息的速率，过多的请求信息就开始排队等待被处理，如果等待队列过长，节点就会减少令牌的产生速率，从而避免节点由于接收过多的连接而引起负载超荷。

查找过程根据流控制策略也要作相应的修改。

当一个节点向另一个节点的请求被拒绝时，则在路由表中按匹配度依次寻找其它节点来建立连接。

３．３路由信息表的更新与维护在每个节点中保存一定大小的路由信息表，信息表是根据节点的前一段时间的学习来建立的，其更新算法如下：假定Ｌ为路由信息表，对于每个应答信息，在应答路径上的节点的信息表更新算法如下：ｉｆＬ．ｕｓｅｄ＜Ｌ．ｌｅｎｇｔｈ（索引表未满）ｒｅｓｐｏｎｓｅ．ｍｅｓｓａｇｅｉｎｓｅｒｔＬ；ｍａｒｋ＝１；ｅｎｄｉｆｅｌｓｅｉｆＬ．ｕｓｅｄ＝＝Ｌ．ｌｅｎｇｔｈ（索引表已满）ｆｏｒｉｆｒｏｍ１ｔｏＬ．ｌｅｎｇｔｈ（对插入位置进行查找）李运娣，冯勇：分布非结构化Ｐ２Ｐ网络资源定位研究１５７２００７，４３（６）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用［２］ＳｒｉｓｕｒｅｓｈＰ，ＫｕｔｈａｎＪ，ＲｏｓｅｎｂｅｒｇＪ．Ｍｉｄｄｌｅｂｏｘｃｏｍｍｕｎｉｃａｔｉｏｎａｒｃｈｉ－ｔｅｃｔｕｒｅａｎｄｆｒａｍｅｗｏｒｋ，ＲＦＣ３３０３［Ｒ］．２００２－０８．［３］ＲｏｓｅｎｂｅｒｇＪ，ＷｅｉｎｂｅｒｇｅｒＪ，ＨｕｉｔｅｍａＣ．ＲＦＣ３４８９ＳｉｍｐｌｅｔｒａｖｅｒｓａｌｏｆＵｓｅｒＤａｔａｇｒａｍＰｒｏｔｏｃｏｌ（ＵＤＰ）ｔｈｒｏｕｇｈＮｅｔｗｏｒｋＡｄｄｒｅｓｓＴｒａｎｓ－ｌａｔｏｒｓ（ＮＡＴｓ）［Ｓ］．２００３－０３．［４］ＲｏｓｅｎｂｅｒｇＪ，ＭａｈｙＲ，ＨｕｉｔｅｍａＣ．ＴｒａｖｅｒｓａｌＵｓｉｎｇＲｅｌａｙＮＡＴ（ＴＵＲＮ）．Ｉｎｔｅｒｎｅｔ－Ｄｒａｆｔ［Ｓ］．２００５－０９－０９．［５］谢希仁．计算机网络［Ｍ］．４版．北京：电子工业出版社，２００３．［６］ＴｈｅＷｉｎＰｃａｐＴｅａｍｈｏｍｅｐａｇｅ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｗｉｎｐｃａｐ．ｏｒｇ．（上接１２４页）ｉｆｍａｒｋ＝＝０ｒｅｍｏｖｅｔｈｉｓｉｔｅｍｒｅｓｐｏｎｓｅ．ｍｅｓｓａｇｅｉｎｓｅｒｔＬ；ｍａｒｋ＝１；ｅｎｄｉｆｅｎｄｆｏｒｉｆｉ＞Ｌ．ｌｅｎｇｔｈｒｅｓｅｔ；（置所有的ｍａｒｋ位为０）重新查找插入位置；ｅｎｄｉｆｅｎｄｅｅｎｄ算法１路由表更新算法在算法１中，在路由信息表的更新过程中，用ｍａｒｋ位的值来标志信息表中的某项是否被替换，此准则考虑了条目中保存的路由节点最近是否有过应答信息送回。