一種高效可擴展的自組織鄰域故障檢測協議

常光輝 陳蜀宇 徐光俠③ 盧華瑋

①(重慶大學計算機學院 重慶 400030)②(重慶大學軟件學院 重慶 400030)③(重慶郵電大學軟件學院 重慶 400067)

1 引言

以因特網為代表的信息化網絡已成為現代社會最重要的基礎設施之一。以往的網絡研究主要集中在信息傳輸的效率，網絡功能的完善性，以及系統的可擴展性等方面，對于網絡的安全可靠性沒有引起足夠的重視。然而網絡故障，節點失效，惡意攻擊等可靠性，安全性隱患的存在卻導致網絡服務不可信的嚴重后果[1,2]。如今網絡服務面臨的一個關鍵任務就是如何讓用戶得到可信賴的服務結果。正如美國工程院院士David Patterson教授所指出的：當今的計算機系統是想要建造高可信的網絡服務[3]。

隨著網格，P2P，傳感器等大型網絡化應用系統的快速發展，已經出現了基于網格，P2P，傳感器網絡的帶故障檢測的高可靠性應用系統[4?6]。傳統的故障檢測不再適應其大規?；?、強動態性、傳輸時延不確定等特點。據此，研究人員提出了多種故障檢測算法，同時也提出了對動態網絡故障檢測的新要求：協議或算法應當滿足系統的動態性，可擴展性，低耗費，靈活性[7,8]。文獻[9]提出基于灰模型的動態心跳故障檢測方法，有效縮小了觀測樣本容量，但沒有考慮心跳消息傳播方式的問題，若系統規模擴大則該方法的有效性會隨著網絡耗費的增大而降低。文獻[10,11]提出了以線性回歸方法來預測故障時間間隔Δt，較好地解決了分布式系統動態性的問題，但是其所需樣本量較大，也存在網絡耗費過大的問題。

Renesse提出了gossip-style的故障檢測協議[12],該協議利用了流言廣播在網絡中散播消息的高可靠性，并且能夠避免泛洪廣播消息引起的網絡擁塞問題。但此方法的缺點是系統會產生過多的冗余信息，同樣導致系統的可擴展性變差。對于系統耗費過大的的問題，文獻[13]提出了一種寄生式故障檢測算法，該算法能有效的降低系統消耗，并不額外產生探測信息，但檢測組件與應用系統高度耦合，使該方法通用性變差。文獻[14]采用故障檢測的方法來確定網絡節點的可信任值，這要求故障檢測方法能精確快速地對故障定位，以適應網絡節點可信任值的動態性。

本文提出基于自組織鄰域的隨機散播故障檢測協議在構造自治鄰域的基礎上有效地利用了隨機散播的可靠性，同時由于每個鄰域相對自治，大大降低了探測所帶來的通信消耗和時間損耗，使得協議具有高可擴展性和低耗費等特點。

2 系統模型及基本協議

2.1 系統模型描述

定義一個網絡系統為包含有有限多個結點集Π={p1, p2,…,pi}，其中i＞2且i∈N；集合中的pi為網絡系統中的一個組件或進程的抽象表示。

定義網絡系統中的故障檢測集為?={d1,d2,…,dj}，其中j＞2且j∈N；對于上面兩個集合中的元素pi，dj：?pi∈Π，?dj∈?，其中i=j；稱dj為依附于pi的檢測器。

假定 系統中任取網絡節點集中的兩個節點pi和pj(i≠j)，它們之間具有概率為1的網絡連通性，當且僅當系統中通信的兩節點其中之一出現崩潰(crash)情形時才出現不能連通，這個假定其實是明確系統中的鏈路不存在故障。同時，系統中任意節點不存在Byzantine式故障。

2.2 隨機散播檢測基本協議

為系統中的n個節點都配備一個檢測器d，它們形成一個檢測集，其中?pi∈Π，?di∈?,i∈N 。每個故障檢測器將會維持一個視圖Viewi，視圖中存有成員的ID(ID即成員的身份信息包含有地址信息)，健康節點集Shealth，懷疑節點集Ssuspicion，以及故障節點集Scrash，實現時可以采用一個結構體變量，另外視圖中還有一個成員計數器beat counter，此計數器具有通常檢測器的心跳數意義。

系統中每個節點的檢測器，經過一個時間間隔Tinterval，它自己將會主動把自己的信息隨機發送給View中健康節點集或懷疑節點集里面的一個節點。發送時，節點p將自己的心跳計數beat counter自加一次。其他節點的檢測器，收到此信息后，記錄收到的時間戳last time，并設置懷疑時間間隔Tsuspicion，隨后等待下一次信息的到來。若在 last time +Tsuspicion時刻仍然沒有收到某一被檢測點的更新心跳信息，或者收到的心跳信息不是beat counter +1，那么表明該節點可能發生了異常，則將會把該節點從Sheath中移入Ssuspicion集合中。

但此時卻不允許刪除，若在Tsuspicion之后將被檢測點直接移除，則有可能導致錯誤。實際操作中，可以采用已有的各種基于時間預測的故障檢測方法[9?11]計算出Tout的值。但這種方法通常需要較大的計算量來得出預測的時間，在系統資源緊張時甚至會帶來算法的失效。另一種簡單有效的做法可以采用設置移除時間Tout=2×Tsuspicion。這樣做的好處是不會使得系統中的某個故障節點的心跳消息持續逗留在系統中。

2.3 鄰域構造方法

由前所述，如果可信系統規模擴大，那么網絡節點間的故障探測就會導致消息量劇增，時延也會變得不能忍受，隨之系統的誤檢測率也將隨網絡規模的擴大不斷增加，引發檢測方法程度性失效。為了解決這個問題，本文引入了自組織鄰域的方法來對節點進行劃分，使之形成較小規模的自治域，這樣可以有效避免隨網絡規模擴大引發的上述缺陷。其構造過程如下：

算法1

步驟1 選取系統中的一個節點I對系統發出廣播探測信息，信息數為N-1；

步驟2 每個存活的節點對此廣播信息作出應答，初始節點在回收的時候對應答消息按時間排序，選取前N/ δ?1個節點，作為以初始節點為中心的一個鄰域；

步驟3 排除掉已選取的 N/ δ ?1個節點，在剩余的節點中選取應答時延最長的節點作為下一個初始節點，重復步驟1，步驟2；

步驟4 當剩余節點數小于 N/ δ ?1的時候結束循環。

在這里，N為系統總節點數，參數δ的值代表要劃分的鄰域的個數。在實際中可以根據Tsuspicion來確定，因為如果在初始節點構造探測的應答時間已經超出了Tsuspicion的范圍，那么它已經可以作為一個可疑節點，然而既然有響應那么應答節點必定處于活動狀態。如此說明包含初始節點 I 的鄰域對其探測已經失效，這樣反過來說明采用最長時延節點作為另外一個鄰域的中心是合理的。

此算法中每次選取的鄰域初始節點同時也是新生成鄰域的代理節點。當有節點要散播自己的存活消息時，通過代理節點進行鄰域間的消息散播。

推論1 當系統中的節點執行算法1時，在有限步內將劃分為若干個鄰域，且覆蓋系統內所有節點。

證明 由以上步驟經過遞推可知，此結論成立。

3 協議的分析與評估

3.1 檢測協議的可靠性分析

本文提出的故障檢測協議采用隨機散播方式進行檢測，首先分析單一鄰域內的協議執行情況。

稱系統中的節點收到其他節點存活信息為被感染。稱系統經過一個Tinterval時間為系統散播的一個輪次，記為r。設在第r輪系統中已經有λr個節點被感染，考察未被感染節點的將被感染的概率(當r=0時λ0=1)。

考慮隨機散播的執行過程，當某一個節點被感染后則會從它的本地視圖中隨機抽選出一個節點作為下一輪散播的對象，View中存儲了自身鄰域中的節點，鄰域中包含的節點數是n，通過鄰域構造之后，可以得知n=N/δ ，在單個鄰域中，最簡單的是從除自己外的節點中隨機選一個，這樣鄰域中任一節點被i感染的概率為1/(n?1)，從而鄰域中任一節點未收到i發出的探測消息的概率為1?1/(n?1)。既然鄰域中已經有λr個節點被感染，那么很顯然鄰域中未被感染的節點在本輪仍不會被感染的概率應該是(1?1/(n?1))λr。由此可以得出隨機散播過程中，經過前r輪有λr個節點被感染的情形下，某個未被感染節點被感染的概率為

從存活消息的散播方式可以看出，一個正準備散播消息的節點從其視圖中選擇了n?1個節點進行隨機散播。但實際上在這n?1個節點中存在若干個節點已經得到了此消息的情況。這樣，此協議必定會產生不必要的信息耗費。這是由于節點在散播時選擇目標的盲目性決定的。所以我們可以考慮某種選擇方式以降低散播的盲目性。

在本文中采用存儲路由信息的方法對其改進。具體做法為：被感染節點進行下一輪散播時，將上一輪發送存活信息的節點嵌入到本次散播的消息中，并作記號Mark，標記為信息的途經節點。這樣，在下一節點做下一輪散播選擇的時候，消息曾經過的途徑節點將被剔除。于是可得改進后的ρ(λr)為

這里的hi稱為協議的避免因子，是在散播選擇中被剔除掉的節點數。它的存在可以有效地削減協議隨機散播帶來的系統冗余消息，降低所謂的“乒乓效應”。

從以上的分析可以得出系統感染情況演化的迭代關系式為

N為系統總節點數。

另外，系統中任一節點在第r+1輪收到探測消息的概率為λr/n ，則所有節點在第r+1都被感染的概率為(λr/n)n。設α為給定的檢測覆蓋率的閾值，則當

時，通過式(2)-式(4)可以計算經過多少輪次算法將滿足系統檢測的覆蓋率α。

3.2 網絡耗費以及檢測時間相關分析

過大的網絡耗費會使得網絡負荷超載引起網絡擁塞等問題。這一節分析本文所述協議的網絡耗費問題。

根據式(3)所給出的ρ′(λr)的計算式，會使得后續的分析在數學處理上變得復雜。另外在實際的應用中有可能采用不同的避免“乒乓效應”的方法。因此可以近似的假設每一個節點的避免因子為一個hi的期望值h。這樣的假設不會給協議的本質帶來變化。則式(2)變為

將其代入式(3)則

可以得到

因為(n?h?1)遠小于1，上式近似于：

進一步可得

從協議散播的方法可知第r輪在系統中所產生的消息數就是λr，所以系統中直到覆蓋完成的第r+1輪所產生的消息數

所以消息數θ為(n?h?1)ln(n?1)。

引理 設系統總節點數為N，采用隨機散播方式傳播存活消息的系統總耗費數為(N?h?1)?ln(N?1)。

證明 由以上分析直接可以得出結論。

定理1 基于隨機散播的分鄰域檢測方法在通信耗費上必定優于單一集合的故障檢測方法。

證明 設系統集合Π中總節點數為N，由式(8)可知，采用隨機散播的檢測方法系統中產生的消息數θ為(N?h?1)ln(N ?1)。

若將其劃分為幾個彼此相近的鄰域集合Π1,Π2,…,Πn，對每個子集合中的節點也做隨機散播的故障檢測，則鄰域子集的通信耗費θi為( N/δ ?h?1)ln( N/ δ ?1)。

在鄰域檢測中總的耗費為

因為通過算法1劃分鄰域時，存在最后一個鄰域中節點數目小于 N/ δ 的情況，所以由式(9)可以推導出：

同時， N/δ ≤N/δ+1，代入式(10)，得θ′≤(N?δh)ln( N/δ ?1)。

根據前述鄰域劃分方法，δ必為大于1的正整數，故可得

定理2 基于隨機散播的分鄰域檢測方法在時間耗費上必定優于單一集合的故障檢測方法。

證明 設系統總節點數為N，則鄰域子集內節點總數必然小于N。分析協議本身，其檢測消息的散播基于輪次的概念，設未劃分鄰域的系統檢測在第r輪覆蓋所有節點。根據3.1節中式(3)：λr+1=λr+(N ?λr) ρ′(λr)，其中(N?λr)＞0，且傳染概率ρ′(λr)＞0;則必然有λr+1＞λr；所以系統中節點的被感染數λr必定為關于輪次r的離散單調遞增函數。

由單調函數的性質可知：當λ＞λ′時其對應的輪次也必定有如下關系r＞r′。故此感染系統總節點數為N的節點所耗費的輪次必定大于感染其鄰域子集的輪次。而分領域隨機散播檢測的情況下，對某個鄰域子集的檢測時間等于對全集檢測的時間。

證畢

4 實驗結果

本文利用Socket網絡編程API在Linux系統上開發了網絡故障探測工具。并采用它在廣域網絡環境下仿真隨機散播故障檢測，以對本文所提協議的若干結論及有效性進行驗證。鄰域內消息散播采用UDP方式，鄰域間則采用TCP方式。

4.1 SONFDP協議對系統內節點的檢測覆蓋性試驗

選取16個節點作為實驗床，節點操作系統采用Linux2.6.20內核版本，100 M的網絡接入帶寬。每一個節點上開辟N/16個故障檢測線程進行模擬仿真隨機散播實驗。每個線程都有r輪次的變量，另外為了設置Tinterval，需要在每個線程配置一個Timer對象，用于控制節點發送檢測消息的時間間隔，實驗中取400 ms。實驗監測隨著輪次r的變化檢測協議在系統中感染節點的覆蓋情況。模擬的系統感染曲線如圖1所示。

圖1 系統感染數變化曲線

由圖1可以看出，對于不同規模的系統節點，前5輪感染曲線的斜率較小，隨后逐漸增大，到后期又逐漸降低。說明隨機散播協議對系統節點的感染為慢啟動過程，這可以有效的避免泛洪引起的網絡擁塞。另外，不同系統規模下執行此協議的節點覆蓋率對比情況，如表1所示。

從表1 中的數據可以看出，隨著系統規模的擴大，探測的覆蓋率和時間的比值大大減小。取閾值α=0.95，當N=64，r=20時，覆蓋率α＞0.95；當N=128時，r=25時，α＞0.95；而反觀N=256的情形，直到第40輪才有覆蓋率達到閾值要求。這充分說明系統規模越大探測在時間耗費上效果越不理想，同時也證實了本文基本思想的正確性。

表1 不同輪次系統感染節點覆蓋率對比

4.2 SONFDP協議網絡耗費對比

實驗以重慶大學的兩個實驗室以及電子科技大學一個實驗室作為實驗床。其中每個實驗室取8個節點，每個節點運行8個故障檢測線程，總仿真節點數為192，探測閾值取α=0.95。由于實際網絡使用的情況會隨著時段的不同有較大差異，本實驗取兩個時段，日間和夜間分別做3組相同實驗，同樣的考慮取略長的散播時間間隔Tinterval=600 ms 。

根據2.3節的鄰域構造方法，選取δ=3，則可得3個鄰域的節點拓撲，每個鄰域用δi表示。在每個模擬線程中增設一個消息接受計數器Ci，節點每收到一個消息則其計數器加1。在系統達到探測的閾值時，則可計算系統總的耗費為

實際計算時先在每個鄰域中計算總的耗費，然后將每個鄰域的消息總數相加即得系統總耗費。

對比實驗結果如表2所示。

表2 4種方法的系統耗費及誤測率對比

表2中G表示實驗組別，P表示檢測協議，C為平均耗費，e為誤檢測率。從表2可以看出，SONFDP檢測協議在網絡耗費方面比文獻[12]的檢測方法減少了31%；在誤檢測率方面比文獻[12]以及文獻[9]中的方法分別降低了7個百分點和5個百分點。網絡耗費減少的原因由3.2節的分析可知。而誤檢測率低的原因是，SONFDP所劃分鄰域內的節點所處網絡狀況相對穩定，網絡時延也較短，這對于檢測時間的預測非常重要，所以即便在白天網絡使用高峰期其誤報率仍然較低。Flood方法盡管在通信量有很大的優勢，但在檢測有效性方面與上述兩種方法的差距同樣很大，尤其是在網絡使用高峰時，它引起的網絡擁塞使得丟包率和消息傳遞時延過大，致使其變的幾乎不可用。

5 結束語

本文根據可信網絡服務的大規?；邉討B性，消息傳遞時延不確定性等特點，提出了SONFDP故障檢測協議。采用自組織劃分鄰域的思想建立了一種高效可擴展的故障檢測方法，仿真實驗表明：SONFDP可以有效地控制故障檢測時的冗余網絡耗費，并且在時間上也有較為明顯的優勢。由于這兩方面性能的提高，從而使得故障檢測時間易于預測，進一步增強了故障檢測的可靠性。

下一步的研究工作是如何建立更加合理有效的自組織檢測鄰域。根據故障檢測和可信服務的特點分析自治域的劃分方法，以期使得檢測協議的服務對象更具有針對性，檢測耗費進一步降低，將其應用于具有可信性的網格，P2P等大型網絡化應用系統。

[1] 林闖，彭學海. 可信網絡研究[J]. 計算機學報, 2005, 28(5):751-758.Lin Chuang and Peng Xue-hai. Research on Trustworthy Networks[J]. Chinese Journal of Computers, 2005, 28(5):751-758.

[2] 閔應華. 網絡容錯與安全研究評述[J]. 計算機學報, 2003,26(9): 1035-1041.Min Ying-hua. Coments on basic research of reliable and Secure Networks[J]. Chinese Journal of Computers, 2003,26(9): 1035-1041.

[3] Patterson D. Recovery oriented computing. Presented at Princeton University [EB/OL]. 2002, http://roc.cs.berkeley.edu /talks/UIUC.ppt.

[4] Yamanouchi M, Matsuura S, and Sunahara H. A fault detection system for large scale sensor networks considering reliability of sensor data[C]. Proc of the Ninth Annual International Symposium on Applications and Internet(SAINT’09). Seattl, USA, 2009: 255-258.

[5] Lee H M, Park D S, and Hong M, et al.. A resource management system for fault tolerance in grid computing[C].Proc of International Conference on Computational Science and Engineering (CSE’09). Vancouver, CA, 2009, 2:609-614.

[6] Chtepen M, Claeys F, and Dhoedt B, et al.. Adaptive task checkpointing and replication: toward efficient fault-tolerant grids[J]. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(2): 180-190.

[7] Jain A and Shyamasundar R K. Failure detection and membership in grid environments [C]. Proc of the 5th IEEE/ACM Int’l Workshop on Grid Computing (GRID’04),Los Alamitos, CA, IEEE Computer Society Press, 2004:44-52.

[8] Hwang S and Kesselmanl C. A flexible framework for fault tolerance in the grid [J]. Journal of Grid Computing, 2003,1(3): 251-272.

[9] 姬曉波，陳蜀宇，田東，等. 高效可擴展的網格系統動態故障檢測算法[J]. 武漢大學學報(信息科學版). 2008, 33(10):1046-1050.Ji Xiao-bo, Chen Shu-yu, and Tian Dong, et al.. An efficient and scalable fault detection algorithm for grid systems[J].Geomatics and Information Science of Wuhan University.2008, 33(10): 1046-1050.

[10] Chen W, Toueg S, and Aguilera1 M K. On the quality of service of failure detectors [J]. IEEE Transactions on Computers, 2002, 51(2): 13-32.

[11] Hayashibara N, Défago X, and Yared R, et al.. The φ accrual failure detector[C]. Proc of the 23rd IEEE Int’l Symp on Reliable Distributed Systems(SRDS’04), Los Alamitos,CA, IEEE Computer Society Press, 2004: 66-78.

[12] Renesse R, Minsky Y, and Hayden M. A gossip-style failure detection service[C]. Proceedings of International Conference of Distributed Systems Platforms and Open Distributed Processing (IFIP), The lake district, UK, Springer-Verlag Press, 2009: 55-70.

[13] 左朝樹，劉心松，邱元杰，等. 一種分布式并行服務器節點故障檢測算法[J]. 電子科技大學學報. 2007, 36(1): 119-122.Zuo Chao-shu, Liu Xin-song, and Qiu Yuan-jie, et al.. A node fault detection algorithm in distributed parallel server[J].Journal of University of Electronic Science and Technology of China, 2007, 36(1): 119-122.

[14] 紀俊杰，陽小龍，王進，等. 基于信任關系的IP網絡容錯容侵機制[J].電子與信息學報. 2009, 31(7): 1576-1581.Ji Jun-jie, Yang Xiao-long, and Wang Jin, et al.. An efficient fault-tolerant and intrusion-tolerant scheme based on trust relationship for IP networks[J]. Journal of Electronics &Information Technology, 2009, 31(7): 1576-1581.