虚拟网络

摘要

一种虚拟网络具有多个节点的，每个节点都具有一列表，该列表用于存储多达预定数量(L)个表示到其他这种节点的链接的地址。通过以下步骤管理这些链接：接收(300)请求第一节点与第二节点之间的链接的消息；确定(301、305)第一节点和第二节点是否在每种情况下都在其列表中具有比预定数量要少的数量个地址；在满足该条件的情况下，将第一节点的地址插入(308)到第二节点的列表中，并将第二节点的地址插入(307)到第一节点的列表中；在不满足该条件的情况下，确定(309)第一节点在其列表中是否具有比所述预定数量少至少两个的数量个地址，如果满足此，则：(a)从第二节点的列表中选择(310)第三节点的地址；(b)从第二节点的列表删除(313)第三节点的地址；(c)从第三节点的列表删除(314)第二节点的地址；以及(d)将第二节点的地址插入(311)到第一节点的列表中，并将第三节点的地址插入(312)到第一节点的列表中；(e)将第一节点的地址插入(313)到第二节点的列表并将第一节点的地址插入(314)到第三节点的列表。

权利要求

1.一种用于操作具有多个节点的虚拟网络的方法，其中每个节点都具有用于存储多达预定数量个其他这种节点的地址的列表，该方法包括以下步骤：(i)接收用于请求第一节点与第二节点之间的链接的消息；

(ii)确定第一节点和第二节点是否在每种情况下都在其列表中具有比预定数量要少的多个地址；

(iii)在步骤(ii)中的确定结果是肯定的情况下，将第一节点的地址插入到第二节点的列表中，并将第二节点的地址插入到第一节点的列表中；

(iv)在步骤(ii)中的确定结果是否定的情况下，确定第一节点在其列表中是否具有比所述预定数量少至少两个的多个地址，并且在步骤(iv)中的确定结果是肯定的情况下，则：(a)从第二节点的列表中选择第三节点的地址；

(b)从第二节点的列表中删除第三节点的地址；

(c)从第三节点的列表中删除第二节点的地址；并且(d)将第二节点的地址插入到第一节点的列表中，并将第三节点的地址插入到第一节点的列表中；

(e)将第一节点的地址插入到第二节点的列表中，并将第一节点的地址插入到第三节点的列表中。

2.如权利要求1所述的方法，其中，在第一节点处接收请求链接的消息，并且其中，在步骤(iii)中：把第二节点的地址连同表示它未被确认的标记插入到第一节点的列表中；

从第一节点向第二节点发送一消息，该消息请求第二节点将第一节点的地址添加到第二节点的链接；

在第二节点处照此添加所述第一节点的地址并向第一节点发送确认消息；以及在第一节点处，当接收到确认消息时删除“未确认”标记。

3.如权利要求2所述的方法，其中，节点在接收到请求其向其列表添加指定节点的地址的消息时，首先向该指定节点发送请求该指定节点的列表的副本的消息，然后仅在它从该指定节点接收到包含有接收该请求的节点的地址的列表时，遵照所述添加请求。

4.如前述任一权利要求所述的方法，其中在第一节点处接收请求链接的消息，并且其中：第一节点向第二节点发送对第二节点的列表的副本的请求；

第二节点向第一节点发送所请求的副本；

在第一节点处执行从所述第二节点的列表选择第三节点的地址的步骤(iv)(a)；并且按如下方式执行步骤(iv)(a)和(b)：第一节点向第一节点的列表添加第二节点的地址和第三节点的地址，在每种情况下都连同添加表示它未被确认的标记；

第一节点向第二节点发送一消息，该消息请求第二节点从它的列表删除第三节点的地址并将其替换为第一节点的地址；

第一节点向第三节点发送一消息，该消息请求第三节点从它的列表删除第二节点的地址并将其替换为第一节点的地址；

第二节点在接收到这种消息时从它的列表删除第三节点的地址，将其替换为第一节点的地址，并向第一节点发送确认消息；

第三节点在接收到这种消息时从它的列表删除第二节点的地址，将其替换为第一节点的地址，并向第一节点发送确认消息；

第一节点在接收到来自第二或第三节点的确认消息时从它的列表删除相应的“未确认”标记。

5.如权利要求4所述的方法，其中，节点在接收到请求其从其列表删除另一节点的地址并将其替换为指定节点的地址的消息时，首先向该指定节点发送请求该指定节点的列表的副本的消息，然后仅在其从该指定节点接收到包含有接收该请求的节点的地址的列表时，才遵照从节点的列表删除另一节点的地址并将其替换为该指定节点的地址的请求。

6.如权利要求3所述的方法，其中，通过中间节点来发送针对所述指定节点的列表请求消息和对这种消息的回复，其中不把发送列表请求消息的节点的地址通知给所述指定节点。

7.如权利要求1-3、6的任一项所述的方法，其中，各节点还具有用于存储至少一个备用链接的装置，所述方法还包括：当第一节点在它的列表中具有等于预定数量的多个地址时，在接收到请求第一节点与第二节点之间的链接的消息的情况下，将第二节点的地址存储到第一节点的备用链接存储装置中；并且当接收到后面的请求第一节点与另一节点之间的链接的消息时，将该消息转发给从第一节点的备用链接存储装置获取的地址。

8.一种用于操作具有多个节点的虚拟网络的装置，每个节点都具有用于存储多达预定数量个其他这种节点的地址的列表，该装置包括以下单元：第一单元，用于接收用于请求第一节点与第二节点之间的链接的消息；

第二单元，用于确定第一节点和第二节点是否在每种情况下都在其列表中具有比预定数量要少的多个地址；

第三单元，用于在第二单元中的确定结果是肯定的情况下，将第一节点的地址插入到第二节点的列表中，并将第二节点的地址插入到第一节点的列表中；

第四单元，用于在第二单元中的确定结果是否定的情况下，确定第一节点在其列表中是否具有比所述预定数量少至少两个的多个地址，并且在第四单元中的确定结果是肯定的情况下，则：(a)从第二节点的列表中选择第三节点的地址；

(b)从第二节点的列表中删除第三节点的地址；

(c)从第三节点的列表中删除第二节点的地址；并且(d)将第二节点的地址插入到第一节点的列表中，并将第三节点的地址插入到第一节点的列表中；

(e)将第一节点的地址插入到第二节点的列表中，并将第一节点的地址插入到第三节点的列表中。

9.一种用于操作虚拟网络的节点的方法，该节点由存储装置和处理装置限定，该存储装置包含有用于存储多达预定数量个其他这种节点的地址的列表，该方法包括以下步骤：接收消息；

响应用于请求有关所述列表的内容的信息的消息；

遵照接收的请求从该列表删除地址；

遵照请求将地址插入到该列表中的消息；以及

响应于接收到请求第一节点与第二节点之间的链接的消息：(A)生成到第二节点的消息，该消息请求有关第二节点的列表的内容的信息；

(B)确定第一节点和第二节点是否在每种情况下都在各自的列表中具有比预定数量要少的多个地址；

(C)在满足该条件的情况下，将第二节点的地址插入到第一节点的列表中，并生成到第二节点的消息，该消息用于请求第二节点向其列表添加第一节点的地址；

(D)在不满足该条件的情况下，确定第一节点在其列表中是否具有比所述预定数量少至少两个的多个地址，如果满足此，则：(a)从第二节点的列表中选择第三节点的地址；

(b)将第二节点的地址插入到第一节点的列表中，并将第三节点的地址插入到第一节点的列表中；

(c)生成到第二节点的消息，该消息请求从第二节点的列表中删除第三节点的地址并插入第一节点的地址；以及(d)生成到第三节点的消息，该消息请求从第三节点的列表中删除第二节点的地址并插入第一节点的地址。

说明书

虚拟网络

技术领域

[0001] 本发明涉及虚拟网络，更具体地，尽管并非专门在诸如对等系统的分布式系统的环境下，尤其涉及没有中央化存储或控制的虚拟网络。

发明内容

[0002] 根据本发明的一个方面，提供了一种用于操作具有多个节点的虚拟网络的方法，其中每个节点都具有用于存储多达预定数量个其他这种节点的地址的列表，该方法包括以下步骤：

[0003] (i)接收用于请求第一节点与第二节点之间的链接的消息；

[0004] (ii)确定第一节点和第二节点是否在每种情况下都在其列表中具有比预定数量要少的数量个地址；

[0005] (iii)在满足该条件的情况下，将第一节点的地址插入到第二节点的列表中，并将第二节点的地址插入到第一节点的列表中；

[0006] (iv)在不满足该条件的情况下，确定第一节点在其列表中是否具有比所述预定数量少至少两个的数量个地址，并且如果满足此，则：

[0007] (a)从第二节点的列表中选择第三节点的地址；

[0008] (b)从第二节点的列表中删除第三节点的地址；

[0009] (c)从第三节点的列表中删除第二节点的地址；并且

[0010] (d)将第二节点的地址插入到第一节点的列表中，并将第三节点的地址插入到第一节点的列表中；

[0011] (e)将第一节点的地址插入到第二节点的列表中，并将第一节点的地址插入到第三节点的列表中。

[0012] 在另一方面中，本发明提供了一种虚拟网络的节点，该节点由存储装置和处理装置限定，该存储装置包含有用于存储多达预定数量个其他这种节点的地址的列表，该处理装置被编程以执行以下操作：

[0013] 接收消息；

[0014] 响应用于请求有关所述列表的内容的信息的消息；

[0015] 遵照接收的请求从该列表删除地址；

[0016] 遵照用于请求将地址插入到该列表中的消息；以及

[0017] 响应于接收到用于请求第一节点与第二节点之间的链接的消息：

[0018] (A)生成到第二节点的消息，该消息请求有关第二节点的列表的内容的信息；

[0019] (B)确定第一节点和第二节点是否在每种情况下都在各自的列表中具有比预定数量要少的数量个地址；

[0020] (C)在满足该条件的情况下，将第二节点的地址插入到第一节点的列表中，并生成到第二节点的消息，该消息用于请求第二节点向其列表添加第一节点的地址；

[0021] (D)在不满足该条件的情况下，确定第一节点在其列表中是否具有比所述预定数量少至少两个的数量个地址，如果满足此，则：

[0022] (a)从第二节点的列表中选择第三节点的地址；

[0023] (b)将第二节点的地址插入到第一节点的列表中，并将第三节点的地址插入到第一节点的列表中；

[0024] (c)生成到第二节点的消息，该消息请求从第二节点的列表中删除第三节点的地址并插入第一节点的地址；以及

[0025] (d)生成到第三节点的消息，该消息请求从第三节点的列表中删除第二节点的地址并插入第一节点的地址。

[0026] 在权利要求中限定了本发明的其他优选方面。

附图说明

[0027] 下面参照附图通过示例对本发明的一些实施例进行描述，附图中：

[0028] 图1是本发明一个实施例中所用的计算机的框图；

[0029] 图1A是示出使用主虚拟网络和次虚拟网络的数据获取操作的流程图；

[0030] 图2是示出计算机网络的多个节点之间的链接的管理的原理图；

[0031] 图3到10是示出次虚拟网络的节点的操作的多个方面的流程图；

[0032] 图11到14以及16是示出主虚拟网络的节点的操作的多个方面的流程图；以及[0033] 图15是说明图14所示过程中的消息流的原理图。

具体实施方式

[0034] 节点

[0035] 在该说明中，将涉及具有处理、存储以及通信能力的计算节点。计算节点可以是计算机或其他设备，或者——注意，单个计算机可以具有在其上运行的多个独立程序或进程——可以是这种程序或进程。也可以将存储数据项视为独特节点，即使多个这种项可由单个程序或进程提供服务。

[0036] 该说明假定每个计算节点都连接到某些通信基础结构(该通信基础结构例如可以是诸如IP(网际协议)网络的电信网络)，使得可以将消息发送到该计算节点。因此，每个计算节点还构成该通信基础结构内的节点。

[0037] 还涉及属于虚拟网络的多个虚拟节点。由于计算节点能够具有与其相关联的两个或更多个虚拟节点(可能属于不同的虚拟网络)，所以区别很重要。如它的名称所蕴含的，虚拟节点并不在任何物理意义上存在，而是如将马上变得清楚的那样，其存在性由限定虚拟节点之间的链接从而也限定其所属虚拟网络的存储数据来建立。

[0038] 虚拟节点必须与计算节点相关联，该计算节点为该虚拟节点提供处理、存储以及通信能力：提及虚拟节点发送、接收以及处理消息，将提到代表该虚拟节点的计算节点进行这种发送、接收或处理。

[0039] 图1示出了一示例。计算机具有通用组件，即处理器1、存储器2、显示器3、键盘4以及用于通过网络10进行通信的通信接口5。

[0040] 存储器2包含操作系统和其他程序(未示出)以及诸如所示文本文件20的数据文件。其还具有存储部21，该存储部21包含有与文本文件20对应的标签21a及其自己的地址21b。此外，它具有地址列表22和支持程序23，它们一起定义了虚拟网络节点在计算机上的存在性。该节点具有地址24。还示出有地址列表25和支持程序26，它们一起定义了另一虚拟网络的节点在计算机上的存在性。该节点具有地址27。存储在列表22、25中的地址是同一虚拟网络中的其他节点的地址。

[0041] 查找系统

[0042] 现在描述分布式查找系统，尽管其仅为本发明的应用的一个可能示例。该系统允许用户把评述与网页关联起来。无论用户何时访问该页，他都有机会也看到其他用户所作的评述。评述存储在作出该评述(例如，作为文本文件)的用户的计算机上。

[0043] 观看网页的用户(或其计算机)具有该网页的统一资源定位符(URL)，所需要的是该用户可以借以获取到所述评述的机制。在本示例中该机制如下：

[0044] 将文本文件存储在作出评述的用户的计算机上，并与在我们的国际专利申请No.WO 03/034669[代理案号：A30044]中所述类型的虚拟网络的节点相关联，该文本文件也可以是包含关于其他网页的评述的其他文本文件，还可以是其他不相关的文件。该虚拟网络(在本说明书的语境下被称为主虚拟网络，或简称为主网络)起到这样的作用：只要具有标识消息的标签，就允许在不知道其地址的情况下发送该消息。尽管这种类型的网络可以通过唯一的标签(一个节点一个标签)来运行，但是在本示例中标签是不唯一的；相反，与包含关于特定网页的评述的多个文本文件相关联的所有节点都具有相同标签。该标签是网页URL的散列函数。该虚拟网络提供了只到达一个节点的获取机制。

[0045] 文本文件还与次虚拟网络的节点相关联。其(该次虚拟网络)只含有与包含关于所述一个特定网页的评述的文本文件相关联的节点。

[0046] 然而，需要指出的是，虽然使用根据我们的前述国际专利申请的主网络是优选的，但是这并不是必要的。实际上，根本上并非一定要使用虚拟网络；而是可以使用另一主获取机制，其接收标签并返回与该标签对应的一个节点的地址。

[0047] 发布评述的计算机如图1所示并且必须：

[0048] ●在主网络中创建节点。该节点具有标签21a和网络地址24。

[0049] ●在次网络中创建节点。该节点具有网络地址27。

[0050] 最初地址列表22、25是空的，只是列表22包含有引导链接(bootstrap link)。稍后将描述网络的自组织，其用于确保列表22包含有主网络的某些其他节点的标签和地址并确保列表25包含有次网络的某些其他节点的地址。现在，在假设存在这些标签和地址的情况下描述该系统。

[0051] 这里需要对地址作一些阐述。由文本文件20形成的节点、主虚拟网络的节点以及次虚拟网络的节点虽然在概念上来说具有同一性，但是它们具有它们自己的地址。在通信网络10中可以为各节点分配不同的地址，尽管在实际中这并不是很方便。在我们的优选实施例中每个节点都具有由以下三部分组成的地址：

[0052] ●因特网地址，其用于“定位”计算节点。例如130.146.209.15

[0053] ●端口号，其用于定位计算节点处的特定通信端口。端口是因特网地址的标准部分。例如它们允许不同的独立应用程序独立地发送和接收消息。即，每个应用程序都以它自己的端口接收消息，并且不接收发送给其他应用程序的消息或被这些消息“混淆”。可以将因特网地址与端口地址一起视为网络地址(正如所使用的通信协议(如TCP/IP)的一部分那样)。用于所有主节点和次节点的网络地址都可以是相同的，但是并非一定要如此。例如，可以在与接收第二消息的端口不同的端口接收针对主节点的所有消息(这是用于区分这种消息的一种方式)。

[0054] ●节点标识符(整数值)，其用于定位消息所针对的特定节点。例如，如果在专用端口接收主网络上的所有消息，那么还存在与各节点相关联的本地唯一标识符。因此，当存在多个节点时，很清楚消息所针对的节点。该节点标识符是应用特有的地址扩展(它不是标准网际协议的一部分)。简单地将它包括在发送的消息中。接收它的进程“知道”此情况并检查该节点标识符以确定应当将该消息转发给哪个节点。

[0055] 有可能两个节点具有同一网络地址，但并非一定如此。并不是每个节点都将具有它自己的端口(部分原因是可用端口数量受到一定限制)，但是一个节点完全可以具有两个端口(从而具有两个不同的网络地址)：一个用于主网络，一个用于次网络。典型地，存在多个次网络，它们可以全都使用同一端口。

[0056] 应当强调的是，以下，提到节点的地址，指的是该节点的完整地址。

[0057] 一种尤其具有吸引力的方法是规定文本文件和主节点以及次节点都具有相同的节点标识符(和IP地址)，只有端口号不同。这种编址协议可以提供在以下方面简化某些处理的机会：当具有一个节点的地址并需要与该节点相关联的另一节点的地址时，可以根据前一节点的地址推断后一节点的地址，而不必查找之。然而，在以下说明中，未作这种简化，因此这些过程将与任意编址协议一起执行。

[0058] 查看网页的计算机通过以下步骤获取关联评述：

[0059] ●将相同的散列函数应用于URL以获得标签；

[0060] ●在主虚拟网络上发送查询(包含有该标签)，以获得一个节点的地址；

[0061] ●使用找到的地址，在次虚拟网络上发送查询以获得次虚拟网络上的更多(甚至所有)其他节点的地址；

[0062] ●使用这些地址获取用于显示的评述。

[0063] 注意，获取计算机并不一定要包含虚拟网络的节点；它可以是这样的常规计算机，即，该计算机加载有用于实现获取处理的软件，并具有通信接口以使该计算机可与其上驻留有虚拟网络节点的计算机相通信。在图1A的流程图中示出了该过程，其如下地执行：

[0064] 步骤30：在用户输入URL(或调用超链接)之后计算机获取对应的网页。该步骤完全是常规的。

[0065] 步骤31：将散列函数应用于URL以获得标签。如在我们早先的国际专利申请中所述的，这可以使用SHA-1算法。

[0066] 步骤32：向主网络的一节点发送包含有该标签和获取计算机的网络地址的“Find(查找)”消息。显然，该计算机必需具有至少一个这种地址。

[0067] 步骤33：该获取计算机从主网络接收“Find”消息。该消息包含有已查找到的节点的标签和地址，也包含有次网络的关联节点的以及评述的地址。可以包括超时机制，以在未在合理时间内接收到Find消息的情况下中止该过程。

[0068] 步骤34：在本示例中，将主网络配置成使得其始终返回具有与在Find消息中包含的标签最接近的标签的节点的标签和地址。从而执行检查以查看返回的标签是否与要求的标签相同，如果不相同，结束该过程。对“最接近”的意思的说明见下。

[0069] 步骤35：假设所述标签相匹配，获取计算机执行(稍后要详细描述的)过程，由此其使用由Find消息返回的地址来通过次网络获取进一步的地址。

[0070] 步骤36：然后使用这些地址从“发布”计算机获取包含有评述的文本文件。

[0071] 次虚拟网络

[0072] 该网络的目的是用于将一组节点自组织成单个虚拟网络，随后可以通过该单个虚拟网络发现作为该组的一部分的所有节点。主要要求是所得网络包含所有节点。另一要求是创建和维持网络的所需系统负载平均地分布在所有节点上。这不仅是最“公平”的(当不同的用户向分布式应用贡献它们的资源时这是很重要的)，而且有助于防止系统过载。

[0073] 因此，该网络具有以下特性：

[0074] ●优选地，由各节点维持的链接数量是相同的。

[0075] ●所有链接都是双向的。结果，到一节点的链接数量对于各节点来说也是相同的。这是很重要的，因为这影响着节点接收的和必须处理的消息数量。

[0076] ●其具有“平”结构。这些节点不会分级地排列它们自己。结果，系统负载平均地分布在所有节点上。

[0077] 各节点的结构

[0078] 各节点具有以下与其相关联的数据：

[0079] ●到其他节点的几个链接。每个链接都仅仅是另一节点的地址。与每个链接相关联的是状态，其可以是“已确认”或“未确认”。各节点只能保持最大数量个链接，其由系统宽度参数L给出。L的典型值例如是6。该参数并非必须对所有节点来说都相同；但是使它们不同并不会获得益处。

[0080] ●备用(spare)链接或短期备用的列表。各备用仅仅是另一节点的地址。由自组织过程使用这些备用来建立虚拟网络。当节点被通知无法将一节点添加为链接(要么是由于它已链接到该节点，要么是由于它已具有最大链接数量)时，该节点添加其他节点作为备用。节点可以保持的备用数量也受到限制，并由系统宽度参数S给出。S的典型值例如是3。通常备用链接列表并不是必需的，但是在提供这样的附加机制方面很有价值：通过该机制，不能被当地容纳的链接可以传播到虚拟网络中的某个其他点。但是在其中到来的通知消息始终到达次网络的同一节点处(或很小数量的节点中的一个)的系统中必须使用备用链接(或类似的传播机制)。

[0081] 消息

[0082] 为了自组织到一网络中并发现哪个节点是给定网络的一部分，多个节点相互发送消息。次网络使用以下类型的消息：

[0083] ●带有以下内容的AddLink消息：

[0084] ●发送方地址

[0085] ●接收方地址

[0086] 由一节点(发送方)向另一节点(接收方)发送该消息以请求相互链接。

[0087] ●带有以下内容的ChangeLink消息：

[0088] ●发送方地址

[0089] ●接收方地址

[0090] ●对象地址

[0091] 由节点(X)向另一节点(Y)发送该消息以请求它将其多个链接(Z)中的一个改变成到其自(X)的链接。该协议是这样的，即，X将向Z发送类似的消息，该消息请求Z将它的到Y的链接改变成到它自(X)的链接。因此，实际上，X请求将它自己插入到当前在Y与Z之间的链接。

[0092] ●带有以下内容的LinkAdded消息

[0093] ●发送方地址

[0094] ●接收方地址

[0095] 其用于通知一节点：发送方刚刚向它添加了链接。

[0096] ●带有以下内容的LinkError消息

[0097] ●发送方地址

[0098] ●接收方地址

[0099] ●对象地址

[0100] ●错误码

[0101] 其用于通知一节点：它的一个链接出现了问题。例如，该对象节点可以不响应，或者该链接可以不是相互的。该消息包括用于表示错误类型的错误码。

[0102] ●带有以下内容的Links消息

[0103] ●发送方地址

[0104] ●接收方地址

[0105] ●所有链接的地址

[0106] ●引用(reference)值

[0107] ●该Links消息还可以包含来自发送方节点的某些其他数据。在

[0108] 网页评述示例中这是关联评述的地址。

[0109] 该消息包含有发送节点的所有当前链接。总是响应于LinksQuery消息发送该消息。可以将该引用用于区分所响应的具体查询。

[0110] ●带有以下内容的LinksQuery消息

[0111] ●发送方地址

[0112] ●接收方地址

[0113] ●引用值

[0114] 其用于请求一节点发送Links消息作为答复(包含有其当前链接)。

[0115] ●带有以下内容的Notify消息

[0116] ●发送方地址

[0117] ●接收方地址

[0118] ●对象地址

[0119] ●通知级别

[0120] 该消息用于向节点通知网络中的另一节点。通知级别用于控制和限制Notify消息的传播。如这里所述的，不使用发送方地址，但是它在调试时或在希望发送确收的情况下很有用。

[0121] 建立次网络

[0122] 该系统使组节点自组织到单个虚拟网络中，使得在具有一个节点的地址的情况下可以查找到该组中的其他节点的地址。这部分描述当发现应当属于同一次网络的节点时如何创建新链接。这里可以分为两个部分：

[0123] 发现应当属于同一次网络的节点对。将节点分组到同一网络的准则是应用特有的。在该网页评述示例中，应当将表示有关同一URL的评述的所有节点都一起归组到次网络中。如何发现应当归组在一起的节点也是应用特有的。稍后给出一示例。

[0124] 作为节点发现的结果，对次网络进行更新/扩展。当发现应当属于同一次网络的一对节点时，作为结果，系统可能建立一个或更多个新链接。新链接并不一定在该对节点之间，而是例如可以在这两个节点链接到的节点之间。稍后详细描述如何创建新链接。

[0125] 初始通知消息

[0126] 次网络的组织预先假定到来的“Notify(通知)”消息的存在性，其例如可以标识所述组的现有或新成员(尽管在初始时，可能两个节点都不是组的一部分，然而，后来在自组织过程中，两个节点可能都已经是组的一部分)。系统的另一部分向次网络通知应当属于它的节点。有不同的方式可以这样做。这里我们给出结合在我们早先的国际专利申请中描述的类型的主网络一起使用次网络时如何这样做的示例。在该网页评述示例中，每条评述以基于对应网页的URL的标签发布它自己，作为主网络中的节点。这样，可以使用主网络查找给定URL的评述，如果存在的话。为了示出对于给定URL的所有评述，每条评述都具有与其相关联的次网络的节点。与关于同一URL的评述对应的节点自组织到该URL特有的次网络。这样，一旦使用主网络查找关于URL的单个评述，那么就可以使用次网络查找关于该同一URL的其他评述。

[0127] 因此在此情况下，以主网络中的同一标签发布应当归组在一起的次网络的各节点。以下将描述这样的机制，即，通过该机制，在主网络中，节点定期执行“推(Push)”更新以建立和保持链接，该机制包括一变型，使得只要节点知道以同一标签发布了另一节点，就生成所需的Notify消息。

[0128] 处理Notify消息

[0129] 当节点接收到与其尚未链接到的节点有关的Notify消息时，将发生以下几者之一：

[0130] 如果接收节点已具有最大允许链接数，则它将其添加为备用(除非它已将其作为备用)。如果这样做时该节点将超过它的最大备用数量，则它将删除一个备用。然后它还可以把Notify消息转发给删除的备用。是否这样做取决于通知级别的值。每次都降低通知级别以防止消息无穷传播。

[0131] 否则，如果对象节点也尚未具有最大链接数，则接收节点试图在两个节点之间创建相互链接。图2(图a和b)示出了该情况。其中，L＝3，节点1接收到关于节点2的Notify消息。由于两个节点都只有两个链接，所以在节点1与节点2之间创建一链接。

[0132] 否则，当对象节点已具有最大链接数时，不可能简单地在两个节点之间创建相互链接。因此将发生的是接收节点试图将它自己插入到现有链接中。图2(图c和d)示出了此情况。其中，节点2与节点3之间的链接是断开的，但是它被两个新链接来取代：节点1与节点2之间的链接，和节点1与节点3之间的链接。因此总链接数增加了一。即使节点2和节点3已具有最大链接数，也是起作用的。然而，为此，节点1需要能够创建两个新链接。在图3到图9的流程图中更详细地阐述了该过程。

[0133] 图3示出了节点如何处理到来的Notify消息。其中确定是否应当创建新链接，并且如果创建的话如何创建(通过添加新链接或通过把现有链接改变成两个链接)。如果不创建新链接，则可以更新备用组并可以发送另一Notify消息。

[0134] 在步骤300处，接收到Notify消息，其包含有发送它的节点(发送方)的地址、对象节点的地址以及传播极限值notifylevel。接收节点首先检查(301)是否存在建立新链接的空间，若存在，检查(302)是否存在到对象节点的链接。如果不存在，则试图建立与对象的链接。

[0135] 在步骤303处向对象节点发送LinksQuery消息，在步骤304处，等待回复。一旦接收到回复——Links消息，则再次检查(305)是否还存在空间建立新链接(在其间已接收并处理任何其他消息并作为结果创建链接的情况下)。如果存在，然后(306)检查接收的Links消息以检查对象节点是否存在空间建立新链接。如果存在，然后在步骤307和308处接收节点把对象节点的地址添加到它的链接列表(但是被标记为“未确认”)并向对象节点发送AddLink消息。

[0136] 然而，如果在步骤306处确定对象节点无法接受更多链接，那么接收节点如先前参照图2所述的那样试图把它自己插入到现有链接中。第一步骤(309)将检查接收节点是否存在用于两个链接的空间；如果不存在，则终止过程。然而如果存在，那么接收节点从链接列表随机选择接收的Links消息中的链接(但是不选择接收节点已存在到其的链接的节点)，即，对象节点与另一节点(这里被称为其他节点)之间的链接。然后接收节点试图通过以下步骤将它自己插入到该链接中：

[0137] 311把对象节点(未确认)的地址添加到它的链接列表；

[0138] 312把其他节点(未确认)的地址添加到它的链接列表；

[0139] 313向对象节点发送包含有其他节点的地址的ChangeLink消息

[0140] 314向其他节点发送包含有对象节点的地址的ChangeLink消息

[0141] 然而，假设在步骤301处确定接收节点不存在添加链接的空间，或者在步骤302处已存在到对象节点的链接，那么过程检查接收节点是否应当向它的备用链接列表添加链接。在步骤315中，如果发现对象节点已存在于备用列表中，则过程结束。在316处检查是否存在向备用列表添加链接的空间，如果存在，则在317处及时添加链接。如果不存在，那么在318处随机选择备用链接中的一现有链接，并在步骤319处删除它，从而在步骤317处可以将它替换为到对象的链接。此外，在320处使变量notifylevel递减，如果(步骤321)该值保持非零，则在步骤322处将最初的Notify消息(连同该新值notifylevel)转发给随机选择的现有链接所指向的节点(称为替换节点)。

[0142] 该过程的效果是：当已具有全组链接的节点A接收到要求它链接到对象节点B的Notify消息时，将B的地址记录为备用链接。该链接保持休眠，直到A的备用链接列表已满为止。然后，当A接收到稍后的要求它链接到节点C的Notify消息并且在步骤318处选择了到节点B的备用链接时，在步骤322处生成的新Notify消息事实上是对节点B的请求以创建从它自己到节点C的链接。

[0143] 还提供了这样一种机制(但是在流程图上未示出)，通过该机制，当链接是未确认的并且在给定时段内接收节点未(通过如下参照图6所述的LinkAdded消息的方式)接收到确认时，删除未确认链接。注意，当接收节点具有仍然处于“未确认”状态的链接时，它响应于LinksQuery消息返回这些未确认链接(当然也返回确认的链接)，使得其他节点可以确认它试图建立链接。

[0144] 在图3中，步骤305和309的“否”分支导致过程终止；然而如果希望，可以将它们导向在步骤315处开始的“备用链接”过程，这可以稍微提高效率。

[0145] 在步骤309到314中，实际上节点断开一个对象链接并将它自己插入到这之间。在流程图中未示出的另一可选做法是：节点断开它自己的一个链接(当然假设它已具有至少一个链接)并将对象插入到这之间。如果实施该做法，则应当在从步骤301的“否”分支之后立即尝试该做法。首先，接收节点需要检查对象是否具有少于L-1个链接、随机选择它自己的(到节点其他的)多个链接中的一个、将该链接替换为到对象的未确认链接、并向对象发送AddLink消息。为了建立对象与其他之间的双向链接，然后(a)接收节点向对象发送特殊的AddLink消息，该消息要求对象无条件地将其他作为未确认链接添加到它的链接列表；(b)向其他发送特殊的ChangeLink消息，该消息以接收节点作为待删除旧链接并将对象称为待添加的新链接。除了步骤309到314，也可以包括该做法，或以该做法取代步骤
309到314。

[0146] 接收节点断开它自己的一个链接的另一做法可以是它(首先验证了对象具有少于L-1个链接)向对象发送把它自己当作对象的Notify消息。这将得到同样的结果，但是要花费稍多的消息开销。

[0147] 图4示出了节点如何处理到来的ChangeLink消息。当接收到Notify消息的节点X想要把现有链接改变成两个新链接时发送这些ChangeLink消息(见图2)。接收节点Y在400处接收Notify消息，该Notify消息以节点Z为对象，即，要求节点Y将它的到节点Z的现有链接替换为到节点X的链接。如果它已具有到X的链接，则不再采取进一步的动作(401)，然而如果(402)它实际上不具有到节点Z的链接，则向发送方X发送(403)错误消息。

[0148] 假设一切正常，则它向发送方X发送(404)LinksQuery消息并等待(405)来自发送节点X的回复Links消息，以检查发送节点X是否确实创建了它在改变对象链接之间应当已创建的两个新链接。如果这些检查(406、407)是成功的，则接收节点删除它到Z的链接(408)、添加X作为确认链接(409)并把LinkAdded消息返回给发送方X(410)。

[0149] 图5示出了节点如何处理到来的AddLink消息。当节点想要创建与一节点的新链接时发送这些消息(见图1)。在501处接收到该消息之后，在步骤502处节点检查它是否具有用于另一链接的空间，如果没有，则在503处返回错误消息。否则，向发送方发送(504)LinksQuery消息并等待(505)发送节点回复的Links消息，使得它在506处可以检查发送方是否确实创建了到接收节点的链接。若否，则它拒绝添加链接并终止，但是若是，那么它添加发送方作为确认链接(507)，并通过确认把LinkAdded消息返回给发送方(508)。

[0150] 图6示出了节点如何处理到来的LinkAdded消息。当另一节点接受了到接收节点的链接时发送这些消息，或者响应于ChangeLink或AddLink消息发送这些消息。当在600处接收到表示已接受链接的LinkAdded消息时，在步骤601处将其状态改变成“已确认”。然后保持该链接，直到它被新链接改变(响应于ChangeLink消息)或该链接被断开为止。

[0151] 图7示出了节点如何处理到来的LinkError消息。当在接收节点请求相互链接之后节点无法创建到该接收节点的链接(通过ChangeLink或AddLink消息)时，或当链接似乎被断开时(位于另一端的节点可能对消息不响应，或者链接可能不是相互的)，发送这些LinkError消息。不是由自组织过程而是在客户机遍历次网络(如稍后要阐述的)时检测断开的链接。

[0152] 在700处接收到该消息之后，确定(701)该消息是否与这样的节点有关，即，接收节点到该节点具有未确认链接。若是，那么(702)该消息携带表示未能创建所请求的链接的错误码，然后在703处删除该链接。然而如果该消息与这样的节点无关，即，接收节点到该节点具有未确认链接，则接收节点向对象发送(704)LinksQuery消息，等待(705)回复的Links消息，在706处检查该回复以检查对象是否具有到它自己的链接，若否，那么在步骤703处删除到对象节点的该链接。

[0153] 图8示出了节点如何处理到来的LinksQuery消息。当另一节点想要知道接收节点的链接时发送这些消息，并且因此，接收节点在800处接收该消息时，在801以Links消息作为响应。

[0154] 图9示出了节点如何处理到来的Links消息。如何处理该消息完全取决于为什么发送对应的LinksQuery消息。由于不同的原因而发送该消息，如在图3、图4、图5以及图7之中所示。因此要发生的是：当发送LinksQuery消息时，给定当地唯一的引用值并将一消息处理器与该引用关联起来。然后，当接收到Links消息时(900)，识别出合适的消息处理器并在步骤902处将该消息转发给该合适的消息处理器，以按正确的方式处理该消息。

[0155] 当然可能发生未响应LinksQuery而接收到任何Links消息的情况，例如这是因为已关闭接收节点。因此，如果在给定时段之后未接收到任何Links消息，则删除对应的消息处理器。尽管这里所讨论的任何流程图中都未明确示出该情况，但是这仅仅意味着当链接查询超时时，不再采取进一步的动作并且“走完”了整个流程图。

[0156] 获取检点

[0157] 给定次网络的单个节点的地址，可以发现网络中的其他(有可能全部)节点。可以这样做的方法是非常简单的。向已知节点发送LinksQuery消息以请求它的所有链接。该节点以Links消息作为答复，该Links消息包含有该节点链接到的所有节点的地址。然后可以依次联系这些节点中的每一个，请求它们的链接并由此获得所有它们的链接的地址。通过按此方式继续下去，遍历该网络并逐渐发现它包含的所有节点。

[0158] 图10更详细地示出了该过程。应当明白，这是在图1A所示的获取步骤35中使用的过程。把已成功联系到的所有已知节点的地址放在“已确认”列表中。可以同时对数据进行获取。在“网页评述”示例的情况下，数据的相关项是评述的地址，并且也把它输入到确认列表中与节点地址并排在一起。然后该确认列表提供在图1A中的步骤(36)处“获取”评述所需的地址。另一方面，“未确认”列表包含有尚未联系的已知节点的地址。最后，“已知”列表包含有所有已知节点的地址。它包括“确认”和“未确认”列表中的所有地址，但是也包括已联系并且未响应的节点的地址。已知列表还具有针对输入到该列表中的每个地址的用于包含源他址(即，该地址是这样的节点的地址，从该节点的列表获得了当前(当前)指针指向的地址)的附加域，以用于错误报告的目的。

[0159] 在何处发生获取过程并不重要：可以在节点处，或其他地方。在步骤1000处，与后动地址(即，已被确定属于所讨论的虚拟网络的一个节点的地址)一起接收到对获取节点地址的请求。在步骤1002处，最初将地址指针当前设置为该地址，而最初将第二地址指针源设置为空(1003)。

[0160] 在步骤1004和1005处向由当前所给定的地址发送LinksQuery消息，并等待回复。当接收到Links消息时，将当前与来自Links消息的评述地址一起添加到已确认列表(步骤1006)。

[0161] 在步骤1007处，进入子过程，针对包含在Links消息中的每个地址执行该子过程。如果(1008)该地址已在已知列表中，该过程进行到下一地址。否则将该地址添加到已知列表和未确认列表中(步骤1009、1010)。此外(1011)，将当前中的地址输入到已知列表中作为所添加地址的源。

[0162] 一旦完成了该子过程，然后(除非未确认列表是空的，在此情况下在步骤1012处结束该过程)在步骤1013处从未确认列表随机选择一地址。该地址成为新当前地址，并从未确认列表删除该地址。下一步骤(1014)是在已知列表中查找当前以获取与之相关联的源地址，并把该源地址输入到源指针中。并非一定要进行随机选择。例如，在未确认列表中可以选择当前作为“最老的”节点，或者可以按照另一准则(例如，节点的地址)对列表进行排序并且当前可以始终是该列表中的“第一个”节点。然而，对当前的随机选择具有它的优点。这将负载分布在系统中(尤其是并非总是获取所有节点时)，并且还分布对网络链接的测试，使得更快速地发现断开链接。

[0163] 然后再从步骤1004继续该过程并一直重复，直到未确认列表是空的为止——即，不能再找到新地址。

[0164] 获取过程的副作用是发现断开链接。例如，可能节点不响应，或链接不是相互的。后者是这样的情况：节点A链接到节点B，但是节点B在其链接表中没有节点A。当发现断开链接时，通过LinkError消息通知作为该链接的“源”的节点。如图7已示出的，然后该源节点可以检查该链接本身(以确认错误报告的准确性)，结果可以删除该链接。通过步骤1005处的失败识别出未响应的节点，以在设置的超时时段内接收Links消息，并在步骤1015处向源发送错误消息，该错误消息包含有当前的地址和“未回复”错误码，于是控制返回到步骤1012。通过在步骤1016处的测试识别链接的非相互性，以确定为当前接收的Links消息是否包含有源地址：若否，向源发送(步骤1017)包含有当前地址和“非相互的”错误码的错误消息，但是获取过程照旧进行，因为采取补救措施(根据图7的过程)是源节点的责任。如果源是空的，则跳过步骤1016处的测试。

[0165] 注意，即使多个已确认节点可能链接到对Links消息没有响应的节点，也只通知首先贡献该链接的节点(源节点)“没有回复”。这部分地是因为这使得更容易理解流程图。然而，可以证明存在另一实际的好处。可能存在这样的情况：节点由于暂时过载而未(及时)回复。在此情况下，不能希望多个节点同时向它发送LinksQuery消息以测验是否存在错误(如图7中的那样)。无论如何，如果希望，当发现这种链接时，都可以直接更新节点获取算法以通知被断开链接影响的所有已知节点。

[0166] 在图10中节点获取一直进行到已联系所有已知节点。实际中，可能希望早一些结束该过程。例如，如果用户在寻找下载文件的位置，为他或她提供十个可能的下载地址就足够了，而不是例如全部一千个。

[0167] 完全串行地示出了图10中的算法。每次只联系一个节点。只在已接收到回复(或已超时)之后向前一节点发送另一LinksQuery消息。然而，实际中，我们更愿意通过并行发出多个LinksQuery消息来加速获取。也可以是这样的情况：在框1000处，由图10的过程的多个实例同时处理多个获取请求。

[0168] 讨论

[0169] 自组织的成功性

[0170] 次虚拟网络的目的是把应当归组在一起的所有节点自组织到单个网络中，而不是自组织到几个不相连接的网络。是否是这种情况很大程度上取决于如何生成最初的Notify消息。例如，如果存在应当全部被归组在一起的一组12个节点，但是在该组中5个节点只接收到有关这5个节点的组中的其他节点的通知，并且其他7个节点中没有一个节点被通知这5个节点中的任何一个，那么不可能将这些节点自组织成单个网络。相反，它们排列成两个独立网络，一个是5个节点的，一个是7个节点的。然而，只要最初的通知不会使得不可能将节点自组织成单个网络，那么自组织过程就几乎不可能使节点不自组织成单个网络。对自组织导致单个网络的可能性的计算是很复杂的，并且依赖于生成初始通知的机制。然而，在仿真过程中我们已经试验了几种不同的初始通知机制，到目前为止节点从未无法自组织成单个网络。

[0171] 对恶意节点的健壮性

[0172] 迄今为止假定所有节点都遵守协议。但是，有可能存在不遵守规则的恶意节点。它们可能试图断开由其他节点保持的连接并且/或者试图获得太多到它们自己的连接。希望整个系统对这种恶意尽可能地健壮。

[0173] 迄今所述的系统已经对恶意节点相当健壮了。这是因为每个节点在改变它自己的连接之前总是检查LinksQuery-Links消息，该消息交换由其他相关节点所保持的连接。例如，当节点接收到AddLink消息(见图3)时，它在添加发送方作为它自己的连接之前首先检查发送节点是否确实已链接到它。

[0174] 然而，系统仍然具有相对的弱点。实际上，当节点响应Links消息时它们很容易“撒谎”。往往节点发送LinksQuery消息以检查链接到它的接收节点。接收节点在知道这种情况的前提下可以回复假的Links消息，该消息被修改成使得始终包含Links消息的发送方作为链接。这使得节点可以具有比允许数量L大得多的到它的节点的链接。因而，这将降低系统中的“好”链接的总数量。

[0175] 幸运的是，存在解决该弱点的方法。只要节点通过代理节点发送它们的LinksQuery就可以了。每当节点想要发送查询时随机选择这些代理。每个节点例如可以使用它当前链接到的节点作为代理。这样，想要知道另一节点(B)的链接的节点(A)对于节点B来说不了解，因为它接收到的LinksQuery消息来自代理节点(C)，并且节点B从节点C接收的消息根本不涉及节点A。因此节点B没有可行的方法来发送对整个系统具有重要影响的假消息。

[0176] 当然，存在恶意代理的后果如何的问题。尽管显然恶意代理具有有害影响(不可避免地，不遵守协议的节点一定程度上会影响性能)，但是该影响是有限的。原因是它们只能恶意处理它们要求转发的LinksQuery，这些请求在所有节点上大体上平均地散布开来。另一方面，当不使用代理时，恶意节点可以通过变得特别活跃而导致严重破坏。如果这些节点发送许多虚假的AddLink消息，并冒充它们随后发送的许多Links消息，那么对整个系统的影响要大得多。

[0177] 主虚拟网络

[0178] 在我们的前述国际专利申请中详细描述了主网络。这里，与使得可以生成用于驱动次网络的自组织的Notify消息的修改例一起对基本获取和自组织机制进行描述。

[0179] 首先需要说明由该机制使用的虚拟坐标空间的概念。已经提到过，每个节点都具有标签。将该标签翻译成虚拟空间中的坐标。该空间可以是一维、二维或更高维的。确切的翻译机制并不是很关键：对于一维空间，可以把被视为二进制数的标签直接用作坐标。对于二维或更高维，优选方法是：把被视为位串的标签划分成两个或更多个相等的组，被视为二进制数的每个组都形成一个坐标。将每个坐标(或者，在一维空间中是坐标)都缩放成位于范围[0，1]内。

[0180] 如果希望，可以使用虚拟空间中两个标签之间的两个坐标组之间的欧几里得距离的距离(尽管可以使用其他距离，如城市块距离(通常被称为曼哈顿距离))。坐标空间是卷起来的，因此在x方向上x1与x2之间的距离是：

[0181] Min{(1-|x1-x2|)，|x1-x2|}

[0182] 因而在二维中点(x1，y1)与(x2，y2)之间的欧几里得距离是：

[0183]

[0184] 至此我们记得每个节点都具有列表22(图1)，该列表22带有表示到其他节点的链接的数量个条目。每个条目都由标签和这种另一节点的地址组成。最初，该列表是空的，因此该节点具有第二个类似的引导链接列表——即，较少的链接(典型的是4个)，使得最初可以联系网络中的其他节点。除了列表22中的链接(被称为短程链接)，节点还可以具有附加的分级排列的列表，和/或长程链接列表。在我们早先的国际专利申请中描述了这些列表，但是，由于它们是可选的，所以这里不描述它们。

[0185] 消息

[0186] 首先，使用以下消息(注意，在主虚拟网络中使用的消息与在次虚拟网络中使用的消息不同，并且与之完全独立)。

[0187] FIND消息用于启动和完成节点查找并用于支持“拉(PULL)”更新。它们包含有：

[0188] ●目标节点的标签

[0189] ●启动查询的节点的地址

[0190] FOUND消息用于返回查询结果。它们包含有：

[0191] ●目标节点的标签

[0192] ●找到的节点的标签

[0193] ●找到的节点的地址

[0194] ●与找到的节点相关联的次网络的节点的地址

[0195] ●应用专有数据——在此情况下是与找到的节点相关联的评述节点的地址[0196] PUSH消息把节点的标签通告给其他节点。它们包含有：

[0197] ●对象节点的标签

[0198] ●对象节点的地址

[0199] ●到达目标节点的跳距数

[0200] NOTIFY消息用于传播“推”更新。它们包含有：

[0201] ●对象节点的标签

[0202] ●对象节点的地址

[0203] 获取

[0204] 图11示出了每个节点如何处理到来的Find消息。原则上，接收节点寻找这样的节点：该节点比接收节点本身到Find消息中标识出的目标节点更近。如果找到了，传递该Find消息。如果未找到，返回它自己的地址和标签。通过执行以下步骤来执行该过程：

[0205] 步骤1100：节点接收到Find消息，该Find消息包含有目标节点的标签和启动节点的地址；

[0206] 步骤1105：节点将目标节点的坐标翻译成标签空间中的坐标，并计算在标签空间中该节点所记录的所有链接(节点)中哪个链接距目标节点最近。将相关节点指定为最近的节点。

[0207] 步骤1110：节点对它自己的坐标与目标节点的坐标之间的距离与最近节点的坐标与目标节点的坐标之间的距离进行比较。

[0208] 步骤1115：如果它自己的坐标与目标节点的坐标之间的距离较小(或相等)，则节点通过网络10向启动节点发送包含有它自己的标签和地址的Found消息；

[0209] 步骤1120：如果最近节点的坐标与目标节点的坐标之间的距离较小，则节点把Find消息转发给最近的节点。

[0210] 在步骤1115中返回的节点的地址要么是带有目标标签的节点的地址，要么是在标签空间中距它最近的节点的地址。当返回的标签与目标标签不匹配时，这可能意味着目标节点不存在或虚拟网络不是足够自组织的。

[0211] 推

[0212] 各节点自发地启动“推”更新。例如，各节点可以定期启动“推”更新过程。在“推”更新中，节点通过随机节点序列(在设置了该序列的长度限制的情况下)发送带有它自己的标签和地址的“推”消息。该序列中的最后一个节点向启动节点发回Notify消息。图12、13以及14示出了该过程的各个部分。

[0213] 图12示出了节点如何通过以下步骤启动Push更新：

[0214] 步骤1200：节点从它的引导链接中随机选择链接并输入由所选链接标识的节点地址作为下一消息的转发地址。

[0215] 步骤1205：节点在“推”消息中为跳程域输入较小的正随机数；

[0216] 步骤1210：节点输入它自己的标签和地址作为“推”消息中的对象节点的标签和地址，并通过网络10向位于转发地址的节点发送该“推”消息。

[0217] 图13和14示出了如何更新短程链接。将“推”消息与Notify消息一起用于更新短程链接。在该更新过程中有两个阶段。在第一阶段，各节点随机转发“推”消息，直到接收到的消息中的跳程值是“0”为止。如果跳程值是“0”，则接收节点将通过发送Notify消息启动“推”更新的第二阶段。在第二阶段中，将Notify消息相继转发给这样的节点：其标签在虚拟空间中距对象节点的标签逐渐较近。如果找不到带有较近标签的节点，那么必要时更新最后找到的节点的链接。当否则无法找到给定的对象节点(例如，由于它尚未建立短程链接)时总是如此。然后最后找到的节点还向可能还改进它们的链接设置的节点发送附加的Notify消息。

[0218] 参照图13，处理到来的“推”消息的“推”更新的第一阶段包括以下步骤：

[0219] 步骤1300：节点接收“推”消息。该“推”消息将包含作为对象节点的启动节点的标签和地址并具有跳程域值。

[0220] 步骤1305：接收节点从它的引导链接中随机选择链接并输入由所选链接标识的节点地址作为下一消息的转发地址；

[0221] 步骤1310和1315：接收节点使跳程域值减1并检查减小的跳程值是否仍然大于零；

[0222] 步骤1320：如果减小的跳程值仍然大于零，节点向它已输入的转发地址转发“推”消息。

[0223] 步骤1325：如果该值为零，那么节点输入(在接收的“推”消息中给定的)启动节点的标签和地址作为Notify消息中的对象节点并向它已输入的转发地址发送Notify消息。

[0224] 参照图14，处理“推”更新的第二阶段(用于处理Notify消息)包括以下步骤：

[0225] 步骤1400：节点接收Notify消息，该Notify消息包含有节点的标签和地址作为对象节点。

[0226] 步骤1401：接收节点检查Notify消息的对象是否具有与接收节点相同的标签；

[0227] 步骤1402：若是，接收节点检查Notify消息的对象是否具有与接收节点相同的地址。在此情况下它不再采取进一步的动作；

[0228] 然而如果Notify消息的对象是具有与接收节点相同的标签但是不同的地址的节点，那么将出现两种情况。首先(步骤1403)接收节点向到来的Notify消息的对象节点发送Notify消息，该Notify消息把从接收节点自己的短程链接列表随机选出的节点当作对象。其次，步骤1404针对次网络的动作导致Notify消息的生成。然而，接收节点不能直接生成这种消息。通常，我们倾向于避免在不同虚拟网络之间在通信网络上发送消息，但是主要问题在于：接收节点不仅需要次网络自己的节点地址，而且需要与对象节点相关联的次节点的节点地址。接收节点没有该地址。因此，使用双阶段过程。

[0229] 首先，接收节点把特殊的CrossNotify消息发送给被指定为到来的Notify消息的对象的主网络节点。该消息包含有：

[0230] ●发送方地址，被设置为接收节点(即，接收到来的(主网络)消息的节点)的地址；

[0231] ●接收方(或目的地)地址，被设置为包含在到来的Notify消息中的地址；

[0232] ●对象地址，被设置为与接收节点相关联的次网络节点的地址。

[0233] 注意，前两个地址是主网络上的节点地址，第三个地址是次网络上的节点地址。

[0234] 其次，实际上，接收CrossNotify消息的主网络节点将其转发给次网络的相关节点。若有必要，转发节点可以将该消息的格式改成在次网络上使用的格式，并将(主网络)接收方地址替换成次网络的相关节点地址。然后正如图3所示的那样处理该消息。我们说“实际上”的原因是，实际中，我们倾向于：接收CrossNotify消息的主网络节点仅仅向它的次网络相关节点发送简单的本地消息，该消息包含有在该CrossNotify消息的对象域中指定的地址。在该情况下，将图3的过程修改成包括把notifylevel设置成合适的值的步骤。

[0235] 参照图15通过示例说明该过程，该图中，方框表示节点，箭头表示消息。假设在图14的步骤1400中主网络的节点P1接收到Notify消息，该Notify消息包含有作为对象的主网络节点P2的标签LP2和地址AP2。在节点P1处，它识别出(图14中的步骤1401、1402)对象节点具有与P1相同的标签(即，LP1＝LP2)但是不同的地址(AP1≠AP2)。节点P1知道它的次网络节点S1的地址AS1，并以发送方地址AP1、接收方地址AP2以及对象地址AS1生成(在图14的步骤1404处)CrossNotify消息。在主网络节点P2处接收到该消息，并且该节点把带有地址AS1的本地通知消息发送给次网络的相关节点S2。另选地，次网络节点S2在收到LocalNotify消息时可以不根据图3的过程创建链接本身，而是生成(次网络的)又一将自己当作对象的Notify消息(由图12的虚线所示)，节点S2把该Notify消息发送给节点S1。然后在节点S1处处理该Notify消息，然后节点S1使用图3的过程。该做法涉及附加消息，但是其优点在于：当执行图3的过程时，实际上其地址在该消息的对象域中的节点已发送Notify消息，并由此内在地将对象节点确认为仍然存在。

[0236] 现在回到图14：步骤1405：接收节点将对象节点的标签翻译成坐标，并计算它已记录的短程链接中的哪一个得到这样的节点标签，即，该节点标签的坐标在虚拟空间中距对象节点的坐标最近。将相关节点指定为最近的节点；

[0237] 步骤1415：接收节点对它自己的坐标与对象节点的坐标之间的距离与最近节点的坐标与对象节点的坐标之间的距离进行比较。

[0238] 如果在步骤1415处发现接收节点与对象节点之间的距离相等或更短，那么接收节点将对象节点的标签和地址添加为它自己的短程链接组中的链接((步骤1420)：以下参照图16对该过程进行进一步的讨论)、向对象节点发送包含有接收节点的标签和地址的Notify消息(步骤1430)并向最近节点发送包含有对象节点的标签和地址的Notify消息(步骤1435)；

[0239] 如果在步骤1415处发现最近的节点与对象节点之间的距离较远，则接收节点回到步骤1435，在步骤1435处它向最近节点发送包含有对象节点的标签和地址的Notify消息。

[0240] 图16详细示出了节点在更新其短程链接时如何动作。它把新链接添加到它的短程链接并删除由该链接取代的所有短程链接。

[0241] 参照图16，例如由于图14的步骤1420的结果，节点可能需要将新链接添加到它的短程链接列表。

[0242] 步骤1600：更新节点(即，正在对其短程链接组执行更新的节点)具有新链接的节点的标签和地址；

[0243] 步骤1605：更新节点识别出所有现有的这样的链接：其节点距新节点比距更新节点更近。将要取代这些被识别的链接。为了识别这些链接，更新节点针对每个现有链接计算新节点的坐标与在它的现有链接中所指定的节点的坐标之间的距离。它对这些距离中的每个距离与它自己的坐标与在相应的现有链接中所指定的节点的坐标之间的距离进行比较。

[0244] 步骤1610：从短程链接中删除所有这样的链接：其相对于新节点的距离比相对于更新节点的距离要短；

[0245] 步骤1620：更新节点将新节点的链接添加到它的短程链接。