宋靜靜

摘 要：大多數(shù)結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)是利用分布式哈希表（DHT）來實(shí)現(xiàn)無管理、容錯(cuò)的覆蓋網(wǎng)絡(luò)，并保證在O（logn）跳內(nèi)將消息傳遞到目標(biāo)。雖然從理論上講很完善，但這些系統(tǒng)在開放環(huán)境下面臨著一些困難。節(jié)點(diǎn)頻繁的加入和離開不僅會(huì)產(chǎn)生巨大的維護(hù)開銷，而且節(jié)點(diǎn)的各種行為和資源也會(huì)影響網(wǎng)絡(luò)的性能和安全性。本文構(gòu)建了一個(gè)與互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)緊密匹配的獨(dú)特的覆蓋網(wǎng)絡(luò)?；谶@種結(jié)構(gòu)的P2P系統(tǒng)不僅路由效率高，而且即使在高動(dòng)態(tài)環(huán)境下，維護(hù)開銷也很低。

我們將首先討論如何構(gòu)造一個(gè)近似于互聯(lián)網(wǎng)拓?fù)涞母采w層，然后基于該覆蓋層構(gòu)建一個(gè)高效查找、低維護(hù)開銷和高可用性的P2P系統(tǒng)。

覆蓋網(wǎng)絡(luò)的本質(zhì)是根據(jù)節(jié)點(diǎn)在Internet中的物理網(wǎng)絡(luò)位置來組織節(jié)點(diǎn)，所有節(jié)點(diǎn)都可以通過其自治系統(tǒng)（AS）軌跡劃分為組。由于互聯(lián)網(wǎng)由ASE組成，每個(gè)AS都是一個(gè)單一管理權(quán)限下的網(wǎng)絡(luò)，因此它為P2P節(jié)點(diǎn)提供了良好的邊界。與Internet中的一樣，組是網(wǎng)絡(luò)中路由和組織節(jié)點(diǎn)的基本單元。

一、P2P覆蓋網(wǎng)絡(luò)

為了支持類似DHT的ID查找操作，覆蓋網(wǎng)采用了類似的ID機(jī)制。與當(dāng)前的DHT設(shè)計(jì)一樣，覆蓋網(wǎng)的每個(gè)對象都被分配了一個(gè)128位的ID。覆蓋網(wǎng)的每個(gè)節(jié)點(diǎn)不需要映射一個(gè)小范圍的對象，而是使用兩級映射機(jī)制，第一個(gè)級別是在這些組中，第二個(gè)級別是在簇中。一個(gè)簇中的節(jié)點(diǎn)數(shù)量是可變的，以便于群集物理附近的節(jié)點(diǎn)，并增加系統(tǒng)下的穩(wěn)定性。

通常一個(gè)簇包括10到50個(gè)節(jié)點(diǎn)。每個(gè)簇都將選擇一個(gè)擁有良好網(wǎng)絡(luò)帶寬和可用性的領(lǐng)導(dǎo)者。此外，每個(gè)簇還分配了一個(gè)32位的ID。這些ID將隨機(jī)分配給每個(gè)組及其簇，因?yàn)樗鼈兪紫瘸霈F(xiàn)在覆蓋網(wǎng)中。對象ID的前64位分為兩部分。前32位用于映射組ID，后32位用于簇ID。每個(gè)組使用自身和下一組之間的ID對對象進(jìn)行充電，簇也是如此。

簇是存儲(chǔ)對象的基本單元。為了提高可靠性和可用性，每個(gè)簇將保留兩份對象副本。一份副本保存在領(lǐng)導(dǎo)者中，以響應(yīng)所有其他同行的查詢。另一個(gè)將通過擦除代碼技術(shù)分塊存儲(chǔ)在簇成員中。由于大多數(shù)對等端都是通過對稱網(wǎng)絡(luò)連接的，因此從許多相鄰對等端讀取數(shù)據(jù)的速度明顯快于從一個(gè)對等端讀取數(shù)據(jù)的速度。這一特點(diǎn)有助于舊領(lǐng)導(dǎo)失敗后，迅速重建新領(lǐng)導(dǎo)。

二、路由機(jī)制

除了讓許多不穩(wěn)定的節(jié)點(diǎn)參與系統(tǒng)路由之外，只有選定的具有適當(dāng)帶寬和可用性的節(jié)點(diǎn)將成為覆蓋路由的代理。通常，3個(gè)代理可以在不影響其主機(jī)的情況下提供足夠的可用性和性能。

由于我們的覆蓋網(wǎng)與Internet拓?fù)浣Y(jié)構(gòu)緊密匹配，因此與當(dāng)前的DHT設(shè)計(jì)相比，路由機(jī)制實(shí)際上很簡單。由于覆蓋網(wǎng)使用了兩級映射機(jī)制，因此路由表由兩部分組成。一個(gè)記錄覆蓋網(wǎng)中每個(gè)組的ID和代理信息，稱為路由表。此表在每個(gè)代理和領(lǐng)隊(duì)中維護(hù)，以路由普通節(jié)點(diǎn)的消息。另一個(gè)記錄了簇中所有簇的ID和領(lǐng)導(dǎo)信息，稱為交付表。給定一個(gè)對象ID，可以通過路由表找到負(fù)責(zé)組及其代理。消息將直接發(fā)送到目標(biāo)組的代理，而不是一個(gè)接一個(gè)地到達(dá)目標(biāo)組。當(dāng)消息到達(dá)該代理時(shí)，只需通過傳遞表將其轉(zhuǎn)發(fā)給響應(yīng)簇負(fù)責(zé)人。最后，領(lǐng)隊(duì)解析并回復(fù)查詢。

三、節(jié)點(diǎn)加入與離開

節(jié)點(diǎn)的加入和離開過程很簡單。當(dāng)一個(gè)新節(jié)點(diǎn)加入覆蓋時(shí)，它的軌跡可以由它的IP地址決定。通過覆蓋網(wǎng)的任何節(jié)點(diǎn)，加入請求將被轉(zhuǎn)發(fā)給代理。在測量其地標(biāo)向量后，節(jié)點(diǎn)將根據(jù)網(wǎng)絡(luò)位置加入一個(gè)簇。如果一個(gè)簇人口太多，它將根據(jù)節(jié)點(diǎn)的網(wǎng)絡(luò)位置劃分為兩個(gè)簇。如果加入節(jié)點(diǎn)是網(wǎng)絡(luò)中的第一個(gè)節(jié)點(diǎn)，則加入請求將轉(zhuǎn)發(fā)到附近的物理組。而不是形成一個(gè)新的組，節(jié)點(diǎn)最初將成為組內(nèi)的一個(gè)隊(duì)友。當(dāng)其中的節(jié)點(diǎn)足以容納三個(gè)簇時(shí)，將選擇代理并生成一個(gè)單獨(dú)的新組。

對于正常節(jié)點(diǎn)，簇會(huì)自動(dòng)容忍其離開或失敗。如果領(lǐng)導(dǎo)或代理離開，將選擇一個(gè)新的領(lǐng)導(dǎo)或代理，并且信息將快速傳播。

四、維護(hù)機(jī)制

在P2P環(huán)境下，由于每個(gè)節(jié)點(diǎn)都可以任意加入和退出覆蓋層，所以不僅每個(gè)節(jié)點(diǎn)的離開和失敗都是不可預(yù)測的，而且整個(gè)覆蓋層都是高度動(dòng)態(tài)的。對于所有的P2P覆蓋網(wǎng)絡(luò)來說，這確實(shí)是一個(gè)挑戰(zhàn)。

雖然代理和領(lǐng)導(dǎo)被認(rèn)為比普通的更可用，但他們并不是維護(hù)良好的服務(wù)器。這里使用一個(gè)環(huán)協(xié)議來監(jiān)視它們。例如，所有領(lǐng)導(dǎo)者都將形成一個(gè)環(huán)作為他們的ID關(guān)系，并且每秒鐘每個(gè)節(jié)點(diǎn)都會(huì)向其繼任者和前任發(fā)送一條保持活動(dòng)的消息。雖然這個(gè)協(xié)議很簡單，但它足以檢測到一個(gè)或多個(gè)領(lǐng)導(dǎo)者的失敗。同樣，一個(gè)簇的領(lǐng)導(dǎo)者也可以通過他們的查詢消息來監(jiān)控隊(duì)友的變化。但是，為了準(zhǔn)確區(qū)分每個(gè)節(jié)點(diǎn)對于領(lǐng)導(dǎo)者和代理候選人的行為，每個(gè)節(jié)點(diǎn)設(shè)計(jì)30秒向領(lǐng)導(dǎo)者發(fā)送一個(gè)查詢或保持活動(dòng)的消息。

由于領(lǐng)隊(duì)緩存來自組代理的路由表，因此需要一些方法來保持它們的一致性。對于有幾十個(gè)簇的小簇，領(lǐng)導(dǎo)者可以直接與附近的代理交換信息。但是，如果一個(gè)組非常大，其中有數(shù)百個(gè)簇，那么這樣簡單的時(shí)間表將不會(huì)具有可伸縮性。因此，可以利用當(dāng)前路由器廣泛支持的管理范圍的IP多播有效地傳遞最新的代理信息。對于不支持多播協(xié)議的網(wǎng)絡(luò)，將使用以代理為根的分發(fā)樹將信息多播給所有領(lǐng)導(dǎo)者。當(dāng)組更大時(shí)，它將被劃分為兩個(gè)或多個(gè)組。

如前所述，每個(gè)代理都維護(hù)一個(gè)路由表，記錄所有代理的信息。使這些路由表保持最新對于查找的正確性至關(guān)重要。此外，這種維護(hù)的開銷應(yīng)該很低，否則，系統(tǒng)性能和可擴(kuò)展性都會(huì)受到影響。因此，我們的覆蓋網(wǎng)設(shè)計(jì)成將維護(hù)工作集成到公共操作、查找中。

五、總結(jié)

針對開放互聯(lián)網(wǎng)環(huán)境下P2P覆蓋結(jié)構(gòu)面臨的困難，從不同角度提出了一種構(gòu)建P2P覆蓋網(wǎng)絡(luò)的新方法。與當(dāng)前專注于自身系統(tǒng)覆蓋的設(shè)計(jì)不同，我們的方法側(cè)重于物理網(wǎng)絡(luò)，并按照物理網(wǎng)絡(luò)構(gòu)建覆蓋網(wǎng)絡(luò)。自然地利用物理網(wǎng)絡(luò)特性，構(gòu)建高效、安全的P2P覆蓋網(wǎng)絡(luò)?；诠?jié)點(diǎn)的物理網(wǎng)絡(luò)特性，網(wǎng)絡(luò)打印為開放Internet環(huán)境下的節(jié)點(diǎn)提供了一個(gè)實(shí)用的自認(rèn)證標(biāo)識符。結(jié)合簡單的覆蓋路由機(jī)制，路由過程是安全的。此外，覆蓋網(wǎng)絡(luò)還可以通過彈出惡意節(jié)點(diǎn)來自我修復(fù)。