SCDN在P2P網絡中的動態內容管理應用研究

張攀東

【摘 要】本文首先介紹了 SCDN 基礎的拓撲結構，然后提出了基于需求的資源發現機制，混合 Push/Pull 的更新發布機制，節點加入離開相關的處理機制以及節點類型管理機制，最后對 SCDN 進行了理論分析和仿真實驗。

【關鍵詞】SCDN；P2P；動態內容

1 SCDN 的雙層結構

SCDN 的目標是在 P2P 網絡中構建穩定的內容分布網絡，可以在參與節點頻繁動態變化的情況下定位所需的內容，并對內容及其副本進行有效的管理。所以，SCDN 包括兩層：節點層和內容層。根據 CAN 協議，路由信息在節點層構成一個d 維協作空間，同時每個內容通過 DHT 被映射到鍵值最接近的節點上，如圖 1所示。

圖1 SCDN 的雙層結構

我們之所以選擇 CAN 作為基礎拓撲是因為：首先，通過使用 d 維協作空間，CAN 可以支持多關鍵字查詢；其次，CAN 的路由表是節點基于局部信息構建的，所以節點的加入離開僅會造成該節點周圍少數節點的路由表變化；此外，CAN 具有良好的魯棒性。雖然相對于其他 DHT 模型而言，CAN 的平均查詢路徑較長，但我們可以通過使用基于節點需求構建的遠程連接有效提高查詢速度。

2 基于需求的資源發現

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

每個節點通過搜索自己所有的鄰居連接和遠程連接進行資源發現，并將查詢請求轉發給和目標內容鍵值最接近的節點，直到找到目標內容的 CP。和 CAN 網絡中漸進式的路由不同的是，SCDN 使用跳躍式的路由。假設節點 P5需要尋找內容 A，如果是在 CAN 網絡中，查詢路徑會沿著 P5→P4→P3→P1前進，直到抵達內容 A 的 CAN 負責節點 P1節點，如圖 2 所示；如果是在 SCDN 網絡中且節點 P4和 P1之間存在一條遠程連接，則查詢路徑會沿著 P5→P4→P1前進，如圖 3所示。

圖 2 CAN 的查詢路徑示意圖

圖 3 SCDN 的查詢路徑示意圖

通過使用遠程連接提供的捷徑，SCDN 可以提高資源發現的速度。內容越流行，則需要該內容的節點越多，這就會產生越多連向該內容 CP 的遠程連接，資源發現的速度也會越快。

3 混合 Push/Pull 的更新發布

由于每個復制節點都存儲了一個內容的副本，所以網絡存在多副本。SCDN使用一種混合的 Push/Pull 的機制實現對內容的更新和更新的發布，從而保證每個節點都可以在較低的通信成本下獲得最新版本的內容并對內容進行更新。

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

內容的更新和更新的發布可以分為三個階段：更新請求、更新檢測、更新發布。

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

4 理論分析

通過對 SCDN 中遠程連接的個數和平均查詢路徑的長度這兩者之間的關系進行推導分析。

4.1 基于 Markov 鏈的分析

資源發現的過程可以形式化成為 Markov 鏈的一個吸收過程，如文[1]所示。每個節點僅根據自身當前的狀態決定查詢請求需要被轉發的下一個節點。最后，在不考慮節點失效的情況下，查詢請求被轉發到目標節點，成為一個吸收態。

假設一個系統中共有 N 個節點，所有的節點被從 0 到 N-1 進行命名。不失一般性，我們將節點 0 作為查詢的目標節點，而其他的所有節點都是查詢源節點。我們將查詢請求從節點 i 轉發到節點 j 的概率定義為轉移概率 pi，j，則整個轉移矩陣為P =（pi，j ） N* N。

我們使用hi，j記錄一個查詢請求從節點i被成功轉發到節點j的查詢路徑長度，則：

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

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

5 實驗和分析

使用仿真實驗測量了 SCDN 資源發現的性能，內容和副本的一致性，以及在參與節點頻率動態變化下資源發現協議的魯棒性。

5.1 資源發現的性能

為了測量 SCDN 網絡中資源發現的性能，首先對比了在不同網絡規模下SCDN，CAN，SWOP 三種網絡的查詢效率，然后測量了在不同的網絡維數下，不同的最大存儲內容數量下的查詢效率，最后對比了 CAN 路由和捷徑路由兩種路由方式對 SCDN 的影響。

實驗 1：在不同網絡規模下 SCDN、CAN、SWOP 三種網絡的查詢性能

SWOP 也是一種知名的在結構化 P2P 網絡上使用遠程連接構建的改進 P2P 網絡。在 SWOP 中，所有的節點根據它們的鍵值有序排成環形結構，并在環上形成聚類。每個聚類中有一個 head 節點，同一個聚類內的所有其他節點都和 head節點直接相連。不同聚類之間通過遠程連接相連。當一個節點需要尋找某個內容時，查詢請求先在聚類內轉發，此后才會通過聚類中的遠程連接轉發給其他聚類，這個過程不斷重復，直至找到所需內容。

我們將 SCDN 和 SWOP 相比，因為 SWOP 使用隨機選擇的遠程連接，而 SCDN使用基于節點需求選擇的遠程連接，兩個都是使用遠程連接來提高查詢性能。所以，我們可以通過構建相同數量的遠程連接來對 SWOP 和 SCDN 進行公平的比較。我們將 SCDN 和 CAN 相比，是因為 SCDN 是構建在 CAN 的基礎網絡之上。

分別考慮網絡規模為 N=1000 和 4096 兩種情況下的連通圖。每個節點發布一個內容，所以網絡中總共有 N 個內容。每個節點進行 1000 次查找，查詢目標在網絡所有內容中隨機選擇。使用平均查詢路徑來衡量不同網絡的查詢性能。SCDN 使用 3 維鍵值空間，每個節點平均所需的內容為 12 個，上限為 24 個。為了公平起見，SWOP 的遠程連接個數也設為 24 個，CAN 也使用 3 維鍵值空間。

查詢路徑長度

圖 4 在網絡規模 N=1000，網絡維數 d=3 的情況下，

SWOP、CAN、SCDN 三種網絡的查詢路徑長度分布圖

查詢路徑長度

圖 5 在網絡規模 N=4096，網絡維數 d=3 的情況下，

SWOP、CAN、SCDN 三種網絡的查詢路徑長度分布圖

網絡規模N

圖 6 在不同網絡規模下，SWOP、CAN、SCDN

三種網絡的平均查詢路徑長度

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

5.2 內容和副本的一致性

實驗2：內容和副本的一致性

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

表 1 在網絡規模 N=1000 和 4096，網絡維數 d=3 的情況下，SCDN 的內容更新頻率對副本正確率的影響

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

6 分析和討論

綜上所述，證明了 SCDN 可以提高資源發現和更新發布的性能，同時提供了良好的數據一致性和系統魯棒性。

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

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

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

此外，在 SCDN 中使用雙層結構進行資源發現和更新發布。內容和副本之間的拓撲結構形成了一種層次結構可用于更新發布，而這些內容和副本之間的遠程連接還可以作為“捷徑”被用于資源發現。不同于其他的 P2P 系統，比如SWOP為了資源發現專門構建遠程連接，從而產生了額外的構建和維護的成本，SCDN 的遠程連接是根據節點的需求在內容和副本之間自動構建的，并可以通過更新發布過程自動維護，所以 SCDN 不需要任何額外的成本用于構建和維護遠程連接。

【參考文獻】

[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.

[責任編輯：楊玉潔]