鄭曉健，馬晨誌

（1.昆明理工大學(xué)津橋?qū)W院電氣與信息工程學(xué)院，云南昆明 650106；2.University of Wisconsin-Stevens Point，Wisconsin Stevens Point 54481，United States of America）

0 引言

近年來保障P2P 網(wǎng)絡(luò)資源的持續(xù)有效性問題受到關(guān)注［1-3］，由于P2P 網(wǎng)絡(luò)的節(jié)點自由地加入和退出網(wǎng)絡(luò)［4］，使分布在網(wǎng)絡(luò)中的資源經(jīng)常處于不穩(wěn)定狀態(tài)，影響到網(wǎng)絡(luò)服務(wù)的質(zhì)量。尤其是節(jié)點的退出使網(wǎng)絡(luò)中的資源量減少，資源需求節(jié)點獲取資源失敗，降低了系統(tǒng)的查詢成功率，也影響到系統(tǒng)的可用性［5-6］。已有研究顯示，采用資源備份技術(shù)可以提高查詢成功率和可用性［7-8］。

混合型P2P 網(wǎng)絡(luò)架構(gòu)多采用被動式資源備份策略，通過系統(tǒng)服務(wù)節(jié)點監(jiān)測資源節(jié)點發(fā)送的心跳消息來感知節(jié)點的在線狀況，為了延續(xù)退出節(jié)點服務(wù)則通過切換到備份節(jié)點實現(xiàn)。研究表明此種方式在近99%的節(jié)點資源訪問中有效，但也存在1.007%的訪問失敗情況。問題主要是既有方法對退出節(jié)點的發(fā)現(xiàn)機制不完善。系統(tǒng)服務(wù)節(jié)點發(fā)現(xiàn)節(jié)點退出的方法是定期（一般在每個監(jiān)測周期結(jié)束時）檢查是否存在超期未發(fā)心跳消息的節(jié)點。由于節(jié)點退出事件發(fā)生在系統(tǒng)服務(wù)節(jié)點監(jiān)測周期內(nèi)的某個時刻，該時刻至監(jiān)測周期結(jié)束時系統(tǒng)發(fā)現(xiàn)節(jié)點的退出，中間存在一個時間差。如果節(jié)點退出發(fā)生在系統(tǒng)服務(wù)節(jié)點監(jiān)測周期的開始階段，加上轉(zhuǎn)移節(jié)點服務(wù)到備份節(jié)點所耗費的時間，時間差值甚至?xí)^一個監(jiān)測周期。在此段時間內(nèi)退出節(jié)點的鏈接信息已經(jīng)失效，需求節(jié)點按此訪問資源將失敗，本文將此現(xiàn)象稱為顛簸問題（Bumpy problem）。實驗顯示，顛簸事件發(fā)生的幾率低于1.007%，當(dāng)局域網(wǎng)的規(guī)模較小，系統(tǒng)服務(wù)節(jié)點監(jiān)測周期延長時顛簸事件發(fā)生率較高。

本文對顛簸問題進(jìn)行了分析研究，提出一種基于資源環(huán)備份結(jié)構(gòu)及節(jié)點狀態(tài)監(jiān)測的方法。將資源節(jié)點組織成為備份環(huán)，環(huán)上的節(jié)點在各自的心跳周期內(nèi)對相鏈接的環(huán)節(jié)點隨機發(fā)送問候消息，相互主動檢測和回復(fù)在線狀態(tài)。實驗表明，該方法降低了被測節(jié)點的監(jiān)測時間間隔，使檢索盲區(qū)縮短，顛簸風(fēng)險下降。

1 相關(guān)工作

顛簸事件發(fā)生的幾率較低，相關(guān)研究較少。諸多研究在利用節(jié)點備份技術(shù)提高資源查詢成功率［9-10］的同時，一定程度上降低了顛簸現(xiàn)象的發(fā)生。文獻(xiàn)［5］提出感知服務(wù)質(zhì)量的備份恢復(fù)算法，通過資源備份的分布情況和資源備份安全規(guī)則劃分安全等級，給出分階段資源備份恢復(fù)算法，結(jié)果表明，與直接資源備份恢復(fù)算法相比，可有效提高應(yīng)用服務(wù)質(zhì)量及數(shù)據(jù)安全保障能力；文獻(xiàn)［6］采用主動策略查找稀有資源，通過獲取資源的局部需求信息來備份資源，提高文件在網(wǎng)絡(luò)中的流行度，從而提高稀有資源的查詢成功率和可用性；文獻(xiàn)［8］根據(jù)節(jié)點的存儲能力和節(jié)點間的物理距離，選擇存儲空間充足和物理位置更近的節(jié)點備份資源，使維護(hù)消耗更低，檢索成功率也得到改善；文獻(xiàn)［9］將備份資源文件保存到在線時間更長的節(jié)點上，改善了網(wǎng)絡(luò)資源動態(tài)變化時的適應(yīng)性和服務(wù)質(zhì)量；文獻(xiàn)［11］提出動態(tài)備份資源分布式方法，按所設(shè)計的備份目錄和信息獲得資源的所有備份信息，對訪問頻率高和平均響應(yīng)時間長的資源進(jìn)行備份，提供用戶訪問特征和節(jié)點的實時帶寬等信息，計算存放備份的節(jié)點，使備份的分布能夠適應(yīng)訪問請求和網(wǎng)絡(luò)帶寬的動態(tài)變化；文獻(xiàn)［12］提出將資源備份部署到網(wǎng)絡(luò)中的骨干節(jié)點或骨干鏈路上，提高檢索成功率。以上方法主要采用被動式方法備份文件，重點放在提高文件的檢索成功率，能夠改善系統(tǒng)檢索性能并提高系統(tǒng)可用性，但由于P2P 網(wǎng)絡(luò)所具有的動態(tài)性，備份節(jié)點隨時可能退出網(wǎng)絡(luò)造成資源檢索失敗，所以研究可持續(xù)且服務(wù)質(zhì)量穩(wěn)定的備份技術(shù)很有必要。

2 顛簸問題

P2P 網(wǎng)絡(luò)中節(jié)點具有的動態(tài)性使網(wǎng)絡(luò)資源文件的分布、數(shù)量及狀況發(fā)生變化［13-14］，而節(jié)點呈現(xiàn)出5 種基本狀態(tài)：加入態(tài)、在線態(tài)、刷新態(tài)、顛簸態(tài)和離線態(tài)，這些狀態(tài)變化由相應(yīng)的網(wǎng)絡(luò)事件觸發(fā)，其中顛簸狀態(tài)為暫時性過程，隨著節(jié)點的服務(wù)轉(zhuǎn)移到備份節(jié)點上，原節(jié)點的服務(wù)將恢復(fù)，顛簸也將消失。本文進(jìn)一步明確切換和顛簸的概念，分析顛簸的性質(zhì)，根據(jù)相應(yīng)性質(zhì)提出減少顛簸的方法。

2.1 問題定義

設(shè)P=｛p1，p2，…，pi，…｝是網(wǎng)絡(luò)中節(jié)點的有限集，1≤i≤n，n 為節(jié)點的總數(shù)目，?pi∈P兩次心跳的最大間隔時間為?tq,0

定義1（切換）時間[t,th]內(nèi)，t0時pi∈P退出網(wǎng)絡(luò)，t+?tq時pm∈P發(fā)現(xiàn)pi退出，系統(tǒng)將pi的服務(wù)轉(zhuǎn)移到pb∈P，并在th時轉(zhuǎn)移結(jié)束，則稱時間[t0,th]內(nèi)對pi切換或后切換。其中稱t0∈[t,t+?tq)為節(jié)點退出網(wǎng)絡(luò)時間，同時也是切換開始時間，th為切換結(jié)束時間，[t0,t+?tq]是節(jié)點退出發(fā)現(xiàn)期，(t+?tq,th]是節(jié)點服務(wù)轉(zhuǎn)移期，[t0,t+?tq]∪(t+?tq,th]?[t,th]是節(jié)點切換期。

定義2（顛簸）在時間[t,th]內(nèi)對pi∈P切換期間，如果t1∈(t0,th]時?pq∈P，請求pi的服務(wù)發(fā)生暫時性失敗，則稱pq在t1時產(chǎn)生顛簸。

2.2 顛簸事件性質(zhì)

假設(shè)節(jié)點退出網(wǎng)絡(luò)事件和資源需求節(jié)點的檢索請求［15-17］相互獨立。

性質(zhì)1節(jié)點切換期間任何資源需求節(jié)點對該節(jié)點提出服務(wù)請求都將產(chǎn)生顛簸。

分析：設(shè)?pi,pm,pb,pq∈P，?tq是節(jié)點pm收到節(jié)點pi的心跳信號的最大時間間隔，t 是節(jié)點pm接收到節(jié)點pi心跳的時間，t+?tq為節(jié)點pi的心跳到達(dá)pm的最大限制時間，th是節(jié)點pi的服務(wù)轉(zhuǎn)移到節(jié)點pb的時間。

（1）若t0∈(t,t+?tq]時節(jié)點pi退出網(wǎng)絡(luò)，那么節(jié)點pm在[t0,t+?tq]不會接收到節(jié)點pi的心跳消息。若t+?tq時，pm仍然沒有收到pi的心跳，pm將推斷節(jié)點pi已經(jīng)退出網(wǎng)絡(luò)。

（2）在(]t+?tq,th時段，節(jié)點pi的服務(wù)轉(zhuǎn)移到節(jié)點pb，th之后節(jié)點pb接替pi提供資源服務(wù)。

（3）若在時間(t0,th]內(nèi)?pq∈P檢索節(jié)點pi文件，那么由式（1）可知，在時間[t0,t+?tq]內(nèi)由于沒有發(fā)現(xiàn)節(jié)點pi退出，所以檢索到的還是節(jié)點pi的鏈接信息。另外由式（2）可知，在(t+?tq,th]時間內(nèi)，盡管已經(jīng)發(fā)現(xiàn)節(jié)點pi退出，但還沒有完成節(jié)點pi到節(jié)點pb的轉(zhuǎn)移，所以不能提供pb的鏈接信息。因此在時間[t0,th]內(nèi)，節(jié)點pq對節(jié)點pi文件的檢索將失敗。

性質(zhì)2當(dāng)節(jié)點退出網(wǎng)絡(luò)時，訪問該節(jié)點資源文件失敗的概率與節(jié)點退出的概率密度函數(shù)以及節(jié)點切換期的長度有關(guān)。

分析：設(shè)?pi∈P，節(jié)點pi退出網(wǎng)絡(luò)的時間為連續(xù)型隨機變量Q，Q 在(t1,t2)上的概率密度函數(shù)為f（q），t10。?pq∈P向節(jié)點pi發(fā)送檢索文件消息，檢索時間為連續(xù)型隨機變量R，R 在(t1,t2)上的概率密度函數(shù)為h（r），t1

在(t,t+ε)期間，網(wǎng)絡(luò)中節(jié)點pq檢索節(jié)點pi文件的概率為：

那么，在(t,t+ε)期間，當(dāng)節(jié)點pi退出網(wǎng)絡(luò)時，節(jié)點pq檢索節(jié)點pi的文件概率為：

在式（3）中R 和Q 相互獨立，即：

由性質(zhì)1，(t,t+ε)時間段內(nèi)如果發(fā)生對節(jié)點pi的檢索事件，則檢索失敗。由式（4）可知檢索失敗的概率等于檢索事件發(fā)生的概率，再由式（2）可知從節(jié)點退出網(wǎng)絡(luò)到節(jié)點切換完成期間，檢索節(jié)點pi中資源文件的概率與其概率密度函數(shù)、節(jié)點切換所用時間有關(guān)。

由此可知，檢索的頻度增加則顛簸的概率也會增大。

3 資源環(huán)備份結(jié)構(gòu)

由顛簸的性質(zhì)及其實驗驗證結(jié)果可知，假設(shè)節(jié)點退出事件隨機性不變，由此顛簸發(fā)生的概率取決于切換期長度。采用資源節(jié)點的環(huán)備份結(jié)構(gòu)，環(huán)節(jié)點間按鏈接關(guān)系在心跳周期內(nèi)互發(fā)問候消息以相互監(jiān)測，系統(tǒng)服務(wù)節(jié)點設(shè)置節(jié)點表和資源表，節(jié)點表用于保存環(huán)節(jié)點信息以供節(jié)點檢索服務(wù)，資源表保存節(jié)點的資源文件信息以供資源檢索服務(wù)。資源環(huán)備份結(jié)構(gòu)如圖1 所示。

Fig.1 Resource ring backup structure圖1 資源環(huán)備份結(jié)構(gòu)

3.1 節(jié)點加入環(huán)結(jié)構(gòu)

節(jié)點加入網(wǎng)絡(luò)分成兩步：①節(jié)點加入資源環(huán)備份結(jié)構(gòu)。建立節(jié)點與系統(tǒng)服務(wù)節(jié)點和首節(jié)點間的環(huán)鏈接，并以首節(jié)點為備份節(jié)點；②資源備份。節(jié)點的自治文件轉(zhuǎn)存到備份節(jié)點。

節(jié)點加入環(huán)結(jié)構(gòu)算法：

輸入：節(jié)點pi，系統(tǒng)服務(wù)節(jié)點ps，首節(jié)點pb

輸出：新系統(tǒng)環(huán)備份結(jié)構(gòu)

（1）pi向ps發(fā)送請求插入消息Is；收到回復(fù)Rs后利用返回的信息pi向pb發(fā)送請求插入消息Ib；收到回復(fù)Rb后，在pi建立ps與pi和pb與pi鏈接信息，pi向ps發(fā)送請求刷新消息Us，轉(zhuǎn)步驟（4）；如果未收到回復(fù)Rs||Rb，轉(zhuǎn)步驟（5）；

（2）ps收到消息Is后，pb回復(fù)Rs；ps收到消息Us后查詢和刷新節(jié)點表。

（3）pb收到消息Ib后，在pb建立pb與pi的鏈接信息，回復(fù)Rb。

（4）pi和pb開始交換資源文件，pb作為備份節(jié)點，返回加入節(jié)點成功。

（5）返回加入節(jié)點失敗。

3.2 環(huán)節(jié)點間的監(jiān)測與節(jié)點切換

與被動式監(jiān)測模式不同，在環(huán)備份結(jié)構(gòu)中每個節(jié)點監(jiān)測相鏈接的2 個節(jié)點。節(jié)點在心跳周期內(nèi)向相鏈接節(jié)點發(fā)送問候消息，收到消息后須立即回復(fù)，從而獲知其在線狀況，然后向系統(tǒng)服務(wù)節(jié)點通報被監(jiān)視節(jié)點的在線狀態(tài)；如果未收到問候的回復(fù)，環(huán)節(jié)點斷定被監(jiān)測節(jié)點已經(jīng)退出網(wǎng)絡(luò)，立即轉(zhuǎn)換到備份并向系統(tǒng)服務(wù)節(jié)點通報。

環(huán)節(jié)點間的監(jiān)測與節(jié)點切換算法：

輸入：環(huán)節(jié)點pi，相鏈接節(jié)點pp，備份節(jié)點pn，系統(tǒng)服務(wù)節(jié)點ps

輸出：節(jié)點在線狀態(tài)

（1）pi心跳期內(nèi)，pi向節(jié)點pp和pn發(fā)送問候消息H(p/n)。

（2）pp/pn收到消息H(p/n)后回復(fù)R(p/n)。

（3）pi收到回復(fù)R(p/n)后向ps發(fā)送L(p/n)消息，通報pp/pn在線。若pi未收到回復(fù)R(p/n)則向ps發(fā)送Q(p/n)消息，通報pp/pn退出。

（4）ps收到消息Q后更新調(diào)整節(jié)點表，反映新的環(huán)備份結(jié)構(gòu)，安排新備份；ps收到消息L，刷新節(jié)點表。

環(huán)節(jié)點在每個心跳周期內(nèi)向被監(jiān)測節(jié)點發(fā)送一次或多次問候消息。如果環(huán)中有3 個及以上節(jié)點，則被監(jiān)測節(jié)點可能會在其當(dāng)前心跳周期內(nèi)接收到兩個及以上問候消息，因此各問候消息間的時間間隔小于等于心跳周期長度，所以利用環(huán)節(jié)點的心跳周期內(nèi)的監(jiān)測去發(fā)現(xiàn)節(jié)點退出，與系統(tǒng)服務(wù)節(jié)點的監(jiān)測方法相比可以縮短監(jiān)測盲區(qū)。

假設(shè)節(jié)點退出事件和對節(jié)點資源文件的檢索事件獨立，但并不能保證它們的交事件為空，即存在節(jié)點退出事件和對節(jié)點資源文件的檢索事件同時發(fā)生的可能性。

性質(zhì)3環(huán)監(jiān)測中節(jié)點發(fā)生顛簸的概率小于等于系統(tǒng)服務(wù)節(jié)點監(jiān)測時節(jié)點發(fā)生顛簸的概率。

分析：設(shè)節(jié)點在心跳周期中t∈[t0,tq]時接到相鏈接的環(huán)節(jié)點問候消息，所以[t0,t]?[t0,tq]，由概率的性質(zhì)可知：

由式（5）可知，環(huán)監(jiān)測中節(jié)點發(fā)生顛簸的概率小于等于系統(tǒng)服務(wù)節(jié)點監(jiān)測時節(jié)點發(fā)生顛簸的概率。

4 實驗結(jié)果與分析

4.1 實驗設(shè)置

本節(jié)驗證不同網(wǎng)絡(luò)規(guī)模下［18-19］節(jié)點退出網(wǎng)絡(luò)時檢索該節(jié)點文件失敗的概率與節(jié)點退出的概率密度函數(shù)，以及從節(jié)點退出到完成節(jié)點切換的時間關(guān)系。另外，用后切換與環(huán)備份節(jié)點間的監(jiān)測與節(jié)點切換算法進(jìn)行性能對比測試，以檢驗本文提出的環(huán)備份算法在降低顛簸事件中的有效性。本文測試平臺采用Python 編程實現(xiàn)。

4.2 顛簸事件性質(zhì)驗證

為了呈現(xiàn)顛簸事件的特性，測試參數(shù)設(shè)置如下：節(jié)點心跳周期為1s，節(jié)點加入和退出網(wǎng)絡(luò)事件在心跳周期內(nèi)隨機產(chǎn)生。隨機挑選在線節(jié)點發(fā)送訪問請求，訪問事件產(chǎn)生頻度為100 次/s，節(jié)點的切換時間設(shè)置5 組即1～5s，各種規(guī)模的測試時間為100s，測試節(jié)點數(shù)量設(shè)定為100～2 000，共20 組，顛簸事件測試結(jié)果如圖2 所示。

Fig.2 Bumpy event test results圖2 顛簸事件測試結(jié)果

測試結(jié)果證實了性質(zhì)2 的結(jié)論，即在不同網(wǎng)絡(luò)規(guī)模情況下，產(chǎn)生顛簸的概率與節(jié)點退出的概率密度函數(shù)以及從節(jié)點退出到完成節(jié)點切換的時間長短有關(guān)，而且當(dāng)網(wǎng)絡(luò)中節(jié)點規(guī)模較小而節(jié)點退出到切換到備份節(jié)點完成時間較長時，發(fā)生顛簸的幾率較大，反之發(fā)生顛簸的幾率較小，節(jié)點規(guī)模較大而訪問頻度不變時，顛簸幾率較為接近，即當(dāng)網(wǎng)絡(luò)中節(jié)點規(guī)模逐漸增大時，節(jié)點退出到完成切換的時間即便較長，顛簸的增長會比較平緩。由此可以看到顛簸事件發(fā)生幾率與檢索事件發(fā)生率密切相關(guān)。

4.3 環(huán)備份監(jiān)測算法有效性驗證

為了驗證環(huán)備份算法的有效性，將它與后切換進(jìn)行比較。設(shè)置測試參數(shù)如下：節(jié)點加入和退出網(wǎng)絡(luò)事件在心跳周期內(nèi)隨機產(chǎn)生，并且隨機訪問在線節(jié)點，系統(tǒng)服務(wù)節(jié)點的心跳周期和節(jié)點切換處理周期設(shè)為1s，各種節(jié)點規(guī)模的測試時間定為100s，且測試節(jié)點數(shù)量設(shè)定為100～2 000，共20 組，將訪問節(jié)點頻度分別為10 次/s、100 次/s、1000 次/s時，環(huán)備份和后切換發(fā)生顛簸事件的結(jié)果進(jìn)行比較，測試結(jié)果如圖3、圖4、圖5 所示。

由測試結(jié)果可以看出，后切換方法的顛簸發(fā)生率明顯高于環(huán)備份方法，但隨著訪問頻度的降低和節(jié)點數(shù)量的增加，兩種方法顛簸事件的發(fā)生逐漸減少。實驗證實了性質(zhì)3 的結(jié)果，在不同網(wǎng)絡(luò)規(guī)模下，環(huán)備份方法比后切換方法產(chǎn)生顛簸的概率明顯要小。實驗數(shù)據(jù)表明，顛簸事件平均降低50.894%。隨著網(wǎng)絡(luò)規(guī)模的增大，顛簸事件的發(fā)生幾率在下降。另外，訪問頻度的實驗結(jié)果對比也進(jìn)一步證實了隨著檢索頻度增加顛簸的概率也會增大。

Fig.3 Comparison of bumpy events between ring backup and post handover（1ms）圖3 環(huán)備份與后切換顛簸事件比較（1ms）

Fig.4 Comparison of bumpy events between ring backup and post handover（10ms）圖4 環(huán)備份與后切換顛簸事件比較（10ms）

Fig.5 Comparison of bumpy events between ring backup and post handover（100ms）圖5 環(huán)備份與后切換顛簸事件比較（100ms）

4.4 算法的資源消耗和性能分析

環(huán)備份監(jiān)測算法對節(jié)點的存儲和網(wǎng)絡(luò)帶寬占用都有所增加。首先，每個節(jié)點要部署監(jiān)測算法程序和工作存儲，因此總的存儲資源比后切換方式只在系統(tǒng)服務(wù)節(jié)點設(shè)置監(jiān)測算法程序和工作存儲時占用的存儲量要大，兩者存儲資源占用為：Sc≈nSb，其中Sc為環(huán)備份監(jiān)測算法對網(wǎng)絡(luò)節(jié)點存儲的占用，Sb為后切換方式占用系統(tǒng)服務(wù)節(jié)點存儲，n 為網(wǎng)絡(luò)節(jié)點數(shù)量。由于監(jiān)測程序采用輕量化設(shè)計而且分散在各節(jié)點上，所以對系統(tǒng)性能影響不大。另外，由于環(huán)備份監(jiān)測算法相互間要通過發(fā)送問候消息來監(jiān)測節(jié)點狀態(tài)，所以對網(wǎng)絡(luò)帶寬的消耗增加，在每個監(jiān)測周期內(nèi)相鄰節(jié)點間的通信至少增加1 次，因此對網(wǎng)絡(luò)帶寬的消耗比后切換增加1 倍。

由圖3、圖4、圖5 和測試數(shù)據(jù)可知，環(huán)備份的顛簸事件比后切換減少50.894%，性能提升明顯。測試中也發(fā)現(xiàn)，隨著網(wǎng)絡(luò)規(guī)模的增加，需求節(jié)點對資源節(jié)點平均訪問頻率降低，兩種方法的性能差距逐步縮小，但是環(huán)備份算法優(yōu)勢依然保持，表明算法性能穩(wěn)定。

5 結(jié)語

為了提高非結(jié)構(gòu)化P2P 網(wǎng)絡(luò)［20］中資源文件的可用性，本文基于資源的備份技術(shù)，對節(jié)點的切換方法和產(chǎn)生顛簸的因素進(jìn)行了研究。訪問節(jié)點資源時顛簸事件影響著系統(tǒng)的可用性，而顛簸產(chǎn)生在系統(tǒng)服務(wù)節(jié)點監(jiān)測節(jié)點狀態(tài)時，退出節(jié)點的監(jiān)測和節(jié)點的切換處理時段。為了減少顛簸現(xiàn)象發(fā)生，提出了一種環(huán)備份結(jié)構(gòu)及其監(jiān)測策略，實驗結(jié)果證實，環(huán)備份結(jié)構(gòu)及監(jiān)測方法在降低顛簸事件發(fā)生上明顯優(yōu)于后切換方法。后續(xù)將在網(wǎng)絡(luò)節(jié)點退出的預(yù)測方法和新的切換方法上深入研究，進(jìn)一步減少節(jié)點顛簸現(xiàn)象和資源消耗，提高系統(tǒng)可用性。