基于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.