1、“.....在图中重新绘出了个查找过程的示例。节点查找关键字过程是节点首先按照路由算法把查询请求转发给它的指针表中的节点。同理节点也按规则把请求转发给节点，节点发现落在它和它的后继节点标识之间，因而就把节点的标识和地址等信息返回给节点。这个查找过程结束后，节点就可以根据得到的地址等信息直接到节点上存取与关键字相关的，对。图扩展查询示例从例子中我们可以看到的缺陷节点查询时虽然只经过了跳，但这正如前面指出的，是应用层跳数而不是网络层跳数，例如发起节点和目的节点可能位于的同网段内，而中间节点和却可能是分别位于欧洲和美国的两台主机。显然，源节点和目的节点处于同个网段而查询报文却要在广域范围内路由是不合理的另外，可能有许多与相关联的文件散布于网络的各个局部，即有很多关键字标识为的，对。但中这些，对全部存储于节点上，若有大量用户提出针对的部分查询请求，即只需找到部分而不是所有的......”。

2、“.....这些请求仍然被当作整体查询路由到。显然，这样做的后果是增加了网络的开销并可能导致负载过重。中国科学技术大学硕士学位论文第章利用拓扑信息改进针对的不足，本节提出了。其思想是把网络中的节点划分为多个组，保证组内节点之间的时延较小。如图所示，在各个组内构造内层，赋予每个节点个比特标识，然后在所有组之间构造个外层，并赋予每个组个比特标识。则网络中的节点可唯地由标识。相应地每个关键字是个比特的数值，仍记为或。它的高位比特和低位比特是通过对文件名或关键字进行两次不同的哈希运算产生的。图中的是根据和组织的，则是根据和组织的。并不寻求重叠网络和物理网络严格匹配，而是采取把的覆盖范围控制在个合适的局部物理网络上，从而有效地降低每逻辑所对应的平均物理时延。区域划分的可以利用节介绍的方法。图中，的插入过程设，是节点要向系统中插入的个，对，又表示为。这个......”。

3、“.....并在中路由到该组负责的节点插入第二次。从这个过程可以看出，每个关键字都分两次存放到系统中，从而改变了关键字在原来中的分布。这是和的不同所在，也是层次化能支持部分查询的根本原因。中，的获取过程对于整体查询请求，节点先根据把查询报文路由到负责给定的组，在该组中查找负责的节点。对于部分查询请求，节点先在所属组内查找负责的节点，如果找到满足要求的，对，则本次查询结束否则象整体查询那样在上把查询报文往负责的组路由，期间每经过个组都要先路由到该组内负责相应的节点，若找到满足要求的，对，则查询结束，否则由该节点把查询报文转发给后面的组直到取得要求的，对或者到达负责的组中负责的节点。下面详细给出的操作过程。的查询过程与相比，为了能在组间和组内寻路，节点需要维护组间路由表和组内路中国科学技术大学硕士学位论文第章利用拓扑信息改进由表......”。

4、“.....表和中的表不同在于每个表项中维护了相应组中的个代表节点。表和给出了和表的示例。表示标识为的组，而则表示标识为的组中节点标识为的节点。表给出了中整体查询算法的描述。符号，表示在组或节点标识圆环上从不包括顺时针移动到包括所获得的标识子空间。的部分查询算法比较简单，只需在路由经过的每个组中都查找该组内负责相应的节点，旦找到满足要求的的，对，则查询提前结束。组的加入假定新加入节点已经知道网络中的个或多个引导节点。获得引导节点的方法有很多，例如中就给出了种机制。本节仅利用已有的方法，并不讨论这方面的内容。如果组已经存在于之中，那么节点的加入请求通过路由到组中任何个节点后，加入的过程同基本类似。本文仅讨论组需要创建的情况。为了使组加入的过程平稳，每个节点还需要维护表。该表维护数个候选组，用来保存那些可能组成新的后继组的节点。从引导节点中取得表后......”。

5、“.....在组中广播通知有节点要求加入系统，中所有的节点在自己的表中的组中若没有，则创建该条目增加。然后检查中节点数目，若小于则不把组引入到中，可能属于组的节点暂时仅具有提出查询功能，不负责存储，对。否则若节点数目为个，组中所有节点独立检查自己是否存储的，对，若是则测试所有个中的节点，若均为活动节点，则通知个节点构建并初始化其表，。并在组中广播新前驱组加入报文，该组所有收到此报文的节点将自己表中的从改为，然后由属于相应组的个节点表组中节点的表表组中节点的表根据表查找∈，∈，从中随机选择个节点从中随机选择个节点根据表查找∈∈，∈，表整体查询算法中国科学技术大学硕士学位论文第章利用拓扑信息改进中存储的，对的节点在组中广播新后继组加入报文，组中所有收到该报文的节点将其表中用置换，并删除表中的。组的退出的正确性是建立在每个节点都知道其后继节点的基础上的......”。

6、“.....这在文献中已有详细的讨论。然而在维护的正确性时，需要特殊的考虑。由第节分析知道，上面的组创建过程可以保证，中个组内的个活动节点同时失效的概率很小。即便如此，本节借鉴的做法仍然给出了检测组失效的机制。为此，每个节点可以额外维护紧接其所属组后的个后继组，旦检测到最临近的后继组失效，可以用下个后继组来置换。这样只有当所有个组同时失效的情况下，才被破坏。每个组失效是近似独立的哈希函数的随机性可以保证这点，设失效概率是，则个组同时失效的概率是。如果组中节点在进行查询或插入操作时，发现表中内所有个节点都失效，则在组中向所有节点广播组中是否有活动节点的询问消息，收到此消息的节点测试其所维护的中个节点，若发现中有活动节点且没有收到其它节点发送的应答消息，则在组中广播应答消息组中有活动节点。组中的任何节点在收到此报文时，若发现其中有失效节点......”。

7、“.....进步更新其中个节点信息。否则，各节点将组从表转移到表中，同时把下个后继组作为，并通知该组内所有节点将前驱组改为组。性能评估和进步的讨论组创建过程中参数的选取网络中节点的频繁加入和退出会给系统带来较大的开销，为了解决这个问题，我们在创建组时使用了个门限参数，使得中的组的创建过程比较平稳。当个物理网络局部仅有少数几个节点加入网络时，这几个节点不组成，即不对外提供检索能力，仅具有提出查询请求的功能。旦活动节点数目达到系统中设定的门限并创建组后，那么属于该组的后来节点只需以很小的开销即可加入到中。例如，就等效于不设门限，此时组的创建和退出会比较频繁而明显就要优于不设门限的情形。可以把潜在的组看作是没有等待时延的个排队系统。近似认为该组内节点到达加入网络是参数为的泊松过程，服务时间节点存在于网络中是参数为的指数分布，该系统的服务员数量是无穷个，即个∞排队模型......”。

8、“.....则节点在系统中的平均时延就是其平均服务时间。根据定理，稳态时中的平均节点数。使用门限参数的目的是保证稳态时节点数的组不创建没有到达稳态或不能到达稳态的组也不创建。然而和不仅依赖于不同的潜在组而且也依赖于特定的应用，因此也就很难给出各个潜在组稳态节点数的般信息。但是这并不妨碍尝试给设定个初值从而使获得较好的性能。为此我们下步要做的工作之就是，针对特定的应用，通过逐步增大并仿真来找到个合适的值。中国科学技术大学硕士学位论文第章利用拓扑信息改进对查询和插入操作性能的改善查询或插入个，对的平均时延是衡量个系统性能的重要指标，可以用查询路径包含的跳数乘以每跳所对应的平均物理时延来表示。设网络中具有个节点，无论是整体查询还是部分查询提供的查询性能都是。为了问题的简化，我们假设网络中的链路都是对称的，由于哈希函数的随机均匀性，则应当是网络中所有可能的节点对之间时延的平均......”。

9、“.....。而，的组合数为，且每种组合对应于，的概率可以认为都是均等的，为。设，之间的时延为，为网络中所有的节点集合，则有，很明显，因为组内剔除了长时延链路，所以内每逻辑跳对应的平均物理时延记为，而中的记为比在整个网络上构造会有显著的降低。在中，假设有个节点和个，部分查询的性能是整体查询的性能是，当或时，就退化为，性能为。显然，的查询性能要比优越。结语和未来工作通过把网络中节点划分为多个组，在各个组内构造并在所有组之间构造，中各个节点完全对等，避免了单点瓶颈与节点离开的概率相比，组离开的概率较小，因而系统更平稳。在部分查询时，提供了比简单系统更优越的性能。进步的工作包括寻找更有效的划分组的机制，和针对不同的应用对进行仿真。中国科学技术大学硕士学位论文第章利用拓扑信息改进本章小结本章首先指出现有系统存在的最大问题之......”。