论文部分内容阅读
一、引言
随着德国媒体集团巨子贝塔斯曼以800万美元的价格收购Napster，以网络自由为己任的“开放源代码运动”（Open Source）与商业公司进行的堂吉诃德似的斗争也告一段落。然而，Napster把一种全新的网络应用模式“对等网络”（Peer-to-Peer Networks，P2P）带入人们的视野，并迅速被人们所接受。
P2P 信息共享技术是一种用于不同PC用户间，不经过中继设备直接交换数据或服务的技术，它允许网络用户直接使用对方的文件，改变了传统的将资源集中放置在服务器端，用户要获得资源，必须先和服务器建立连接，并通过网络传输到本地计算机上的客户机/服务器模式（Client/Server，C/S），消除了中间环节，使内容从“中心”走向“边缘”，避免了C/S 结构固有的性能瓶颈，并使位于网络边缘节点上的信息资源参与共享。 P2P网络拓扑是P2P信息共享技术的基础，它负责合理地组织网络中的节点以及节点上提供共享的信息资源，并在此基础上高效地发送查询请求和查询应答消息，其目的是在保证检索质量的情况下，尽可能减少查询所引发的各种开销。
本文力求寻找一种具有高可伸缩性、低开销的对等网络拓扑，改进算法。
二、常见P2P网络拓扑结构及不足
拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，节点之间的拓扑结构一直是确定系统类型的重要依据。对等网络拓扑构造是目前对等信息共享研究的一个核心问题。以下是四种常见的拓扑结构。
1．单目录服务器型混合式拓扑
混合式拓扑是一种混合了中央服务器结构的对等网络拓扑结构, 在某些文献中也被称为集中索引模型（Central Index Server Model）。在基于此类拓扑结构的系统中，存在一个或多个特殊的被所有节点共知的中央节点——服务器，中央服务器集中管理各种索引并执行检索。拓扑结构如图1。
这种拓扑结构严格来说是C/S模型与P2P模型的混合体。其资源发现和查找过程采用C/S模式，节点间的文件传输则采用P2P模式。由此带来的问题是仍带有集中式的特征，单点故障使系统的容错性很差，一旦出现技术问题，服务器会减速甚至停止服务，同时服务器很容易成为系统的瓶颈，服务器可承受的负载限制了系统扩展。
2．多超级节点型混合式拓扑
针对单目录服务器型混合式拓扑存在的问题，后续的混合式P2P系统作了相应的改进。改进的基本思想都是在增加超级节点的数目的基础上弱化系统中的集中性，同时加强超级节点间的联系，以降低单点故障的危害。拓扑结构如图2所示。
3．全分布式非结构化拓扑
全分布式非结构化拓扑不存在索引服务器，所有用户节点完全对等，结构如图3所示。为了搜索某个文件，查询发出节点会向其邻居列表上的节点发出查询请求并附加该查询的TTL（Time-To-Live）。收到查询消息的节点，首先检查本地资源，看是否有与查询匹配的目标文件。如果有，则发送查询应答消息给查询发起者，如果没有，则转发给邻居节点。不管查询是否成功，只要查询的TTL不为0，接收查询的节点都会将该查询的TTL值减1后，转发给自己邻居列表上的节点。这种转发查询的洪泛机制以消耗相当高的网络带宽为代价，会导致较高的查询成本和较长的响应时间。
4．全分布式结构化拓扑
全分布式结构化拓扑一般都是基于DHT（Distributed Hash Table，分布式哈希表）技术，其共性是每个节点都有一个逻辑地址，新节点在加入时必须获取逻辑地址，这些逻辑地址反映了拓扑结构，路由、拓扑的维护等都是相对于这个逻辑地址而言。全分布式结构化拓扑具有良好的系统可伸缩性，是目前P2P领域研究的热点。因为在全分布式结构化拓扑中，文件存放和消息路由严格受控，所以这类系统都能实现一定程度的高效查找。但这种严格受控的系统也面临一些问题，由于P2P系统固有的动态性，使得这种维护的开销很大。拓扑结构如图4所示。
三、拓扑结构及算法实现
依据全分布式构化拓扑，笔者给出了一个拓扑结构的框架模型，如图5所示。该模型包含资源发布、路由维护、索引维护、数据对象维护、资源检索/定位等功能，将网络中信息资源的提供节点结合在一起，使得在保证系统可伸缩性的前提下，把信息共享覆盖到整个互联网。
1．P-Grid算法的基本思想
P-Grid是由Karl Aberer为首的P-Grid工作组研究给出的P2P系统。它是一种基于虚拟分布式搜索树的P2P系统：每个节点（Peer）只保存整棵树的一部分内容，这种树结构只有通过各个节点间的通信合作才能建立起来。P-Grid的搜索高效、快速，极大地减少了网络带宽，是一个真正的分布式系统，不需要中央协调者。它完全基于随机性的算法和节点间的交互来运作。与其它基于树结构的分布式索引不同，P-Grid节点能在非常不可靠的网络环境中执行搜索/更新操作，并且系统假设节点经常出现故障，节点在线概率低至10%左右。
为了能在没有中央控制的情况下，实现大量节点间的可靠搜索，并且使系统在节点数量上具有良好的伸缩性，P-Grid定义了一种新的数据访问结构。它的基本思想是：节点通过相互间随机的访问，连续不断地分割搜索空间，每个节点均保留足够的信息以便在以后响应搜索请求时与其它节点通信。最终形成的分布式访问结构就称为“P-Grid”（Peer Grid）。
尽管P-Grid算法有上述吸引人的特征，但在P-Grid中，只是沿着搜索树执行定向查找，在每次选择下一跳转发节点时，算法并没有考虑该节点或沿着该节点到达的节点是否真的拥有与查询请求相关的信息，这样的后果有可能直接造成某次查询的失败，而且由于算法没能从失败的查询中“吸取教训”，同样的失败将有可能一直存在，一直重复。另外，对于一次非常成功的查询，算法也不能从中“汲取经验”，这样相同的查询可能会走很多“歪路”，甚至失败，造成搜索效率的下降，增加网络带宽消耗。针对这个问题，本文在P-Grid算法的基础上加以改进，引入反馈机制。
2．基于推荐的P-Grid算法的基本思想
在对P-Grid算法研究的基础上作者给出了基于推荐的P-Grid算法以弥补不足。该算法利用已执行查询的反馈来有效地指导后继查询，是一种基于可靠消息的搜索算法。在算法中，每个节点都保持一个本地索引，索引由每个被请求或转发的数据对象关于每个邻居节点的一个条目（即三元组<数据对象，邻居节点，索引值>）组成。每个条目的值反映了在以后对特定数据对象的请求中，这个节点的邻居节点被选为下一跳转发节点的相对概率。
在转发过程中，一个节点不是随机选择它的下一跳邻居节点，而是使用它的索引值提供的概率，即选择“最好”的节点进行转发。在每一步转发中，节点都把自己的节点标识符添加到查询消息中，并为它们处理过的查询保持软状态。假如来自同一查询的两个转发节点路径相交（比如，由于环的存在，一个节点收到一个副本查询消息），第二个转发节点就被认为是失败结束，副本查询消息被丢弃。
作为反馈的索引值可以从以下两种方法得到：
（1）乐观方法
乐观算法建立在转发节点将成功完成查询请求的假定条件之上：当一个节点向一个或几个邻居节点转发查询时，就增加被选节点的索引值。当查询消息转发终止时，如果成功则任何事情也不用做（因为转发过程中已经增加了索引值），如果失败则沿着转发路径的逆路径修正那些与被请求对象相关的索引值（即转发过程中已经增加的索引值）。利用查询消息中的信息，转发路径上的最后一个节点发一个correct消息给它前面的节点。当这个节点收到correct消息后就减少对最后节点的索引值以反映失败。修正过程一直沿着这个请求的转发路径逆向返回，中间节点减少它们的本地关于下一跳的索引值。最后，发起查询的请求节点减少与这个转发路径相关的邻居节点的索引值。
（2）悲观方法
悲观算法与乐观算法相反：当一个节点向一个或几个邻居节点转发查询时，就减少被选节点的索引值（假设转发节点将失败）。当查询消息转发终止时，如果失败则任何事情也不用做，如果成功则沿着转发路径的逆路径增加那些与被请求对象相关的索引值。
虽然可以采用悲观和乐观两种方法，但在实际应用中，由于各种意外因素，导致查询消息还没结束就在转发途中丢失，这时查询失败，而又无从沿转发路径的逆路径修正索引值，因此，乐观的方法在实际应用中存在困难，所以本文接下来的讨论都针对悲观算法。
为了确定修正值，引入公式：
v（t）=v0 (v0>0, t>0)
其中，v0是当一个节点向一个或几个邻居节点转发查询时，对被选节点的索引值的减少值， t是从一个节点发起查询到得到查询结果之间的延迟，v（t）是查询成功后沿着转发路径的逆路径对相关索引值的增加值。显然,v（t）大于v0，即对索引值的增量大于对索引值的减量，且当t1>t2时v（t2）>v（t1），即对于同一查询的两条成功路径中，延迟小的索引值的增量大。所以，最后关于同一个数据对象的所有条目的索引值呈现：转发成功的（延迟较小）>转发成功的（延迟较大）>没被转发的>转发失败的。这正是算法要达到的效果。 这样，当系统运行一段时间后，每个节点上都保持了已被修正的索引表，这时查询转发将根据索引表提供的信息，选择索引值较高的节点进行，即选择查询延迟较小的路径。可见基于推荐P－Grid算法能通过有效路由减少查询延迟，提高路由性能。
3．基于推荐的P-Grid算法访问结构
定义1 二进制树是n(n≥0)个节点的有限集T，T为空时称为空树，否则它满足如下两个条件：
有且仅有一个特定的称为根(Root)的节点，若n＝1，则二进制树只包含一个Root节点；
其余的节点可分为两个互不相交的子集Tl和T2，其中Tl和T2本身又是一棵二进制树，并称其为根的子树(Subtree)。
在二进制树中，如果某个节点的子树个数为0，则称此节点为叶子节点。
定义2 ?坌p∈P,path (p)=b1…bn,bi∈{0, 1},P为节点集合
系统由N个节点的集合P={p1, …, pN}构成，每个节点都有自己的节点路径。节点路径有最大长度maxlength，根据实际应用情况设定，用于控制二进制搜索树的深度。maxlength反映了整个搜索空间被划分的程度，系统稳定后，整个搜索空间将被划分为2maxlength份。节点路径允许相同，路径相同的节点称为复制节点。
（注：节点路径的下标从1开始。）
每个节点均负责管理一个搜索区间，负责该区间内数据对象的信息，响应针对这些数据对象的检索请求。节点p负责数据对象d的条件是：path(p) 是key(d)的前缀，或key(d)是path(p)的前缀。节点p称为数据对象d的负责节点。而数据对象d有可能由其他节点q提供共享，并不存储在节点p上。节点q称为数据对象d的存储节点。 复制节点负责相同的数据对象。由于复制节点的存在，不会因某些节点的失效造成信息的丢失，从而进一步提高了系统健壮性。
即节点p维护了一张路由表，该表分层记录其他节点的地址。对于第i层路由表Ri中的任一节点r，r的路径和p的路径具有长度为 i的公共前缀，但第i+ 1位的值不同。当搜索请求的前i位和path(p)一致，但第i+1位与path(p)不匹配时，节点p可通过Ri将请求路由到适当的节点。为控制路由表的大小，每层中的最大节点数由参数为了实现层内推荐，提高检索效率，节点p在本地维护一张索引表，索引表和其路由表对应，分层记录数据对象关于各转发节点的索引值。对于第i层索引表Ii中的任一索引(d,r,v)：数据对象d的键值key ( d )和节点p的路径具有长度为 i的公共前缀，但第i + 1位的值不同；节点r为相对应第i层路由表Ri中的节点；索引值v为任一实数。对于一个特定的数据对象只可能向路由表中的某一层转发，所以也只可能出现在索引表中的某一层，而不会是很多层。
4．基于推荐的P-Grid算法的简单模型
图6中的简单例子描述了基于推荐的P-Grid算法的结构。图中包含6个节点，用带数字的圆圈表示，这些节点位于树结构的叶子节点上，用其节点路径（分别是00、01、10、11）来标识。
图6中也描述了查询请求被转发的过程：查询“100”（“100”为要查询的数据对象所对应的二进制标识符）被发送到图中的节点 6，节点 6的路径为“00”，第1位就与key不同，根据路由表的表项可以把请求转发给节点3、4、5。其中节点3和4的路径和“100”匹配，查询结束。节点5的路径为“11”，和“100”有一位相同，但第2位不同，根据路由表表项又将请求转发给节点4，查询结束。 假设只有节点4上负责了“100”，初始值全为1.0，并取修正公式中的v0为0.3，表2显示了查询“100”前后的索引值的变化。
由此可见，基于推荐的P-Grid算法访问结构中，搜索沿二进制搜索树从根到叶子执行定向查找的同时，在树的同一层上又执行基于层内推荐的可靠消息路由，这种“双保险”机制使得搜索成功率、搜索响应时间得到更进一步的保证。
四、总结和展望
近年来，人们对P2P网络中的拓扑结构进行了不断的探索和研究，本文在现有P-Grid系统算法的基础上加以改进，利用反馈来有效地指导后继查询，节约了大量的时间和带宽资源。总的来说，本文基本达到了预期的目标，找到了一种具有较高可伸缩性、较低开销的对等网络拓扑结构及更加快捷的搜索算法。随着网络技术的日益成熟，研究的不断深入，P2P网络模式必将发挥越发重要的作用，而对等网络的拓扑结构，版权问题，安全问题等也将得到有效的解决。
[参考文献]
［1］Karl Aberer, Manfred Hauswirth. Peer-to-peer Information Systems: Concepts and Models, State-of-the-art, and Future Systems. 18th International Conference on Data Engineering, San Jose, California, 2002.
［2］刘晓红，邱力戈.对等网络运营模式探讨[J].通讯世界，2001,(9).
［3］余智华，陆天波等.P2P技术与信息安全[J].信息技术快报，2004,(3).
［4］周宁.信息组织[M].武汉：武汉大学出版社，2001,(5).
［5］刘继光，陈立伟.一种基于DHT的P2P搜索方法[J].微计算机信息，2006,22（3）.
［6］黄宏斌，杨光，秦振.一种分布式信息资源定位机制的研究[J].计算机工程，2006,32（6）.
［7］汪维华，汪维清. 一种P2P网络信息分类检索模型研究[J].计算机工程与设计, 2007,(4).
［8］王平根，刘勇，周脚根. 基于蚁群算法的P2P网络路由[J].广西师范大学学报(自然科学版), 2007,(02).
[作者简介]
方玉田，浙江广播电视大学现代教育技术中心。
ON P2P Topology Frame and Algorithm
Fang Yutian
（Modern Education Technology Center of Zhejiang Radio & TV University, Hangzhou Zhejiang 310012）
【Abstract】 Nowadays, the brand-new network mode of “peer-to-peer general acceptance of information sharing” is attracting people’s attention. The paper aims to find a more flexible, speedy peer to peer network topology frame on the basis of the traditional common one, and to improve algorithm.
【Keywords】 P2P；Network topology；Algorithm
本文责编：胡智标
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
随着德国媒体集团巨子贝塔斯曼以800万美元的价格收购Napster，以网络自由为己任的“开放源代码运动”（Open Source）与商业公司进行的堂吉诃德似的斗争也告一段落。然而，Napster把一种全新的网络应用模式“对等网络”（Peer-to-Peer Networks，P2P）带入人们的视野，并迅速被人们所接受。
P2P 信息共享技术是一种用于不同PC用户间，不经过中继设备直接交换数据或服务的技术，它允许网络用户直接使用对方的文件，改变了传统的将资源集中放置在服务器端，用户要获得资源，必须先和服务器建立连接，并通过网络传输到本地计算机上的客户机/服务器模式（Client/Server，C/S），消除了中间环节，使内容从“中心”走向“边缘”，避免了C/S 结构固有的性能瓶颈，并使位于网络边缘节点上的信息资源参与共享。 P2P网络拓扑是P2P信息共享技术的基础，它负责合理地组织网络中的节点以及节点上提供共享的信息资源，并在此基础上高效地发送查询请求和查询应答消息，其目的是在保证检索质量的情况下，尽可能减少查询所引发的各种开销。
本文力求寻找一种具有高可伸缩性、低开销的对等网络拓扑，改进算法。
二、常见P2P网络拓扑结构及不足
拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，节点之间的拓扑结构一直是确定系统类型的重要依据。对等网络拓扑构造是目前对等信息共享研究的一个核心问题。以下是四种常见的拓扑结构。
1．单目录服务器型混合式拓扑
混合式拓扑是一种混合了中央服务器结构的对等网络拓扑结构, 在某些文献中也被称为集中索引模型（Central Index Server Model）。在基于此类拓扑结构的系统中，存在一个或多个特殊的被所有节点共知的中央节点——服务器，中央服务器集中管理各种索引并执行检索。拓扑结构如图1。
这种拓扑结构严格来说是C/S模型与P2P模型的混合体。其资源发现和查找过程采用C/S模式，节点间的文件传输则采用P2P模式。由此带来的问题是仍带有集中式的特征，单点故障使系统的容错性很差，一旦出现技术问题，服务器会减速甚至停止服务，同时服务器很容易成为系统的瓶颈，服务器可承受的负载限制了系统扩展。
2．多超级节点型混合式拓扑
针对单目录服务器型混合式拓扑存在的问题，后续的混合式P2P系统作了相应的改进。改进的基本思想都是在增加超级节点的数目的基础上弱化系统中的集中性，同时加强超级节点间的联系，以降低单点故障的危害。拓扑结构如图2所示。
3．全分布式非结构化拓扑
全分布式非结构化拓扑不存在索引服务器，所有用户节点完全对等，结构如图3所示。为了搜索某个文件，查询发出节点会向其邻居列表上的节点发出查询请求并附加该查询的TTL（Time-To-Live）。收到查询消息的节点，首先检查本地资源，看是否有与查询匹配的目标文件。如果有，则发送查询应答消息给查询发起者，如果没有，则转发给邻居节点。不管查询是否成功，只要查询的TTL不为0，接收查询的节点都会将该查询的TTL值减1后，转发给自己邻居列表上的节点。这种转发查询的洪泛机制以消耗相当高的网络带宽为代价，会导致较高的查询成本和较长的响应时间。
4．全分布式结构化拓扑
全分布式结构化拓扑一般都是基于DHT（Distributed Hash Table，分布式哈希表）技术，其共性是每个节点都有一个逻辑地址，新节点在加入时必须获取逻辑地址，这些逻辑地址反映了拓扑结构，路由、拓扑的维护等都是相对于这个逻辑地址而言。全分布式结构化拓扑具有良好的系统可伸缩性，是目前P2P领域研究的热点。因为在全分布式结构化拓扑中，文件存放和消息路由严格受控，所以这类系统都能实现一定程度的高效查找。但这种严格受控的系统也面临一些问题，由于P2P系统固有的动态性，使得这种维护的开销很大。拓扑结构如图4所示。
三、拓扑结构及算法实现
依据全分布式构化拓扑，笔者给出了一个拓扑结构的框架模型，如图5所示。该模型包含资源发布、路由维护、索引维护、数据对象维护、资源检索/定位等功能，将网络中信息资源的提供节点结合在一起，使得在保证系统可伸缩性的前提下，把信息共享覆盖到整个互联网。
1．P-Grid算法的基本思想
P-Grid是由Karl Aberer为首的P-Grid工作组研究给出的P2P系统。它是一种基于虚拟分布式搜索树的P2P系统：每个节点（Peer）只保存整棵树的一部分内容，这种树结构只有通过各个节点间的通信合作才能建立起来。P-Grid的搜索高效、快速，极大地减少了网络带宽，是一个真正的分布式系统，不需要中央协调者。它完全基于随机性的算法和节点间的交互来运作。与其它基于树结构的分布式索引不同，P-Grid节点能在非常不可靠的网络环境中执行搜索/更新操作，并且系统假设节点经常出现故障，节点在线概率低至10%左右。
为了能在没有中央控制的情况下，实现大量节点间的可靠搜索，并且使系统在节点数量上具有良好的伸缩性，P-Grid定义了一种新的数据访问结构。它的基本思想是：节点通过相互间随机的访问，连续不断地分割搜索空间，每个节点均保留足够的信息以便在以后响应搜索请求时与其它节点通信。最终形成的分布式访问结构就称为“P-Grid”（Peer Grid）。
尽管P-Grid算法有上述吸引人的特征，但在P-Grid中，只是沿着搜索树执行定向查找，在每次选择下一跳转发节点时，算法并没有考虑该节点或沿着该节点到达的节点是否真的拥有与查询请求相关的信息，这样的后果有可能直接造成某次查询的失败，而且由于算法没能从失败的查询中“吸取教训”，同样的失败将有可能一直存在，一直重复。另外，对于一次非常成功的查询，算法也不能从中“汲取经验”，这样相同的查询可能会走很多“歪路”，甚至失败，造成搜索效率的下降，增加网络带宽消耗。针对这个问题，本文在P-Grid算法的基础上加以改进，引入反馈机制。
2．基于推荐的P-Grid算法的基本思想
在对P-Grid算法研究的基础上作者给出了基于推荐的P-Grid算法以弥补不足。该算法利用已执行查询的反馈来有效地指导后继查询，是一种基于可靠消息的搜索算法。在算法中，每个节点都保持一个本地索引，索引由每个被请求或转发的数据对象关于每个邻居节点的一个条目（即三元组<数据对象，邻居节点，索引值>）组成。每个条目的值反映了在以后对特定数据对象的请求中，这个节点的邻居节点被选为下一跳转发节点的相对概率。
在转发过程中，一个节点不是随机选择它的下一跳邻居节点，而是使用它的索引值提供的概率，即选择“最好”的节点进行转发。在每一步转发中，节点都把自己的节点标识符添加到查询消息中，并为它们处理过的查询保持软状态。假如来自同一查询的两个转发节点路径相交（比如，由于环的存在，一个节点收到一个副本查询消息），第二个转发节点就被认为是失败结束，副本查询消息被丢弃。
作为反馈的索引值可以从以下两种方法得到：
（1）乐观方法
乐观算法建立在转发节点将成功完成查询请求的假定条件之上：当一个节点向一个或几个邻居节点转发查询时，就增加被选节点的索引值。当查询消息转发终止时，如果成功则任何事情也不用做（因为转发过程中已经增加了索引值），如果失败则沿着转发路径的逆路径修正那些与被请求对象相关的索引值（即转发过程中已经增加的索引值）。利用查询消息中的信息，转发路径上的最后一个节点发一个correct消息给它前面的节点。当这个节点收到correct消息后就减少对最后节点的索引值以反映失败。修正过程一直沿着这个请求的转发路径逆向返回，中间节点减少它们的本地关于下一跳的索引值。最后，发起查询的请求节点减少与这个转发路径相关的邻居节点的索引值。
（2）悲观方法
悲观算法与乐观算法相反：当一个节点向一个或几个邻居节点转发查询时，就减少被选节点的索引值（假设转发节点将失败）。当查询消息转发终止时，如果失败则任何事情也不用做，如果成功则沿着转发路径的逆路径增加那些与被请求对象相关的索引值。
虽然可以采用悲观和乐观两种方法，但在实际应用中，由于各种意外因素，导致查询消息还没结束就在转发途中丢失，这时查询失败，而又无从沿转发路径的逆路径修正索引值，因此，乐观的方法在实际应用中存在困难，所以本文接下来的讨论都针对悲观算法。
为了确定修正值，引入公式：
v（t）=v0 (v0>0, t>0)
其中，v0是当一个节点向一个或几个邻居节点转发查询时，对被选节点的索引值的减少值， t是从一个节点发起查询到得到查询结果之间的延迟，v（t）是查询成功后沿着转发路径的逆路径对相关索引值的增加值。显然,v（t）大于v0，即对索引值的增量大于对索引值的减量，且当t1>t2时v（t2）>v（t1），即对于同一查询的两条成功路径中，延迟小的索引值的增量大。所以，最后关于同一个数据对象的所有条目的索引值呈现：转发成功的（延迟较小）>转发成功的（延迟较大）>没被转发的>转发失败的。这正是算法要达到的效果。 这样，当系统运行一段时间后，每个节点上都保持了已被修正的索引表，这时查询转发将根据索引表提供的信息，选择索引值较高的节点进行，即选择查询延迟较小的路径。可见基于推荐P－Grid算法能通过有效路由减少查询延迟，提高路由性能。
3．基于推荐的P-Grid算法访问结构
定义1 二进制树是n(n≥0)个节点的有限集T，T为空时称为空树，否则它满足如下两个条件：
有且仅有一个特定的称为根(Root)的节点，若n＝1，则二进制树只包含一个Root节点；
其余的节点可分为两个互不相交的子集Tl和T2，其中Tl和T2本身又是一棵二进制树，并称其为根的子树(Subtree)。
在二进制树中，如果某个节点的子树个数为0，则称此节点为叶子节点。
定义2 ?坌p∈P,path (p)=b1…bn,bi∈{0, 1},P为节点集合
系统由N个节点的集合P={p1, …, pN}构成，每个节点都有自己的节点路径。节点路径有最大长度maxlength，根据实际应用情况设定，用于控制二进制搜索树的深度。maxlength反映了整个搜索空间被划分的程度，系统稳定后，整个搜索空间将被划分为2maxlength份。节点路径允许相同，路径相同的节点称为复制节点。
（注：节点路径的下标从1开始。）
每个节点均负责管理一个搜索区间，负责该区间内数据对象的信息，响应针对这些数据对象的检索请求。节点p负责数据对象d的条件是：path(p) 是key(d)的前缀，或key(d)是path(p)的前缀。节点p称为数据对象d的负责节点。而数据对象d有可能由其他节点q提供共享，并不存储在节点p上。节点q称为数据对象d的存储节点。 复制节点负责相同的数据对象。由于复制节点的存在，不会因某些节点的失效造成信息的丢失，从而进一步提高了系统健壮性。
即节点p维护了一张路由表，该表分层记录其他节点的地址。对于第i层路由表Ri中的任一节点r，r的路径和p的路径具有长度为 i的公共前缀，但第i+ 1位的值不同。当搜索请求的前i位和path(p)一致，但第i+1位与path(p)不匹配时，节点p可通过Ri将请求路由到适当的节点。为控制路由表的大小，每层中的最大节点数由参数为了实现层内推荐，提高检索效率，节点p在本地维护一张索引表，索引表和其路由表对应，分层记录数据对象关于各转发节点的索引值。对于第i层索引表Ii中的任一索引(d,r,v)：数据对象d的键值key ( d )和节点p的路径具有长度为 i的公共前缀，但第i + 1位的值不同；节点r为相对应第i层路由表Ri中的节点；索引值v为任一实数。对于一个特定的数据对象只可能向路由表中的某一层转发，所以也只可能出现在索引表中的某一层，而不会是很多层。
4．基于推荐的P-Grid算法的简单模型
图6中的简单例子描述了基于推荐的P-Grid算法的结构。图中包含6个节点，用带数字的圆圈表示，这些节点位于树结构的叶子节点上，用其节点路径（分别是00、01、10、11）来标识。
图6中也描述了查询请求被转发的过程：查询“100”（“100”为要查询的数据对象所对应的二进制标识符）被发送到图中的节点 6，节点 6的路径为“00”，第1位就与key不同，根据路由表的表项可以把请求转发给节点3、4、5。其中节点3和4的路径和“100”匹配，查询结束。节点5的路径为“11”，和“100”有一位相同，但第2位不同，根据路由表表项又将请求转发给节点4，查询结束。 假设只有节点4上负责了“100”，初始值全为1.0，并取修正公式中的v0为0.3，表2显示了查询“100”前后的索引值的变化。
由此可见，基于推荐的P-Grid算法访问结构中，搜索沿二进制搜索树从根到叶子执行定向查找的同时，在树的同一层上又执行基于层内推荐的可靠消息路由，这种“双保险”机制使得搜索成功率、搜索响应时间得到更进一步的保证。
四、总结和展望
近年来，人们对P2P网络中的拓扑结构进行了不断的探索和研究，本文在现有P-Grid系统算法的基础上加以改进，利用反馈来有效地指导后继查询，节约了大量的时间和带宽资源。总的来说，本文基本达到了预期的目标，找到了一种具有较高可伸缩性、较低开销的对等网络拓扑结构及更加快捷的搜索算法。随着网络技术的日益成熟，研究的不断深入，P2P网络模式必将发挥越发重要的作用，而对等网络的拓扑结构，版权问题，安全问题等也将得到有效的解决。
[参考文献]
［1］Karl Aberer, Manfred Hauswirth. Peer-to-peer Information Systems: Concepts and Models, State-of-the-art, and Future Systems. 18th International Conference on Data Engineering, San Jose, California, 2002.
［2］刘晓红，邱力戈.对等网络运营模式探讨[J].通讯世界，2001,(9).
［3］余智华，陆天波等.P2P技术与信息安全[J].信息技术快报，2004,(3).
［4］周宁.信息组织[M].武汉：武汉大学出版社，2001,(5).
［5］刘继光，陈立伟.一种基于DHT的P2P搜索方法[J].微计算机信息，2006,22（3）.
［6］黄宏斌，杨光，秦振.一种分布式信息资源定位机制的研究[J].计算机工程，2006,32（6）.
［7］汪维华，汪维清. 一种P2P网络信息分类检索模型研究[J].计算机工程与设计, 2007,(4).
［8］王平根，刘勇，周脚根. 基于蚁群算法的P2P网络路由[J].广西师范大学学报(自然科学版), 2007,(02).
[作者简介]
方玉田，浙江广播电视大学现代教育技术中心。
ON P2P Topology Frame and Algorithm
Fang Yutian
（Modern Education Technology Center of Zhejiang Radio & TV University, Hangzhou Zhejiang 310012）
【Abstract】 Nowadays, the brand-new network mode of “peer-to-peer general acceptance of information sharing” is attracting people’s attention. The paper aims to find a more flexible, speedy peer to peer network topology frame on the basis of the traditional common one, and to improve algorithm.
【Keywords】 P2P；Network topology；Algorithm
本文责编：胡智标
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文