前切換：P2P 共享文件備份技術(shù)研究

鄭曉健，李 彤

（1.昆明理工大學(xué)津橋?qū)W院電氣與信息工程學(xué)院，云南昆明 650106；2.云南農(nóng)業(yè)大學(xué)大數(shù)據(jù)學(xué)院，云南昆明 650201）

0 引言

讓用戶能夠持續(xù)有效地共享網(wǎng)絡(luò)資源是P2P 網(wǎng)絡(luò)研究重點(diǎn)，然而在非結(jié)構(gòu)化P2P 網(wǎng)絡(luò)中，由于提供共享文件資源的節(jié)點(diǎn)頻繁而自由地加入和退出網(wǎng)絡(luò)，對(duì)系統(tǒng)的共享文件服務(wù)質(zhì)量產(chǎn)生影響，尤其是節(jié)點(diǎn)退出網(wǎng)絡(luò)可能會(huì)減少網(wǎng)絡(luò)中的共享資源量，造成資源需求節(jié)點(diǎn)查詢不到共享文件資源情況，降低了系統(tǒng)查詢成功率，也影響到系統(tǒng)可用性［1］。有研究提出采用文件備份技術(shù)，將共享文件資源的多個(gè)備份分布到網(wǎng)絡(luò)中，以形成一定程度的有效冗余［2］，通過(guò)提高文件備份在網(wǎng)絡(luò)節(jié)點(diǎn)中的占有率來(lái)改善文件查詢成功率［3-7］，同時(shí)提高系統(tǒng)可用性。

通常P2P 架構(gòu)的文件共享系統(tǒng)采用被動(dòng)式方法實(shí)現(xiàn)文件備份［8-10］，在節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)就選擇合適的備份節(jié)點(diǎn)并進(jìn)行文件備份。如果備份節(jié)點(diǎn)先于主節(jié)點(diǎn)退出網(wǎng)絡(luò)，還應(yīng)該尋找其它節(jié)點(diǎn)作為備份節(jié)點(diǎn)。為使共享文件在網(wǎng)絡(luò)中持續(xù)存在，設(shè)置系統(tǒng)服務(wù)節(jié)點(diǎn)監(jiān)測(cè)網(wǎng)絡(luò)中節(jié)點(diǎn)的在線狀況。各節(jié)點(diǎn)定期向系統(tǒng)服務(wù)節(jié)點(diǎn)發(fā)送心跳信號(hào)通報(bào)在線狀態(tài)，系統(tǒng)服務(wù)節(jié)點(diǎn)在規(guī)定的心跳周期時(shí)間內(nèi)未接收到節(jié)點(diǎn)的心跳信號(hào)即可斷定該節(jié)點(diǎn)已經(jīng)退出網(wǎng)絡(luò)。系統(tǒng)服務(wù)節(jié)點(diǎn)會(huì)將主節(jié)點(diǎn)的服務(wù)切換到備份節(jié)點(diǎn)，讓備份節(jié)點(diǎn)接替其服務(wù)成為新的主節(jié)點(diǎn)，而后再選擇新的備份節(jié)點(diǎn)。

系統(tǒng)服務(wù)節(jié)點(diǎn)按照設(shè)定的監(jiān)測(cè)周期，在每個(gè)監(jiān)測(cè)周期末期通過(guò)檢查各共享文件節(jié)點(diǎn)是否存在超期未發(fā)送心跳信號(hào)現(xiàn)象來(lái)發(fā)現(xiàn)節(jié)點(diǎn)的退出工況。從節(jié)點(diǎn)退出到系統(tǒng)服務(wù)節(jié)點(diǎn)發(fā)現(xiàn)節(jié)點(diǎn)退出這段時(shí)間存在一段檢索服務(wù)盲區(qū)。如果節(jié)點(diǎn)退出發(fā)生在系統(tǒng)服務(wù)節(jié)點(diǎn)監(jiān)測(cè)周期開始階段，要經(jīng)過(guò)幾乎整個(gè)監(jiān)測(cè)周期直到監(jiān)測(cè)周期末才會(huì)發(fā)現(xiàn)節(jié)點(diǎn)離線，再加上節(jié)點(diǎn)切換所耗時(shí)間，盲區(qū)時(shí)間甚至?xí)^(guò)一個(gè)監(jiān)測(cè)周期。在此期間網(wǎng)絡(luò)周期節(jié)點(diǎn)對(duì)退出節(jié)點(diǎn)文件的請(qǐng)求都會(huì)失敗，原因是系統(tǒng)服務(wù)節(jié)點(diǎn)返回的節(jié)點(diǎn)檢索信息為已離線節(jié)點(diǎn)的連接信息。本文將這種在被動(dòng)式系統(tǒng)中存在的檢索服務(wù)暫時(shí)性失敗或檢索時(shí)間延長(zhǎng)現(xiàn)象稱為“顛簸問(wèn)題”（Bumpy Problem）。實(shí)驗(yàn)顯示，顛簸事件發(fā)生的幾率較低，所以未引起人們重視。

本文對(duì)顛簸問(wèn)題進(jìn)行研究，提出一種更加簡(jiǎn)便實(shí)用的改進(jìn)方法，即前切換方法（PreSwitching Mechanism，PSM）。通過(guò)對(duì)混合型P2P 架構(gòu)的共享文件系統(tǒng)網(wǎng)絡(luò)中節(jié)點(diǎn)的停留時(shí)間預(yù)測(cè)節(jié)點(diǎn)的動(dòng)態(tài)特征，對(duì)在線節(jié)點(diǎn)提前進(jìn)行主備份節(jié)點(diǎn)切換，切換完成后備份節(jié)點(diǎn)可以接替主節(jié)點(diǎn)向網(wǎng)絡(luò)提供服務(wù)。為了降低節(jié)點(diǎn)切換頻度，在備份節(jié)點(diǎn)選擇可能會(huì)有更長(zhǎng)存留時(shí)間的節(jié)點(diǎn)，以有效減少系統(tǒng)顛簸發(fā)生，減少資源消耗。

1 相關(guān)工作

采用備份技術(shù)提高共享文件的占有率是有效提高文件查詢成功率［11-12］和資源可用性的重要方法。在非結(jié)構(gòu)化P2P 網(wǎng)絡(luò)環(huán)境中，文獻(xiàn)［1］采用主動(dòng)策略搜索識(shí)別稀有共享文件，在搜索過(guò)程中獲取共享文件的局部需求信息，然后按照用戶的需求信息備份共享文件，有針對(duì)性地提高文件在網(wǎng)絡(luò)中的流行度，從而提高稀有資源查詢的點(diǎn)擊率和可用性，但是獲取共享文件資源的整體流行度不容易；文獻(xiàn)［2］提出一種主動(dòng)復(fù)制資源技術(shù)，用隨機(jī)漫步的方式對(duì)節(jié)點(diǎn)上的共享資源進(jìn)行自搜索，用探測(cè)函數(shù)確定資源的稀有性，各節(jié)點(diǎn)用保存資源的需求閾值確定是否對(duì)資源進(jìn)行搜索和復(fù)制，該方式有效降低了資源探測(cè)和復(fù)制的額外網(wǎng)絡(luò)開銷；文獻(xiàn)［3］根據(jù)待選節(jié)點(diǎn)的存儲(chǔ)能力及與主節(jié)點(diǎn)的物理距離作為選擇節(jié)點(diǎn)條件，將備份文件布置到存儲(chǔ)空間充足和物理位置更近的節(jié)點(diǎn)上，使維護(hù)消耗更低，檢索成功率得到改善；文獻(xiàn)［4］將備份文件保存到能夠長(zhǎng)時(shí)間存留于網(wǎng)絡(luò)的節(jié)點(diǎn)上，提高系統(tǒng)在動(dòng)態(tài)變化時(shí)的適應(yīng)性。還有研究將文件備份布置到以往成功檢索所形成的路徑上，即放在檢索需求點(diǎn)和目標(biāo)文件節(jié)點(diǎn)之間，以提高資源在網(wǎng)絡(luò)中的流行度，降低網(wǎng)絡(luò)資源消耗。文獻(xiàn)［5］提出采用基于位置信息和流行度的備份資源管理算法PLAR，利用混合式服務(wù)器選擇策略以及遠(yuǎn)程增強(qiáng)策略，使資源下載平均速率明顯提高，有效提高共享速度并減少帶寬消耗；文獻(xiàn)［6］提出一種動(dòng)態(tài)備份文件資源分布方法，即按所設(shè)計(jì)的備份文件目錄和信息的獲取方法獲得資源的所有備份信息，并對(duì)訪問(wèn)頻率高和平均響應(yīng)時(shí)間長(zhǎng)的資源進(jìn)行備份，提供用戶訪問(wèn)特征和節(jié)點(diǎn)的實(shí)時(shí)帶寬等信息，計(jì)算存放備份的節(jié)點(diǎn)，使備份的分布能夠適應(yīng)訪問(wèn)請(qǐng)求和網(wǎng)絡(luò)帶寬的動(dòng)態(tài)變化；文獻(xiàn)［7］提出將備份文件部署到網(wǎng)絡(luò)的骨干節(jié)點(diǎn)或骨干鏈路上，提高檢索成功率，但是識(shí)別這些特殊路徑開銷較大。

以上備份方法主要采用被動(dòng)式方法備份文件，重點(diǎn)解決的是文件檢索成功率，這些方法確實(shí)能夠改善系統(tǒng)檢索性能并在一定程度上提高系統(tǒng)可用性，但由于P2P 網(wǎng)絡(luò)的動(dòng)態(tài)性，主備份節(jié)點(diǎn)都可能退出系統(tǒng)，使花費(fèi)大量時(shí)間布置的備份文件隨節(jié)點(diǎn)的退出而減少，造成檢索失敗，所以采用持續(xù)備份技術(shù)機(jī)制很有必要。

2 檢索文件時(shí)的顛簸問(wèn)題

2.1 場(chǎng)景描述

以下將P2P 網(wǎng)絡(luò)中自主產(chǎn)生和提供共享文件的節(jié)點(diǎn)稱為主節(jié)點(diǎn)，存放主節(jié)點(diǎn)的備份文件節(jié)點(diǎn)稱為備份節(jié)點(diǎn)，對(duì)主節(jié)點(diǎn)提出資源請(qǐng)求的節(jié)點(diǎn)稱為需求節(jié)點(diǎn)。主節(jié)點(diǎn)和備份節(jié)點(diǎn)在資源服務(wù)方面形成互補(bǔ)和相互依存關(guān)系。為了快速方便地搜尋到主節(jié)點(diǎn)或備份節(jié)點(diǎn)，在混合型P2P 網(wǎng)絡(luò)中，系統(tǒng)服務(wù)節(jié)點(diǎn)存儲(chǔ)各主節(jié)點(diǎn)以及對(duì)應(yīng)的備份節(jié)點(diǎn)網(wǎng)絡(luò)連接信息和共享文件目錄信息，并向所有資源需求節(jié)點(diǎn)提供共享文件檢索服務(wù)。資源需求節(jié)點(diǎn)從系統(tǒng)服務(wù)節(jié)點(diǎn)檢索到主節(jié)點(diǎn)的網(wǎng)絡(luò)連接信息和共享文件信息后，就可向主節(jié)點(diǎn)發(fā)出文件請(qǐng)求消息，再通過(guò)文件交換，資源需求節(jié)點(diǎn)就可獲得文件資源。系統(tǒng)服務(wù)節(jié)點(diǎn)還負(fù)責(zé)在主節(jié)點(diǎn)退出網(wǎng)絡(luò)后刷新節(jié)點(diǎn)連接信息，使主節(jié)點(diǎn)提供的服務(wù)切換到備份節(jié)點(diǎn)上。

在混合型P2P 網(wǎng)絡(luò)中，一些網(wǎng)絡(luò)事件會(huì)導(dǎo)致節(jié)點(diǎn)的狀態(tài)發(fā)生變化，呈現(xiàn)為加入、在線、刷新、顛簸和離線5 種狀態(tài)，形成節(jié)點(diǎn)的生命周期。

（1）加入狀態(tài)。當(dāng)節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)時(shí)，先向系統(tǒng)服務(wù)節(jié)點(diǎn)發(fā)送加入網(wǎng)絡(luò)請(qǐng)求，在等待對(duì)方回復(fù)的這段時(shí)間節(jié)點(diǎn)處于加入狀態(tài)。此時(shí)系統(tǒng)將節(jié)點(diǎn)的連接信息和共享文件信息記錄下來(lái)，準(zhǔn)備為其它資源需求節(jié)點(diǎn)提供檢索服務(wù)。

（2）在線狀態(tài)。節(jié)點(diǎn)收到系統(tǒng)服務(wù)節(jié)點(diǎn)的回復(fù)消息后進(jìn)入在線狀態(tài)。

（3）刷新狀態(tài)。在線狀態(tài)下的主節(jié)點(diǎn)和備份節(jié)點(diǎn)均可能轉(zhuǎn)變?yōu)樗⑿聽顟B(tài)。如果本節(jié)點(diǎn)是主節(jié)點(diǎn)，當(dāng)它共享的文件內(nèi)容發(fā)生變化時(shí)須通知系統(tǒng)服務(wù)節(jié)點(diǎn)和備份節(jié)點(diǎn)，刷新文件信息和內(nèi)容，以便保持主節(jié)點(diǎn)和備份節(jié)點(diǎn)文件一致；如果節(jié)點(diǎn)是備份節(jié)點(diǎn)，在收到主節(jié)點(diǎn)發(fā)送過(guò)來(lái)的刷新消息后即開始與主節(jié)點(diǎn)交換備份文件內(nèi)容，以上兩種情況下節(jié)點(diǎn)都處于刷新狀態(tài)。

（4）顛簸狀態(tài)。在線狀態(tài)下的需求節(jié)點(diǎn)向系統(tǒng)服務(wù)節(jié)點(diǎn)發(fā)出檢索共享文件消息，系統(tǒng)服務(wù)節(jié)點(diǎn)收到消息后查詢共享文件，向需求節(jié)點(diǎn)回復(fù)提供共享文件的主節(jié)點(diǎn)連接信息和相關(guān)信息。假設(shè)主節(jié)點(diǎn)在此前已經(jīng)退出網(wǎng)絡(luò)，離線時(shí)又沒(méi)有通知系統(tǒng)服務(wù)節(jié)點(diǎn)，而系統(tǒng)服務(wù)節(jié)點(diǎn)的監(jiān)測(cè)周期還未結(jié)束就不能發(fā)現(xiàn)該主節(jié)點(diǎn)已經(jīng)退出，所以它回復(fù)的依舊是主節(jié)點(diǎn)退出前的信息，按此狀態(tài)去連接主節(jié)點(diǎn)將失敗，這時(shí)節(jié)點(diǎn)處于顛簸狀態(tài)。

（5）離線狀態(tài)。即節(jié)點(diǎn)退出網(wǎng)絡(luò)時(shí)的狀態(tài)。P2P 節(jié)點(diǎn)退出和加入網(wǎng)絡(luò)是自由的，加入和退出網(wǎng)絡(luò)時(shí)是否通知系統(tǒng)服務(wù)節(jié)點(diǎn)不確定。

5 種節(jié)點(diǎn)狀態(tài)相互變換過(guò)程如圖1 所示。

Fig.1 Node lifetime process圖1 節(jié)點(diǎn)生命期過(guò)程

P2P 網(wǎng)絡(luò)中節(jié)點(diǎn)具有動(dòng)態(tài)性［13-14］，節(jié)點(diǎn)的加入和退出對(duì)網(wǎng)絡(luò)共享文件資源分布及數(shù)量狀況產(chǎn)生明顯影響，從而對(duì)網(wǎng)絡(luò)中相關(guān)資源的服務(wù)產(chǎn)生影響。因此，P2P 網(wǎng)絡(luò)是一個(gè)資源動(dòng)態(tài)變化的網(wǎng)絡(luò)。

2.2 問(wèn)題定義

主節(jié)點(diǎn)退出網(wǎng)絡(luò)時(shí)，網(wǎng)絡(luò)中需求節(jié)點(diǎn)對(duì)主節(jié)點(diǎn)的共享文件請(qǐng)求會(huì)失敗。隨著系統(tǒng)將主節(jié)點(diǎn)服務(wù)轉(zhuǎn)移到備份節(jié)點(diǎn)上，之前的服務(wù)將恢復(fù)并延續(xù)。本文通過(guò)對(duì)顛簸、后切換、前切換等概念和性質(zhì)的討論得出前切換策略。

定義1（顛簸）將從主節(jié)點(diǎn)退出網(wǎng)絡(luò)到系統(tǒng)完成主節(jié)點(diǎn)至備份節(jié)點(diǎn)的切換這一時(shí)段內(nèi)，資源需求節(jié)點(diǎn)對(duì)主節(jié)點(diǎn)的服務(wù)請(qǐng)求出現(xiàn)暫時(shí)性失敗的現(xiàn)象稱為服務(wù)顛簸或顛簸。

定義2（后切換）將系統(tǒng)服務(wù)節(jié)點(diǎn)發(fā)現(xiàn)主節(jié)點(diǎn)退出后再安排主節(jié)點(diǎn)服務(wù)切換到備份節(jié)點(diǎn)的切換方法稱為被動(dòng)式切換或后切換。

定義3（前切換）將節(jié)點(diǎn)未發(fā)生退出事件前就進(jìn)行主節(jié)點(diǎn)到備份節(jié)點(diǎn)的切換方法稱為主動(dòng)式切換或前切換。

2.3 顛簸事件性質(zhì)

在P2P 網(wǎng)絡(luò)中，節(jié)點(diǎn)退出和節(jié)點(diǎn)被檢索都是隨機(jī)發(fā)生的，所以顛簸的發(fā)生也具有隨機(jī)性，產(chǎn)生顛簸的時(shí)間是連續(xù)型隨機(jī)變量。下面從備份過(guò)程分析顛簸產(chǎn)生的原因和概率相關(guān)因素。

引理1主節(jié)點(diǎn)退出和需求節(jié)點(diǎn)對(duì)主節(jié)點(diǎn)共享文件的檢索是相互獨(dú)立事件。

定理1從主節(jié)點(diǎn)退出網(wǎng)絡(luò)到系統(tǒng)服務(wù)節(jié)點(diǎn)發(fā)現(xiàn)主節(jié)點(diǎn)退出，再到啟動(dòng)并完成節(jié)點(diǎn)的切換，這段時(shí)間內(nèi)對(duì)節(jié)點(diǎn)文件的檢索和訪問(wèn)會(huì)失敗。

證明：設(shè)?a∈Node，Node 為網(wǎng)絡(luò)節(jié)點(diǎn)集合，時(shí)間段(0,tq]為節(jié)點(diǎn)a 兩次心跳之間的時(shí)間間隔，其中tq＞0，tq是節(jié)點(diǎn)的心跳周期。

（1）若t0∈(0,tq]時(shí)節(jié)點(diǎn)a 退出，那么系統(tǒng)服務(wù)節(jié)點(diǎn)在[t0,tq]不會(huì)接收到節(jié)點(diǎn)a 的心跳信號(hào)，因而(0,tq]期間不能斷定節(jié)點(diǎn)是否已經(jīng)退出；tq時(shí)刻之后，系統(tǒng)服務(wù)節(jié)點(diǎn)將可以推斷節(jié)點(diǎn)a 已經(jīng)退出網(wǎng)絡(luò)。

（2）在(tq,th],tq＜th時(shí)段，系統(tǒng)服務(wù)節(jié)點(diǎn)將節(jié)點(diǎn)a 的服務(wù)切換到備份節(jié)點(diǎn)。

（3）若其他資源需求節(jié)點(diǎn)檢索節(jié)點(diǎn)a 文件的事件在(t0,th]時(shí)間內(nèi)發(fā)生，那么由（1）可知系統(tǒng)服務(wù)節(jié)點(diǎn)在[t0,tq]期間還沒(méi)有發(fā)現(xiàn)節(jié)點(diǎn)a 退出，所以提供的還是節(jié)點(diǎn)a 的檢索信息。由（2）可知系統(tǒng)服務(wù)節(jié)點(diǎn)在(tq,th]時(shí)間內(nèi)盡管已經(jīng)發(fā)現(xiàn)節(jié)點(diǎn)退出，但還沒(méi)有完成節(jié)點(diǎn)a 到備份節(jié)點(diǎn)的切換，所以不能提供節(jié)點(diǎn)a 的備份節(jié)點(diǎn)正確信息，因此在[t0,th]時(shí)段內(nèi)，資源需求節(jié)點(diǎn)對(duì)節(jié)點(diǎn)a 文件的檢索將失敗。

本文將時(shí)間段[t0,tq]稱為退出節(jié)點(diǎn)發(fā)現(xiàn)期，(tq,th]時(shí)間段稱為節(jié)點(diǎn)切換期。

定理2當(dāng)節(jié)點(diǎn)退出網(wǎng)絡(luò)時(shí)，檢索該節(jié)點(diǎn)文件失敗的概率只與節(jié)點(diǎn)退出的概率密度函數(shù)以及從節(jié)點(diǎn)退出到完成節(jié)點(diǎn)切換的時(shí)間長(zhǎng)短有關(guān)。

證明：設(shè)?a∈Node，Node 為網(wǎng)絡(luò)節(jié)點(diǎn)集合，節(jié)點(diǎn)a 退出網(wǎng)絡(luò)的時(shí)間為連續(xù)型隨機(jī)變量Q，且Q 在(t1,t2),t1＜t2上的概率密度函數(shù)為（fq）。這里以節(jié)點(diǎn)退出網(wǎng)絡(luò)為前提條件，所以P（Q）＞0，?b∈Node，節(jié)點(diǎn)b 向節(jié)點(diǎn)a 發(fā)送檢索文件消息，檢索時(shí)間為連續(xù)型隨機(jī)變量R，R 在(t1,t2)上的概率密度函數(shù)為h（r），t1＜q＜t2，t1＜r＜t2，同時(shí)?t∈(t1,t2)，且(t,t+ε)?(t1,t2)，其中t 是節(jié)點(diǎn)b 檢索節(jié)點(diǎn)a 的時(shí)間，ε=th-t，th是節(jié)點(diǎn)切換結(jié)束的時(shí)間，則節(jié)點(diǎn)在(t,t+ε)期間節(jié)點(diǎn)a 退出網(wǎng)絡(luò)的概率為：

在（t，t+ε）期間，網(wǎng)絡(luò)中節(jié)點(diǎn)b 檢索節(jié)點(diǎn)a 的文件概率為：

在（t，t+ε）期間，當(dāng)節(jié)點(diǎn)a 退出網(wǎng)絡(luò)時(shí)，節(jié)點(diǎn)b 檢索節(jié)點(diǎn)a 的文件概率為：

在式（3）中，由引理1 知R 和Q 相互獨(dú)立，即：

而由定理1，（t，t+ε）時(shí)間段內(nèi)如果發(fā)生對(duì)節(jié)點(diǎn)a 的檢索事件則檢索失敗。由式（4）可知檢索失敗的概率等于檢索事件發(fā)生的概率。由式（2）可知，從節(jié)點(diǎn)退出網(wǎng)絡(luò)到節(jié)點(diǎn)切換完成期間，檢索節(jié)點(diǎn)a 中文件的概率只與其概率密度函數(shù)、發(fā)現(xiàn)節(jié)點(diǎn)退出和切換所用的時(shí)間有關(guān)。

3 前切換策略

通過(guò)對(duì)顛簸問(wèn)題的分析和實(shí)驗(yàn)驗(yàn)證，本文提出一種新的主節(jié)點(diǎn)和備份節(jié)點(diǎn)切換方法，即前切換算法PSM。在系統(tǒng)服務(wù)節(jié)點(diǎn)控制下，從在線節(jié)點(diǎn)中預(yù)測(cè)即將退出的節(jié)點(diǎn)，提前進(jìn)行節(jié)點(diǎn)切換，由備份節(jié)點(diǎn)繼續(xù)提供服務(wù)。

有些方法可保持檢索服務(wù)成功率，但是要付出一定代價(jià)。如系統(tǒng)服務(wù)節(jié)點(diǎn)回應(yīng)資源需求節(jié)點(diǎn)檢索時(shí)，同時(shí)向其提供主節(jié)點(diǎn)和備份節(jié)點(diǎn)的網(wǎng)絡(luò)連接信息。資源需求節(jié)點(diǎn)對(duì)主節(jié)點(diǎn)和備份節(jié)點(diǎn)同時(shí)發(fā)起資源請(qǐng)求，收到它們反饋的檢索結(jié)果后進(jìn)行仲裁，再選擇利用，或者采用一些無(wú)需檢索信息支持的搜索方法，如洪泛、隨機(jī)漫步等搜索方式。這些方法帶來(lái)的問(wèn)題是產(chǎn)生大量的網(wǎng)絡(luò)帶寬消耗或更長(zhǎng)的檢索時(shí)間［15］。

3.1 前切換性質(zhì)

由引理1 可知節(jié)點(diǎn)退出事件和對(duì)節(jié)點(diǎn)共享文件的檢索事件獨(dú)立，但不能保證它們的交事件為空，即存在節(jié)點(diǎn)退出事件和對(duì)節(jié)點(diǎn)共享文件的檢索事件同時(shí)發(fā)生的可能性。盡管前切換算法也有產(chǎn)生顛簸的風(fēng)險(xiǎn)，但是前切換與后切換產(chǎn)生顛簸的概率呈現(xiàn)下面性質(zhì)。

定理3節(jié)點(diǎn)前切換時(shí)發(fā)生顛簸的概率小于等于后切換時(shí)發(fā)生顛簸的概率。

證明：前切換算法的顛簸來(lái)自于節(jié)點(diǎn)切換期(tq,th]，即在切換過(guò)程中如果遇到節(jié)點(diǎn)退出將產(chǎn)生顛簸。后切換發(fā)生顛簸的時(shí)段包括退出節(jié)點(diǎn)發(fā)現(xiàn)期和節(jié)點(diǎn)切換期，即[t0,th]，而(tq,th]?[t0,th]，且(tq,th]∩[t0,th]=?，由概率的有限可加性得：

式（5）中P{t0＜R＜tq}≥0，則有：

即前切換遇到顛簸概率小于等于后切換。

3.2 前切換機(jī)制

前切換需完成兩個(gè)階段任務(wù)：

（1）第一階段完成共享文件的備份和一致性維護(hù)。①共享文件備份。節(jié)點(diǎn)加入和退出網(wǎng)絡(luò)要由系統(tǒng)服務(wù)節(jié)點(diǎn)按照備份節(jié)點(diǎn)選擇算法尋找合適的備份節(jié)點(diǎn)，記錄主備份節(jié)點(diǎn)的連接信息和共享文件信息，然后向主節(jié)點(diǎn)和備份節(jié)點(diǎn)發(fā)送消息，將主節(jié)點(diǎn)文件發(fā)送到備份節(jié)點(diǎn)，使得共享文件在2 個(gè)或以上節(jié)點(diǎn)中存在；②共享文件一致性維護(hù)。當(dāng)主節(jié)點(diǎn)的共享文件發(fā)生變化時(shí)，通過(guò)系統(tǒng)服務(wù)節(jié)點(diǎn)的備份節(jié)點(diǎn)連接信息向備份節(jié)點(diǎn)發(fā)送消息，刷新備份節(jié)點(diǎn)文件內(nèi)容，以保持主節(jié)點(diǎn)和備份節(jié)點(diǎn)文件的一致性。

（2）第二階段進(jìn)行主節(jié)點(diǎn)和備份節(jié)點(diǎn)的前切換。系統(tǒng)服務(wù)節(jié)點(diǎn)預(yù)測(cè)即將退出網(wǎng)絡(luò)主節(jié)點(diǎn)，在它退出前，通過(guò)更新系統(tǒng)服務(wù)節(jié)點(diǎn)信息表將主節(jié)點(diǎn)轉(zhuǎn)換為備份節(jié)點(diǎn)，以實(shí)現(xiàn)節(jié)點(diǎn)切換。切換完成后，所有對(duì)主節(jié)點(diǎn)的共享文件檢索將提供備份節(jié)點(diǎn)連接信息，需求節(jié)點(diǎn)可繼續(xù)訪問(wèn)共享文件。

在切換中主節(jié)點(diǎn)與備份節(jié)點(diǎn)間的共享文件交換需要消耗網(wǎng)絡(luò)帶寬及備份節(jié)點(diǎn)存儲(chǔ)的資源，頻繁切換會(huì)增大資源消耗，甚至丟失備份文件［8-10］。根據(jù)文獻(xiàn)［4］的研究，節(jié)點(diǎn)存留于網(wǎng)絡(luò)的時(shí)間對(duì)于系統(tǒng)可用性有影響，即節(jié)點(diǎn)存留于網(wǎng)絡(luò)的時(shí)間長(zhǎng)度與保存在節(jié)點(diǎn)上的文件可用性成正比。通過(guò)統(tǒng)計(jì)設(shè)定在線節(jié)點(diǎn)集合的平均存留時(shí)間作為衡量指標(biāo)，找到存留時(shí)間更長(zhǎng)的節(jié)點(diǎn)使節(jié)點(diǎn)切換延后。

設(shè)在系統(tǒng)服務(wù)節(jié)點(diǎn)各監(jiān)測(cè)周期∑t時(shí)段內(nèi)，?ai∈Node，i=1，2，…，n，Node為有n 個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的集合。

定義4（節(jié)點(diǎn)存留時(shí)間）時(shí)間?t內(nèi)，節(jié)點(diǎn)ai在網(wǎng)絡(luò)中的存留時(shí)間為?ti=tie-tis，其中tis為ai加入網(wǎng)絡(luò)的時(shí)間，tie為ai退出網(wǎng)絡(luò)的時(shí)間。

定義5（節(jié)點(diǎn)平均存留時(shí)間）時(shí)間?t內(nèi)，網(wǎng)絡(luò)節(jié)點(diǎn)的平均存留時(shí)間為：

其中,?ti為ai的節(jié)點(diǎn)存留時(shí)間，fi是節(jié)點(diǎn)存留時(shí)間為?ti的節(jié)點(diǎn)數(shù)。

定義6（節(jié)點(diǎn)在線時(shí)間）時(shí)刻t網(wǎng)絡(luò)中在線節(jié)點(diǎn)ai的在線時(shí)間為?tiL=t-tis，其中tis為節(jié)點(diǎn)ai加入網(wǎng)絡(luò)的時(shí)間。

定義7（節(jié)點(diǎn)平均在線時(shí)間）設(shè)t時(shí)刻網(wǎng)絡(luò)在線節(jié)點(diǎn)平均在線時(shí)間為：

其中，?tiL為節(jié)點(diǎn)ai的在線時(shí)間，fi是在線時(shí)間為?tiL的節(jié)點(diǎn)數(shù)。

系統(tǒng)服務(wù)節(jié)點(diǎn)為了記錄節(jié)點(diǎn)和共享文件信息，設(shè)置節(jié)點(diǎn)信息表NIT、備份節(jié)點(diǎn)表CIT、共享文件信息表SIT。NIT的每個(gè)記錄為＜ai，s，t1，t2＞，其中ai為節(jié)點(diǎn)號(hào)，s 為狀態(tài)，加入時(shí)間為t1，當(dāng)前在線時(shí)間為t2。CIT的每個(gè)記錄為＜am，ab＞，其中am為主節(jié)點(diǎn)號(hào)，ab為備份節(jié)點(diǎn)號(hào)，SIT的每個(gè)記錄為＜ID，file，am，t＞，其中ID為記錄編號(hào)，file為共享文件名，am為主節(jié)點(diǎn)號(hào)，t為更新時(shí)間。

共享文件備份和一致性維護(hù)［14-15］時(shí)，選擇備份節(jié)點(diǎn)以存留時(shí)間超過(guò)網(wǎng)絡(luò)的平均存留時(shí)間為條件。在線節(jié)點(diǎn)的存留時(shí)間由系統(tǒng)服務(wù)節(jié)點(diǎn)的存留時(shí)間算法實(shí)現(xiàn)。當(dāng)系統(tǒng)服務(wù)節(jié)點(diǎn)接收到節(jié)點(diǎn)的心跳信號(hào)時(shí)會(huì)更新節(jié)點(diǎn)信息表NIT的信息，然后按照定義5 計(jì)算并刷新網(wǎng)絡(luò)的節(jié)點(diǎn)平均存留時(shí)間E，以提供給備份節(jié)點(diǎn)選擇算法使用。

算法1 備份節(jié)點(diǎn)選擇算法

輸入：節(jié)點(diǎn)信息表NIT，T時(shí)間段內(nèi)網(wǎng)絡(luò)節(jié)點(diǎn)平均存留時(shí)間E

輸出：選擇出的備份節(jié)點(diǎn)

步驟1：按條件ai.s=0 且ai.tie-ai.tis＞E查詢節(jié)點(diǎn)信息表NIT，得節(jié)點(diǎn)記錄集NTiL：

如果NTiL≠ ?，則執(zhí)行步驟2；

如果NTiL=?，則amax=?，執(zhí)行步驟6；

步驟2：移動(dòng)到NTiL的第一個(gè)記錄ak∈NTiL；

步驟3：amax=ak；

步驟4：移動(dòng)到NTiL的下一個(gè)記錄ak∈NTiL；

步驟5：如果amax.tie-amax.tis＜ak.tie-ak.tis，則amax=ak，執(zhí)行步驟4；

否則執(zhí)行步驟6；

步驟6：返回amax。

系統(tǒng)服務(wù)節(jié)點(diǎn)心跳周期結(jié)束時(shí)執(zhí)行前切換算法。

算法2 前切換算法

輸入：節(jié)點(diǎn)信息表NIT，節(jié)點(diǎn)平均在線時(shí)間EL

輸出：選出的節(jié)點(diǎn)切換到備份節(jié)點(diǎn)

步驟1：按條件ai.s=1 且t-ai.tiL＞EL查詢節(jié)點(diǎn)信息表NIT，得節(jié)點(diǎn)記錄集NITs：

如果NITs≠ ?則執(zhí)行步驟2；

如果NITs=?則執(zhí)行步驟8；

步驟2：移動(dòng)到NITs的第一個(gè)記錄aj∈NITs；

步驟3：更新SIT 的所有記錄rec∈SIT,rec.am=aj,aj∈NITs，為rec.am=aj；

步驟4：調(diào)用備份節(jié)點(diǎn)選擇算法，選擇備份節(jié)點(diǎn)an；

如果an=?，則執(zhí)行步驟7；

如果an≠ ?，則執(zhí)行步驟5；

步驟5：更新CIT 的記錄＜am，ab＞，am=aj,ab=an；

步驟6：發(fā)送消息給節(jié)點(diǎn)am，通知它可以退出網(wǎng)絡(luò)；

步驟7：移動(dòng)到NITs的下一個(gè)記錄：如果NITs≠ ?則執(zhí)行步驟3；

如果NITs=?則執(zhí)行步驟8；

步驟8：返回切換節(jié)點(diǎn)數(shù)量。

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

4.1 實(shí)驗(yàn)設(shè)置

先驗(yàn)證不同網(wǎng)絡(luò)規(guī)模下［16］節(jié)點(diǎn)退出網(wǎng)絡(luò)時(shí)檢索該節(jié)點(diǎn)文件失敗的概率與節(jié)點(diǎn)退出的概率，用后切換作對(duì)比，對(duì)前切換算法進(jìn)行性能測(cè)試，以檢驗(yàn)本文提出的前切換算法降低顛簸事件的有效性。系統(tǒng)仿真環(huán)境為：操作系統(tǒng)Windows VistaTHHome Basic，處理器Intel（R）Core（TH）2 Duo CPU P8600 @2.40GHz 2.40GHz，內(nèi)存2.0GB。測(cè)試平臺(tái)采用VB6.0 編程實(shí)現(xiàn)。

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

為清晰呈現(xiàn)發(fā)生顛簸事件情況，測(cè)試參數(shù)設(shè)置如下：節(jié)點(diǎn)加入和退出網(wǎng)絡(luò)事件的頻度為1 節(jié)點(diǎn)/s，退出節(jié)點(diǎn)隨機(jī)產(chǎn)生；隨機(jī)挑選在線節(jié)點(diǎn)發(fā)送檢索請(qǐng)求事件，檢索事件產(chǎn)生頻度為10 次/s；系統(tǒng)服務(wù)節(jié)點(diǎn)的心跳周期設(shè)置為0.5s；所有節(jié)點(diǎn)規(guī)模的測(cè)試時(shí)間長(zhǎng)度均為1 800s。模擬測(cè)試節(jié)點(diǎn)數(shù)量規(guī)模分別為100 個(gè)、500 個(gè)、1 000 個(gè)、2 000 個(gè)；顛簸事件測(cè)試結(jié)果如圖2 所示。

測(cè)試結(jié)果證實(shí)了定理2，即在不同網(wǎng)絡(luò)規(guī)模情況下產(chǎn)生顛簸的概率只與節(jié)點(diǎn)退出的概率密度函數(shù)以及從節(jié)點(diǎn)退出到完成節(jié)點(diǎn)切換的時(shí)間長(zhǎng)短有關(guān)。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模較小而節(jié)點(diǎn)退出切換到備份節(jié)點(diǎn)完成時(shí)間較長(zhǎng)時(shí)，發(fā)生顛簸幾率較大，顛簸發(fā)生次數(shù)增長(zhǎng)較快。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)規(guī)模逐漸增大時(shí)，節(jié)點(diǎn)退出到切換到備份節(jié)點(diǎn)完成時(shí)間即便較長(zhǎng)，顛簸事件發(fā)生的幾率仍在增長(zhǎng)，但增長(zhǎng)速度會(huì)比較平緩。顛簸事件發(fā)生幾率與檢索事件發(fā)生率直接相關(guān)。

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

4.3 前切換算法有效性驗(yàn)證

為評(píng)價(jià)減少顛簸事件時(shí)前切換算法的有效性，將它與后切換進(jìn)行對(duì)比。設(shè)置測(cè)試參數(shù)如下：節(jié)點(diǎn)加入和退出網(wǎng)絡(luò)事件的頻度為1 節(jié)點(diǎn)/s，退出節(jié)點(diǎn)隨機(jī)產(chǎn)生；隨機(jī)選擇在線節(jié)點(diǎn)發(fā)送檢索資源請(qǐng)求，檢索事件產(chǎn)生頻度為10 次/s；系統(tǒng)服務(wù)節(jié)點(diǎn)的心跳周期和節(jié)點(diǎn)切換處理周期設(shè)為1s，各種節(jié)點(diǎn)規(guī)模測(cè)試時(shí)間長(zhǎng)度均設(shè)為1 800s。模擬測(cè)試節(jié)點(diǎn)數(shù)量分別為100 個(gè)、500 個(gè)、1 000 個(gè)、1 500 個(gè)、2 000 個(gè)；將前切換和后切換發(fā)生顛簸事件切換處理時(shí)間為1、3 和5s 時(shí)測(cè)試結(jié)果進(jìn)行比較，如圖3、圖4、圖5 所示。

Fig.3 Comparison of pre-switching Switch before and after switching turbulence event（1 second switching time）圖3 前切換與后切換顛簸事件比較（1s 切換時(shí)間）

Fig.4 Comparison of pre-switching and after switching turbulence event（3 seconds switching time）圖4 前切換與后切換顛簸事件比較（3s 切換時(shí)間）

從圖中可以看出，前切換測(cè)試結(jié)果比較穩(wěn)定，后切換方法存在明顯的顛簸現(xiàn)象，隨著節(jié)點(diǎn)數(shù)量的增加顛簸事件發(fā)生有所減少，但是發(fā)生率仍然很高。前切換方法顛簸事件發(fā)生率比較低且保持穩(wěn)定狀態(tài)，主要原因在于前切換排除了節(jié)點(diǎn)退出發(fā)現(xiàn)期的顛簸事件問(wèn)題。實(shí)驗(yàn)證實(shí)了定理3的結(jié)果，即在不同網(wǎng)絡(luò)規(guī)模下，節(jié)點(diǎn)前切換時(shí)發(fā)生顛簸的概率明顯小于等于后切換，而且隨著網(wǎng)絡(luò)規(guī)模的增大，顛簸事件的發(fā)生幾率也在下降。所以，前切換在避免顛簸事件上效果較好。

Fig.5 Comparison of pre-switching and after switching turbulence event（5 seconds switching time）圖5 前切換與后切換顛簸事件比較（5s 切換時(shí)間）

5 結(jié)語(yǔ)

為提高非結(jié)構(gòu)P2P 網(wǎng)絡(luò)［17-18］中共享文件系統(tǒng)可用性，本文從共享文件備份技術(shù)著手，對(duì)主、備份節(jié)點(diǎn)的切換技術(shù)進(jìn)行了研究。發(fā)現(xiàn)影響系統(tǒng)可用性［19-20］的主要因素是顛簸事件的發(fā)生，而顛簸產(chǎn)生在系統(tǒng)節(jié)點(diǎn)退出時(shí)段和切換處理時(shí)段。為了減少顛簸現(xiàn)象發(fā)生，提出一種基于主動(dòng)切換策略的前切換方法，它比后切換方法減少了系統(tǒng)服務(wù)節(jié)點(diǎn)退出這一過(guò)程。實(shí)驗(yàn)結(jié)果證實(shí)前切換方法在降低顛簸事件發(fā)生方面明顯優(yōu)于后切換方法。后續(xù)將在網(wǎng)絡(luò)節(jié)點(diǎn)退出的預(yù)測(cè)方法上進(jìn)一步研究以提高預(yù)測(cè)準(zhǔn)確性，從而進(jìn)一步降低節(jié)點(diǎn)切換頻度和資源消耗，提高系統(tǒng)可用性。