張攀東

【摘 要】本文首先介紹了 SCDN 基礎(chǔ)的拓?fù)浣Y(jié)構(gòu)，然后提出了基于需求的資源發(fā)現(xiàn)機(jī)制，混合 Push/Pull 的更新發(fā)布機(jī)制，節(jié)點加入離開相關(guān)的處理機(jī)制以及節(jié)點類型管理機(jī)制，最后對 SCDN 進(jìn)行了理論分析和仿真實驗。

【關(guān)鍵詞】SCDN；P2P；動態(tài)內(nèi)容

1 SCDN 的雙層結(jié)構(gòu)

SCDN 的目標(biāo)是在 P2P 網(wǎng)絡(luò)中構(gòu)建穩(wěn)定的內(nèi)容分布網(wǎng)絡(luò)，可以在參與節(jié)點頻繁動態(tài)變化的情況下定位所需的內(nèi)容，并對內(nèi)容及其副本進(jìn)行有效的管理。所以，SCDN 包括兩層：節(jié)點層和內(nèi)容層。根據(jù) CAN 協(xié)議，路由信息在節(jié)點層構(gòu)成一個d 維協(xié)作空間，同時每個內(nèi)容通過 DHT 被映射到鍵值最接近的節(jié)點上，如圖 1所示。

圖1 SCDN 的雙層結(jié)構(gòu)

我們之所以選擇 CAN 作為基礎(chǔ)拓?fù)涫且驗椋菏紫龋ㄟ^使用 d 維協(xié)作空間，CAN 可以支持多關(guān)鍵字查詢；其次，CAN 的路由表是節(jié)點基于局部信息構(gòu)建的，所以節(jié)點的加入離開僅會造成該節(jié)點周圍少數(shù)節(jié)點的路由表變化；此外，CAN 具有良好的魯棒性。雖然相對于其他 DHT 模型而言，CAN 的平均查詢路徑較長，但我們可以通過使用基于節(jié)點需求構(gòu)建的遠(yuǎn)程連接有效提高查詢速度。

2 基于需求的資源發(fā)現(xiàn)

由于每個節(jié)點不僅存儲了鄰居節(jié)點的信息，還存儲了若干通過遠(yuǎn)程連接相連的遠(yuǎn)程節(jié)點作為“捷徑”，所以 SCDN 可以通過將捷徑和 CAN 路由結(jié)合提高資源發(fā)現(xiàn)的性能。

每個節(jié)點通過搜索自己所有的鄰居連接和遠(yuǎn)程連接進(jìn)行資源發(fā)現(xiàn)，并將查詢請求轉(zhuǎn)發(fā)給和目標(biāo)內(nèi)容鍵值最接近的節(jié)點，直到找到目標(biāo)內(nèi)容的 CP。和 CAN 網(wǎng)絡(luò)中漸進(jìn)式的路由不同的是，SCDN 使用跳躍式的路由。假設(shè)節(jié)點 P5需要尋找內(nèi)容 A，如果是在 CAN 網(wǎng)絡(luò)中，查詢路徑會沿著 P5→P4→P3→P1前進(jìn)，直到抵達(dá)內(nèi)容 A 的 CAN 負(fù)責(zé)節(jié)點 P1節(jié)點，如圖 2 所示；如果是在 SCDN 網(wǎng)絡(luò)中且節(jié)點 P4和 P1之間存在一條遠(yuǎn)程連接，則查詢路徑會沿著 P5→P4→P1前進(jìn)，如圖 3所示。

圖 2 CAN 的查詢路徑示意圖

圖 3 SCDN 的查詢路徑示意圖

通過使用遠(yuǎn)程連接提供的捷徑，SCDN 可以提高資源發(fā)現(xiàn)的速度。內(nèi)容越流行，則需要該內(nèi)容的節(jié)點越多，這就會產(chǎn)生越多連向該內(nèi)容 CP 的遠(yuǎn)程連接，資源發(fā)現(xiàn)的速度也會越快。

3 混合 Push/Pull 的更新發(fā)布

由于每個復(fù)制節(jié)點都存儲了一個內(nèi)容的副本，所以網(wǎng)絡(luò)存在多副本。SCDN使用一種混合的 Push/Pull 的機(jī)制實現(xiàn)對內(nèi)容的更新和更新的發(fā)布，從而保證每個節(jié)點都可以在較低的通信成本下獲得最新版本的內(nèi)容并對內(nèi)容進(jìn)行更新。

為了降低系統(tǒng)的通信量，節(jié)點的類型是根據(jù)節(jié)點訪問內(nèi)容的速度決定的。頻繁訪問內(nèi)容的節(jié)點會成為內(nèi)容的 CRP，而訪問內(nèi)容的節(jié)點則會成為內(nèi)容的IRP。如何管理 CRP 和 IRP，我們將在后面詳細(xì)介紹。每個內(nèi)容都使用版本號區(qū)別不同的版本，并在每一次 VS 更新內(nèi)容之后對版本號進(jìn)行修改。

內(nèi)容的更新和更新的發(fā)布可以分為三個階段：更新請求、更新檢測、更新發(fā)布。

SCDN 根據(jù)節(jié)點訪問內(nèi)容的頻率決定節(jié)點更新內(nèi)容和更新發(fā)布的方式。VS 主動向所有的 CRP 發(fā)送更新信息，從而避免了頻繁的版本檢測；IRP 在使用副本之前主動檢測版本信息，從而避免了頻繁接收到更新消息。通過使用這種方式，SCDN 可以在較低的通信量之下對內(nèi)容進(jìn)行管理和更新，同時保證了所有的節(jié)點在它們需要使用或更新內(nèi)容時，可以獲得最新版本的內(nèi)容信息。

4 理論分析

通過對 SCDN 中遠(yuǎn)程連接的個數(shù)和平均查詢路徑的長度這兩者之間的關(guān)系進(jìn)行推導(dǎo)分析。

4.1 基于 Markov 鏈的分析

資源發(fā)現(xiàn)的過程可以形式化成為 Markov 鏈的一個吸收過程，如文[1]所示。每個節(jié)點僅根據(jù)自身當(dāng)前的狀態(tài)決定查詢請求需要被轉(zhuǎn)發(fā)的下一個節(jié)點。最后，在不考慮節(jié)點失效的情況下，查詢請求被轉(zhuǎn)發(fā)到目標(biāo)節(jié)點，成為一個吸收態(tài)。

假設(shè)一個系統(tǒng)中共有 N 個節(jié)點，所有的節(jié)點被從 0 到 N-1 進(jìn)行命名。不失一般性，我們將節(jié)點 0 作為查詢的目標(biāo)節(jié)點，而其他的所有節(jié)點都是查詢源節(jié)點。我們將查詢請求從節(jié)點 i 轉(zhuǎn)發(fā)到節(jié)點 j 的概率定義為轉(zhuǎn)移概率 pi，j，則整個轉(zhuǎn)移矩陣為P =（pi，j ） N* N。

我們使用hi，j記錄一個查詢請求從節(jié)點i被成功轉(zhuǎn)發(fā)到節(jié)點j的查詢路徑長度，則：

h■=1+■p■h■（1）

此后可以獲得從遷移態(tài) i（i=1，2，…，N-1）到吸收態(tài) j（j=0）的平均查詢路徑長度。

5 實驗和分析

使用仿真實驗測量了 SCDN 資源發(fā)現(xiàn)的性能，內(nèi)容和副本的一致性，以及在參與節(jié)點頻率動態(tài)變化下資源發(fā)現(xiàn)協(xié)議的魯棒性。

5.1 資源發(fā)現(xiàn)的性能

為了測量 SCDN 網(wǎng)絡(luò)中資源發(fā)現(xiàn)的性能，首先對比了在不同網(wǎng)絡(luò)規(guī)模下SCDN，CAN，SWOP 三種網(wǎng)絡(luò)的查詢效率，然后測量了在不同的網(wǎng)絡(luò)維數(shù)下，不同的最大存儲內(nèi)容數(shù)量下的查詢效率，最后對比了 CAN 路由和捷徑路由兩種路由方式對 SCDN 的影響。

實驗 1：在不同網(wǎng)絡(luò)規(guī)模下 SCDN、CAN、SWOP 三種網(wǎng)絡(luò)的查詢性能

SWOP 也是一種知名的在結(jié)構(gòu)化 P2P 網(wǎng)絡(luò)上使用遠(yuǎn)程連接構(gòu)建的改進(jìn) P2P 網(wǎng)絡(luò)。在 SWOP 中，所有的節(jié)點根據(jù)它們的鍵值有序排成環(huán)形結(jié)構(gòu)，并在環(huán)上形成聚類。每個聚類中有一個 head 節(jié)點，同一個聚類內(nèi)的所有其他節(jié)點都和 head節(jié)點直接相連。不同聚類之間通過遠(yuǎn)程連接相連。當(dāng)一個節(jié)點需要尋找某個內(nèi)容時，查詢請求先在聚類內(nèi)轉(zhuǎn)發(fā)，此后才會通過聚類中的遠(yuǎn)程連接轉(zhuǎn)發(fā)給其他聚類，這個過程不斷重復(fù)，直至找到所需內(nèi)容。

我們將 SCDN 和 SWOP 相比，因為 SWOP 使用隨機(jī)選擇的遠(yuǎn)程連接，而 SCDN使用基于節(jié)點需求選擇的遠(yuǎn)程連接，兩個都是使用遠(yuǎn)程連接來提高查詢性能。所以，我們可以通過構(gòu)建相同數(shù)量的遠(yuǎn)程連接來對 SWOP 和 SCDN 進(jìn)行公平的比較。我們將 SCDN 和 CAN 相比，是因為 SCDN 是構(gòu)建在 CAN 的基礎(chǔ)網(wǎng)絡(luò)之上。

分別考慮網(wǎng)絡(luò)規(guī)模為 N=1000 和 4096 兩種情況下的連通圖。每個節(jié)點發(fā)布一個內(nèi)容，所以網(wǎng)絡(luò)中總共有 N 個內(nèi)容。每個節(jié)點進(jìn)行 1000 次查找，查詢目標(biāo)在網(wǎng)絡(luò)所有內(nèi)容中隨機(jī)選擇。使用平均查詢路徑來衡量不同網(wǎng)絡(luò)的查詢性能。SCDN 使用 3 維鍵值空間，每個節(jié)點平均所需的內(nèi)容為 12 個，上限為 24 個。為了公平起見，SWOP 的遠(yuǎn)程連接個數(shù)也設(shè)為 24 個，CAN 也使用 3 維鍵值空間。

查詢路徑長度

圖 4 在網(wǎng)絡(luò)規(guī)模 N=1000，網(wǎng)絡(luò)維數(shù) d=3 的情況下，

SWOP、CAN、SCDN 三種網(wǎng)絡(luò)的查詢路徑長度分布圖

查詢路徑長度

圖 5 在網(wǎng)絡(luò)規(guī)模 N=4096，網(wǎng)絡(luò)維數(shù) d=3 的情況下，

SWOP、CAN、SCDN 三種網(wǎng)絡(luò)的查詢路徑長度分布圖

網(wǎng)絡(luò)規(guī)模N

圖 6 在不同網(wǎng)絡(luò)規(guī)模下，SWOP、CAN、SCDN

三種網(wǎng)絡(luò)的平均查詢路徑長度

圖4和圖5給出了在網(wǎng)絡(luò)規(guī)模N分別為1000和4096這兩種情況下，SWOP、CAN 和 SCDN 三種網(wǎng)絡(luò)的查詢路徑長度分布。圖6則總結(jié)了當(dāng)網(wǎng)絡(luò)規(guī)模從 1000 增加到 10000 時，這三種網(wǎng)絡(luò)的平均查詢路徑長度變化。從結(jié)果可以看出，SCDN 的平均查詢路徑長度始終低于 SWOP 和 CAN 兩種網(wǎng)絡(luò)。SCDN 的平均查詢路徑長度約為 SWOP 的 80.86%，僅為 CAN 的 30.69%。SCDN 的標(biāo)準(zhǔn)差也始終小于 SWOP 和 CAN 兩種網(wǎng)絡(luò)。

5.2 內(nèi)容和副本的一致性

實驗2：內(nèi)容和副本的一致性

研究 SCDN 在內(nèi)容被動態(tài)更新的情況下副本的正確率。假設(shè)內(nèi)容的更新服從泊松分布，參數(shù) T 從 0.5s 變化到 300s；每一跳的延遲也服從均值為 85ms的泊松分布[3]。

表 1 在網(wǎng)絡(luò)規(guī)模 N=1000 和 4096，網(wǎng)絡(luò)維數(shù) d=3 的情況下，SCDN 的內(nèi)容更新頻率對副本正確率的影響

表 1 顯示了 SCDN 在 N=1000 和 4096 這兩種網(wǎng)絡(luò)規(guī)模下，副本正確率隨內(nèi)容更新周期變化的情況。對于一般的文件共享系統(tǒng)而言，文件更新的周期一般大于等于 300s[4]。SCDN 在更新周期大于等于 10s 的時候總能保證副本正確率在 99%以上。即使對于內(nèi)容更新周期可能達(dá)到 0.5s～1s 的大規(guī)模多人在線游戲[5]而言，SCDN 的副本正確率也始終能大于 83.06%。

6 分析和討論

綜上所述，證明了 SCDN 可以提高資源發(fā)現(xiàn)和更新發(fā)布的性能，同時提供了良好的數(shù)據(jù)一致性和系統(tǒng)魯棒性。

1）SCDN 和 SWOP、CAN 相比具有更好的資源發(fā)現(xiàn)效率，當(dāng)網(wǎng)絡(luò)規(guī)模 N=4096，網(wǎng)絡(luò)維數(shù) d=3 時，平均查詢路徑長度僅為 3.71。查詢性能可以通過增加網(wǎng)絡(luò)維數(shù)和節(jié)點存儲的最大內(nèi)容數(shù)進(jìn)一步提高。這是因為 SCDN 總是先使用所需內(nèi)容提供的遠(yuǎn)程連接進(jìn)行粗糙的全局搜索，再進(jìn)行精確定位，從而降低了平均查詢路徑長度。

2）即使內(nèi)容被頻繁更新，內(nèi)容和副本仍能保持良好的可用性和一致性。當(dāng)更新周期在 10s 之上時，SCDN 可以保證 99%的副本都是正確一致的，這種更新頻率對于一般的文件共享系統(tǒng)而言已經(jīng)相當(dāng)高了。

3）即使參與節(jié)點頻繁動態(tài)加入離開網(wǎng)絡(luò)，SCDN 仍能保持良好的查詢性能。即使網(wǎng)絡(luò)中的節(jié)點替換率保持在 20%，（下轉(zhuǎn)第67頁）（上接第15頁）SCDN 仍能保證 98.83%的路由成功率和 4.77 跳的平均查詢路徑長度。

此外，在 SCDN 中使用雙層結(jié)構(gòu)進(jìn)行資源發(fā)現(xiàn)和更新發(fā)布。內(nèi)容和副本之間的拓?fù)浣Y(jié)構(gòu)形成了一種層次結(jié)構(gòu)可用于更新發(fā)布，而這些內(nèi)容和副本之間的遠(yuǎn)程連接還可以作為“捷徑”被用于資源發(fā)現(xiàn)。不同于其他的 P2P 系統(tǒng)，比如SWOP為了資源發(fā)現(xiàn)專門構(gòu)建遠(yuǎn)程連接，從而產(chǎn)生了額外的構(gòu)建和維護(hù)的成本，SCDN 的遠(yuǎn)程連接是根據(jù)節(jié)點的需求在內(nèi)容和副本之間自動構(gòu)建的，并可以通過更新發(fā)布過程自動維護(hù)，所以 SCDN 不需要任何額外的成本用于構(gòu)建和維護(hù)遠(yuǎn)程連接。

【參考文獻(xiàn)】

[1]AZZOUNA N B， GUILLEMIN F. Experimental analysis of the impact of peer-to-peer applications on traffic in commercial IP networks [J]. European Transactions on Telecommunications： Special Issue： Special Issue on P2P Networking and P2P Services， 2004， 15（6）： 511-522.

[2]ZHANG M， JOHN W， CLAFFY M， et al. State of the Art in Traffic Classification： A Research Review： PAM 2009： proceedings of the 10th International Conference on Passive and Active Measurement， South Korea， April 1-3， 2009[C]// Berlin： Springer， 2009.

[3]STEINMETZ R， WEHRLE K. Peer-to-Peer Networking and Computing [J]. Informatik-Spektrum， 2004， 27（1）： 51-54.

[4]Napster [EB/OL]. [2014-02-19]. http：//music.napster.com.

[責(zé)任編輯：楊玉潔]