一種高效可擴(kuò)展的自組織鄰域故障檢測協(xié)議

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

①(重慶大學(xué)計(jì)算機(jī)學(xué)院 重慶 400030)②(重慶大學(xué)軟件學(xué)院 重慶 400030)③(重慶郵電大學(xué)軟件學(xué)院 重慶 400067)

1 引言

以因特網(wǎng)為代表的信息化網(wǎng)絡(luò)已成為現(xiàn)代社會最重要的基礎(chǔ)設(shè)施之一。以往的網(wǎng)絡(luò)研究主要集中在信息傳輸?shù)男?，網(wǎng)絡(luò)功能的完善性，以及系統(tǒng)的可擴(kuò)展性等方面，對于網(wǎng)絡(luò)的安全可靠性沒有引起足夠的重視。然而網(wǎng)絡(luò)故障，節(jié)點(diǎn)失效，惡意攻擊等可靠性，安全性隱患的存在卻導(dǎo)致網(wǎng)絡(luò)服務(wù)不可信的嚴(yán)重后果[1,2]。如今網(wǎng)絡(luò)服務(wù)面臨的一個關(guān)鍵任務(wù)就是如何讓用戶得到可信賴的服務(wù)結(jié)果。正如美國工程院院士David Patterson教授所指出的：當(dāng)今的計(jì)算機(jī)系統(tǒng)是想要建造高可信的網(wǎng)絡(luò)服務(wù)[3]。

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

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

本文提出基于自組織鄰域的隨機(jī)散播故障檢測協(xié)議在構(gòu)造自治鄰域的基礎(chǔ)上有效地利用了隨機(jī)散播的可靠性，同時由于每個鄰域相對自治，大大降低了探測所帶來的通信消耗和時間損耗，使得協(xié)議具有高可擴(kuò)展性和低耗費(fèi)等特點(diǎn)。

2 系統(tǒng)模型及基本協(xié)議

2.1 系統(tǒng)模型描述

定義一個網(wǎng)絡(luò)系統(tǒng)為包含有有限多個結(jié)點(diǎn)集Π={p1, p2,…,pi}，其中i＞2且i∈N；集合中的pi為網(wǎng)絡(luò)系統(tǒng)中的一個組件或進(jìn)程的抽象表示。

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

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

2.2 隨機(jī)散播檢測基本協(xié)議

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

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

但此時卻不允許刪除，若在Tsuspicion之后將被檢測點(diǎn)直接移除，則有可能導(dǎo)致錯誤。實(shí)際操作中，可以采用已有的各種基于時間預(yù)測的故障檢測方法[9?11]計(jì)算出Tout的值。但這種方法通常需要較大的計(jì)算量來得出預(yù)測的時間，在系統(tǒng)資源緊張時甚至?xí)硭惴ǖ氖?。另一種簡單有效的做法可以采用設(shè)置移除時間Tout=2×Tsuspicion。這樣做的好處是不會使得系統(tǒng)中的某個故障節(jié)點(diǎn)的心跳消息持續(xù)逗留在系統(tǒng)中。

2.3 鄰域構(gòu)造方法

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

算法1

步驟1 選取系統(tǒng)中的一個節(jié)點(diǎn)I對系統(tǒng)發(fā)出廣播探測信息，信息數(shù)為N-1；

步驟2 每個存活的節(jié)點(diǎn)對此廣播信息作出應(yīng)答，初始節(jié)點(diǎn)在回收的時候?qū)?yīng)答消息按時間排序，選取前N/ δ?1個節(jié)點(diǎn)，作為以初始節(jié)點(diǎn)為中心的一個鄰域；

步驟3 排除掉已選取的 N/ δ ?1個節(jié)點(diǎn)，在剩余的節(jié)點(diǎn)中選取應(yīng)答時延最長的節(jié)點(diǎn)作為下一個初始節(jié)點(diǎn)，重復(fù)步驟1，步驟2；

步驟4 當(dāng)剩余節(jié)點(diǎn)數(shù)小于 N/ δ ?1的時候結(jié)束循環(huán)。

在這里，N為系統(tǒng)總節(jié)點(diǎn)數(shù)，參數(shù)δ的值代表要劃分的鄰域的個數(shù)。在實(shí)際中可以根據(jù)Tsuspicion來確定，因?yàn)槿绻诔跏脊?jié)點(diǎn)構(gòu)造探測的應(yīng)答時間已經(jīng)超出了Tsuspicion的范圍，那么它已經(jīng)可以作為一個可疑節(jié)點(diǎn)，然而既然有響應(yīng)那么應(yīng)答節(jié)點(diǎn)必定處于活動狀態(tài)。如此說明包含初始節(jié)點(diǎn) I 的鄰域?qū)ζ涮綔y已經(jīng)失效，這樣反過來說明采用最長時延節(jié)點(diǎn)作為另外一個鄰域的中心是合理的。

此算法中每次選取的鄰域初始節(jié)點(diǎn)同時也是新生成鄰域的代理節(jié)點(diǎn)。當(dāng)有節(jié)點(diǎn)要散播自己的存活消息時，通過代理節(jié)點(diǎn)進(jìn)行鄰域間的消息散播。

推論1 當(dāng)系統(tǒng)中的節(jié)點(diǎn)執(zhí)行算法1時，在有限步內(nèi)將劃分為若干個鄰域，且覆蓋系統(tǒng)內(nèi)所有節(jié)點(diǎn)。

證明 由以上步驟經(jīng)過遞推可知，此結(jié)論成立。

3 協(xié)議的分析與評估

3.1 檢測協(xié)議的可靠性分析

本文提出的故障檢測協(xié)議采用隨機(jī)散播方式進(jìn)行檢測，首先分析單一鄰域內(nèi)的協(xié)議執(zhí)行情況。

稱系統(tǒng)中的節(jié)點(diǎn)收到其他節(jié)點(diǎn)存活信息為被感染。稱系統(tǒng)經(jīng)過一個Tinterval時間為系統(tǒng)散播的一個輪次，記為r。設(shè)在第r輪系統(tǒng)中已經(jīng)有λr個節(jié)點(diǎn)被感染，考察未被感染節(jié)點(diǎn)的將被感染的概率(當(dāng)r=0時λ0=1)。

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

從存活消息的散播方式可以看出，一個正準(zhǔn)備散播消息的節(jié)點(diǎn)從其視圖中選擇了n?1個節(jié)點(diǎn)進(jìn)行隨機(jī)散播。但實(shí)際上在這n?1個節(jié)點(diǎn)中存在若干個節(jié)點(diǎn)已經(jīng)得到了此消息的情況。這樣，此協(xié)議必定會產(chǎn)生不必要的信息耗費(fèi)。這是由于節(jié)點(diǎn)在散播時選擇目標(biāo)的盲目性決定的。所以我們可以考慮某種選擇方式以降低散播的盲目性。

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

這里的hi稱為協(xié)議的避免因子，是在散播選擇中被剔除掉的節(jié)點(diǎn)數(shù)。它的存在可以有效地削減協(xié)議隨機(jī)散播帶來的系統(tǒng)冗余消息，降低所謂的“乒乓效應(yīng)”。

從以上的分析可以得出系統(tǒng)感染情況演化的迭代關(guān)系式為

N為系統(tǒng)總節(jié)點(diǎn)數(shù)。

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

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

3.2 網(wǎng)絡(luò)耗費(fèi)以及檢測時間相關(guān)分析

過大的網(wǎng)絡(luò)耗費(fèi)會使得網(wǎng)絡(luò)負(fù)荷超載引起網(wǎng)絡(luò)擁塞等問題。這一節(jié)分析本文所述協(xié)議的網(wǎng)絡(luò)耗費(fèi)問題。

根據(jù)式(3)所給出的ρ′(λr)的計(jì)算式，會使得后續(xù)的分析在數(shù)學(xué)處理上變得復(fù)雜。另外在實(shí)際的應(yīng)用中有可能采用不同的避免“乒乓效應(yīng)”的方法。因此可以近似的假設(shè)每一個節(jié)點(diǎn)的避免因子為一個hi的期望值h。這樣的假設(shè)不會給協(xié)議的本質(zhì)帶來變化。則式(2)變?yōu)?/p>

將其代入式(3)則

可以得到

因?yàn)?n?h?1)遠(yuǎn)小于1，上式近似于：

進(jìn)一步可得

從協(xié)議散播的方法可知第r輪在系統(tǒng)中所產(chǎn)生的消息數(shù)就是λr，所以系統(tǒng)中直到覆蓋完成的第r+1輪所產(chǎn)生的消息數(shù)

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

引理 設(shè)系統(tǒng)總節(jié)點(diǎn)數(shù)為N，采用隨機(jī)散播方式傳播存活消息的系統(tǒng)總耗費(fèi)數(shù)為(N?h?1)?ln(N?1)。

證明 由以上分析直接可以得出結(jié)論。

定理1 基于隨機(jī)散播的分鄰域檢測方法在通信耗費(fèi)上必定優(yōu)于單一集合的故障檢測方法。

證明 設(shè)系統(tǒng)集合Π中總節(jié)點(diǎn)數(shù)為N，由式(8)可知，采用隨機(jī)散播的檢測方法系統(tǒng)中產(chǎn)生的消息數(shù)θ為(N?h?1)ln(N ?1)。

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

在鄰域檢測中總的耗費(fèi)為

因?yàn)橥ㄟ^算法1劃分鄰域時，存在最后一個鄰域中節(jié)點(diǎn)數(shù)目小于 N/ δ 的情況，所以由式(9)可以推導(dǎo)出：

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

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

定理2 基于隨機(jī)散播的分鄰域檢測方法在時間耗費(fèi)上必定優(yōu)于單一集合的故障檢測方法。

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

由單調(diào)函數(shù)的性質(zhì)可知：當(dāng)λ＞λ′時其對應(yīng)的輪次也必定有如下關(guān)系r＞r′。故此感染系統(tǒng)總節(jié)點(diǎn)數(shù)為N的節(jié)點(diǎn)所耗費(fèi)的輪次必定大于感染其鄰域子集的輪次。而分領(lǐng)域隨機(jī)散播檢測的情況下，對某個鄰域子集的檢測時間等于對全集檢測的時間。

證畢

4 實(shí)驗(yàn)結(jié)果

本文利用Socket網(wǎng)絡(luò)編程API在Linux系統(tǒng)上開發(fā)了網(wǎng)絡(luò)故障探測工具。并采用它在廣域網(wǎng)絡(luò)環(huán)境下仿真隨機(jī)散播故障檢測，以對本文所提協(xié)議的若干結(jié)論及有效性進(jìn)行驗(yàn)證。鄰域內(nèi)消息散播采用UDP方式，鄰域間則采用TCP方式。

4.1 SONFDP協(xié)議對系統(tǒng)內(nèi)節(jié)點(diǎn)的檢測覆蓋性試驗(yàn)

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

圖1 系統(tǒng)感染數(shù)變化曲線

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

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

表1 不同輪次系統(tǒng)感染節(jié)點(diǎn)覆蓋率對比

4.2 SONFDP協(xié)議網(wǎng)絡(luò)耗費(fèi)對比

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

根據(jù)2.3節(jié)的鄰域構(gòu)造方法，選取δ=3，則可得3個鄰域的節(jié)點(diǎn)拓?fù)洌總€鄰域用δi表示。在每個模擬線程中增設(shè)一個消息接受計(jì)數(shù)器Ci，節(jié)點(diǎn)每收到一個消息則其計(jì)數(shù)器加1。在系統(tǒng)達(dá)到探測的閾值時，則可計(jì)算系統(tǒng)總的耗費(fèi)為

實(shí)際計(jì)算時先在每個鄰域中計(jì)算總的耗費(fèi)，然后將每個鄰域的消息總數(shù)相加即得系統(tǒng)總耗費(fèi)。

對比實(shí)驗(yàn)結(jié)果如表2所示。

表2 4種方法的系統(tǒng)耗費(fèi)及誤測率對比

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

5 結(jié)束語

本文根據(jù)可信網(wǎng)絡(luò)服務(wù)的大規(guī)模化，高動態(tài)性，消息傳遞時延不確定性等特點(diǎn)，提出了SONFDP故障檢測協(xié)議。采用自組織劃分鄰域的思想建立了一種高效可擴(kuò)展的故障檢測方法，仿真實(shí)驗(yàn)表明：SONFDP可以有效地控制故障檢測時的冗余網(wǎng)絡(luò)耗費(fèi)，并且在時間上也有較為明顯的優(yōu)勢。由于這兩方面性能的提高，從而使得故障檢測時間易于預(yù)測，進(jìn)一步增強(qiáng)了故障檢測的可靠性。

下一步的研究工作是如何建立更加合理有效的自組織檢測鄰域。根據(jù)故障檢測和可信服務(wù)的特點(diǎn)分析自治域的劃分方法，以期使得檢測協(xié)議的服務(wù)對象更具有針對性，檢測耗費(fèi)進(jìn)一步降低，將其應(yīng)用于具有可信性的網(wǎng)格，P2P等大型網(wǎng)絡(luò)化應(yīng)用系統(tǒng)。

[1] 林闖，彭學(xué)海. 可信網(wǎng)絡(luò)研究[J]. 計(jì)算機(jī)學(xué)報, 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] 閔應(yīng)華. 網(wǎng)絡(luò)容錯與安全研究評述[J]. 計(jì)算機(jī)學(xué)報, 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] 姬曉波，陳蜀宇，田東，等. 高效可擴(kuò)展的網(wǎng)格系統(tǒng)動態(tài)故障檢測算法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版). 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] 左朝樹，劉心松，邱元杰，等. 一種分布式并行服務(wù)器節(jié)點(diǎn)故障檢測算法[J]. 電子科技大學(xué)學(xué)報. 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] 紀(jì)俊杰，陽小龍，王進(jìn)，等. 基于信任關(guān)系的IP網(wǎng)絡(luò)容錯容侵機(jī)制[J].電子與信息學(xué)報. 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.