短路径优先的覆盖网络构造

吴国福，韩岗，窦文华

（国防科技大学 计算机学院，湖南 长沙 410073）

1 引言

P2P系统中 Peer节点显示或隐式地形成覆盖(overlay)网络。短路径优先的覆盖网络构建策略使逻辑连接尽可能限制在自治域范围内，能有效减少主干网流量，加快信息的传播速度。短路径优先策略需要获知节点之间的网络延迟，如果直接测量网络延迟，随着系统规模的增大，探测报文产生的开销将远大于覆盖网络结构优化带来的收益。理想的方案应该是低成本、分布式、易扩展的。

网络坐标系统[1]将网络中节点映射到有限维度度量空间，使用节点在度量空间的距离估算网络延迟。本文提出基于被动路标的网络距离预测技术，利用 Internet上已经部署的服务器对探测报文的响应，获得节点到路标的网络延迟，通过Lipschitz[1]变换将节点网络延迟映射到有限维度量空间中的元素，然后使用网络距离函数估算网络距离。

网络距离预测技术以较小的网络开销准确地估算节点间的网络延迟，新的问题是节点如何快速定位临近节点。一种好的思路是先快速筛选一组可能的临近节点，缩小计算范围；然后从中选择距离最近的临近节点。本文引入空间填充曲线(SFC,space filling curve)[2]技术并提出基于查表的映射算法完成快速筛选的预处理工作。

综合网络坐标技术和空间填充曲线技术，本文提出短路径优先的覆盖网络构建策略。通过较小的网络开销和计算代价，节点获得临近节点的信息并与之建立逻辑连接。短路径优先策略使得逻辑覆盖网络与底层物理网络拓扑结构尽可能匹配，有效减少物理链路上的重复报文。实验结果表明，本文方法构建的覆盖网络具备良好的性能。

文章的后续组织如下：第2节介绍相关工作，第 3节提出基于被动路标的网络距离预测技术，第4节提出基于查表的对角线空间填充曲线映射算法，第5节给出短路径优先的覆盖网络构造方法，第6节实验验证本文方案的有效性，第7节是结束语。

2 相关工作

P2P应用系统中，消息沿着覆盖网络中继传输，其质量对系统性能有重要影响。覆盖网络中一跳对应物理网络中的一条端到端路径。逻辑路径P对应的物理路径集合，称为实际路径。以逻辑路径P的起始节点开头，在物理网络中遍历 P上所有 Peer节点的具有某种最优属性（如最短距离）的路径P’，称之为理想路径（理想路径可能不只一条）。如果实际路径中Peer节点的访问顺序与理想路径中Peer节点的访问顺序一致，称之为路径完美匹配。如果覆盖网络中所有的逻辑路径都是路径完美匹配的，则称覆盖网络是拓扑完美匹配的。实现拓扑完美匹配是困难的，实际中学者一般利用某种网络结构信息优化覆盖网络，使其与物理网络在拓扑上尽量匹配。实现拓扑匹配有2种策略：一是直接构造拓扑匹配地覆盖网络；二是动态优化覆盖网络，使其与物理网络相匹配。下面介绍相关文献中的典型方法。

S.Ratnasamy[3]等提出基于节点分类的方法构建拓扑匹配的覆盖网络。物理网络中距离近的节点划为同一类别，称之为一个bin。分类方法如下：网络中部署一组路标节点，节点测量到各个路标节点的网络距离；按照从小到大的顺序排列网络距离，从而获得路标节点的序列，将该序列作为节点的bin。节点选取邻居节点时，首先从同一个bin中选取，数量不够时从差别最小的bin中继续选取。

Mithos[4]基于网络坐标系统构建连接高效覆盖网络。节点加入系统时根据初始邻近节点的网络坐标计算自身网络坐标；节点以自身为中心在每个象限内寻找最近节点与之建立邻居关系。该方案初始加入过程冗长，节点需要经过多次迭代才能在系统中找到临近节点；节点坐标一旦确定后不再变化，这与P2P系统的动态特性不相适应。

Zhichen Xu[5]等结合基于路标的分类技术和小范围直接测量技术选择邻近节点。使用基于路标的分类技术选择与自身类别相同或相似的部分节点，然后直接测量网络距离以选取最近的节点。系统将节点到路标的网络距离信息作为系统软状态分布保存在相关节点上，其他节点根据到路标的距离信息查找到相关节点获取同类别或相似类别的节点信息。

SAT-Match[6]是一种针对结构化覆盖网络CAN[7]的局部优化措施。每次迭代由2个阶段组成：探测阶段和跳转阶段。在探测阶段，节点S在限定范围内（比如两跳内）泛洪探测报文，收集限定区域内节点的IP地址，然后测量网络传输延时。在跳转阶段，判断是否跳转应该对比跳转前后该区域内所有节点平均逻辑连接长度的变化，如果变小则进行跳转。在结构化覆盖网络中节点状态与节点位置密切相关，SAT-Match优化过程需要大量跳转操作，状态迁移和探测报文会给系统代理沉重的负担。

Quasi-Chord[8]直接利用GNP[9]技术预测网络距离构建Chord[10]覆盖网络。首先使用网路距离预测技术 GNP获取节点网络坐标，然后使用二维卡托空间填充曲线对网络坐标作映射得到节点序号，最后使用序号作为标识符构建环形覆盖网络。

LTM[11]是一种分布式的基于位置感知局部优化技术，其主要使用2种操作提高拓扑匹配度：剪枝操作、加边操作。剪枝操作主要针对图1(a)和图1(b)2种情况，在图1(a)中，节点S向外泛洪TTL＝2的探测报文，节点P接收到节点S发送的探测报文和节点N1转发的探测报文，计算出连接PS、PN1和SN1的长度LPS、L1PN、L1SN。如果LPS或者L1PN明显长于其他2条连接，则将其剪除。同样在图1(b)中，节点P获取L1PN、L2PN、L1SN、L2SN的长度，如果L1PN或者L2PN明显长于其他3条连接，则将其剪除。加边操作发生在图1(c)的情形，节点S与节点P之间没有直接连接，节点P接收泛洪报文后主动探测到节点S的网络传输延迟LPS，如果LPS明显长于L1PN、L1SN，则不需添加新边，否则添加新边PS。LTM存在一些不足：①需要大量迭代才能取得较好的效果；②节点要保持时间同步，现有的网络时间协议服务精度有限，影响优化效果。

图1 LTM中的剪枝、加边操作

3 基于被动路标的网络距离预测

本节提出一种基于被动路标的网络距离预测方法，从而获得物理网络的拓扑信息以指导覆盖网络的构建。

3.1 网络距离预测方案

在基于网络坐标系统的网络距离预测方案[1]中，大都引入路标节点。路标或者全局固定不变，或者由随机选择的普通节点担当，2种方法各有缺陷。前者部署成本昂贵，通用性差；后者容易产生误差积累并且坐标易陷于局部最优。目前 Internet上存在大量的高性能稳定的服务器节点，如 DNS服务器、Web服务器等，响应端节点的探测报文。如果利用这些节点充当路标，既解决路标全局不变方案中部署成本昂贵的问题，又解决路标随机选择方案中的误差累积和局部性问题。但是这些服务器节点只被动响应客户端请求，无法主动对外探测，需要特殊方法利用其路标功能。

Internet上的节点是按一定层次结构组织的，这种结构使得区域内节点间延迟小，而区域间节点间延迟大。网络距离近节点往往处在同一区域中，到路标的网络距离较为接近；网络距离远节点可能处在不同区域中，到路标的网络距离差异较大。直接使用节点到路标的网络传输延迟作为节点的网络坐标，坐标值之间的欧式距离能够反映出节点的网络距离。

鉴于上述认识，提出基于被动路标的网络距离预测方法（PLNDP, passive-landmark based network distance prediction）。PLNDP整体思路是：在Internet上搜索已经部署的高性能服务器作为路标节点；普通节点提前获知路标通信地址并测量到各个路标的网络延迟，使用Lipschitz变换获取网络坐标；通过中心服务器交换网络坐标，普通节点使用特定的距离函数计算网络坐标在向量空间Rn中的距离，进而预测节点间的网络距离。

3.2 网络距离预测方法执行过程

3.2.1 路标节点的选择

Internet上已经部署高性能服务器节点大多数响应客户端的探测报文，端节点使用ping命令很容易获得到服务器的网络延迟。选择哪些服务器节点作为路标需要解决下面的问题。①路标节点的数量k，数量过多产生大量探测报文，同时会提供冗余信息；数量太少使得预测结果偏差过大。实验结果表明，数量在8～10之间就可获得较高的预测准确度。考虑到路标节点的失效，认为路标数量在 12个比较合适。②路标节点的分布区域，为了发挥参考作用，路标应该分布在合理的范围。其范围取决于应用程序的使用范围，如果应用程序面向整个Internet，则路标节点应该分布在全球各个地方；如果应用程序是区域性的，比如面向中国大陆地区，则路标节点应该限制在区域以内。③路标节点的相对位置，距离太近的路标提供的信息存在很大的冗余，因此路标节点应该尽可能分散。实验表明随机选择即可。本文在应用程序使用范围内搜集性能稳定的大型服务器，从中选择数量合适、均匀分布的服务器作为路标节点，其他服务器留作备份使用。

3.2.2 普通节点获取网络坐标

路标节点的地址和序号提前发送给普通节点，普通节点i发送echo request 探测报文到所有路标节点，接收到echo replay响应报文后计算往返传输延迟RTT，则节点i到对应路标的网络延迟近似为RTT/2。普通节点可多次测量 RTT，选择延迟的最小值或者平均值来规避网络暂时拥塞带来的影响。当测得到所有路标节点的网络延迟后，普通节点使用Lipschitz变换获得自身网络坐标。失效路标节点对应的坐标元素值为0。

3.2.3 网络距离预测

普通节点获取自身网络坐标后，向中心服务器注册。普通节点通过中心服务器或者其他节点获取感兴趣节点的网络坐标，使用距离函数计算两者之间的网络距离。假设路标节点的数量为 n，普通节点 a、b坐标分别为 ( a1, a2,… ,an)、(b1, b2,… ,bn)。原始坐标不能直接进行距离计算，要对其进行两方面的预处理。首先去除失效路标，失效路标对应的坐标元素值为 0，去除失效路标对应的坐标元素得到新坐标。由于路标节点是性能稳定的服务器，失效概率很低，该方法完全可应对路标失效问题。其次去除冗余路标，如果普通节点a、b到路标节点A、B的网络传输延时之差相当，则认为A、B对a、b的参考作用相同，A、B相对于a、b而言是互为冗余的，保留一个即可。将失效路标和冗余路标对应的坐标元素去除后，a、b的新坐标变为(a1′ , a2′ ,… ,am′ )、( b1′ , b2′ ,… ,bm′)，m为有效路标节点数目，则 a、b之间的网络距离由下面的距离函数计算得到：

下面举例说明PLNDP的具体操作。在图2所示的网络拓扑结构中，选择节点 ACDEFH作为路标节点，abc为普通节点，连接线上的数字表示节点间的传输延迟。假设路标E对节点a是失效的，则节点 a、b、c的坐标分别为（3，3，6，0，9，13）、（13，9，6，6，3，3）、（8，6，1，7，4，8）。计算 a、b之间的距离时，剔除失效路标得到坐标（3，3，6，9，13），（13，9，6，3，3），无冗余路标，计算得到Lab=12.78。计算b、c之间的距离时，b、c到路标A、D的距离差都是5，所以A、D相互冗余，去掉路标D，同样路标E、F也是相互冗余的，去掉路标F，得到新坐标（13，9，6，3），（8，6，7，8），计算得到Lbc= 6.71。同理可得Lac= 7.7。a、b、c之间的实际距离为Mab=12、Mbc=7、Mac= 7，预测误差分别为6.5%、4.1%、10%。预测距离与实际距离较为接近，该方法具有较高的预测准确度。

图2 随机连接网络

3.3 动态网络环境下PLNDP的处理

在网络环境动态变化情况下，将网络看作由一系列快照组成，快照持续时间为τ，在时间τ内，网络变化可忽略。PLNDP每隔周期 T更新节点的网络坐标，如果限制 T＜τ/2，则保证坐标测量和预测在同一网络快照内完成，仍然可以看作PLDNP在静态网络中运行。只要合理设置更新周期T，PLDNP在动态网络中仍保持高的预测准确性。

4 基于查表的空间填充曲线快速映射算法

基于被动路标的网络距离预测较为准确地预测节点之间的距离信息。当节点需要获取临近节点集合时，最直观的方法是计算到所有节点网络距离，然后挑选最近的节点集合。在大规模分布式系统中，这种方式将导致计算资源紧张。一种有效方法是首先快速筛选出一组粗糙节点集合，然后通过精确计算确定所需的节点。本文引入空间填充曲线技术完成快速筛选工作。本节主要介绍基于查表的空间填充曲线快速映射算法，快速筛选方案在下一节给出。

4.1 空间填充曲线介绍

空间填充曲线是数据降维处理的典型方法，在多维空间元素映射与整数之间建立一一映射关系。皮亚诺[12]首先提出空间填充曲线的概念，给出单位长度到单位正方形的连续满射函数，即皮亚诺曲线。希尔伯特[13]扩展了空间填充曲线的概念，给出单位长度到单位d维立方体映射的几何构造。空间填充曲线一个良好性质是映射具有临近性，即2个元素在D维空间中临近，像点在数值上保持接近。图3给出了几种典型的2维空间曲线填充示例。

4.2 对角线空间填充曲线

图3 2维空间填充曲线

已有文献给出的空间填充曲线映射算法或者局限在二维空间内，或者计算较为复杂。本文给出对角线空间填充曲线的映射算法，计算简单且容易扩展到高维空间。在下面的描述中假定原始空间的维度为m，每一维度上有个格点，格点的序号从1开始计数。首先规定对曲线的访问规则，假设格点C = (c1,c2,…,cm)和 C′=( c1′, c2′,…,cm′)的序号分别为p、q，令则 p＜q当且仅当下列条件之一成立：① k

4.3 对角线空间填充曲线映射算法

当m=2时格点的访问顺序很直观，求解的方法很多；对于高维空间m＞ 2 中的格点C =( c1, c2,… ,cm)，如果简单使用递归方法求解其计算量随m和g成指数规模增长。下面给出基于查表的空间填充曲线快速映射算法。

首先引入等势面的概念，等势面是指坐标元素之和相等的所有格点集合，用符号Ek表示，其中下标 表示等势面高度，即格点坐标元素之和，显然k≥ 2 。对于格点令由必要条件知格点 C的顺序 SFC_Order(C)决定于Ei中元素的数量|Ei|(i ＜k)和C在Ek中的顺序Ek_Order(C)，即

下面分别介绍Ek中元素数量|Ek|和C在Ek中顺序Ek_Order(C)的计算方法。

本文使用函数 f ( k, g, m) 表示等势面 Ek中元素的数量。由于k是格点的坐标元素之和，所以k的有效取值范围是[0,m( g- 1 )]，规定

当m=1时每个等势面只有一个格点，即

k=0当且仅当格点坐标每个元素值都为 0，也就是说等势面E0中仅有一个元素，即

等势面 Ek中格点 C =(c1, c2,…,cm)的坐标元素值之和为k，首先考虑cm的取值，当cm取0时其他m-1个元素之和必须为 k，即 cm取 0时共有f( k, g, m- 1 )个格点在 Ek中，同理当 cm取i∈[0,g -1]时，共有f( k -i ,g, m- 1 )个格点在Ek中，因此可得

这样m维等势面元素数量可用多个(m-1)维等势面元素数量之和表示。同样m维高度为k-1的等势面元素数量可表示为

式(7)、式(8)相减得到函数 f ( k, g, m )的递推关系。

f( k, g, m )- f( k- 1 ,g, m )=f( k- 0 ,g, m- 1)-f( k-1 -g+ 1 ,g, m-1)

即

使用式(3)～式(6)以及式(9)，可依次快速求解各个维度上不同高度的等势面中含有的元素数量。

确定格点顺序还需要求解格点 C= (c1, c2,…,cm)在等势面中的顺序。求解思路如下：假设格点 X =( x1, x2, …,xm-1,xm)位于等势面 Ek中并且X在中的顺序p小于C在Ek中的顺序q，根据条件(2)求解满足条件的数量。先考虑 x1的取值，当 x1∈[0,c1-1]，xi∈[0,g-1](i ∈[2,m])时，因为x1＜c1，根据条件(2)得知p＜q，这种情况下 X的数量固定 x1= c1，考虑 x2的取值，当 x2∈[0,c2-1]，xi∈ [ 0,g- 1 ](i∈[ 3,m])时，因为x1=c1且x2＜c2，由条件(2)得知 p＜q，这种情况下 X 的数量依次可得显然Nm=0。上述推导过程中各个Ni之间没有重叠部分且涵盖X所有可能取值，所以满足条件的X数量为则C在等势面中的顺序为N+1，即

结合式(2)和式(10)得格点 C = (c1, c2,… ,cm)在对角线空间填充曲线中的访问顺序为

等势面中格点元素数量表可离线构造，函数 f值通过查表获得，根据式（11）在O(mg)时间内可得到格点C在对角线空间填充曲线中的访问顺序。

5 短路径优先的覆盖网络构建

5.1 传输路径对传输效率的影响

P2P系统中，覆盖网络与物理网络的拓扑匹配程度对消息的传输效率有重要影响。两者不相匹配导致消息传输效率低下，例如当北京大学的节点发送消息到清华大学的节点经过斯坦福大学中的节点中继时，会极大增加传输延迟。短路径优先策略使得节点在2个网络中的相对位置尽量一致。图4展示了采用短路径建立覆盖网络的优势。图4(a)显示的是原始物理网络拓扑结构，假设每条链路的传输延迟为单位1，图4(b)、图4(c)分别展示2种不同结构的覆盖网络，其中图4(b)采用短路径将节点连接在一起。当节点1有单位消息发送到其他3个节点时，图4 (b)中拓扑仅需要3个单位的时间，每条物理链路上仅通过一次消息；图4(c)中拓扑则需要6个单位时间，其中链路l23上通过3次消息，链路l34上通过2次消息。

图4 不同覆盖网络对消息传输的影响

5.2 覆盖网络构建过程

本节综合运用网络距离估计技术和空间填充曲线技术，采用短路径优先覆盖（SPF-overlay,shorter path first overlay）的策略构建拓扑匹配的网络。使用基于被动路标的网络距离估计技术估算节点之间的传输延迟，在空间填充曲线技术的辅助下，快速选择距离最近节点与之建立邻居关系。下面详细描述其过程。

1) 生成、存储网络坐标

普通节点P测量到路标的网络距离获取自身网络坐标Cp。如果直接对Cp进行空间填充曲线映射（假设Cp中元素均为整数），由于Cp变化范围较大，像点稀疏地分布在巨大数值空间中，给快速检索带来困难。因此对Cp中元素进行量化处理，采用具有g个量化等级的非均匀量化方法，前g-1个等级的量化步长为t ms，最后一个量化等级的量化步长为+∞大，这样Cp中元素ci的量化值为ri=min{cimod t,g-1}。将量化后的坐标值进行对角线SFC映射得到像点fp。节点p将网络坐标Cp、fp以及通信地址发送至中心汇聚节点RP。汇聚节点RP以fp为索引存储网络坐标Cp及其通信地址。为提高查找速度，存储采用如下策略：如果SFC值域空间D大小低于阈值W，则使用哈希链表存储节点记录；否则值域空间D等分为S个不同的子空间，fp属于子空间i则将节点记录存储在子集合si中。阈值W大小取决于汇聚节点可用存储空间大小。

2) 快速筛选临近节点

节点 p需要获取临近节点信息建立邻居关系时，向汇聚节点RP发送请求信息。请求中包括节点p的网络坐标映射值fp以及要求的邻居节点数量k。汇聚节点RP查找与节点p临近的一组节点（例如 2k），并通告给节点 p。查找临近节点策略与存储策略相对应。当采用散列链表存储节点记录时，汇聚节点在以节点p的映射值fp为中心，半径依次增大的超立方体中寻找临近节点。图5显示了在二维空间的搜索过程，RP首先在节点 p所处的格点中查找有无临近节点，然后查找半径d=1的所有格点，依次扩大搜索范围，直至发现所需数量的临近节点。当采用子集策略存储节点记录时，根据fp确定其所属子集si，然后以子集si为中心，在左右延伸的子集中寻找足够数量临近节点。

图5 二维空间中临近节点搜索过程

3) 计算确定最近节点集合

汇聚节点只是对临近节点进行粗糙筛选，节点p通过距离函数获得更准确的信息。节点p使用网络距离公式计算到临近节点的距离，选择距离最近的k个节点与之建立邻居关系，其余节点作为候选邻居节点。

4) 建立邻居关系

节点p向距离最近的k个节点发送建立连接请求，如果临近节点能够接纳新的连接则响应请求，并在邻居列表中添加新的记录；否则拒绝。如果被接受，节点p增加新的邻居记录；否则从候选节点中选择新节点请求与之建立邻居关系，直至邻居节点的数量达到要求。

5.3 覆盖网络构造协议的其他部分

覆盖网络连通性保证：分布式方式建立邻居关系，不能保证建立的覆盖网络是连通的；同时节点根据网络状况调整邻居关系也有可能导致覆盖网络的分裂，因此需要一定的机制来保证网络的连通性。采用如下的连通性保证机制：根节点周期性向外广播连通性报文，报文序号标识报文的新旧。节点接收到连通性报文后，对比记录中的序号，如果新接收的报文序号大于记录中的序号，则将报文转发给邻居节点，并且更新记录中的序号和时戳，否则不采取任何动作。节点在一定时间间隔内没有更新连通性报文序号，则假定覆盖网络已经形成网络孤岛，节点以一定概率建立新的连接。采用上述保证机制，在每个周期内节点接收和发送的报文数量是其邻居数量的2倍，对系统影响可以忽略。

局部动态优化：节点加入覆盖网络后动态调整邻居关系以适应网络的变化。邻居节点相互交换临近节点列表以选择更近的邻居节点。节点将邻居节点的数量限制在k～2k之间，当发现更近节点或邻居数量不够时尝试建立新的邻居关系；当网络资源紧张或者邻居节点不能为该连接提供足够资源（包括邻居节点失效）时，则剔除部分邻居关系。

节点退出系统：P2P系统一个重要特性是节点的不稳定性。节点退出系统时，向邻居节点和汇聚节点发送退出消息。汇聚节点收到退出消息后删除该节点对应的记录。邻居节点收到退出消息后，检查该节点是否在临近节点列表中，如果在则删除相关记录并将退出消息转发给邻居节点以删除邻居节点缓存的信息。节点退出使得邻居节点连接数量减少，可能触发建立新的邻居关系。节点被动失效（如强行杀死进程、网络断掉）在交换内容消息时检测，节点一旦发现邻居节点失效，向汇聚节点通告，在删除本地对应记录同时通告其他邻居节点。

更新节点网络坐标：节点周期性测量到路标的网络延迟重新计算其网络坐标，如果新、旧网络坐标之间的距离超过门限值则需要更新网络坐标，并将新的网络坐标通告汇聚节点和邻居节点。网络坐标关联一个顺序号，每更新一次顺序号递增，这样不会因网络延迟等原因混淆。

路标失效的处理：网络拥塞或者路标失效导致无法测得到路标的网络延迟，其网络坐标中对应的元素值为 0。对网络坐标中的零元素进行量化时，假定节点在该维度上与所有其他节点都是临近的，即零元素的量化值分布在每个量化等级上，相当于将节点复制g份（g为量化等级）。

6 实验分析

本节通过模拟实验验证方案 SPF-overlay的有效性，旨在构建拓扑匹配的高质量覆盖网络，减少消息传播时间。本文引入匹配度来定量描述覆盖网络与底层物理网络的拓扑匹配程度。称覆盖网络中路径为实际路径，称物理网络中的最短路径为理想路径。下面给出路径匹配度和拓扑匹配度的定义。

路径匹配度：覆盖网络中不相邻的2个节点理想路径与实际路径长度的比率。

拓扑匹配度：覆盖网络中所有不相邻节点之间路径匹配度的均值。

在上述定义中没有考虑覆盖网络中直接相连节点之间的匹配度，因为其路径匹配度为常数 1，不能体现覆盖网络与物理网络的匹配程度。

6.1 实验设置

在讨论拓扑匹配时使用如下的网络模型：物理网络由路由器节点相互连接构成，端节点粘贴在与其相连的路由器节点上，到对应路由器的网络距离忽略不计，物理网络与覆盖网络均采用最短路径路由策略。

本文采用文献[14]的方法生成具有10 000个路由器节点的物理网络拓扑。覆盖网络节点规模变化范围为1 000～5 000，默认数量为2 000。覆盖网络中节点的邻居数量k取值范围为4～10。PLNDP中路标节点数量为10，在路由器节点中随机选取。实验中比较4种不同的覆盖网络构造方案：①最短路径方案，这是一种集中式的算法，每个节点测量到其他所有节点的距离，然后选择距离最近的k个节点作为邻居，同时保证整个覆盖网络的连通性，下文中以“best”标识。②SPF-overlay方案，每个节点按照5.2节中介绍的过程分布式加入到覆盖网络中。网络坐标的量化等级设为 5，使用散列链表存储节点记录，在半径依次增大的超立方体中寻找最近节点。覆盖网络构造完成后继续进行局部动态优化操作，本文初衷是直接构造高质量的覆盖网络，因此实验中仅验证 SPF-overlay方案中初始构造的覆盖网络的质量，下文中以“SPF”标识；③随机的覆盖网络构造方案，节点随机地选择 个节点作为邻居节点，下文中以“rand”标识；④LTM方案，在随机覆盖网络的基础上进行LTM中的优化操作，下文中以“LTM”标识。LTM方案中迭代的最大次数为200次，迭代终止条件为在一次迭代过程中优化的连接数量小于整个覆盖网络连接数量的万分之一。一次迭代过程指所有节点都向外泛洪一次探测报文并优化连接。LTM中剪枝的截止系数设为1.6，也就是长边长度至少是短边的1.6倍时才被剪除；加边的截止系数设为1.3，也就是增加的连接的长度最多不能超过现有相关连接的1.3倍。模拟实验的硬件环境为普通桌面PC机，3.0GHz Pentium 4 CPU，2GB内存，模拟软件采用MATLAB 7.0。

6.2 实验结果

图6显示了4种不同覆盖网络单跳逻辑连接长度的分布，可以看出best和SPF方案形成的覆盖网络中边的长度比较集中且明显比 LTM 和 rand方案中短。best方案较SPF方案优势更为明显，但是 best方案中节点需要获知全局网络状态信息，可扩展性差，网络规模受到限制。LTM在迭代过程中每个节点平均调整 6.4条逻辑连接，其中平均增加逻辑连接 3.6条，剪除逻辑连接 2.8条（增加的逻辑连接比剪除的多是因为程序中放松了对节点度的限制）。图7显示了4种不同方案中节点之间逻辑路径长度的累积分布，best方案中逻辑路径平均长度最小且路径长度分布范围集中。SPF方案中路径长度分布相对分散，不如其余三者集中，主要原因是选择邻居节点时由于预测误差导致选取远距离的节点。但是相比LTM和rand方案还是具有优势，特别是短路径所占比例明显高于后两者。例如SPF中路径长度小于500的占所有路径数量的57.2%，而LTM中为27.7%，rand中仅为10.5%。

图6 逻辑连接长度的分布

图7 逻辑路径长度的累积分布

图8显示了路径匹配度的分布，SPF的表现好于LTM和rand方案，特别是路径匹配度小于0.25的路径在SPF方案中所占比例极小，可以忽略。相反在 LTM 和 rand方案中大量路径的匹配度小于0.25。4种方案的拓扑匹配度分别为0.616、0.438、0.366、0.306。

图8 路径匹配度的分布

图9显示了拓扑匹配度随系统规模的变化，best和SPF方案中略微增长，而LTM和rand方案中稍微有所下降。这是因为在保持节点度不变的情况下，随着系统规模的增大，SPF中找到临近节点的可能性增大，而 LTM 中逻辑路径的跳数增加，需要更多的迭代次数才能保持匹配度不变。SPF方案相比LTM具有更好的扩展性。

图9 拓扑匹配度随系统规模的变化

假设邻居节点数量为 k。best方案需要获取全局信息，其通信开销O(n2)。SPF通信开销由2个主要部分组成，①测量到路标的网络延迟，路标的数量为常数，测量开销O(n)；②获取临近节点信息并与邻居节点建立逻辑连接，通信开销为O(kn)。LTM是在随机网络基础上做局部优化，建立随机网络的通信开销为O(kn)；局部优化时测量到2跳范围内节点的网络延迟，测量开销取决于邻居节点的数量和迭代次数。图10显示SPF和LTM方案在不同的网络规模下需要的通信消息数量。SPF的通信开销远小于 LTM，但是 SPF方案在筛选临近节点时需要一定的计算量。

图10 额外通信开销的比较

7 结束语

P2P应用中消息沿着覆盖网络中的peer节点中继传输，如果覆盖网络与底层物理网络拓扑不相匹配，不仅增大消息的传播延时，而且增加主干网的网络流量。因此构建拓扑匹配的覆盖网络是提高大规模P2P应用系统性能的关键因素之一。若有网络拓扑信息的指导，节点在加入覆盖网络时会找到更好的邻居节点。本文提出短路径优先的覆盖网络构建策略，主要工作包括以下3个方面：①提出基于被动路标的网络距离预测算法，提供节点间较为准确的网络拓扑信息；②提出基于查表的对角线空间填充曲线快速映射算法，解决快速提取具有相关拓扑信息节点的问题；③综合网络距离预测算法和空间填充曲线技术提出拓扑匹配的覆盖网络构造算法SPF-overlay。实验结果表明SPF-overlay方法构造的覆盖网络比随机网络和 LTM 算法能够更好的匹配底层物理网络；同时本文以计算开销代替网络开销，使得SPF-overlay的额外网络负载开销更小，具备良好的可扩展性，能够提高大规模分布式系统的性能。

[1] LUA E, GRIFFIN T, PIAS M. On the accuracy of embeddings for internet coordinate systems[C]. Proc of IMC05[C]. USENIX Association Berkeley, CA, USA, 2005. 1-11.

[2] SAGAN H, Space Filling Curves[M]. Berlin: Sprubger, 1994.

[3] RATNASAMY S, HANDLE M, SHENKER S. Topologically-aware overlay construction and server selection[A]. Proc of INFOCOM 2002[C]. New York, USA, 2002.1190-1199.

[4] MARCEL W, RINALDI R. Efficient topologyaware overlay net-work[J]. ACM Computer Communication Review, 2003, 33(1):101-106.

[5] XU Z, TANG C, ZHANG Z. Building topology-aware overlays using global soft-state[A]. Proc of the 23rd International Conference on Distributed Computing Systems[C]. Washington, DC, USA, 2003. 500-508.

[6] REN S, GUO L, ZHANG X. SAT-match: a self-adaptive topology matching method to achieve low lookup latency in structured P2P overlay networks[A]. Proc of the 18th International Parallel and Distributed Processing Symposium(IPDPS'04)[C]. 2004. 83-91.

[7] RATNASAMY R, FRANCIS P, KARP R. A scalable content-addressable network[A]. Proc of SIGCOMM2001[C]. San Diego, CA, USA, 2001.161-172.

[8] SUN M, ZHANG Z. Quasi-chord: physical topology aware structured P2P network[A]. Proc of the 11th Joint Conference on Information Sciences[C]. Shenzhen, China, 2008.

[9] EUGENE T, ZHANG H. Predicting internet network distance with coordinates-based approaches[A]. Proc of INFOCOM2002[C]. New York, USA, 2002.170-179.

[10] STIUCA I, MORRUS R, BAKARISHNAN H. Chord: a scalable peer-to-peer lookup service for internet applications[A]. Proc of SIGCOMM 2001[C]. San Deigo, CA, USA, 2001.149-160.

[11] LIU Y, LIU X, ZHANG X. Location-aware topology matching in P2P systems[A]. Proc of Infocom2004[C]. Hong Kong, China, 2004.2220-2230.

[12] PEANO G. sur une courbe qui remplit toute une air plaine[J].Mathiematishe Annalen, 1981, 96(1): 157-160.

[13] HILBERT D. Ueber stetige abbildung einer linie auf ein flashenstuck[J]. Mathiematishe Annalen, 1981, 96(3): 459-460.

[14] ZEGURA E, CALVERT K, BHATTACHARJEE S. How to model an internetwork[A]. Proc of INFOCOM96[C]. San Francisco, CA, USA,1996. 594-602.