基于CAN覆盖网的网络配置同步技术

汪子涵 方滨兴

摘 要：为了高效、可靠地完成各个网络节点的配置文件同步任务，设计了一种基于CAN覆盖网络的配置文件同步模型。为了适应广播应用，优化了CAN覆盖网络的相关实现机制，包括节点加入退出机制以及失效恢复机制。优化后的CAN网络空间划分更均匀，失效恢复速度更快，网络的健壮性更强。另外，和传统的树状分发模型相比，该配置同步模型具有较好的扩展性和低延迟性，配置同步所产生的下载流量不会随着节点数量的增加而线性增加。

关键词：分布式系统；文件同步；CAN；P2P

中图分类号：TP393.08 文献标识号：A 文章编号：2095-2163（2015）04-

Network Configuration Synchronization Technology based on CAN Overlay Network

WANG Zihan1 ， FANG Binxing2

（1 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China； 2 Beijing University of Posts and Telecommunications， Beijing 100876，China）

Abstract： In order to accomplish the synchronization tasks of each network node， a synchronization model based on CAN overlay network is designed. In order to adapt to broadcast applications， the implementation mechanism of CAN overlay network is optimized， including the node joining mechanism and the failure recovery mechanism. In the optimized CAN network， space division is more uniform， the failure recovery speed is faster， and the network's robustness is stronger. Compared with the traditional tree distribution model， the configuration synchronization model has good scalability and low delay. The download traffic generated by the synchronization will not increase linearly with the number of nodes.

Keywords： Distributed System； Configuration Synchronization； CAN； P2P

0 引 言

近年来，各种大型的任务或系统频繁出现，方兴未艾。在这些系统或任务中，各个功能节点往往较为分散，因此，网络配置同步技术显得尤为重要。传统的配置同步技术主要为树状分发模型和层次分发模型，在这两种模型中，网络节点的加入退出对系统整体影响较大[1-2]，当节点数量增加或配置文件较大时，下载节点会产生流量瓶颈。在本文中，即对CAN的实现机制进行了优化，并对优化后的CAN网络实现了仿真，从仿真结果可以看出，优化后的CAN网络更有利于广播应用，最后，本文给出一种基于CAN覆盖网络的配置同步模型。

1相关研究工作以及背景知识

1.1 CAN网络

CAN[3]（content addressable network）是分布式哈希表（distributed sloppy hash table）技术的一种，CAN节点的加入过程主要为：节点自举、获取区域、更新路由表。

在节点自举时，节点A向DNS服务器请求已经存在于CAN网络中的节点IP信息。之后，节点会选择一个引导点B，引导点B将join消息路由到区域中包含目标点的节点C，节点C将部分区域转交给节点A。CAN机制规定节点需定期向自身邻居发送探测消息，当邻居感知到节点A而将节点A补充至自身的邻居表后，节点A便真正加入到了CAN网络中。

1.2 CAN最小冗余度广播

和传统转发树策略需要存储全局节点信息不同，CAN网络只需要借助邻居节点信息就可以实现最小冗余度广播[4]。在CAN最小冗余度广播中，消息传递方式如下[4]：

（1） 源节点将广播消息发送给其所有邻居（泛红法）；

（2） 节点会将从自身在第i维相邻的邻居节点收到的广播消息转发给和自己在第1，…，（i – 1）维相邻的邻居节点和在第i维相反方向相邻的邻居节点；

（3） 节点存储已经收到消息的序列号，节点不会再次广播已经收到的相同消息。

2 CAN优化机制

2.1 CAN广播性能评价指标

当考虑面向P2P的CAN网络时，研究主要关注的是CAN的资源定位能力、查询资源开销和负载均衡等问题[5-7]，但在考虑面向广播的CAN网络时，将更多关心的则是CAN网络的广播能力。在本文中，相应定义了衡量CAN广播性能的间接评价指标，具体描述为空间划分均匀度、节点空间度、GNP坐标偏移度以及节点失效恢复能力。

在此，给出重点评价指标的技术含义，分别是：节点空间度为节点拥有的空间区域数量。偏移距离为节点区域的中心位置与节点目标点的距离，GNP坐标偏移度为偏移距离与区域最大边长的比值。在构建CAN覆盖网时，GNP思想[8]可以有效降低覆盖网络中节点间的传输延迟，但基于霍夫曼思想的节点退出策略将会导致节点的GNP坐标产生较大偏移，严重降低CAN的广播效率。在一个系统中，意外恢复机制尤为重要[9-10]，而且在CAN网络中，失效区域会对最小冗余度广播造成截断影响。

2.2 CAN节点加入退出机制

基于霍夫曼机制的加入退出机制[3]可以有效减少区域碎片，但是该机制过分依赖于霍夫曼编码信息，导致CAN系统非常脆弱，当多个节点同时失效时，霍夫曼策略的恢复周期较长。另外，递归查找可合并区域的策略将会造成严重的GNP坐标偏移现象。

在本文中，开发设计了消息重定向机制，该机制主要面向join消息，当节点判断join消息的目标点在自身负责的区域内，就会继而判断是否存在空间度或区域面积较大的邻居节点，如果存在，则将join消息重定向到空间度或区域面积最大的邻居节点（向该邻居节点发送join_redirect消息）。收到join_redirect消息的节点不能再次重定向。另外，当节点退出时，节点不会迭代寻找可合并区域，而是将区域信息递交给自己的某个邻居。

2.3 CAN节点失效恢复机制

这里，首先定义了恢复服务器。恢复服务器用于保存节点区域与CAN边界重合的节点。该服务器既可作为DNS服务器，也可用于失效区域恢复。另外，相继引出区域贡献值的概念：如果区域A在区域B的缺失区域的非缺失维度上与区域B存在交集，那么在沿着区域B的缺失区域方向，区域A距离缺失区域基准坐标的最短距离即为区域A对区域B的缺失区域的贡献值。贡献值小于0也被视为不存在贡献值。

图1失效区域示意图

Fig.1 Schematic diagram of failure zone

在图1中，节点L存在一个缺失区域，缺失区域的方向为1（x正方向），非缺失维度为y轴方向，缺失区域的基准坐标为15，空间G对空间L的缺失区域贡献值为25（40 - 15），空间A、M、H不存在对空间L的缺失区域的贡献值。

2.3.1 广播搜索策略

启动广播搜索策略时，节点会设定消息的TTL值，再将广播消息发送给所有的邻居节点。当CAN节点收到广播消息时，就会将自身的区域和邻居信息发送给请求节点。如果消息的TTL大于零，节点将消息的TTL减1，继续转发该消息到邻居节点。

当收到回复消息时，原始请求节点会判断消息中包含的区域A对缺失区域的贡献值，如不存在贡献值，则忽略此消息。否则，节点会判断区域A是否存在比自身的贡献值更小的邻居区域，如果存在，则忽略此消息，若不存在，则进行恢复工作。

如图1所示，当L收到节点P的回复消息时，由于P存在比自身区域贡献值更小的邻居节点X，则忽略该消息，当L收到节点X的回复消息时，节点L便可恢复空间（15，30，20，25）。在此，明确规定，节点只能恢复方向为1（x轴正方向）的缺失区域，这样可以有效避免恢复缺失区域造成的区域重复问题。

当节点G启动广播搜索策略时，由于在缺失区域的方向不存在区域贡献值大于零的区域，因此广播搜索策略失败。另外，由于我们规定了广播消息的TTL值，在图1中，如果所规定的TTL最大值为4，节点L便无法感知到节点X和Y，因此无法恢复失效区域。

3.3.2 迭代搜索策略

当节点M启动迭代搜索策略时，节点首先请求恢复服务器是否存在对当前缺失区域的贡献值大于零的边界区域，在图1中，恢复服务器返回的消息为空，这时节点M便可恢复区域（45，50，25，40）。当恢复服务器的返回消息中包含对当前缺失区域的贡献值大于零的边界区域时（此情况由区域大面积失效所致），同时当节点L启动迭代搜索策略时，恢复服务器会将节点G的信息返回给节点L，由于节点G存在区域贡献值更小的邻居节点P和Q，因此，节点L会忽略节点G的信息，进而继续请求节点P和节点Q。最终，当节点L收到节点X和节点Y的返回消息时，节点便可完成失效区域恢复工作。

3 CAN算法模拟与分析

3.1 空间划分均匀度

在基于消息重定向的轮转划分策略中，100个节点加入CAN网络，理想情况下，每个节点应该接管整体空间的百分之一，研究中称此区域大小为理想区域大小，图2中的横坐标代表当前区域大小和理想区域大小的比值，纵坐标为节点的数量。

图2基于消息重定向的区域划分统计图

Fig.2 Regional division statistics based on message redirection

由图2可以看出，比值在0.4～1.7之间的区域几乎占据整体的99%，而且网络中几乎不存在比值大于3的区域，这即良好充分地保证了网络广播的效率。

3.2 节点空间度

在空间度测试中，100个节点加入到系统中，其中，10个节点中途失效，10个节点中途退出，最后，20个节点重新加入到网络中，统计结果如表2所示。

表1节点空间度

Tab.1 Node space degree

空间度 节点数量

1 92

2 8

由表1所示，空间度为1的节点占所有节点的92%，由统计信息可知，本文提出的基于消息重定向的节点加入退出机制可以有效降低节点的空间度，当网络中节点加入退出频繁时，该方法能全面控制节点拥有的空间数量。

3.3 GNP坐标偏移度

在GNP坐标偏移度测试中，100个节点加入到系统中，其中，30个节点中途退出。图3为基于消息重定向机制的GNP坐标偏移度统计图，横轴代表节点的坐标偏移度，纵轴代表相应节点的数量。

图3 GNP坐标偏移度

Fig.3 Coordinate offset degree

由图3可以看出，系统中并不存在GNP坐标偏移很大的节点，因此，本文的消息重定向机制可以很好地控制节点间的通信延迟。

3.4 失效恢复能力

在测试失效恢复能力时，加入网络的节点总数为100，为了更全面地反映系统的失效处理能力，分别统计10、20、40个节点同时失效的区域恢复情况，具体情况如图4所示。

图4 失效恢复示意图

Fig.4 Schematic diagram of failure recovery

在图4中，规定横坐标为时间步step，开始时，设定的节点集体失效，当节点检测到失效区域的持续时间超过给定阈值时，节点启动广播搜索策略，到第9个时间步时，广播搜索策略结束。当失效节点数为20和40时，系统中依然存在广播搜索策略不能处理的情况，到第11个时间步时，迭代搜索策略启动，进而完成恢复工作。

通过图4可得到如下信息，广播搜索策略可以快速地对失效区域进行恢复，当存在不能恢复的区域时，则通过启动迭代搜索策略来实现对系统的恢复。对于广播搜索策略和迭代搜索策略来说，缺失区域的恢复是并发进行的，因此，缺失区域的恢复速度较快。

4 基于CAN覆盖网的配置同步模型

4.1 系统架构

模型主要包括下载服务器和分布式节点两部分，下载服务器负责提供配置文件下载服务，分布式节点负责向下载服务器请求配置更新文件。

4.2 配置下载算法

分布式节点会周期性地向下载服务器发送探测消息，判断是否存在新的配置文件，如果存在新的文件，则节点会将配置文件下载信息添加到下载列表中，在文件下载和广播过程中，采取分片策略，片段大小由具体的程序决定。

在本文的程序实现中，具体采用fileInfor表示文件信息，其结构设计为：

class fileInfor

{ char fileName[MAXFILESIZE]；

unsigned int totalDownloadTime；

unsigned int downloadNum；

unsigned int downloadCount；

unsigned int currentDownloadPerNum；

unsigned int broadcastNum；

unsigned int lastTime；

unsigned int threshold

unsigned int wait； }；

综上所示，totalDownloadTime代表下载文件消耗的总时间，downloadNum代表下载文件片段的总数，downloadCount为启动下载的次数，currentDownloadPerNum代表每次下载多少个文件片段，broadcastNum代表广播方式接收到的文件片段数量，lastTime表示上次收到文件片段的时间，threshold为门限值，waitNum为等待时间片数量。本文的下载算法的伪代码如下：

Begin

for p fileDownloadList do

if（ （ p.downloadCount <= 0 ） || （ p.downloadNum <= 0 ） then

downloadFilePiece（p.currentDownloadPerNum）；

endif

Else

tmp = lastTime + wait * p.totalDownloadTime / p.downloadNum；

if（ tmp > time（） ） then

if（ p.broadcastNum / p.downloadCount < p.threshold ） then

p.currentDownloadPerNum++；

endif

if（ p.broadcastNum / p.downloadCount > p.threshold ） then

p.currentDownloadPerNum--；

endif

downloadFilePiece（p.currentDownloaPerNum）；

endif

endElse

endfor

End

下载算法的核心作用在于协调两种数据来源的关系，该算法会最低限度地使用下载通道，同时该算法还能够保证在分布式节点数量较少时文件同步的高效性，具体体现在每次启动下载时，下载片段的数量均会根据系统已经收到的片段数量与系统下载的次数而进行动态调整。

5 结束语

本文给出了一种利用CAN覆盖网进行配置同步的方法，并针对CAN网络的加入退出机制和失效恢复机制进行了优化，通过仿真结果可以看出，优化后的CAN网络更有利于广播应用。同时，本文提出了一种多点下载/多点广播的同步模型，该模型的优点主要有：模型的扩展性较好，当服务器节点较多或配置文件较大时，配置同步的数据来源主要为广播数据，这即有效降低了下载服务器的带宽压力。另外，模型的效率较高，当分布式节点较少时，模型能有效感知到广播流量与下载流量的比例，进而动态调节下载流量。

参考文献：

[1] SHERMAN A， LISIECKI P A， BERKEIMER A， et al. ACMS： The Akamai Configuration Management System[C]//the 2nd Symposium on Networked Systems Design & Implementation， Boston：USENIX，2005：245-258.

[2] ZHANG R， HU Y C. Borg： A Hybrid Protocol for Scalable Application-Level Multicast in Peer-to-Peer Networks[C]//Proc of Nossdav， New York，USA：ACM，2003：172-179.

[3] RATNASAMY S， FRANCIS P， HANDLEY M， et al. A scalable content-Addressable network[C]// Proceedings of SIGCOMM 2001，san diego：ACM，Aug.2001：161-172

[4] RATNASAMY S， HANDLEY M， KARP R， et al. Application-level multicast using content addressable networks[C]//Proceedings of the Third International Workshop on Networked Group Communication（NGC），London：UCL，2001：14-29

[5] 吴太康. 基于CAN模型的覆盖网优化技术[D]. 哈尔滨：哈尔滨工业大学. 2009.

[6] 齐庆虎， 李津生， 洪佩琳，等. 内容寻址网络中内容的有效定位[J]. 电路与系统学报， 2004， 9（5）：67-71.

[7] 蔡明， 谢振平. 一种改良的CAN查询策略[J]. 计算机应用研究， 2005， 22（7）：81-83.

[8] HU Y， ZHU Y. Efficient， proximity-aware load balancing for dht-based p2p systems[J]. IEEE Transactions on Parallel & Distributed Systems， 2005， 16（4）：349--361.

[9] MEJIAS B， ROY P V. A relaxed-ring for self-organising and fault-tolerant peer-to-peer networks[C]// 2011 30th International Conference of the Chilean Computer Science Society. lquique：IEEE Computer Society， 2007：13-22.

[10] ZHUANG S Q， ZHAO B Y， JOSEPH A D， et al. Bayeux： An architecture for scalable and fault-tolerant Wide-area data dissemination[C]//Proc of Workshop on Network & Operating Systems Support for Digital Audio & Video Port， New York， USA：ACM，2001：11-20.