用于分解对等网络并且使用分解的对等网络的方法和设备

摘要

提供了一种用于将P2P网络分解成多个子网并且使用该分解的P2P网络的能力。P2P网络被分解以构成多个子网，其中每个子网是P2P网络。P2P网络可以基于一个或多个分解准则（例如地理位置、关注团体等，以及其各种组合）而被分解成子网。P2P网络的分解被编码成网络地图。节点可以使用该网络地图以加入分解的P2P网络。节点可以加入一个、一些或全部子网。分解的P2P网络的子网可以被安排成任何适当数目的层级。

说明书

相关申请的交叉引用

本申请涉及2009年12月17日提交的标题为“METHOD AND  APPARATUS FOR LOCATING SERVICES WITHIN  PEER-TO-PEER NETWORKS”的美国专利申请号12/640,072（律 师案号Chu 19-43(ALU/130209)），在此引入其全部内容作为参 考。

技术领域

本发明涉及对等网络（P2P）的领域，具体地（但并非只）涉 及将P2P网络分解成子网。

背景技术

文件共享已经从一段时间以来成为激烈研究和基层使用的焦 点。文件共享是通过文件共享方法来实现的，该方法专门针对该 目的并且被实现为具有与其关联的文件共享协议的不同文件共享 系统。若干不同的文件共享系统已经被实现，其开始于Napster， 然后历经若干代的不同文件共享系统，例如gnutella、Kazaa、 eDonkey、Winny、和BitTorrent。除了这些文件共享系统之外， 例如Share和Perfect Dark的新系统也正在开发。总体上，这些 文件共享系统和关联的协议称作对等（P2P）文件共享系统/协议， 或更简单地称作P2P文件共享应用。此外，除了P2P文件共享应 用之外，出现了新的P2P应用类别，即P2P电视（P2PTV），其 在结构上不同于P2P文件共享应用。

从近期的业务研究来看，P2P文件共享的普及是很明显的。 例如，由Ellacoya Networks对美国的一百万宽带用户的近期业务 研究表明，主要业务类型衰减量如下：web（HTTP）-46%;对 等（P2P）-37%;新闻组-9%;非HTTP流式传输视频-3%;游戏 -2%;IP上的语音（VoIP）-1%;以及其他-1%。大量HTTP业 务的主要原因是嵌入式视频流式传输业务，例如来自YouTube的 业务，其占了上述研究中的总业务的9.8%。然而，P2P文件共享 仍然占了很大百分比的业务，并且随着P2PTV的出现，业务量预 期大幅增加。

多数现有的P2P应用涉及文件共享。然而，涉及文件共享的 多数现有P2P应用至少最初并非是完全对等的。更确切地说，多 数现有P2P应用最初使用中央服务器来协调P2P网络成员之间的 活动性。例如，在bitTorrent中，尽管对不同信息段的下载是对 等的，然而在bitTorrent中称作跟踪器的集中式服务器被用来协 调bitTorrent应用的活动性。类似地，例如许多其他涉及文件共 享的P2P应用也具有类似的特征，例如Napster和eDonkey。然 而，中央服务器的使用使得现有P2P应用易于出现拥塞和故障， 并且进一步使得现有P2P应用成为安全威胁的攻击目标。

为了消除与在P2P应用中使用集中式服务器有关的问题，已 经提出新的技术来消除对使用P2P应用的集中式服务器的需求。 这些技术中最流行一种是分布式散列表（DHT）。在DHT中，每 个对象用关联的M比特对象标识符来标识。对象的对象标识符是 利用一致性散列函数（例如，对象标识符=f（对象名），其中f 是一致性散列函数）、通过计算对象名称的散列值来获得的。散 列函数的M比特输出字段通常称作密钥空间，并且散列函数在密 钥空间内一致地映射对象。这些是基于DHT技术的若干不同P2P 结构，例如Chord、Pastry、Tapestry等，其中Chord是最流行 的基于DHT的P2P结构。例如bitTorrent和eDonkey都支持DHT。

在P2P网络中，设计目标之一是容纳大量节点；然而，同时， 每个节点中的搜索表必须相对较小。利用DHT，这个目标通过使 用分布式搜索策略而实现，在该策略中每个节点中的搜索表以协 作的方式构成以使得搜索请求将最后被路由至其最终目标，必要 时经过若干节点。通常，每个DHT技术定义其自己的几何（例如 Chord网络安排成圆形），其通常规定了节点内搜索表的结构并 且还指定了节点如何加入和离开网络。通常，当节点加入网络时， 节点必须向其邻居宣告其存在、创建并填充其搜索表并且获得其 负责的文件。通常，当节点离开网络时，节点必须通知其邻居以 使得相邻节点能够被更新以反映该节点的离开，并且必须传送其 负责的任何文件。节点通常也周期性地发送管理和控制消息至其 各个邻居。

然而，不利的是，在多数DHT技术中，例如Chord，在结构 中并未考虑节点的物理位置（或它们之间的距离）。结果，消息 和信息（例如关联于节点加入/离开过程的状态消息和文件传送）、 在相邻节点之间交换的状态和控制消息、关联于文件搜索的搜索 消息等等，可能穿过较大的地理距离。此外，尽管至少一些DHT 技术尝试利用邻近度量来纳入节点间的“距离”的概念，例如 Pastry，然而这些DHT技术仍具有与其相关的不利因素，即：（1） 难以定义易于使用的近邻度量，特别是对大型网络而言；和（2） 近邻度量应当是满足三角不等式的距离度量。然而，多数流行的 度量，例如网络跳，都未能满足三角不等式。

发明内容，

现有技术中的各种缺陷通过支持对等（P2P）网络分解能力的 实施例而得到解决，其中P2P网络被分解成多个子网。提供了用 于分解P2P网络以构成包括多个子网的分解的P2P网络并且进一 步使用该分解的P2P网络的能力。P2P网络可以基于一个或多个 分解准则（例如地理位置、兴趣团体等，以及其各种组合）而被 分解成子网。P2P网络的分解被编码在网络地图中。节点可以使 用网络地图来加入分解的P2P网络。节点可以加入一个、一些或 全部子网。分解的P2P网络的子网可以被安排成任何适当数量的 层级。

附图说明

参考附图，通过考虑以下详细描述，能够容易地理解这里的 教导，其中：

图1示出了示例性Chord网络；

图2示出了图1中的示例性Chord网络被示例性地分解成控 制网络和五个子网；

图3示出了用于使得文件被存储在分解的P2P网络中的由节 点使用的方法的一个实施例；

图4示出了用于定位存储于分解的P2P网络中的文件的由节 点使用的方法的一个实施例；

图5示出了用于加入分解的P2P网络的子网的由节点使用的 方法的一个实施例；

图6示出了用于离开分解的P2P网络的由节点使用的方法的 一个实施例；

图7示出了用于基于分解的P2P网络的网络地图中的更改而 执行更改的由节点使用的方法的一个实施例；

图8A-E示例性地示出了用于将文件从第一子网传送至第二 子网的过程；

图9示出了用于当初始化分解的Chord网络中的Chord子网 时使得第一子网中的节点从第二子网获取文件的方法的一个实施 例；和

图10示出了适于用来执行这里描述的功能的通用计算机的高 级框图。

为了便于理解，在可能的情况下用相同的参考号码来标识图 中通用的相同元素。

具体实施方式

这里描述和说明对等（P2P）网络分解能力。P2P网络分解能 力使得P2P网络能够被分解以构成包括多个子网的分解的P2P网 络，其中每个子网也作为P2P网络工作。P2P网络分解能力使之 能够适于分解的P2P网络。

尽管这里主要就Chord网络进行描述和说明，然而P2P网络 分解能力可以被用于利用任何合适的P2P技术来分解任何P2P网 络，例如Pastry网络、Tapestry网络等等，以及其组合。

图1示出了示例性Chord网络高级框图。如图1所示，示例 性Chord网络100包括多个被逻辑上安排成环形配置的节点110。 节点110每个都存储有可在节点110之中共享的文件。节点110 包括可以参与到Chord网络中的任何合适的节点类型。例如节点 110可以包括计算机、电话等。节点110每个都被配置成提供这里 描述的P2P网络分解能力的各种功能。通过首先结合图1的示例 性Chord网络100来考虑Chord网络的一般操作，可以更好地理 解利用P2P网络分解能力对Chord网络100进行的分解。

在Chord中，Chord网络的节点具有经由基于分组的网络（例 如IP网络或任何其他合适的网络）的网络连通性，Chord构成基 础的基于分组的网络之上的覆盖网络。

在Chord中，可以参与到Chord网络中的节点数目是基于 Chord网络的密钥空间（地址空间）的大小的。通常，密钥空间 是M比特，其中M可以是任何合适的数目。例如，用于Chord 网络中的典型密钥空间是利用160比特实现而提供的，这使得密 钥空间的大小等于2¹⁶⁰或~1.45*10⁴⁸。一致性散列函数被用来将输 入映射到160比特的值（即将输入映射到密钥空间）。散列函数 的输出被一致地映射到密钥空间。应当认识到，可以使用任何合 适的散列函数，例如安全散列算法（SHA-1）、消息摘要算法5 （MD5）等等。当映射到密钥空间中时，散列函数的输出提供了 用于在C hord网络中逻辑上安排节点的节点ID组。在Chord中， 激活节点（参与到Chord网络中的现有节点）和非激活节点（可 能加Chord网络的潜在节点）以节点的节点ID的顺序被逻辑 上安排成圆形。Chord在利用环绕式处理（with wraparound）的 增加的节点ID值的方向中强制圆圈中的顺序。在Chord中，Chord 网络的激活节点之间的连通性是圆圈中的激活节点的相邻节点之 间的逻辑连通性（因为非激活节点没有连接至Chord网络并且因 而仅是可以加入Chord网络作为激活节点的潜在节点）。以这种 方式，从Chord网络中的目标激活节点的角度来看：（1）其节点 ID大于目标节点的节点ID的圆圈上的下一个激活节点是目标激 活节点的前任，以及（2）其节点ID小于目标节点的节点ID的下 一激活节点是目标激活节点的前任的目标节点。

在图1中，Chord网络的密钥空间是6比特（假设64个节点， 它们以顺时针方式从节点ID 0至节点ID 63被连续编号）。在图 1中，节点0、2-3、5-7、9、12-13、16-24、26、29-30、32、34-35、 37、41、43、45、49、51、53-54、56-58和62是激活的，剩余的 节点是非激活的（出于清楚的目的，激活和非激活节点二者都被 显示）。在图1中，Chord网络100的激活节点之间的逻辑连通 性指示了节点0连接到节点2，节点2连接到节点3，节点3连接 到节点5，等等，节点62连接到节点0以完成圆圈。Chord通过 利用环绕式处理的顺时针方向的增加的值来强制圆圈中的顺序， 节点2称作节点0的继任而节点62称作节点0的前任，节点3称 作节点2的继任而节点0称作节点2的前任，等等。

如这里描述的那样，Chord网络支持文件共享，其中要共享 的每个文件被存储在Chord网络的一个或多个激活节点中。在 Chord中，文件的文件名被散列处理到同一密钥空间中，该同一 密钥空间用于利用同一散列函数来标识Chord网络中的节点，该 同一散列函数用于标识Chord网络中的节点。通过对文件名进行 散列处理而获得的被散列处理的输出是用于文件的文件标识符。 因此，对于具有160比特的密钥空间的Chord网络而言，例如， Chord网络能够潜在地容纳1.45*10⁴⁸个文件。在Chord中，如果 其节点ID匹配于文件的文件ID的节点是激活的，则该文件被存 储在该节点中，并且如果该节点不是激活的，则该文件被存储在 其节点ID大于文件ID的第一激活节点中。

在图1中，Chord网络100总共能够容纳64个文件，其将被 如下存储：节点0存储文件0和63；节点2存储文件1和2；节 点3存储文件3；节点5存储文件4和5；节点6存储文件6；节 点7存储文件7；节点9存储文件8和9；节点12存储文件10、 11和12；节点13存储文件12；节点16存储文件14、15、和16； 节点17存储文件17；节点18存储文件18；节点19存储文件19； 节点20存储文件20；节点21存储文件21；节点22存储文件22； 节点23存储文件23；节点24存储文件24；节点26存储文件25 和26；节点29存储文件27、28和29；节点30存储文件30；节 点32存储文件31和32；节点34存储文件33和34；节点35存 储文件35；节点37存储文件36和37；节点41存储文件38、39、 40和41；节点43存储文件42和43；节点45存储文件44和45； 节点49存储文件46、47、48和49；节点51存储文件50和51； 节点53存储文件52和53；节点54存储文件54；节点56存储文 件55和56；节点57存储文件57；节点58存储文件58；节点62 存储文件59、60、61和62。

在最基本的实现中，任何给定文件只有一个拷贝被存储在 Chord网络中（因为使用了用于分配节点ID和文件ID的同一个 散列函数）；然而，可采用不同的方法来在Chord网络中存储多 个文件的拷贝（例如为了在节点故障、负载均衡等情况下的弹性）。

在一个实施例中，例如，通过利用协商好的命名协定来稍微 不同地将文件名分配给该文件的多个拷贝，文件的多个版本可以 被存储Chord网络中。例如，如果文件的名字是“abc”，例如“-n” 的扩展可以被添加给文件名以代表相同的文件。在这个例子在， 文件的多个拷贝可以以名字“abc”、“abc-1”、“abc-2”等而 被存储。以这种方式，由于文件“abc”的多个文件名并不相同， 对不同文件名的散列处理将导致不同的散列输出以及不同的文件 ID，由此致使文件的多个拷贝被存储在Chord网络的不同节点中。

在一个实施例中，例如，通过使用多个独立的散列函数来利 用文件名生成文件的多个文件ID（而并非如上所述的实现，其中 使用单个一致性散列函数），文件的多个版本可以被存储在Chord 网络中。在这个实施例中，将文件播种到Chord网络中的节点利 用散列函数来确定文件的每个可能的文件ID，并且利用文件ID 而将该文件的多个拷贝插入Chord网络中。在这个实施例中，在 Chord网络中搜索文件的节点将确定文件的所有可能的文件ID （通过利用每个散列函数对文件名进行散列处理）并且因而能够 利用所确定的文件ID来顺次地或并行地搜索文件。

就文件的多个版本在Chord网络中的存储而言，应当认识到， 多个文件版本可以以任何其他适当的方式被存储在Chord网络 中。

如这里所描述的，Chord使得节点能够共享文件。为了使得 Chord网络的节点能够共享文件，Chord网络中的每个节点必须 能够搜索并最终确定期望文件的位置从而能够获得该期望文件。

在Chord中，每个节点维护搜索表。对于具有M比特密钥空 间的Chord网络而言，每个节点N将维护具有M个条目的搜索 表，其中搜索表的条目称作“手指”。在节点N的搜索表中，第 i个手指指向圆圈上的第一节点，其距N至少有2^i-1。通常，除非 特别指出，术语“第i个手指”将被用于表示由搜索表中的第i 个条目所指向的节点。例如，在Chord网络100中，节点0的第 3个手指是节点5。

节点的搜索表共同地提供有效的全局搜索算法，Chord网络 内的对象的位置可通过该算法来确定。

在图1中，密钥空间是6比特，并且因此每个节点在其搜索 表中具有6个手指。在图1中，节点0中的搜索表可以如下面的

表1所示：

  手指   2^i-1  第一节点≥2^i-1  1   1   2   2   2   2   3   4   5   4   8   9   5   16   16   6   32   32

表1

在Chord中，网络是动态的。当新节点加Chord网络而现 有节点离开Chord网络时，Chord网络的激活节点中的搜索表会 受到影响。同样，在Chord中，每个激活节点K将周期性地更新 其关联的搜索表。激活节点K可以以任何适当的方式更新其搜索 表。例如，激活节点K可以通过搜索节点（K+2^i-1）来更新其搜 索表，因为执行该搜索的结果将是搜索表中的第i个手指的值。应 当认识到，Chord网络中的激活节点可以以任何适当的方式更新 其搜索表。

在Chord中，除了搜索表之外，每个节点也在环形中存储其 继任和其前任的身份。这个信息被用于环形维护，例如当新节点 加入网络并且现有节点离开网络时，以及当节点从故障中恢复时。 在一些Chord网络中，为了预防多个并行节点故障的情形，节点 可以在环形中存储器N个继任及其N个前任的身份。

在Chord中，Chord网络中的节点能够从Chord网络中的其 他节点搜索并且获得文件。Chord网络支持搜索算法，节点可以 通过该算法搜索可从Chord网络中的其他节点获得的文件。Chord 搜索算法的操作可以利用图1中的Chord网络100通过例子来说 明。在该例子中，假定节点2想要搜索图1的Chord网络100中 的文件0。节点2将访问其搜索表以选择要向其发送文件请求的其 他节点中的一个。由于从节点2的角度来看，目标文件（即文件0） 的文件ID由于环绕式处理而大于节点2的最大手指的值（即节点 34），节点2将发送第一请求至节点34以请求节点34搜索文件0。 节点34收到来自节点2的文件请求。节点34由于并未存储文件0 而将访问其搜索表以选择要向其转发文件请求的其他节点中的一 个。在节点34中，搜索表包括六个手指，其指向节点35、37、40、 43、51和2。由于文件0的对象ID是在第5和第6个手指（分别 是节点51和节点2）之间，节点34将转发搜索请求至由第5个手 指（节点51）标识的节点。节点51接收来自节点34的文件请求。 节点51由于其未存储文件0而将访问其搜索表以选择要向其发送 文件请求的其他节点中的一个。在节点51中，搜索表包括六个手 指，其指向节点53、53、56、62、3和19。由于文件0的对象ID 是在第4和第5个手指（分别是节点62和3）之间，因此节点51 将搜索请求转发给由第4个手指（节点62）所标识的节点。节点 62收到来自节点51的文件请求。节点62由于其并未存储文件0 而将访问其搜索表以选择要向其发送文件请求的其他节点中的一 个。在节点62中，搜索表包括六个手指，其指向节点0、0、2、6、 16和30。由于文件0的对象ID在第一个和第二个手指（节点0） 中均被指示，因此节点62知道节点0是激活的并且转发搜索请求 至节点0。文件0因而被返回给节点2。例如，文件0然后可以被 直接从节点0提供给节点2（例如在搜索请求包括节点2的IP地 址的情况下），或者可以沿着文件请求所经过的路径被传播回去 （即从节点0到节点62到节点51到节点34到节点2）。因此， 从这个例子中可以看出，在Chord中，Chord网络中的所有节点 互相配合以支持Chord搜索算法。

在Chord中，Chord网络是动态的，因为节点可以随时加入 Chord网络并且离开Chord网络。当节点加入和离开Chord网络 时，文件在节点直接被传送。例如，加入的节点可以假定负责至 少存储其文件ID与该加入的节点的节点ID相同的文件（以及可 能地其他文件），而离开的节点可以将存储一个或多个文件的责 任转移至另一个节点。与加入和离开Chord网络的过程将在下文 详细描述。

在Chord加入过程中，当节点想要加入Chord网络中时，加 入的节点确定其节点ID。加入的节点通过将其名称散列处理成密 钥值来确定其节点ID。例如，如果节点的名称是 node-xyxcompany-abc.com，则节点ID将是SHA-1的输出 （node-xyxcompany-abc.com），其中为了简单而假定散列函数 是SHA-1（尽管可以使用任何合适的散列函数）。在这个例子中， 如根据散列处理操作所确定的那样，令该节点的节点ID为K。

在Chord加入过程中，加入的节点K然后联系Chrod网络中 的激活节点（表示为初始化节点）。乍一看，这个初始化节点像 是集中式服务器，然而情况并非如此，因为：（a）该初始化节点 可以是当前在Chord网络中激活的任何节点（例如如果节点K1 和节点K2同时想要加入Chord网络，则它们可以并且可能使用 不同的激活节点作为它们各自的加入网络的初始化节点），以及 （b）该初始化节点不必提供除了基本能力之外的任何特殊的能力 （即它可以表现得像Chord网络中的任何其他节点那样）。节点 K能够以任何适当的方式获得潜在的候选初始化节点的列表（例 如从加入的节点K中的一个或多个在先搜索表、继任列表和/或前 任列表，从在加入的节点K内被管理性配置的信息中、从网站等 等）。在这个例子中，令初始化节点的节点ID为L。

在Chord加入过程中，加入的节点K然后发送关于初始化节 点L搜索加入的节点K的请求（即搜索ID=K的对象）。此时， 会发生两个事件：

（A）节点L以值N来答复加入的节点K。节点N将是在所 有激活节点之中具有比关联于加入节点K的K要大的节点ID的 那个节点。因此，如果加入的节点K要加入Chord网络，则节点 N应当是加入节点K的继任节点。节点K然后联系节点N并且向 节点N请求节点N的前任节点的身份。在这个例子中，令节点N 的前任表示为N-。节点N向加入节点K提供值N-。基于这个信 息，节点K因而知道它必须将它自己插入Chord网络中的节点N 与节点N-之间。

（B）节点L用值K来答复加入的节点K。这意味着在Chord 网络中存在已经激活的另一个节点ID为K的节点。尽管该情况 在多数Chord网络中可能性极小（例如在密钥空间为160比特的 Chord网络100中，该情况发生的可能性是1.45*10⁴⁸中的1）， 这是有可能的。该情况可以通过使得加入节点K稍微更改其拥有 的名称（例如添加时间标记、添加数字等）并使用新的节点名来 生成不同的节点ID（表示为K’）而得到解决。加入的节点K’能 够通过发送新的搜索请求给初始化节点L来再次开始该过程（即 关于初始化节点L搜索加入的节点K’的请求）。

在Chord加入过程中，在确定加入的节点K的插入点之后， 执行将加入的节点插入Chord网络中的过程。加入的节点K被插 在节点K-（K的候选前任）与节点K+（K的候选继任）之间， 其中在该时刻，在节点K加入网络之前，节点K+是节点K-的继 任。加入的节点K联系继任节点K+以指示它想要加入Chord网 络。继任节点K+然后（1）通知加入的节点K其前任是节点K-， （2）开始向加入的节点K传送该节点K应当负责的任何文件（即 其文件ID从（K-）+1到K的文件），以及（3）通知其前任节点 K-加入的节点K正在加Chord网络。在文件传送完成后，加入 的节点K建立与前任节点K-的连接。在加入的节点K与前任节 点K-之间的连接被建立之后，加入的节点K通知继任节点K+它 已经成功加Chord网络。继任节点K+然后中断与前任节点K- 的连接，并且继任节点K+和前任节点K-二者都更新其前任和继 任列表。

在Chord离开过程中，执行用于以受控的方式而使得离开的 节点K离开Chord网络的处理。正离开的节点K具有与其关联的 前任节点（表示为节点K-）和继任节点（表示为节点K+）。离 开的节点K联系前任节点K-和继任节点K+二者以向其通知它打 算离开Chord网络，并且向这两个节点提供另一个的身份。离开 的节点K然后向继任节点K+传送离开的节点K当前代表Chord 网络存储的所有文件（即文件ID在（K-）+1至K之间的所有文 件，包括K）。在文件传送完毕之后，加入的节点通过与前任节 点K-和继任节点K+断开连接而离开Chord网络。节点K-和K+ 然后在彼此之间建立连接（这可以由它们中的任一个发起）。节 点K-和K+也更新它们的前任和继任列表。

除了使用用于实现对Chord网络的动态更改的Chord加入过 程和Chord离开过程之外，Chord还支持用于使得节点从故障中 恢复的Chord恢复过程（即Chord离开和Chord加入过程不被用 于使得节点从故障中恢复）。Chord网络中的节点周期性地发送 心跳消息分别给它们的前任和继任节点，由此使得Chord网络中 的节点能够快速检测节点故障。通常，来自节点的心跳消息将包 括该心跳消息所源自的节点的前任和继任节点的身份。以这种方 式，当节点收到来自其继任节点的心跳消息时，它知道其继任节 点的继任节点的身份，并且因此当节点的继任出故障时，该节点 能够发起至其继任节点的继任节点的连接并且Chord环得到维 护。如上文所指出的，在一些Chord网络中，节点维护K个前任 和K个继任的列表。在这种情况下，Chord网络能够从K-1个继 任节点的故障中恢复。在这种情况下，即使K值较小，K个继任 节点的故障的可能性也很小。在一些这种Chord网络中，K的值 可以被确定为2*log₂(L)，其中L是网络中的激活节点的平均数（即 Chord通常具有100,000个激活节点，K将是~34）。

上述Chord恢复过程使得Chord网络能够在节点故障的情况 下被修复，然而存储在故障节点中的文件被丢失。这个问题可以 以若干种方式来解决。

在一个实施例中，这个问题是通过在Chord网络内存储多个 文件拷贝来解决的。上面描述了两个这种方法。尽管这个方法提 供了附加的弹性，然而它需要在Chord网络的每个节点中的存储 容量的K倍增加。

在另一个实施例中，这个问题是通过使得获得文件的节点能 够自发变成该文件的种子节点来解决的。下面描述这个实施例。 文件最初通过Chord网络中的成员（其中该成员节点称作文件的 种子节点）而被引入Chord网络中。该种子节点获得文件名的散 列值（即文件ID），并且搜索具有与文件ID相同的节点ID的节 点。种子节点将定位Chord网络中的第一激活节点，其节点ID 等于或大于该文件ID。种子节点发送该文件至被定位的节点。然 后Chord网络中的稍后获得该文件的其他节点可以自发变成该文 件的种子节点。文件的种子节点将周期性地在Chord网络中搜索 该文件，并且如果该种子节点未能定位该文件，则它将发送该文 件至如上所述的合适的节点。以这种方式，“丢失的”文件在Chord 网络中被重新找到。

如这里所描述的那样，P2P网络分解能力使得P2P网络能够 被分解成多个子网，这由此构成了分解的P2P网络。在分解的P2P 网络中，每个子网都作为P2P网络工作并且因而支持如上所述的 P2P网络中的一些或全部能力。下面是对与分解P2P网络以构成 分解的P2P网络以及使用分解的P2P网络有关的各种实施例的描 述。

图2示出了图1的示例性Chord网络分解成子网的例子。

如图2所示，将Chord网络100分解成分解的Chord网络200 涉及构成控制网络202和多个子网2041-2045（共同表示为子网 204）。

在分解的P2P网络中，每个子网使用相同的密钥空间（M比 特）以及相同的密钥空间散列函数（表示为f(x)）。

在分解的P2P网络的一个实施例中，分解的P2P网络具有与 其关联的一组子网索引。子网索引是K比特字段，并且分解的P2P 网络的子网索引是利用将输入串映射到K比特值的子网索引散列 函数（表示为g(x)）来确定的，由此产生了分解的P2P网络的2k 个子网索引。在分解的P2P网络中，每个子网索引被分配给至少 一个子网并且每个子网具有分配给它的至少一个子网索引。子网 索引散列函数被用来计算对象（节点或文件）的子网索引，即节 点的子网索引被确定为g(节点名)并且文件的子网索引被确定为 g(文件名)。

在分解的P2P网络的一个实施例中，密钥空间散列函数f(x) 和子网索引散列函数g(x)应当被选择成它们在统计上不相关。在 一个实施例中，通过选择具有J比特输出的散列函数（表示为 h(x)），来配置密钥空间散列函数f(x)和子网索引散列函数g(x)， 其中J是大于或等于M+K的整数。在这个实施例中，假设对象（节 点或文件），h（对象名）被计算，由此产生了J比特值，其中K 个最高有效位被用来标识对象（g（对象名））的子网，而M个 最低有效位被用来标识子网内的对象（f（对象名））。

在分解的P2P网络中，网络地图被构成以维护适于由加入、 在其中操作（例如存储文件、定位文件等）以及离开分解的P2P 网络的节点来适于的信息。

在一个实施例中，分解的P2P网络的网络地图包括将分解的 P2P网络的子网索引映射到分解的P2P网络的子网。网络地图针 对每个子网而提供子网与标识该子网的至少一个子网索引的映 射。

在一个实施例中，分解的P2P网络的网络地图也可以包括散 列处理信息，例如密钥空间散列函数（f(x)）的身份和密钥空间 的相关大小，子网索引散列函数（g(x)）的身份和索引的相关大小， 等等，以及其各种组合。

在一个实施例中，分解的P2P网络的网络地图可以包括适于 由正在加入、在其中操作以及离开分解的P2P网络的节点来使用 的其他信息，例如由正在确定加入哪些子网的节点使用的描述符， 由网络地图的管理员使用以管理网络地图的网络地图管理信息， 等等，以及其各种组合。

在分解的P2P网络中，控制网络使得分解的P2P网络的节点 能够搜索节点、服务和其他控制信息。因此，对于该网络的每个 节点而言，节点在加入任何子网之前必须加入控制网络，并且类 似地在离开控制网络之前必须离开该节点所属的每个子网。如上 文所指出的，控制网络使用与每个子网相同的密钥空间。通常， 控制网络将不被用来存储任何对象或文件，并且因此与加入和离 开控制网络有关的开销相对较低。控制网络可以利用任何适于为 节点提供在分解的P2P网络上搜索“服务”（例如搜索满足特定 准则的节点，如属于特定子网的节点）的能力的P2P技术来实现。 在一个实施例中，例如，控制网络被实现为Chord网络。在这样 的实施例中，例如，控制网络被实现为支持服务定位能力的Chord 网络，例如在标题为“METHOD AND APPARATUS FOR LOCATING  SERVICES WITHIN PEER-TO-PEER NETWORKS”的美国专利申请 号XX/XXX,XXX[律师案号Chu 19-43(ALU/130209)]中所说明和描述 的服务定位能力，在此引入该申请的全部内容作为参考。应当认 识到，如果其他类型的P2P技术支持这种服务定位能力，则这些 其他类型的P2P技术也能够被用来实现控制网络。

如上文所述，控制网络可由节点使用以搜索其他节点、搜索 服务、获得其他控制信息，等等，以及其各种组合。通过考虑下 面对控制网络的示例性使用，可以更好地理解控制网络所实现的 能力。

作为例子，假设节点A想要联系节点B，但是在分解的网络 中，节点A不知道节点B是那个/哪些子网的成员。然而，尽管节 点A不知道节点B的子网，然而节点A能够在控制网络内发起对 节点B的搜索，因为只要节点B是激活的，节点B就将是控制网 络的一部分。在节点A利用控制网络定位节点B之后，节点A因 而能够联系节点B并且从节点B请求有关的联系信息和能力信息 （例如节点B是其成员的子网、节点B的IP地址、节点B的能 力，等等）。

作为例子，假设节点A想要加入子网X。在多数P2P网络中， 节点A必须联系已经是子网X的成员的节点以发起加入子网X的 过程。在这个例子中，节点A可以使用服务定位搜索能力来搜索 控制网络中作为子网X的成员的任何节点。然后，当标识了作为 子网X的成员的节点之一时，节点A可以发起加入子网X的过程。

作为例子，假设节点A想要使用由P2P网络提供的特定服务。 在这个例子中，节点A可以使用服务定位搜索能力来搜索控制网 络中支持该服务的任何节点。类似地，在这个例子中，节点A可 以使用服务定位搜索能力来搜索特定子网中的服务。然后，当标 识了服务的可用性时，节点A可以发起对该服务的请求。

作为例子，假设节点A加入控制网络。在这个例子中，在加 入控制网络之后，节点A将与其控制网络中的邻居交换消息。所 交换的消息可以由节点A使用以获取当前网络地图（如果节点A 还不具有当前版本的网络地图）。在这个例子中，节点A然后可 以使用该网络地图来在分解的网络中执行其他功能。

尽管主要就控制网络的指定示例性使用进行了描述，然而应 当认识到，分解的网络的控制网络可以被用来执行其他功能。

在分解的P2P网络中，P2P网络至子网的分解可以基于任何 适当的分解准则。例如，P2P网络至子网的分解可以基于一个或 多个下列准则：P2P网络节点的地理位置、P2P网络节点的用户 兴趣团体等等，以及其各种组合。

基于P2P网络节点的地理位置对P2P网络的分解是以旨在减 小或最小化属于同一子网的节点之间的地理距离的方式来执行 的。这减小或最小化了在分解的P2P网络的节点之间所交互的消 息和信息所经过的距离（例如当节点加入和离开网络、心跳消息、 当文件被传送等等），这由此减小了与交换消息和信息有关的延 迟、减少了交换消息和信息所消耗的网络资源，并且提供了其他 益处。通过考虑具有世界范围内的激活节点的示例性全球P2P网 络的一个简单例子，可以更好地理解这些益处。

在这个例子中，假设全球P2P网络没有分解，并且还假设位 于纽约市的P2P节点之一的前任位于东京并且继任位于悉尼。在 这个例子中，当纽约市的节点加入P2P网络和离开P2P网络时， 与其前任和继任交换的消息必须穿过整个世界，其中将包括若干 文件传输。类似地，在这个例子中，当纽约市的节点与其前任和 继任交换心跳消息时，该心跳消息也必须穿过整个世界。类似地， 在这个例子中，当从纽约市的节点执行搜索时，下一个节点可能 位于东京，下一个节点又回到纽约，下一个节点在南美，等等， 这使得搜索消息穿过了非常长的距离。

在这个例子中，通过将P2P网络分解成子网内可以改进该情 形，其中对于每个子网而言，属于该子网的节点相对于P2P网络 中的其他节点而言在地理上彼此接近。在这个例子中，假设P2P 网络被分解成多个子网，包括用于位于日本的节点的子网和用于 位于纽约市地区的节点的子网。在这个例子中，在分解P2P网络 之后，纽约市的节点将拥有纽约市地区中的其他节点作为其前任 和继任，而不是在东京和悉尼的前任和继任。类似地，在这个例 子中，在分解P2P网络之后，在需要在较长距离内执行任何搜索 之前，搜索可以被定位在子网内（假设请求本地可用的文件）并 且被定位在地理上相邻的子网内（再次假定请求可用的文件）。 以这种方式，由纽约市中的节点所交换的任何消息/信息所穿过的 距离大大减小。基于P2P网络节点的地理位置对P2P网络的分解 可以以任何合适的粒度来执行。例如，全球P2P网络的分解可以 通过基于节点所位于的大陆将节点分组成子网来执行。例如，国 家P2P网络的分解可以通过基于节点在国家内的位置将节点分组 成子网来执行（例如使用美国东部、美国中部和美国西部的子网； 使用50个州的五十个子网，等等，以及其各种组合）。例如，包 括位于纽约市内的节点的P2P网络的分解可以通过基于节点位于 其中的区将节点分组为子网来执行。从这些例子中可以看出，节 点可以利用任何适当的粒度在地理上被分组成子网。

基于P2P网络节点的地理位置以特定的粒度对P2P网络的分 解可以基于地理区域中的节点数目来执行。例如，考虑覆盖了美 国大陆的P2P网络。在这个例子中，具有更多节点的人口稠密的 州（例如纽约、加利福尼亚等）每个都可以被分解成多个子网， 而具有较少节点的多个人口较不稠密的州（例如北达科他州、南 达科他州等）可以基于地理位置被组合成单个子网。在这个例子 中，大城市（例如纽约、芝加哥、洛杉矶等）中的节点也可以被 组合以构成单个子网。应当认识到，基于P2P网络节点的地理位 置以特定的粒度对P2P网络的分解可以基于任何其他适当的因素 来执行。

基于P2P网络节点的地理位置对P2P网络的分解可以被执行 为使得节点可以基于其地理位置加入多个子网。例如，考虑覆盖 美国大陆的P2P网络，其中许多子网是针对单个州和州编组而构 成的并且附加的地区子网是针对人口稠密的地区构成的（例如用 于纽约、芝加哥、洛杉矶及其他城市的子网）。在这个例子中， 例如，新泽西中的节点可以加入新泽西的子网和纽约市的子网二 者。

如上文所指出的，基于节点的地理位置对P2P网络的分解（其 中在地理上彼此接近的节点被编组为子网）提供了许多优点，包 括网络资源利用的改进、性能的改进等。在这种情况中，在节点 之间交换的心跳消息保持在各个子网内。类似地，在这种情况下， 当搜索在地理上较远的子网内的文件时，只有初始搜索消息必须 穿过从本地子网到远程子网的相对长的地理距离，并且所有后续 搜索消息将保持在远程子网内。类似地，在这种情况下，当节点 加入或离开子网时，由于加入或离开所产生的文件传送室在子网 内的节点之间。对于所述功能中的每一个而言，相比分解网络之 前，关联的消息/文件所穿过的地理距离相对较短。

基于P2P网络节点的用户的兴趣团体对P2P网络进行的分解 可以基于任何适当的兴趣团体来执行（其也可以以任何适当的粒 度来执行）。例如，大学的P2P网络可以基于被分解成大学的系/ 领域兴趣（例如一个子网用于数学系，一个子网用于物理系等等）。 例如，音乐的P2P网络可以基于音乐类型被分解成子网（例如一 个子网用于蓝调音乐，一个子网用于乡村音乐等等）。

如上文所述，P2P网络可以利用所述分解准则的组合来被分 解。例如，用于交换大学信息的国家P2P网络可以针对国家内的 每个大学而被分解成子网，并且一个或多个大学子网还可以针对 该大学中的每个系而被分解成有关子网。例如，用于交换图书馆 书籍的州P2P网络可以针对该州内的每个郡而被分解成子网，并 且一个或多个郡子网还可以针对该郡内的每个图书馆而被分解成 有关子网。从这些例子中可以看出，P2P网络可以基于分解准则 的任何组合、以任何数目的层级而被分解成任何数目的子网。

尽管这里主要就分解P2P网络以构成具有两个层级的分解的 P2P网络而进行了描述，然而应当认识到，一个或多个子网还可 以被分解成关联的子网等等，以使得P2P网络可以被分解成具有 任何适当数目的层级的任何适当的安排。

通过考虑对图1的Chord网络100的分解以构成图2的分解 的Chord网络200，可以更好地理解为构成分解的P2P网络而对 P2P网络进行的分解。如图2所示，图2中的控制网络202等同 于图1中的Chord网络100，因为图1的Chord网络100中的所 有激活节点也都属于图2中的控制网络202。

如图2所示，分解的Chord网络200包括三个子网。子网204 分别具有与其关联的子网索引，如在用于分解的Chord网络200 的网络地图中所指明的那样。在图2中，为了清楚，假设网络索 引是二比特字段并且用于分解的Chord网络200的网络地图如下 面的表2中所指示的那样而被配置：

  子网   子网索引   204₁  00   204₂  01   204₃  10,11

表2

如图1所示，Chord网络100的六十四个节点中的三十六个 是激活的（即节点0,2-3,5-7,9,12-13,16-24,26,29-30,32, 34-35,37,41,43,45,49,51,53-54,56-58和62），并且剩余 的节点是非激活的。如图2所示，Chord网络100中的三十六个 激活节点中的每一个都是分解的Chord网络200的控制网络202 中的成员，并且Chord网络100中的三十六个激活节点的子集分 别是子网204₁、204₂和204₃的成员。

在分解的Chord网络200中，节点0,6,7,13,16,20,21,24, 29,35,43,53,56和58是子网204₁中的激活节点，节点3,7,12,16, 19,21,22,23,32,37,45,51,53,57和62是子网204₂中的激活节 点，并且节点2,5,9,12,16,17,18,19,26,29,30,34,41,45,49, 54,56和58是子网204₃中的激活节点。

在分解的Chord网络200中，控制网络202的激活节点中的 十个是子网204中的两个的成员：节点7,21和53是子网204₁和 204₂二者中的成员；节点12,19和45是子网2042和204₃二者中 的成员；并且节点9,30,56和58是子网204₁和204₃二者中的成 员。

在分解的Chord网络200中，控制网络202中的激活节点之 一是三个子网204中的每一个的成员，即节点16。

参考图3至图9，可以更好地理解分解的P2P网络的操作， 其中图3至9示出了用于执行分解的P2P网络内的功能（例如存 储文件、搜索文件等等）的方法的各种实施例。

图3示出了用于致使文件被存储在分解的P2P网络内的由节 点使用的方法的一个实施例。

在步骤302，方法300开始。

在步骤304，计算文件的子网索引。通过利用散列函数对文件 的标识符（例如文件名或其它适当的文件标识符）进行散列处理 来计算该文件的子网索引。散列函数可以是子网索引散列函数以 使得该文件的子网索引被确定为g(文件名)。散列函数可以是完全 散列处理以使得该文件的子网索引由h(文件名)的结果中的K个 最高有效位来表示，而该文件的文件ID由h(文件名)的结果中的 M个最低有效位来表示。

在步骤306，关联于该文件的子网索引的子网被标识。关联于 子网索引的子网可以利用分解的P2P网络的网络地图来标识。所 标识的子网是文件应当被存储在其中的子网。

在步骤308，关联于已标识子网的激活节点被标识。在一个实 施例中，对于关联于子网索引的一个或多个子网中的每一个而言， 子网的一个或多个激活节点被标识。

子网的激活节点可以以任何合适的方式来标识。

在一个实施例中，子网的激活节点可以利用本地存储在执行 方法300的节点中的信息来确定。

在一个实施例中，子网的激活节点可以通过利用分解的P2P 网络的控制网络搜索子网的激活节点来标识。在一个实施例中， 对子网激活节点的搜索可以利用服务定位能力来执行，例如在标 题为“METHOD AND APPARATUS FOR LOCATING SERVICES  WITHIN PEER-TO-PEER NETWORKS”的美国专利申请号 XX/XXX,XXX[律师案号Chu 19-43(ALU/130209)]中所说明和描述的 服务定位能力，在此引入该申请的全部内容作为参考。

在步骤310，发起用于致使文件被存储在每个被标识的子网中 的过程。这个过程可以是适于致使文件被存储在每个被标识子网 中的任何过程。这个过程可以是如由分解的P2P网络中使用的P2P 技术所指定的标准文件存储过程。

在步骤312，一个可选步骤，发起用于致使文件被存储在节点 的一个本地子网中（或如果该节点属于分解的P2P网络的多个子 网则被存储在该节点的多个本地子网中）的过程。

在一个实施例中，节点可以在必要或期望的情况下存储文件 到本地子网中。例如，节点可能在以下情况中想要将文件存储到 本地子网中：如果文件包括属于本地子网的信息，如果文件是经 常被本地子网的成员检索的受欢迎的文件（例如如果区域被组织 成使得本地子网的节点在地理上彼此接近，则从本地子网检索文 件比从远程子网检索更加高效），等等，以及其各种组合。

在一个实施例中，节点可以仅将文件存储到本地子网中，若 该节点被特许这样做的话。关于节点是否被特许存储文件到本地 子网中的确定可以以任何适当的方式来执行。在一个这样的实施 例中，例如，当节点加入P2P网络中时，公钥系统可以被用来认 证用户（即，在公钥系统中，每个用户被分配有能够被用来标识 该用户的数字证书，并且该证书可被用来指示该用户是否有特权 存储文件到本地子网中）。

在步骤314，方法300结束。

尽管在描述用于致使文件被存储在分解的P2P网络中的方法 时出于清楚的目的而从图3的方法300中省略，然而在一个实施 例中，为了促进对分解的P2P网络内的文件的管理，文件管理信 息可以被提供作为文件的逻辑同伴以用于促进分解的P2P网络内 的文件管理。文件管理信息可以包含于文件内和/或作为关联于该 文件的分离的文件/消息而被提供。文件的文件管理信息可以包括 适于促进分解的P2P网络内的文件管理的任何信息。在一个实施 例中，例如，文件的文件管理信息包括以下各项中的一个或多个： （1）发起将文件存储在分解的P2P网络中的存储节点的身份和/ 或希望管理分解的P2P网络中的文件存在的一个或多个（关联于 一个或多个子网的）其他节点的身份（其可以被共同称作该文件 的种子节点）；（2）文件最开始被存储在子网中的时间；（3） 用于使能单个子网和/或整个分解网络内的文件的到期的时间标记 （例如，当时间标记到期时，存储节点将查询种子节点以确定关 联于该种子节点的子网是否应当继续存储该文件；如果来自种子 节点的答复是否定的，则该文件从种子节点的子网中被删除，而 如果来自种子节点的答复是肯定的，则该时间标记可以被更新）； （4）用于实现文件从单个子网和/或从整个分解P2P子网中被智 能移除的计数器（例如，在计数器跟踪在过去n天内文件被检索 的次数的情况下，如果检索频率低于特定阈值，则存储节点将查 询种子节点以确定该种子节点的本地子网是否应当存储该文件）； 等等，以及其各种组合。应当认识到，文件管理信息可以包括适 于执行单个子网和/或整个分解P2P网络内的文件管理功能的任何 其他信息。

尽管这里主要以顺次执行的方式进行描述，然而方法300中 的至少一部分步骤可以被同时执行，或者以与参考图3所描述的 不同的顺序来执行。尽管这里就用于将文件存储到分解P2P网络 中的过程逻辑的指定实现进行了描述，然而应当认识到，用于将 文件存储到分解P2P网络中的过程逻辑可以以各种其他方式实现 同时仍支持P2P网络分解能力。

图4示出了用于定位存储于分解的P2P网络内的文件的由节 点使用的方法的一个实施例。

在步骤402，方法400开始。

在步骤404，计算文件的子网索引。通过使用散列函数对文件 的标识符（例如文件名或其他合适的文件标识符）进行散列处理 来计算文件的子网索引。散列函数可以是子网索引散列函数以使 得文件的子网索引被确定为g(文件名)。散列函数可以是完全散列 处理以使得文件的子网索引由h(文件名)的结果中的K个最高有 效位来表示，而文件的ID由h(文件名)的结果中的M个最低有效 位来表示。

在步骤406，关联于文件的子网索引的子网被标识。关联于子 网索引的子网可以利用分解的P2P网络的网络地图来标识。所标 识的子网是文件被存储在其中的子网。如果文件被存储在多个子 网中，则这些子网中的一个或多个可以利用子网索引来标识（例 如根据节点是否将在存储文件的子网中的一个、一些或全部中搜 索文件）。

在步骤408，一个可选的步骤，当多个子网利用子网索引被标 识时（即该文件被存储在多个子网中），所标识子网中的一个或 多个被选择作为要被搜索文件的子网。

在步骤410，关联于所标识（并且可选地所选择）子网的激活 节点被标识。在一个实施例中，对于利用子网索引而标识（并且 可选地从所标识子网之中选出）的一个或多个子网中的每一个而 言，子网中的一个或多个激活节点被标识。子网的激活节点可以 以任何适当的方式被标识。

在一个实施例中，子网的激活节点可以利用本地存储于执行 方法400的节点中的信息而被确定。

在一个实施例中，子网的激活节点可以通过利用分解的P2P 网络的控制网络搜索子网中的激活节点来被标识。在一个这样的 实施例中，对子网的激活节点的搜索可以利用服务定位能力来执 行，例如在标题为“METHOD AND APPARATUS FOR LOCATING  SERVICES WITHIN PEER-TO-PEER NETWORKS”的美国专利申请 号XX/XXX,XXX[律师案号Chu 19-43(ALU/130209)]中所说明和描述 的服务定位能力，在此引入该申请的全部内容作为参考。

在步骤412，发起用于搜索其激活节点被标识的每个子网内的 文件的过程。该过程可以是适于搜索节点不是其成员的P2P网络 中的文件的任何过程。所述节点可以联系激活节点以请求该激活 节点利用如由分解的P2P网络中使用的P2P技术所指定的标准文 件搜索过程来搜索其子网内的文件。对子网内文件的搜索可以利 用通过对文件标识符进行散列处理而确定的文件的文件ID来执 行。

在步骤414，方法400结束。

尽管为了清楚而省略，然而在一个实施例中，除了搜索标识 子网内的文件之外，节点也可以搜索其本地子网内的文件。

尽管为了清楚而描述为结束，然而在方法400的执行导致节 点发起一个或多个文件搜索请求消息的情况下，该节点可以继续 执行处理以支持节点发起的文件搜索请求，这包括当定位存储该 文件的节点时发起至存储该文件的节点的文件请求并且从存储该 文件的节点接收文件。

尽管这里主要描述为顺次地执行，然而方法400的至少一部 分步骤可以同时执行或以与参考图4所描述的不同的顺序执行。 尽管就用于搜索分解的P2P网络中的文件的过程逻辑的指定实现 进行了描述，然而应当认识到，用于搜索分解的P2P网络内的文 件的过程逻辑可以以各种方式实现同时仍支持P2P网络分解能 力。

尽管主要描述为分离的过程，然而应当认识到，用于致使文 件被存储在分解的P2P网络内的由节点使用的过程（如图3所示） 和用于定位存储于分解的P2P网络内的文件的由节点使用的过程 （如图4所示），包括相似的步骤以使得这两个过程可以利用其 中执行以下步骤的单个方法来实现：计算文件的子网索引，标识 关联于该文件的子网索引的子网中的一个或多个，标识所标识子 网之一中的一个或多个激活节点，以及发起用于使用激活节点来 管理分解的P2P网络中的文件的过程，其中用于使用激活节点来 管理文件的过程可以是用于致使文件被存储在网络中的过程或用 于定位网络内的文件的过程。

在一个实施例中，为了加入分解的P2P网络的子网，节点必 须首先加入分解的P2P网络的控制网络。参考图5描述根据一个 实施例的用于使得节点能够加入分解的P2P网络的子网的方法。

图5示出了用于加入分解的P2P网络的子网的由节点使用的 方法的一个实施例。

在步骤502，方法500开始。

在步骤504，节点发起加入分解的P2P网络的控制网络的请 求。加入控制网络的该请求可以以任何合适的方式发起，包括使 用用于加入P2P网络的标准过程。

在步骤506，节点确定要加入的一个或多个子网。

节点可以以任何合适的方式确定要加入的一个或多个子网。 在一个实施例中，节点能够或应当加入的子网在节点上是可用的 （例如在该节点上被管理性地配置）。在一个实施例中，通过向 另一个设备查询信息（例如分解的P2P网络的控制网络、web服 务器等），该节点获得了它能够或应当加入的子网。该节点可以 以任何合适的方式确定要加入的子网。

在一个实施例中，节点能够或应当加入的子网是从分解的P2P 网络的网络地图中确定的。在这个实施例中，网络地图可以在节 点上可用（例如在该网络地图是在节点上被管理性地配置的情况 下），或者由节点以任何合适的方式获得。在一个实施例中，例 如，当节点加入控制网络时，该节点将与其控制网络中的前任和 继任交换消息，并且网络地图可以作为所交换的信息的一部分而 被包含在内。在一个实施例中，例如，节点可以搜索具有可用网 络地图的控制网络的激活节点（例如利用服务定位能力，例如在 标题为“METHOD AND APPARATUS FOR LOCATING SERVICES  WITHIN PEER-TO-PEER NETWORKS”的美国专利申请号 XX/XXX,XXX[律师案号Chu 19-43(ALU/130209)]中所说明和描述的 服务定位能力，在此引入该申请的全部内容作为参考）。在一个 实施例中，例如，节点可以利用web技术获得网络地图（例如从 web服务器检索网络地图等）。节点可以以任何合适的方式获得 网络地图。

在一个实施例中，其中节点根据网络地图确定能够或应当被 加入的子网，网络地图可以利用适于确定能够或应当被加入的子 网的由节点使用的信息来被编码。在该实施例中，网络地图可以 利用任何合适的信息并且以任何合适的方式被编码。

在一个实施例中，适于确定能够或应当被加入的子网的由节 点使用的信息可能取决于分解P2P网络所基于的分解准则的类型 （例如地理位置、兴趣团体等，以及其各种组合）。

以下是对这种信息的不同类型的例子的描述，即适于确定能 够或应当被加入的子网的由节点使用的信息。

在一个实施例中，例如，每个子网的名称可以利用地理信息 被编码以使得节点能够分析子网名以自动选择合适的子网和/或以 使得子网名可以被显示在节点处以使得用户能够选择合适的子 网。例如，子网可以被命名为new-york-regional-network、 new-jersey-regional-network等。

在一个实施例中，例如，每个子网可以具有与其相关的地理 覆盖范围信息，以便在节点的地理位置落于子网的地理覆盖范围 内的情况下，该节点将加入该子网。地理覆盖范围信息可以利用 任何合适的方式成为专用的（例如经度和纬度、矩形的四角或任 何其他合适的方式）。不同子网的地理覆盖范围可以被设置成没 有任何区域重叠，一些区域重叠而另一些不重叠，所有区域具有 一定程度的重叠，等等。如果节点的地理位置落于多个子网的重 叠地理覆盖范围内，则该节点可以加入一个、一些或全部关联的 子网。节点的地理位置可以以任何合适的方式来确定（例如用户 输入、网络测量信息、GPS等）。

在一个实施例中，例如，每个子网都可以具有与其关联的地 理中心，以使得节点将基于从该节点的地理位置到子网地理中心 的距离来加入子网。地理中心可以以任何合适的方式来指定（例 如使用纬度和经度）。节点的地理位置可以以任何合适的方式来 确定（例如用户输入、网络测量信息、GPS等）。例如，节点可 以确定从该节点的地理位置到每个子网的地理中心的距离，然后 基于所确定的距离来选择一个或多个最接近的子网。例如，节点 可以顺次地确定从该节点的地理位置到子网地理中心的距离，直 到找到其相关距离满足阈值的子网。

在一个实施例中，例如，每个子网可以具有与其关联的若干 IP地址前缀，以便如果该节点的IP地址包含于关联于子网的IP 地址前缀中的任一个内，则该节点将加入该子网。例如，子网1 映射到IPv4前缀132.222.x.y、子网2映射到IPv4前缀133.222.x.y， 等等。

在一个实施例中，例如，每个子网的名称可以利用内容类型 信息被编码以使得节点能够分析子网名以自动选择合适的子网和/ 或使得子网名能够被显示在节点处以使得用户能够选择合适的子 网。例如，子网可以被命名为rutgers-physics-network、 rutgers-biology-network等等。

尽管上面提供了适于确定能够或应当被加入的子网的由节点 使用的不同类型信息的指定实例，然而应当认识到，可以使用任 何其他合适的信息。

尽管上面针对适于确定能够或应当被加入的子网的由节点使 用的信息类型而提供的例子主要以互相排除的方式描述了对这种 信息的使用，然而应当认识到，这种信息的任何合适的组合也可 以被用于使得节点能够确定能够或应当被加入的子网。。

在步骤508，节点发起加入要被加入的子网的请求。加入子网 的请求可以以任何合适的方式被发起，包括使用加入P2P网络的 标准过程。

在步骤510，方法500结束。

尽管为了清楚而省略，然而应当认识到，节点也可以执行确 定节点是否已加入控制网络的步骤。在一个实施例中，节点可以 确保它在从步骤504进行到步骤506之前已成功加入控制网络（例 如在节点利用从控制网络获得的信息确定哪个（哪些）子网要加 入的情况下）。在一个实施例中，例如，节点可以确保它在从步 骤506进行到步骤508之前已成功加入控制网络（例如在节点利 用从与控制网络不同的源获得的信息确定哪个（哪些）子网要加 入的情况下）。在所述实施例中，节点确保它在发起加入子网的 请求之前已成功加入控制网络。

尽管主要就用于加入分解的P2P网络的过程逻辑的指定实现 进行了描述，然而应当认识到，用于加入分解的P2P网络的过程 逻辑可以以各种其他方式实现同时仍支持P2P网络分解能力。

尽管是从正加入分解的P2P网络的节点的角度来撰写的，然 而应当认识到，关联的处理可以由控制网络的一个或多个节点来 执行以使得节点能够加入控制网络，并且类似地由节点所加入的 子网的一个或多个节点来执行以使得该节点能够加入子网。

图6示出了用于离开分解的P2P网络的由节点使用的方法的 一个实施例。

在步骤602，方法600开始。

在步骤604，节点发起离开分解的P2P网络的每个子网的请 求（即该节点当前是其成员的每个子网）。离开子网的请求可以 以任何合适的方式发起，包括使用用于离开P2P网络的标准过程。

在步骤606，进行关于节点是否是分解的P2P网络中的任何 子网的成员的确定。如果该节点仍是分解的P2P网络的任何子网 中的成员，则方法600返回到步骤606。如果该节点不再是分解的 P2P网络的任何子网中的成员，则方法600进行到步骤608。

在步骤608，该节点发起离开分解的P2P网络的控制网络的 请求。离开控制网络的请求可以以任何合适的方式被发起，包括 使用用于离开P2P网络的标准过程。

在步骤610，方法600结束。

尽管主要就用于离开分解的P2P网络的过程逻辑的指定实现 进行了描述，然而应当认识到，用于离开分解的P2P网络的过程 逻辑可以以各种其他方式实现同时仍支持P2P网络分解能力。

如这里所描述的那样，分解的P2P网络的网络地图促进了加 入分解的P2P网络、将文件存储到分解的P2P网络内、搜索分解 的P2P网络内的文件，以及与分解的P2P网络有关的类似功能。 在一些实现中，网络地图可以是相对静态，而在其他实现中，网 络地图可以是更加动态的；然而，与网络地图更改的频率无关， 有时可能会修改网络地图的至少一部分信息。

在其中网络地图可能更改的上述实施例中，网络地图也可以 包括适于管理对网络地图的修改的信息。适于管理对网络地图的 修改的信息可以包括适于该目的的任何信息，例如以下各项中的 一个或多个：网络地图的名称、网络地图的版本号、指示创建网 络地图的当前版本的时间的创建时间标记、网络地图的网络管理 员的管理员身份、网络地图的网络管理员的数字签名、用于检测 网络地图的任何未授权修改的消息摘要，等等，以及其各种组合。

通常，当网络地图更改时，应当在一段合理的时间内进行过 渡从而最小化可能由于更改网络地图而造成的破坏。在其中网络 地图可能被更改的实施例中，为了最小化可能由于网络地图更改 而造成的对分解的P2P网络的破坏，网络地图也可以包括时间间 隔值，这里称作过渡时间间隔。过渡时间间隔可以被用来以最小 化对分解的P2P网络的破坏的方式来动态地修改网络地图。

在一个实施例中，网络地图的过渡时间标记可以被节点用来 如下最小化对分解的P2P网络的破坏。节点接收更新消息。节点 将更新消息中的网络地图版本号与本地存储在该节点上的网络地 图版本号（例如来自节点处接收的上一个更新消息）进行比较从 而确定网络地图是否已更改。当节点检测到网络地图已更改时， 该节点将当前时间与指示网络地图的当前（已更改）版本被创建 的时间的创建时间标记进行比较。如果当前时间与创建时间之差 大于过渡时间间隔，则这说明网络自网络地图更改起已经稳定， 并且因此该节点应当尽快地执行任何需要的更改。如果当前时间 与创建时间之差小于过渡时间间隔，则这指示了网络由于网络地 图更改而处于过渡时期（或可能将处于过渡时期），并且因此该 节点应当在执行任何需要的更改之前等待。节点可以在执行任何 需要的更改之前等待任何适当长度的时间（例如预定的时间长度、 随机的时间长度等）。以这种方式，由于网络地图更改而对分解 的P2P网络造成的破坏可以被减少并且甚至被最小化。

过渡时间间隔可以以任何适当的方式设置，这可以取决于网 络中的节点数目以及将被或期望被网络地图更改影响的节点的数 目或百分比。

如上文所指出的，更改网络地图中的挑战之一是最小化或至 少减少由于网络地图更改而造成的分解的P2P网络的破坏量。在 该上下文中，对分解的P2P网络的破坏可以被看作是存储于分解 的P2P网络中的文件丢失、P2P网络的节点之间的文件传送（例 如在子网内和/或在子网之间）以及类似的活动。

通常，网络地图的任何信息都可以被更改；然而，对于更改 网络地图信息的期望对于不同类型的网络地图信息而言是不同 的。

例如，两个散列函数（即密钥空间散列函数f(x)和子网索引散 列函数g(x)）对于分解的P2P网络的操作而言是重要的并且因而 最有可能不被更改（尽管应当认识到可能存在需要或期望更改的 情况）。

例如，指定分解P2P网络以构成分解的P2P网络的方式的分 解准则最有可能被更改。如这里描述的那样，分解准则可以包括 以下各项中的一个或多个：地理描述符、兴趣团体描述符等，以 及其各种组合。对分解描述符的更改可能需要借由分解P2P网络 中的节点而更改子网成员（例如一些节点从子网断开连接和/或一 些节点加入子网）。如果以受控的方式执行更改，则对分解P2P 网络的破坏可能被减少或甚至被消除。在该情况下，很明显如果 大量节点在短期内离开和/或加入子网，则非常有可能破坏分解的 P2P子网。因此，对网络地图的更改应当以试图避免所有受影响 的节点同时离开和/或加入子网的方式来执行。

就更改网络地图而言，尽管已经针对可能包含于网络地图内 的信息类型的子集而提供了实例，然而应当清楚，对可能包含于 网络地图中的其他类型的信息的更改也可能导致对分解的P2P网 络的破坏。

为了减少或最小化对分解的P2P网络的破坏，应当逐步递增 地执行更改。

参考图7描述根据一个实施例的用于控制节点基于网络地图 的更改而执行更改的方式的方法。

图7示出了用于基于分解的P2P网络的网络地图中的更改而 执行更改的由节点使用的方法的一个实施例。

在步骤702，方法700开始。

在步骤704，节点检测网络地图中的更改。节点可以检测网络 地图已经以任何适当的方式更改（例如版本号、网络地图分析信 息等，以及其各种组合）。节点可以在任何合适的时间检测网络 地图中的更改（例如每当节点经由控制网络通信时，通过周期性 地联系控制网络等等，以及其各种组合）。

在步骤706，节点确定检测到的网络地图中的更改是否影响了 节点。

这个确定可以以任何合适的方式执行，其可能取决于已经更 改的网络地图中的信息类型。

例如，如果分解准则包括被指定为关联于每个子网的矩形地 理区域的地理描述符，则关于检测到的网络地图的更改是否影响 节点的确定可以包括确定该节点的地理位置并且将该节点的地理 位置与关联于每个子网的矩形地理区域相比较从而确定该节点是 其成员的子网是否需要被更改。

例如，如果分解准则包括被指定为关联于每个子网的子网名 的兴趣团体描述符，则关于检测到的网络地图的更改是否影响节 点的确定可以包括扫描每个子网名从而确定该节点是其成员的子 网是否需要被更改。

以这种方式，在节点受影响的情况下，关于检测到的网络地 图的更改是否影响节点的确定使得该节点能够确定要由该节点执 行的更改。

如果该节点未受到更改的影响，则该方法700进行到步骤 712，方法700在此结束。

如果节点受到更改的影响，则方法700进行到步骤708。

在步骤708，更改时间被确定。更改时间指示了节点在基于网 络地图中的更改而执行更改之前将等待的时间量。该更改时间可 以以任何合适的方式指定（例如被指定为在执行更改前等待的时 间长度、将来应当执行更改的时间等）。该更改时间可以以任何 适当的方式来确定（例如基于预定的等待时间长度、通过基于当 前时间随机生成时间标记等）。

在步骤710，节点在由更改时间所指示的时间执行更改。

在步骤712，方法700结束。

尽管主要就用于使得节点能够基于网络地图的更改而执行更 改的过程逻辑的指定实现进行了描述，然而应当认识到，用于使 得节点能够基于网络地图的更改而执行更改的过程逻辑可以以各 种其他方式来实现同时仍支持P2P网络分解能力。

当在一个时间间隔内基于网络地图的更改而执行对分解P2P 网络的更改时，应当认识到，图7的方法700仅由作为分解P2P 网络成员的节点在网络地图更改时所需要，因为加入分解的P2P 网络的任何节点在网络地图更改后将加入由网络地图所指示的分 解P2P网络。

从上述内容可以看出，通过逐步递增地更改网络地图并且在 一个合理的时间间隔内展开节点更改，由于网络地图更改而造成 的对分解P2P网络的破坏能够被减少并且可能甚至被消除。

如这里描述的那样，网络地图的更改可以包括对网络地图中 任何类型的信息的更改，这包括子网索引映射。就更改子网索引 映射而言，基本上有两种递增更改：（a）将子网索引添加给子网 和（b）从子网中删除子网索引。将子网索引从第一子网移至第二 子网这一情形可以被处理为后随一“删除”操作的“添加操作”。 然而，针对该情形存在一个附加的问题：即，当子网索引被添加 给第二子网时，第一子网需要将该子网索引的文件传送至第二子 网。参考图8A-8E描述说明了将文件从第一子网传送到第二子网 的过程的例子，并且参考图9描述了将文件从第一子网传送到第 二子网的更一般的过程。

图8A-8E示出了说明将文件从第一子网传送到第二子网的过 程的例子。

在这个例子中，令P2P网络是Chord网络，并且假设现有子 网B当前被分配有子网索引10001并且网络管理员想要创建具有 分配给它的子网索引10001的新的子网A。网络管理员将更新网 络地图以反映新的子网A以及子网索引10001向新子网A的分配。 网络管理员也将更新网络地图以便指示Chord网络的节点网络地 图已经被更新（例如更改网络地图的版本号）。网络管理员将在 Chord控制网络上广播更新的网络地图。更新的网络地图可以在 Chord控制网络上以任何合适的方式被广播。例如，如果Chord 控制网络被实现为支持也可以被用来提供广播能力的服务定位能 力的Chord控制网络，例如在标题为“METHOD AND APPARATUS  FOR LOCATING SERVICES WITHIN PEER-TO-PEER NETWORKS” 的美国专利申请号XX/XXX,XXX[律师案号Chu 19-43(ALU/130209)] 中所说明和描述的服务定位能力，在此引入该申请的全部内容作 为参考，则更新的网络地图可以利用广播能力被广播。除了通过 对更新的网络地图的广播来学习更新的网络地图之外，Chord控 制网络的节点也可以通过与它们的Chord控制网络上的前任和继 任所交换的心跳消息来学习更新的网络地图（例如在一些广播消 息失败的情况下）。以这种方式，Chord控制网络中的所有节点 都被通知了更新的网络地图。

在这个例子中，由于子网所有A被新配给新的子网A，新的 子网A可能不具有与存储于新子网A中的子网所有10001相关联 的所有文件。结果，当节点首先加入新子网A时，该节点可能想 要从支持子网索引10001的另一子网（即该例子中为子网B）获 取关联于子网索引10001的文件。在这个例子中，假设节点1000 利用Chord网络的标准加入程序而加入新子网A。下面描述节点 1000获取关联于子网索引10001的文件以存储在新子网A中的过 程。

如图8A所示，节点1000加入新子网A，并且节点900是节 点1000的前任并且节点1100是新子网A内的节点A的继任。当 加入新子网A时，继任节点1100传送其文件ID在901至1000 之间的所有文件给节点1000（然而该列表可能并不完整，因为子 网A是新构成的）。由于这个文件列表可能不完整，因此节点1000 可能想要确定它确实拥有了它在新子网A中负责的所有必需的文 件。

如图8B所示，节点1000标识子网B（即标识支持子网索引 10001的另一个子网，其在该例子中是子网B），并且如果节点 1000不是子网B的成员，则节点1000在子网B中搜索它自己。 如图8B中进一步显示的那样，由于在子网B中搜索它自己，节点 1000标识了子网B中具有大于并且最接近于节点1000的节点ID 的节点（在该例子中说明性地是节点1050）。

如图8C所示，节点1000然后在子网B中搜索节点900（即 它自己在新子网A中的前任，其再该例子中是节点900）。如图 8C中进一步显示的那样，由于在子网B中搜索它的前任，节点 1000标识了子网B中具有大于并且最接近于节点900的节点ID 的节点（在该例子中说明性地是节点920）。

如图8D所示，节点1000标识了子网B中在节点920至节点 1050之间的所有节点。节点1000能够通过查询每个节点来确定这 些节点（因为所有节点都知道其前任和继任各自的身份）。如图 8D所示，为了清楚，假定在节点920至节点1050之间只有一个 节点在子网B中是激活的，即节点950。

如图8E所示，节点1000从子网B中的所标识节点获得了关 联于子网索引10001并且具有901至1000之间的文件ID的任何 文件，所述文件已经不被节点1000存储。节点1000向所标识的 节点920、950和1050中的每一个查询这些节点所存储的关联于 子网索引10001并且具有901至1000之间的文件ID的文件列表。 节点1000然后将该文件列表与节点1000已经存储的文件相比较。 节点1000然后检索其已经不存储的关联于子网索引10001并且具 有901至1000之间的文件ID的任何文件。

图9示出了用于当在分解的Chord网络中初始化Chord子网 时使得第一子网的节点能够从第二子网获取文件的方法的一个实 施例。

在步骤902，方法900开始。

在步骤904，节点加入第一子网。该节点的节点ID为N并且 第一子网的子网索引为J。

在步骤906，该节点确定其第一子网内的前任。该前任节点的 节点ID为P。

在步骤908，该节点标识子网索引为J的另一个子网（表示为 第二子网，从该第二子网获取文件）。

在步骤910，该节点在第二子网中搜索它自己（在第二子网中 搜索节点ID为N的节点）。搜索结果是节点N接收子网中节点 ID大于并且最接近于节点ID N的节点的指示。所产生的节点标 记为节点N1。

在步骤912，该节点搜索第二子网中的前任P（在第二子网中 搜索节点ID为P的节点）。搜索结果是节点N接收子网中节点 ID大于或最接近于节点ID P的节点的指示。所产生的节点标记为 节点N2。

在步骤914，该节点标识第二子网中在节点N1和节点N2之 间的所有节点（Ni）。

在步骤916，该节点标识存储于所标识的节点Ni中的具有子 网索引J的所有文件。在一个实施例中，例如，该节点发起关于 标识存储于所标识节点Ni中的具有子网索引J的所有文件的查 询，并且从所标识节点Ni接收查询响应，该响应指示了存储于所 表示节点Ni中的具有子网索引J的所有文件。

在步骤918，该节点确定应当被存储在节点中的哪些所标识文 件（若有的话）当前并未存储于节点中。当前未存储于节点中但 应当存储于节点中的所确定文件是基于文件ID和节点ID来确定 的（即具有P至N之间的文件ID的文件，包括N）。

在步骤920，节点从所标识节点Ni获取当前未存储于该节点 中的任何所标识文件。在一个实施例中，例如，节点发起对当前 未存储于节点中的任何所标识文件的请求，并且从所标识节点Ni 接收所请求的文件。

在步骤922，节点存储所获得的文件以使得它们在第一子网中 可用。

在步骤924，方法900结束。

尽管主要就用于使得加入第一子网的节点能够从第二子网获 取文件的过程逻辑的指定实现进行了描述，然而应当认识到，用 于使得加入第一子网的节点从第二子网获取文件的过程逻辑可以 以各种其他方式来实现同时仍支持P2P网络分解能力。

在上面描述的关于使得新子网的节点能够从分解的Chord网 络中的现有子网获取文件的实施例中，当新子网最初被构成时， 该新子网中可能只有少数激活节点，并且因此加入节点与其前任 之间的间隙可能较大。结果，当新节点在具有匹配的子网索引的 现有子网中搜索文件时，新节点可以标识大量的文件。在一个实 施例中，新节点可以只检索并存储所标识文件的子集（例如来自 按照降序的所标识节点的有限数目的文件，或任何其他合适的子 集）。在这个实施例中，随着时间推进，更多的节点可能将加入 新子网A，其中至少一些节点可能在新节点与其当前前任之间， 并且加入新子网的新节点能够执行类似的程序以获得之前无法从 现有子网获得的任何文件。

在上述实施例中，由于新加入的节点为新子网获取文件，新 子网以及时且有序的方式获取了具有关联的子网索引的大多数文 件。然而，由于新子网和现有子网二者都是节点在此加入和离开 子网的动态网络，有可能并非所有文件利用上述实施例被传送到 新子网。因此，在一个实施例中，对于每个文件，文件的种子节 点在新子网中搜索该文件（例如以规律的时间间隔，或以任何其 他合适的时间帧），并且如果种子节点确定该文件遗漏，则种子 节点能够将文件传送到新子网中负责存储该文件的节点。在一个 这样的实施例中，这个程序能够在新子网已稳定时或至少被确定 为相对稳定时被执行或激活。

在上面描述的用于使得新子网的节点能够从分解的P2P网络 中的现有子网获取文件的实施例中，分解的P2P网络是分解的 Chord网络。应当认识到，通过根据其他类型的P2P网络的原理 （例如Pastry、Tapestry等）修改上述实施例，可以在其他类型 的P2P网络中支持类似的能力。

在一个实施例中，例如，上面描述的用于使得新子网的节点 能够从分解的Chord网络中的现有子网获取文件的实施例可以被 修改以使得新子网的节点能够从分解的Pastry网络中的现有子网 获取文件。作为例子，考虑分解的Pastry网络这一情形，其中新 节点x加入具有新分配给它的子网索引10001的新子网A。新节 点x将标识具有分配给它的子网索引10001的子网B。新节点x 然后在所标识的子网B中搜索它自己（在这个例子中假设新节点 x不是所标识子网B的成员，因为如果新节点x已经是所标识子 网B的成员则该搜索就并非必要）。该搜索产生了所标识子网B 中的节点y。在Pastry中，节点y维护“叶集合”，该叶集合包 括与节点y的节点ID接近的节点的节点ID（在该例子中，令节 点y的叶集合的节点是z₁,z₂,...z_x）。新节点x然后标识具有子网 索引10001的文件，所述文件被存储在节点y以及其叶集合z₁, z₂，...z_x中。新节点x然后标识新节点x当前并未存储的所标识文 件。新节点x然后向节点y及其叶集合z₁,z₂,…z_x请求并接收新节 点x当前并未存储的所标识文件，并且存储所接收的文件。因此， 从这个例子中可以看出，图9的方法900可以以使得新子网的节 点能够从分解的Pastry网络中的现有子网获取文件的方式来被修 改。

根据上面描述的用于使得新子网的节点能够从分解的Chord 或Pastry网络中的现有子网获取文件的实施例，应当认识到，用 于使得新子网的节点能够从现有子网获取文件的Chord指定的和 Pastry指定的方法，可以被进一步一般化为适用于任何类型的P2P 网络。在一个实施例中，用于使得新子网的节点能够从分解的P2P 网络中的现有子网获取文件的方法包括：（1）由支持子网索引的 新子网中的新节点搜索支持该子网索引的现有子网中最接近的节 点；（2）获取所标识的最接近节点的邻居集合（例如该邻居集合 可以是一个或多个节点的前任/继任组合，叶集合，或任何其他合 适的集合）；（3）从所述邻居集合的节点中标识具有该子网索引 的文件；和（4）请求、接收并存储当前并未存储于新节点中的至 少一部分所标识文件。

尽管这里主要就其中子网与子网索引之间的映射是一对一或 至少相对近似于一对一的实施例进行了描述（例如一个或多个子 网可以具有分配给它（们）的多个子网索引，但仍是整个子网索 引集合中的一小部分；例如，一个或多个子网索引可以被分配给 多个子网，但仍是具有分配给它（们）的多个子网索引的子网的 整个集合的一小部分），在其他实施例中，子网与子网索引分配 之间的重叠可能增加。这增加了文件下载是在网络内而不是在网 络间的概率，并且因而改进了网络资源利用、性能以及可靠性； 然而，网络资源利用率、性能和可靠性方面的改进是以为将大量 文件多次存储于多个不同子网中所需要的存储能力的相关增加为 代价的。在一个实施例中，子网索引可以与子网成员的大小成比 例地分配（例如具有较多成员的子网可以被分配以更多的子网索 引，以使得所需要的存储能力在子网之中公平地划分）。在一个 实施例中，一个极端的情形，每个子网索引被分配给每个子网以 使得每个子网存储分解的P2P网络的所有文件。以这种方式，在 网络资源利用率、性能和可靠性方面的改进可以相对于增加的存 储能力的成本而获得平衡。

尽管这里主要就其中只给予子网索引而将文件存储到分解的 P2P网络的子网内的实施例进行了描述，然而在其他实施例中， 文件也可以基于除子网索引之外的其他准则而被存储在分解的 P2P网络的子网内，例如基于受欢迎程度或任何其他合适的准则。 在一个实施例中，在特定子网中受欢迎的文件（或甚至被认为是 跨特定数目的子网或子网集合而受欢迎，或甚至跨整个分解的P2P 网络）可以被存储在本地子网中（除了被存储在具有关联于该文 件的子网索引的子网中之外）。在一个这样的实施例中，当节点 搜索文件时，节点将搜索其本地子网以及具有关联于该文件的子 网索引的子网。在该情况下，如果该文件被存储在本地子网中， 则执行搜索的节点将从本地子网获得该文件，或者从支持该文件 的子网索引的子网获得该文件。在其中分解（至少部分上）基于 地理准则的分解的P2P网络中，这在网络成本方面将是高效的， 尽管可能在存储成本上代价更高。在该实施例中，该文件可以从 本地子网中移除（例如在稍后的时间，例如当文件的受欢迎程度 在本地子网内或跨分解的P2P网络减小），同时仍然可从支持该 文件的子网索引的子网获得。在一个这样的实施例中，应当认识 到，受欢迎程度可以以任何合适的方式被度量或确定。

尽管主要就其中子网索引是作为散列函数输出的K比特字段 的实施例进行了描述，在其他实施例中，关联于分解的P2P网络 的子网的子网索引可以在不使用散列函数的情况下被确定。在一 个这样的实施例中，例如，子网的子网索引可以利用天然索引来 设定。作为例子，考虑可能将书籍电子地存储到P2P网络中的图 书馆的情况。在这个例子中，子网可以通过主题来安排，例如数 学子网、物理子网等。在该例子中，所使用的天然索引将是杜威 十进制系统（Dewy Decimal System），因为通过使用杜威十进制 系统将自然导致数学书籍被存储在数学子网中、物理书籍被存储 在物理子网中等等。另外，特定系的感兴趣的书籍也可以被存储 在其他子网中，例如物理系可能想要在物理子网中本地存储一些 数学书籍。尽管主要就使用杜威十进制系统进行了描述，然而应 当认识到，在其他应用中也可以使用各种其他天然索引。

P2P网络分解能力为P2P网络提供了许多益处。

P2P网络分解能力通过将P2P网络分解成子网而改进了P2P 网络的可扩缩性。P2P网络分解能力改进了P2P网络内的文件搜 索性能。当节点搜索文件时，该文件可能定位于与该节点的本地 子网不同的一个子网中，例如在目标子网中而不是在本地子网中。 第一文件搜索可能从节点的本地子网行进至目标子网，然而，定 位文件所需要的所有后续搜索消息将保持在目标子网中。因此， 如果P2P网络的分解是基于“距离”的，则所有搜索消息（除了 目标网络外部的第一批消息）都被定位在目标子网中，并且因而 搜索消息所行进的距离被最小化。这将改进其中地理位置没有在 结构中被说明的P2P网络（例如Chord网络）的性能。这也将改 进可以支持对位置/距离度量的有限使用的P2P网络的性能，因为 位置/距离度量可以是子网特定的。例如，在支持接近性度量的 Pastry网络中，接近性度量仅需要针对同一子网内的节点来限定。 在该例子中，在其中子网覆盖较小地理范围这一极端情形中，子 网中的接近性度量可以被设定成常数（即子网内所有节点具有相 同的距离），这将使得网络管理员限定接近性功能的工作变得容 易。

所提供的P2P网络分解能力使得就节点ID而言，给定节点的 邻居属于同一子网。结果，当节点加入或离开网络时，邻居间的 更新消息和文件传送保持在同一子网内。如果P2P网络的分解是 基于地理的，则更新消息和文件传送所行进的距离被最小化，由 此最小化了在节点间传播这种信息所需要的时间并且减少了在节 点间传播这种信息所消耗的网络资源量。如果分解是基于其他分 解准则的，则实现其他益处。因此，P2P网络的性能被改进。

P2P网络分解能力使得P2P网络能够基于任何合适的分解准 则而被分解，例如基于几何、兴趣团体等中的一个或多个，以及 其各种组合。这实现了高效且鲁棒的P2P网络分解。

P2P网络分解能力使得每个文件能够被存储在指定的子网中 并且可选地也可以使得一些或全部文件被存储在多个子网中（例 如文件的附加拷贝能够被存储在除了指定子网之外的一个或多个 子网中）。这改进了P2P网络的性能和可靠性。

P2P网络分解能力提供了许多其他益处，这对于读过这里提 供的对P2P网络分解能力的描述的本领域技术人员而言是显而易 见的。

尽管这里主要就其中利用控制网络来提供P2P网络分解能力 的实施例进行了描述，然而P2P网络分解也可以在不使用控制网 络的情况下被提供。在一个实施例中，例如，每个子网被配置成 具有一个或多个永久激活的节点，而不是使用控制网络，其中永 久激活节点的身份对于P2P网络的所有节点都是可用的以便每个 节点都可以搜索节点、服务和其他控制信息。永久激活节点的身 份可以以任何适当的方式对于所有节点可用，例如提供网络地图 的扩展、经由web服务器等。

尽管这里主要就其中P2P网络是Chord网络的实施例进行了 描述，然而P2P网络分解能力可以在其他类型的P2P网络内实现， 例如Pastry、Tapestry等。

尽管这里主要描述了P2P网络分解能力，然而P2P网络分解 能力的原理也可以被应用成用于融合组件P2P网络的P2P网络融 合能力以构成融合的P2P网络。融合的P2P网络类似于分解的P2P 网络，因为融合P2P网络的每个组件网络都类似于分解的P2P网 络的子网。组件P2P网络可以属于相同或不同的P2P技术。当分 解P2P网络时，P2P网络可以被分解成使得所有子网都使用相同 的密钥空间和相同的对象-ID散列函数（因为它们是从被分解的原 始P2P网络中被继承的）。然而，当融合组件P2P网络以构成融 合的P2P网络时，有可能被融合的组件网络使用不同的密钥空间 和不同的对象-ID散列函数。结果，为构成融合的P2P网络而对 组件P2P网络的融合可以在考虑了以下一个或多个考虑的情况下 被执行。

对于P2P网络融合能力而言，所有组件网络应当使用相同的 散列函数来计算网络索引（例如通过选择组件网络之一的散列函 数或选择要由组件网络使用的一些其他合适的散列函数）。

对于P2P网络融合能力而言，所有组件网络应当支持相同的 文件命名约定，并且当一个节点从另一个组件网络中的另一个节 点请求文件时，应当使用该文件的文件名而不是文件名的散列值， 因为不同的组件网络可能使用不同的散列函数。

对于P2P网络融合能力而言，控制网络应当使用支持允许每 个节点搜索属于特定组件网络的其他节点的服务定位能力的P2P 技术（例如具有服务定位能力的Chord网络，例如在标题为 “METHOD AND APPARATUS FOR LOCATING SERVICES WITHIN  PEER-TO-PEER NETWORKS”的美国专利申请号XX/XXX,XXX[律 师案号Chu 19-43(ALU/130209)]中所说明和描述的服务定位能力， 在此引入该申请的全部内容作为参考）。

对于P2P网络融合能力而言，组件网络可能使用不同的密钥 空间和不同的散列函数。当融合的P2P网络的两个组件网络使用 不同的密钥空间和散列函数时，同时加入两个组件网络的节点将 具有两个不同的节点ID并且将针对两个组件网络存储不同的文 件，并且一个组件网络中的相邻的（就节点ID而言）两个节点可 能在另一个组件网络中不是邻居。结果，当组件网络被分配以新 的网络索引时，它不能使用上述过程来快速填充网络；相反，文 件将通过有关种子节点而被载入组件网络。

图10示出了用于执行这里描述的功能的计算机的高级框图。 如图10所示，计算机1000包括处理器元件1002（例如中央处理 单元（CPU）或其它合适的处理器）、存储器1004（例如随机访 问存储器（RAM）、只读存储器（ROM）等）、服务定位搜索模 块/过程1005以及各种输入/输出设备1006（例如用户输入设备（例 如键盘、电脑小键盘、鼠标等）、用户输出设备（例如显示器、 扬声器等）、输入端口、输出端口、接收器、发送器和存储设备 （例如磁盘驱动器、软盘驱动器、硬盘驱动器、光盘驱动器等））。

应当指出，这里描述的功能可以被实现为软件和/或软件和硬 件的组合，例如利用通用计算机、一个或多个专用集成电路 （ASIC）、和/或任何其他等同的硬件。在一个实施例中，服务位 置搜索过程1005可以被载入存储器1004并且由处理器1002执行 以实现如这里描述的功能。同样，服务位置搜索过程1005（包括 关联的数据结构）可以被存储在计算机可读存储介质或载体上， 例如RAM存储器、磁或光的驱动器或磁盘等等。

设想被实现为软件的这里讨论的功能的一部分可以以任何合 适的方式被配置在对等网络的节点上（例如在制造节点时提供、 管理性地载入节点、从web服务器或其他合适的源下载等，以及 其各种组合）。设想作为软件方法的这里讨论的步骤的一部分可 以被实现在硬件内，例如与处理器配合以执行各种方法步骤的电 路。这里描述的功能/元素的一部分可以被实现为计算机程序产品， 其中计算机指令当被计算机处理时适配计算机的操作以使得这里 描述的方法和/或技术被调用或被提供。用于调用本发明方法的指 令可以被存储在固定或可去除介质中、经由数据流被传送到广播 或其他信号承载介质中、和/或存储在按照指令操作的计算设备的 存储器内。

本发明的各方面在权利要求中指明。本发明的所述和其他方 面在以下编号的条款中指明：

1.一种用于使得节点能够加入包括多个子网的分解的对等 （P2P）网络的方法，该方法包括：

向请求加入所述分解的P2P网络的节点传播网络地图，该网 络地图包括多个子网索引与所述分解的P2P网络的多个子网的映 射。

2.根据条款1的方法，还包括：

将对所述分解的P2P网络的分解编码到所述网络地图中。

3.根据条款1的方法，其中，对所述分解的P2P网络的分 解是基于至少一个分解准则的。

4.根据条款3的方法，其中，所述至少一个分解准则包括 节点的地理位置和兴趣团体中的至少一个。

5.根据条款1的方法，其中，对于每个子网而言，所述子 网具有一个或多个与其映射的子网索引。

6.根据条款1的方法，其中，所述网络地图还包括以下各 项中的至少一个：

散列处理的信息，其适于被所述节点用来生成对象标识符用 以将文件存储到所述分解的P2P网络中或在所述分解的P2P网络 中定位文件；

针对每个子网的一个或多个描述符，其适于被所述节点用来 确定要加入的子网；和

网络地图管理信息。

7.一种用于使得节点能够加入包括多个子网的分解的对等 （P2P）网络的方法，该方法包括：

从所述节点发起适用于获取所述分解的P2P网络的网络地图 的消息，和

在所述节点接收所述分解的P2P网络的网络地图，

其中，所述网络地图包括多个子网索引与所述分解的P2P网 络的多个子网的映射。

8.根据条款7的方法，其中，所述请求是朝向以下各项中的 至少一个被发起的：

所述分解的P2P网络的控制网络的至少一个节点；和

网络设备。

9.根据条款8的方法，其中，当所述请求朝向所述分解的 P2P网络的控制网络的至少一个节点发起时，所述请求时朝向所 述控制网络中的所述节点的前任节点或继任节点发起的。

10.根据条款7的方法，其中，对所述分解的P2P网络的分 解是基于至少一个分解准则的。

11.根据条款10的方法，其中，所述至少一个分解准则包括 节点地理位置和兴趣团体中的至少一个。

12.根据条款7的方法，其中，对于每个子网而言，所述子网 具有一个或多个与其映射的子网索引。

13.根据条款7的方法，其中，所述网络地图还包括以下各项 中的至少一个：

散列处理的信息，其适于被所述节点用来生成对象标识符用 以将文件存储到所述分解的P2P网络中或在所述分解的P2P网络 中定位文件；

针对每个子网的一个或多个描述符，其适于被所述节点用来 确定要加入的子网；和

网络地图管理信息。

14.根据条款7的方法，还包括：

发起加入所述分解的P2P网络的控制网络的请求，其中所述 控制网络是P2P网络；和

向所述控制网络中的至少一个节点传播适用于获取所述分解 的P2P网络的网络地图的消息。

15.一种用于使得节点能够管理包括多个子网的分解的对等 （P2P）网络中的文件的方法，该方法包括：

计算所述文件的子网索引；

标识关联于所述文件的子网索引的子网之一；

标识所述子网中的被标识子网中的激活节点；和

发起用于使用所述激活节点来管理所述分解的P2P网络中的 文件的过程。

16.根据条款15的方法，其中，所述文件的子网索引是利用 散列函数和所述文件的文件名来计算的。

17.根据条款15的方法，其中，当多个子网被标识成关联于 所述文件的子网索引时，所述多个子网中的每一个的激活节点都 被标识，并且用于管理所述文件的所述过程是以使用所述多个子 网的每个被标识激活节点来管理文件的方式来发起的。

18.根据条款15的方法，其中，标识关联于所述文件的子网 索引的所述子网之一包括：

利用所述文件的子网索引搜索网络地图，

其中，所述网络地图针对每个子网而包括所述子网与一个或 多个子网索引的映射。

19.根据条款15的方法，其中，管理所述文件包括将所述文 件存储到所述分解的P2P网络中。

20.根据条款19的方法，其中，用于管理文件的所述过程包 括用于使得所述文件被存储到所述子网中的被标识子网中的被标 示激活节点中的过程。

21.根据条款20的方法，还包括：

向所述子网中的被标识子网中的激活节点传播所述文件。

22.根据条款19的方法，还包括:

发起用于致使所述文件被存储在所述节点是其成员的所述子 网之一中的过程。

23.根据条款15的方法，其中，管理所述文件包括在所述分 解的P2P网络中定位所述文件。

24.根据条款23的方法，其中，用于管理文件的所述过程包 括用于使用激活节点来搜索所述子网中的被标识子网中的文件的 过程。

25.根据条款24的方法，其中，发起用于使用所述激活节点 来搜索所述子网中的被标识子网中的文件的所述过程包括：

向所述激活节点传播关于该激活节点搜索所述子网中的被标 识子网中的文件的请求。

尽管这里已经详细显示和描述了纳入本发明教学的各种实施 例，然而本领域技术人员可以容易地设想仍纳入所述教学的许多 其他不同的实施例。