短路徑優(yōu)先的覆蓋網(wǎng)絡構造

吳國福，韓崗，竇文華

（國防科技大學 計算機學院，湖南 長沙 410073）

1 引言

P2P系統(tǒng)中 Peer節(jié)點顯示或隱式地形成覆蓋(overlay)網(wǎng)絡。短路徑優(yōu)先的覆蓋網(wǎng)絡構建策略使邏輯連接盡可能限制在自治域范圍內(nèi)，能有效減少主干網(wǎng)流量，加快信息的傳播速度。短路徑優(yōu)先策略需要獲知節(jié)點之間的網(wǎng)絡延遲，如果直接測量網(wǎng)絡延遲，隨著系統(tǒng)規(guī)模的增大，探測報文產(chǎn)生的開銷將遠大于覆蓋網(wǎng)絡結構優(yōu)化帶來的收益。理想的方案應該是低成本、分布式、易擴展的。

網(wǎng)絡坐標系統(tǒng)[1]將網(wǎng)絡中節(jié)點映射到有限維度度量空間，使用節(jié)點在度量空間的距離估算網(wǎng)絡延遲。本文提出基于被動路標的網(wǎng)絡距離預測技術，利用 Internet上已經(jīng)部署的服務器對探測報文的響應，獲得節(jié)點到路標的網(wǎng)絡延遲，通過Lipschitz[1]變換將節(jié)點網(wǎng)絡延遲映射到有限維度量空間中的元素，然后使用網(wǎng)絡距離函數(shù)估算網(wǎng)絡距離。

網(wǎng)絡距離預測技術以較小的網(wǎng)絡開銷準確地估算節(jié)點間的網(wǎng)絡延遲，新的問題是節(jié)點如何快速定位臨近節(jié)點。一種好的思路是先快速篩選一組可能的臨近節(jié)點，縮小計算范圍；然后從中選擇距離最近的臨近節(jié)點。本文引入空間填充曲線(SFC,space filling curve)[2]技術并提出基于查表的映射算法完成快速篩選的預處理工作。

綜合網(wǎng)絡坐標技術和空間填充曲線技術，本文提出短路徑優(yōu)先的覆蓋網(wǎng)絡構建策略。通過較小的網(wǎng)絡開銷和計算代價，節(jié)點獲得臨近節(jié)點的信息并與之建立邏輯連接。短路徑優(yōu)先策略使得邏輯覆蓋網(wǎng)絡與底層物理網(wǎng)絡拓撲結構盡可能匹配，有效減少物理鏈路上的重復報文。實驗結果表明，本文方法構建的覆蓋網(wǎng)絡具備良好的性能。

文章的后續(xù)組織如下：第2節(jié)介紹相關工作，第 3節(jié)提出基于被動路標的網(wǎng)絡距離預測技術，第4節(jié)提出基于查表的對角線空間填充曲線映射算法，第5節(jié)給出短路徑優(yōu)先的覆蓋網(wǎng)絡構造方法，第6節(jié)實驗驗證本文方案的有效性，第7節(jié)是結束語。

2 相關工作

P2P應用系統(tǒng)中，消息沿著覆蓋網(wǎng)絡中繼傳輸，其質(zhì)量對系統(tǒng)性能有重要影響。覆蓋網(wǎng)絡中一跳對應物理網(wǎng)絡中的一條端到端路徑。邏輯路徑P對應的物理路徑集合，稱為實際路徑。以邏輯路徑P的起始節(jié)點開頭，在物理網(wǎng)絡中遍歷 P上所有 Peer節(jié)點的具有某種最優(yōu)屬性（如最短距離）的路徑P’，稱之為理想路徑（理想路徑可能不只一條）。如果實際路徑中Peer節(jié)點的訪問順序與理想路徑中Peer節(jié)點的訪問順序一致，稱之為路徑完美匹配。如果覆蓋網(wǎng)絡中所有的邏輯路徑都是路徑完美匹配的，則稱覆蓋網(wǎng)絡是拓撲完美匹配的。實現(xiàn)拓撲完美匹配是困難的，實際中學者一般利用某種網(wǎng)絡結構信息優(yōu)化覆蓋網(wǎng)絡，使其與物理網(wǎng)絡在拓撲上盡量匹配。實現(xiàn)拓撲匹配有2種策略：一是直接構造拓撲匹配地覆蓋網(wǎng)絡；二是動態(tài)優(yōu)化覆蓋網(wǎng)絡，使其與物理網(wǎng)絡相匹配。下面介紹相關文獻中的典型方法。

S.Ratnasamy[3]等提出基于節(jié)點分類的方法構建拓撲匹配的覆蓋網(wǎng)絡。物理網(wǎng)絡中距離近的節(jié)點劃為同一類別，稱之為一個bin。分類方法如下：網(wǎng)絡中部署一組路標節(jié)點，節(jié)點測量到各個路標節(jié)點的網(wǎng)絡距離；按照從小到大的順序排列網(wǎng)絡距離，從而獲得路標節(jié)點的序列，將該序列作為節(jié)點的bin。節(jié)點選取鄰居節(jié)點時，首先從同一個bin中選取，數(shù)量不夠時從差別最小的bin中繼續(xù)選取。

Mithos[4]基于網(wǎng)絡坐標系統(tǒng)構建連接高效覆蓋網(wǎng)絡。節(jié)點加入系統(tǒng)時根據(jù)初始鄰近節(jié)點的網(wǎng)絡坐標計算自身網(wǎng)絡坐標；節(jié)點以自身為中心在每個象限內(nèi)尋找最近節(jié)點與之建立鄰居關系。該方案初始加入過程冗長，節(jié)點需要經(jīng)過多次迭代才能在系統(tǒng)中找到臨近節(jié)點；節(jié)點坐標一旦確定后不再變化，這與P2P系統(tǒng)的動態(tài)特性不相適應。

Zhichen Xu[5]等結合基于路標的分類技術和小范圍直接測量技術選擇鄰近節(jié)點。使用基于路標的分類技術選擇與自身類別相同或相似的部分節(jié)點，然后直接測量網(wǎng)絡距離以選取最近的節(jié)點。系統(tǒng)將節(jié)點到路標的網(wǎng)絡距離信息作為系統(tǒng)軟狀態(tài)分布保存在相關節(jié)點上，其他節(jié)點根據(jù)到路標的距離信息查找到相關節(jié)點獲取同類別或相似類別的節(jié)點信息。

SAT-Match[6]是一種針對結構化覆蓋網(wǎng)絡CAN[7]的局部優(yōu)化措施。每次迭代由2個階段組成：探測階段和跳轉階段。在探測階段，節(jié)點S在限定范圍內(nèi)（比如兩跳內(nèi)）泛洪探測報文，收集限定區(qū)域內(nèi)節(jié)點的IP地址，然后測量網(wǎng)絡傳輸延時。在跳轉階段，判斷是否跳轉應該對比跳轉前后該區(qū)域內(nèi)所有節(jié)點平均邏輯連接長度的變化，如果變小則進行跳轉。在結構化覆蓋網(wǎng)絡中節(jié)點狀態(tài)與節(jié)點位置密切相關，SAT-Match優(yōu)化過程需要大量跳轉操作，狀態(tài)遷移和探測報文會給系統(tǒng)代理沉重的負擔。

Quasi-Chord[8]直接利用GNP[9]技術預測網(wǎng)絡距離構建Chord[10]覆蓋網(wǎng)絡。首先使用網(wǎng)路距離預測技術 GNP獲取節(jié)點網(wǎng)絡坐標，然后使用二維卡托空間填充曲線對網(wǎng)絡坐標作映射得到節(jié)點序號，最后使用序號作為標識符構建環(huán)形覆蓋網(wǎng)絡。

LTM[11]是一種分布式的基于位置感知局部優(yōu)化技術，其主要使用2種操作提高拓撲匹配度：剪枝操作、加邊操作。剪枝操作主要針對圖1(a)和圖1(b)2種情況，在圖1(a)中，節(jié)點S向外泛洪TTL＝2的探測報文，節(jié)點P接收到節(jié)點S發(fā)送的探測報文和節(jié)點N1轉發(fā)的探測報文，計算出連接PS、PN1和SN1的長度LPS、L1PN、L1SN。如果LPS或者L1PN明顯長于其他2條連接，則將其剪除。同樣在圖1(b)中，節(jié)點P獲取L1PN、L2PN、L1SN、L2SN的長度，如果L1PN或者L2PN明顯長于其他3條連接，則將其剪除。加邊操作發(fā)生在圖1(c)的情形，節(jié)點S與節(jié)點P之間沒有直接連接，節(jié)點P接收泛洪報文后主動探測到節(jié)點S的網(wǎng)絡傳輸延遲LPS，如果LPS明顯長于L1PN、L1SN，則不需添加新邊，否則添加新邊PS。LTM存在一些不足：①需要大量迭代才能取得較好的效果；②節(jié)點要保持時間同步，現(xiàn)有的網(wǎng)絡時間協(xié)議服務精度有限，影響優(yōu)化效果。

圖1 LTM中的剪枝、加邊操作

3 基于被動路標的網(wǎng)絡距離預測

本節(jié)提出一種基于被動路標的網(wǎng)絡距離預測方法，從而獲得物理網(wǎng)絡的拓撲信息以指導覆蓋網(wǎng)絡的構建。

3.1 網(wǎng)絡距離預測方案

在基于網(wǎng)絡坐標系統(tǒng)的網(wǎng)絡距離預測方案[1]中，大都引入路標節(jié)點。路標或者全局固定不變，或者由隨機選擇的普通節(jié)點擔當，2種方法各有缺陷。前者部署成本昂貴，通用性差；后者容易產(chǎn)生誤差積累并且坐標易陷于局部最優(yōu)。目前 Internet上存在大量的高性能穩(wěn)定的服務器節(jié)點，如 DNS服務器、Web服務器等，響應端節(jié)點的探測報文。如果利用這些節(jié)點充當路標，既解決路標全局不變方案中部署成本昂貴的問題，又解決路標隨機選擇方案中的誤差累積和局部性問題。但是這些服務器節(jié)點只被動響應客戶端請求，無法主動對外探測，需要特殊方法利用其路標功能。

Internet上的節(jié)點是按一定層次結構組織的，這種結構使得區(qū)域內(nèi)節(jié)點間延遲小，而區(qū)域間節(jié)點間延遲大。網(wǎng)絡距離近節(jié)點往往處在同一區(qū)域中，到路標的網(wǎng)絡距離較為接近；網(wǎng)絡距離遠節(jié)點可能處在不同區(qū)域中，到路標的網(wǎng)絡距離差異較大。直接使用節(jié)點到路標的網(wǎng)絡傳輸延遲作為節(jié)點的網(wǎng)絡坐標，坐標值之間的歐式距離能夠反映出節(jié)點的網(wǎng)絡距離。

鑒于上述認識，提出基于被動路標的網(wǎng)絡距離預測方法（PLNDP, passive-landmark based network distance prediction）。PLNDP整體思路是：在Internet上搜索已經(jīng)部署的高性能服務器作為路標節(jié)點；普通節(jié)點提前獲知路標通信地址并測量到各個路標的網(wǎng)絡延遲，使用Lipschitz變換獲取網(wǎng)絡坐標；通過中心服務器交換網(wǎng)絡坐標，普通節(jié)點使用特定的距離函數(shù)計算網(wǎng)絡坐標在向量空間Rn中的距離，進而預測節(jié)點間的網(wǎng)絡距離。

3.2 網(wǎng)絡距離預測方法執(zhí)行過程

3.2.1 路標節(jié)點的選擇

Internet上已經(jīng)部署高性能服務器節(jié)點大多數(shù)響應客戶端的探測報文，端節(jié)點使用ping命令很容易獲得到服務器的網(wǎng)絡延遲。選擇哪些服務器節(jié)點作為路標需要解決下面的問題。①路標節(jié)點的數(shù)量k，數(shù)量過多產(chǎn)生大量探測報文，同時會提供冗余信息；數(shù)量太少使得預測結果偏差過大。實驗結果表明，數(shù)量在8～10之間就可獲得較高的預測準確度。考慮到路標節(jié)點的失效，認為路標數(shù)量在 12個比較合適。②路標節(jié)點的分布區(qū)域，為了發(fā)揮參考作用，路標應該分布在合理的范圍。其范圍取決于應用程序的使用范圍，如果應用程序面向整個Internet，則路標節(jié)點應該分布在全球各個地方；如果應用程序是區(qū)域性的，比如面向中國大陸地區(qū)，則路標節(jié)點應該限制在區(qū)域以內(nèi)。③路標節(jié)點的相對位置，距離太近的路標提供的信息存在很大的冗余，因此路標節(jié)點應該盡可能分散。實驗表明隨機選擇即可。本文在應用程序使用范圍內(nèi)搜集性能穩(wěn)定的大型服務器，從中選擇數(shù)量合適、均勻分布的服務器作為路標節(jié)點，其他服務器留作備份使用。

3.2.2 普通節(jié)點獲取網(wǎng)絡坐標

路標節(jié)點的地址和序號提前發(fā)送給普通節(jié)點，普通節(jié)點i發(fā)送echo request 探測報文到所有路標節(jié)點，接收到echo replay響應報文后計算往返傳輸延遲RTT，則節(jié)點i到對應路標的網(wǎng)絡延遲近似為RTT/2。普通節(jié)點可多次測量 RTT，選擇延遲的最小值或者平均值來規(guī)避網(wǎng)絡暫時擁塞帶來的影響。當測得到所有路標節(jié)點的網(wǎng)絡延遲后，普通節(jié)點使用Lipschitz變換獲得自身網(wǎng)絡坐標。失效路標節(jié)點對應的坐標元素值為0。

3.2.3 網(wǎng)絡距離預測

普通節(jié)點獲取自身網(wǎng)絡坐標后，向中心服務器注冊。普通節(jié)點通過中心服務器或者其他節(jié)點獲取感興趣節(jié)點的網(wǎng)絡坐標，使用距離函數(shù)計算兩者之間的網(wǎng)絡距離。假設路標節(jié)點的數(shù)量為 n，普通節(jié)點 a、b坐標分別為 ( a1, a2,… ,an)、(b1, b2,… ,bn)。原始坐標不能直接進行距離計算，要對其進行兩方面的預處理。首先去除失效路標，失效路標對應的坐標元素值為 0，去除失效路標對應的坐標元素得到新坐標。由于路標節(jié)點是性能穩(wěn)定的服務器，失效概率很低，該方法完全可應對路標失效問題。其次去除冗余路標，如果普通節(jié)點a、b到路標節(jié)點A、B的網(wǎng)絡傳輸延時之差相當，則認為A、B對a、b的參考作用相同，A、B相對于a、b而言是互為冗余的，保留一個即可。將失效路標和冗余路標對應的坐標元素去除后，a、b的新坐標變?yōu)?a1′ , a2′ ,… ,am′ )、( b1′ , b2′ ,… ,bm′)，m為有效路標節(jié)點數(shù)目，則 a、b之間的網(wǎng)絡距離由下面的距離函數(shù)計算得到：

下面舉例說明PLNDP的具體操作。在圖2所示的網(wǎng)絡拓撲結構中，選擇節(jié)點 ACDEFH作為路標節(jié)點，abc為普通節(jié)點，連接線上的數(shù)字表示節(jié)點間的傳輸延遲。假設路標E對節(jié)點a是失效的，則節(jié)點 a、b、c的坐標分別為（3，3，6，0，9，13）、（13，9，6，6，3，3）、（8，6，1，7，4，8）。計算 a、b之間的距離時，剔除失效路標得到坐標（3，3，6，9，13），（13，9，6，3，3），無冗余路標，計算得到Lab=12.78。計算b、c之間的距離時，b、c到路標A、D的距離差都是5，所以A、D相互冗余，去掉路標D，同樣路標E、F也是相互冗余的，去掉路標F，得到新坐標（13，9，6，3），（8，6，7，8），計算得到Lbc= 6.71。同理可得Lac= 7.7。a、b、c之間的實際距離為Mab=12、Mbc=7、Mac= 7，預測誤差分別為6.5%、4.1%、10%。預測距離與實際距離較為接近，該方法具有較高的預測準確度。

圖2 隨機連接網(wǎng)絡

3.3 動態(tài)網(wǎng)絡環(huán)境下PLNDP的處理

在網(wǎng)絡環(huán)境動態(tài)變化情況下，將網(wǎng)絡看作由一系列快照組成，快照持續(xù)時間為τ，在時間τ內(nèi)，網(wǎng)絡變化可忽略。PLNDP每隔周期 T更新節(jié)點的網(wǎng)絡坐標，如果限制 T＜τ/2，則保證坐標測量和預測在同一網(wǎng)絡快照內(nèi)完成，仍然可以看作PLDNP在靜態(tài)網(wǎng)絡中運行。只要合理設置更新周期T，PLDNP在動態(tài)網(wǎng)絡中仍保持高的預測準確性。

4 基于查表的空間填充曲線快速映射算法

基于被動路標的網(wǎng)絡距離預測較為準確地預測節(jié)點之間的距離信息。當節(jié)點需要獲取臨近節(jié)點集合時，最直觀的方法是計算到所有節(jié)點網(wǎng)絡距離，然后挑選最近的節(jié)點集合。在大規(guī)模分布式系統(tǒng)中，這種方式將導致計算資源緊張。一種有效方法是首先快速篩選出一組粗糙節(jié)點集合，然后通過精確計算確定所需的節(jié)點。本文引入空間填充曲線技術完成快速篩選工作。本節(jié)主要介紹基于查表的空間填充曲線快速映射算法，快速篩選方案在下一節(jié)給出。

4.1 空間填充曲線介紹

空間填充曲線是數(shù)據(jù)降維處理的典型方法，在多維空間元素映射與整數(shù)之間建立一一映射關系。皮亞諾[12]首先提出空間填充曲線的概念，給出單位長度到單位正方形的連續(xù)滿射函數(shù)，即皮亞諾曲線。希爾伯特[13]擴展了空間填充曲線的概念，給出單位長度到單位d維立方體映射的幾何構造?？臻g填充曲線一個良好性質(zhì)是映射具有臨近性，即2個元素在D維空間中臨近，像點在數(shù)值上保持接近。圖3給出了幾種典型的2維空間曲線填充示例。

4.2 對角線空間填充曲線

圖3 2維空間填充曲線

已有文獻給出的空間填充曲線映射算法或者局限在二維空間內(nèi)，或者計算較為復雜。本文給出對角線空間填充曲線的映射算法，計算簡單且容易擴展到高維空間。在下面的描述中假定原始空間的維度為m，每一維度上有個格點，格點的序號從1開始計數(shù)。首先規(guī)定對曲線的訪問規(guī)則，假設格點C = (c1,c2,…,cm)和 C′=( c1′, c2′,…,cm′)的序號分別為p、q，令則 p＜q當且僅當下列條件之一成立：① k

4.3 對角線空間填充曲線映射算法

當m=2時格點的訪問順序很直觀，求解的方法很多；對于高維空間m＞ 2 中的格點C =( c1, c2,… ,cm)，如果簡單使用遞歸方法求解其計算量隨m和g成指數(shù)規(guī)模增長。下面給出基于查表的空間填充曲線快速映射算法。

首先引入等勢面的概念，等勢面是指坐標元素之和相等的所有格點集合，用符號Ek表示，其中下標 表示等勢面高度，即格點坐標元素之和，顯然k≥ 2 。對于格點令由必要條件知格點 C的順序 SFC_Order(C)決定于Ei中元素的數(shù)量|Ei|(i ＜k)和C在Ek中的順序Ek_Order(C)，即

下面分別介紹Ek中元素數(shù)量|Ek|和C在Ek中順序Ek_Order(C)的計算方法。

本文使用函數(shù) f ( k, g, m) 表示等勢面 Ek中元素的數(shù)量。由于k是格點的坐標元素之和，所以k的有效取值范圍是[0,m( g- 1 )]，規(guī)定

當m=1時每個等勢面只有一個格點，即

k=0當且僅當格點坐標每個元素值都為 0，也就是說等勢面E0中僅有一個元素，即

等勢面 Ek中格點 C =(c1, c2,…,cm)的坐標元素值之和為k，首先考慮cm的取值，當cm取0時其他m-1個元素之和必須為 k，即 cm取 0時共有f( k, g, m- 1 )個格點在 Ek中，同理當 cm取i∈[0,g -1]時，共有f( k -i ,g, m- 1 )個格點在Ek中，因此可得

這樣m維等勢面元素數(shù)量可用多個(m-1)維等勢面元素數(shù)量之和表示。同樣m維高度為k-1的等勢面元素數(shù)量可表示為

式(7)、式(8)相減得到函數(shù) f ( k, g, m )的遞推關系。

f( k, g, m )- f( k- 1 ,g, m )=f( k- 0 ,g, m- 1)-f( k-1 -g+ 1 ,g, m-1)

即

使用式(3)～式(6)以及式(9)，可依次快速求解各個維度上不同高度的等勢面中含有的元素數(shù)量。

確定格點順序還需要求解格點 C= (c1, c2,…,cm)在等勢面中的順序。求解思路如下：假設格點 X =( x1, x2, …,xm-1,xm)位于等勢面 Ek中并且X在中的順序p小于C在Ek中的順序q，根據(jù)條件(2)求解滿足條件的數(shù)量。先考慮 x1的取值，當 x1∈[0,c1-1]，xi∈[0,g-1](i ∈[2,m])時，因為x1＜c1，根據(jù)條件(2)得知p＜q，這種情況下 X的數(shù)量固定 x1= c1，考慮 x2的取值，當 x2∈[0,c2-1]，xi∈ [ 0,g- 1 ](i∈[ 3,m])時，因為x1=c1且x2＜c2，由條件(2)得知 p＜q，這種情況下 X 的數(shù)量依次可得顯然Nm=0。上述推導過程中各個Ni之間沒有重疊部分且涵蓋X所有可能取值，所以滿足條件的X數(shù)量為則C在等勢面中的順序為N+1，即

結合式(2)和式(10)得格點 C = (c1, c2,… ,cm)在對角線空間填充曲線中的訪問順序為

等勢面中格點元素數(shù)量表可離線構造，函數(shù) f值通過查表獲得，根據(jù)式（11）在O(mg)時間內(nèi)可得到格點C在對角線空間填充曲線中的訪問順序。

5 短路徑優(yōu)先的覆蓋網(wǎng)絡構建

5.1 傳輸路徑對傳輸效率的影響

P2P系統(tǒng)中，覆蓋網(wǎng)絡與物理網(wǎng)絡的拓撲匹配程度對消息的傳輸效率有重要影響。兩者不相匹配導致消息傳輸效率低下，例如當北京大學的節(jié)點發(fā)送消息到清華大學的節(jié)點經(jīng)過斯坦福大學中的節(jié)點中繼時，會極大增加傳輸延遲。短路徑優(yōu)先策略使得節(jié)點在2個網(wǎng)絡中的相對位置盡量一致。圖4展示了采用短路徑建立覆蓋網(wǎng)絡的優(yōu)勢。圖4(a)顯示的是原始物理網(wǎng)絡拓撲結構，假設每條鏈路的傳輸延遲為單位1，圖4(b)、圖4(c)分別展示2種不同結構的覆蓋網(wǎng)絡，其中圖4(b)采用短路徑將節(jié)點連接在一起。當節(jié)點1有單位消息發(fā)送到其他3個節(jié)點時，圖4 (b)中拓撲僅需要3個單位的時間，每條物理鏈路上僅通過一次消息；圖4(c)中拓撲則需要6個單位時間，其中鏈路l23上通過3次消息，鏈路l34上通過2次消息。

圖4 不同覆蓋網(wǎng)絡對消息傳輸?shù)挠绊?/p>

5.2 覆蓋網(wǎng)絡構建過程

本節(jié)綜合運用網(wǎng)絡距離估計技術和空間填充曲線技術，采用短路徑優(yōu)先覆蓋（SPF-overlay,shorter path first overlay）的策略構建拓撲匹配的網(wǎng)絡。使用基于被動路標的網(wǎng)絡距離估計技術估算節(jié)點之間的傳輸延遲，在空間填充曲線技術的輔助下，快速選擇距離最近節(jié)點與之建立鄰居關系。下面詳細描述其過程。

1) 生成、存儲網(wǎng)絡坐標

普通節(jié)點P測量到路標的網(wǎng)絡距離獲取自身網(wǎng)絡坐標Cp。如果直接對Cp進行空間填充曲線映射（假設Cp中元素均為整數(shù)），由于Cp變化范圍較大，像點稀疏地分布在巨大數(shù)值空間中，給快速檢索帶來困難。因此對Cp中元素進行量化處理，采用具有g個量化等級的非均勻量化方法，前g-1個等級的量化步長為t ms，最后一個量化等級的量化步長為+∞大，這樣Cp中元素ci的量化值為ri=min{cimod t,g-1}。將量化后的坐標值進行對角線SFC映射得到像點fp。節(jié)點p將網(wǎng)絡坐標Cp、fp以及通信地址發(fā)送至中心匯聚節(jié)點RP。匯聚節(jié)點RP以fp為索引存儲網(wǎng)絡坐標Cp及其通信地址。為提高查找速度，存儲采用如下策略：如果SFC值域空間D大小低于閾值W，則使用哈希鏈表存儲節(jié)點記錄；否則值域空間D等分為S個不同的子空間，fp屬于子空間i則將節(jié)點記錄存儲在子集合si中。閾值W大小取決于匯聚節(jié)點可用存儲空間大小。

2) 快速篩選臨近節(jié)點

節(jié)點 p需要獲取臨近節(jié)點信息建立鄰居關系時，向匯聚節(jié)點RP發(fā)送請求信息。請求中包括節(jié)點p的網(wǎng)絡坐標映射值fp以及要求的鄰居節(jié)點數(shù)量k。匯聚節(jié)點RP查找與節(jié)點p臨近的一組節(jié)點（例如 2k），并通告給節(jié)點 p。查找臨近節(jié)點策略與存儲策略相對應。當采用散列鏈表存儲節(jié)點記錄時，匯聚節(jié)點在以節(jié)點p的映射值fp為中心，半徑依次增大的超立方體中尋找臨近節(jié)點。圖5顯示了在二維空間的搜索過程，RP首先在節(jié)點 p所處的格點中查找有無臨近節(jié)點，然后查找半徑d=1的所有格點，依次擴大搜索范圍，直至發(fā)現(xiàn)所需數(shù)量的臨近節(jié)點。當采用子集策略存儲節(jié)點記錄時，根據(jù)fp確定其所屬子集si，然后以子集si為中心，在左右延伸的子集中尋找足夠數(shù)量臨近節(jié)點。

圖5 二維空間中臨近節(jié)點搜索過程

3) 計算確定最近節(jié)點集合

匯聚節(jié)點只是對臨近節(jié)點進行粗糙篩選，節(jié)點p通過距離函數(shù)獲得更準確的信息。節(jié)點p使用網(wǎng)絡距離公式計算到臨近節(jié)點的距離，選擇距離最近的k個節(jié)點與之建立鄰居關系，其余節(jié)點作為候選鄰居節(jié)點。

4) 建立鄰居關系

節(jié)點p向距離最近的k個節(jié)點發(fā)送建立連接請求，如果臨近節(jié)點能夠接納新的連接則響應請求，并在鄰居列表中添加新的記錄；否則拒絕。如果被接受，節(jié)點p增加新的鄰居記錄；否則從候選節(jié)點中選擇新節(jié)點請求與之建立鄰居關系，直至鄰居節(jié)點的數(shù)量達到要求。

5.3 覆蓋網(wǎng)絡構造協(xié)議的其他部分

覆蓋網(wǎng)絡連通性保證：分布式方式建立鄰居關系，不能保證建立的覆蓋網(wǎng)絡是連通的；同時節(jié)點根據(jù)網(wǎng)絡狀況調(diào)整鄰居關系也有可能導致覆蓋網(wǎng)絡的分裂，因此需要一定的機制來保證網(wǎng)絡的連通性。采用如下的連通性保證機制：根節(jié)點周期性向外廣播連通性報文，報文序號標識報文的新舊。節(jié)點接收到連通性報文后，對比記錄中的序號，如果新接收的報文序號大于記錄中的序號，則將報文轉發(fā)給鄰居節(jié)點，并且更新記錄中的序號和時戳，否則不采取任何動作。節(jié)點在一定時間間隔內(nèi)沒有更新連通性報文序號，則假定覆蓋網(wǎng)絡已經(jīng)形成網(wǎng)絡孤島，節(jié)點以一定概率建立新的連接。采用上述保證機制，在每個周期內(nèi)節(jié)點接收和發(fā)送的報文數(shù)量是其鄰居數(shù)量的2倍，對系統(tǒng)影響可以忽略。

局部動態(tài)優(yōu)化：節(jié)點加入覆蓋網(wǎng)絡后動態(tài)調(diào)整鄰居關系以適應網(wǎng)絡的變化。鄰居節(jié)點相互交換臨近節(jié)點列表以選擇更近的鄰居節(jié)點。節(jié)點將鄰居節(jié)點的數(shù)量限制在k～2k之間，當發(fā)現(xiàn)更近節(jié)點或鄰居數(shù)量不夠時嘗試建立新的鄰居關系；當網(wǎng)絡資源緊張或者鄰居節(jié)點不能為該連接提供足夠資源（包括鄰居節(jié)點失效）時，則剔除部分鄰居關系。

節(jié)點退出系統(tǒng)：P2P系統(tǒng)一個重要特性是節(jié)點的不穩(wěn)定性。節(jié)點退出系統(tǒng)時，向鄰居節(jié)點和匯聚節(jié)點發(fā)送退出消息。匯聚節(jié)點收到退出消息后刪除該節(jié)點對應的記錄。鄰居節(jié)點收到退出消息后，檢查該節(jié)點是否在臨近節(jié)點列表中，如果在則刪除相關記錄并將退出消息轉發(fā)給鄰居節(jié)點以刪除鄰居節(jié)點緩存的信息。節(jié)點退出使得鄰居節(jié)點連接數(shù)量減少，可能觸發(fā)建立新的鄰居關系。節(jié)點被動失效（如強行殺死進程、網(wǎng)絡斷掉）在交換內(nèi)容消息時檢測，節(jié)點一旦發(fā)現(xiàn)鄰居節(jié)點失效，向匯聚節(jié)點通告，在刪除本地對應記錄同時通告其他鄰居節(jié)點。

更新節(jié)點網(wǎng)絡坐標：節(jié)點周期性測量到路標的網(wǎng)絡延遲重新計算其網(wǎng)絡坐標，如果新、舊網(wǎng)絡坐標之間的距離超過門限值則需要更新網(wǎng)絡坐標，并將新的網(wǎng)絡坐標通告匯聚節(jié)點和鄰居節(jié)點。網(wǎng)絡坐標關聯(lián)一個順序號，每更新一次順序號遞增，這樣不會因網(wǎng)絡延遲等原因混淆。

路標失效的處理：網(wǎng)絡擁塞或者路標失效導致無法測得到路標的網(wǎng)絡延遲，其網(wǎng)絡坐標中對應的元素值為 0。對網(wǎng)絡坐標中的零元素進行量化時，假定節(jié)點在該維度上與所有其他節(jié)點都是臨近的，即零元素的量化值分布在每個量化等級上，相當于將節(jié)點復制g份（g為量化等級）。

6 實驗分析

本節(jié)通過模擬實驗驗證方案 SPF-overlay的有效性，旨在構建拓撲匹配的高質(zhì)量覆蓋網(wǎng)絡，減少消息傳播時間。本文引入匹配度來定量描述覆蓋網(wǎng)絡與底層物理網(wǎng)絡的拓撲匹配程度。稱覆蓋網(wǎng)絡中路徑為實際路徑，稱物理網(wǎng)絡中的最短路徑為理想路徑。下面給出路徑匹配度和拓撲匹配度的定義。

路徑匹配度：覆蓋網(wǎng)絡中不相鄰的2個節(jié)點理想路徑與實際路徑長度的比率。

拓撲匹配度：覆蓋網(wǎng)絡中所有不相鄰節(jié)點之間路徑匹配度的均值。

在上述定義中沒有考慮覆蓋網(wǎng)絡中直接相連節(jié)點之間的匹配度，因為其路徑匹配度為常數(shù) 1，不能體現(xiàn)覆蓋網(wǎng)絡與物理網(wǎng)絡的匹配程度。

6.1 實驗設置

在討論拓撲匹配時使用如下的網(wǎng)絡模型：物理網(wǎng)絡由路由器節(jié)點相互連接構成，端節(jié)點粘貼在與其相連的路由器節(jié)點上，到對應路由器的網(wǎng)絡距離忽略不計，物理網(wǎng)絡與覆蓋網(wǎng)絡均采用最短路徑路由策略。

本文采用文獻[14]的方法生成具有10 000個路由器節(jié)點的物理網(wǎng)絡拓撲。覆蓋網(wǎng)絡節(jié)點規(guī)模變化范圍為1 000～5 000，默認數(shù)量為2 000。覆蓋網(wǎng)絡中節(jié)點的鄰居數(shù)量k取值范圍為4～10。PLNDP中路標節(jié)點數(shù)量為10，在路由器節(jié)點中隨機選取。實驗中比較4種不同的覆蓋網(wǎng)絡構造方案：①最短路徑方案，這是一種集中式的算法，每個節(jié)點測量到其他所有節(jié)點的距離，然后選擇距離最近的k個節(jié)點作為鄰居，同時保證整個覆蓋網(wǎng)絡的連通性，下文中以“best”標識。②SPF-overlay方案，每個節(jié)點按照5.2節(jié)中介紹的過程分布式加入到覆蓋網(wǎng)絡中。網(wǎng)絡坐標的量化等級設為 5，使用散列鏈表存儲節(jié)點記錄，在半徑依次增大的超立方體中尋找最近節(jié)點。覆蓋網(wǎng)絡構造完成后繼續(xù)進行局部動態(tài)優(yōu)化操作，本文初衷是直接構造高質(zhì)量的覆蓋網(wǎng)絡，因此實驗中僅驗證 SPF-overlay方案中初始構造的覆蓋網(wǎng)絡的質(zhì)量，下文中以“SPF”標識；③隨機的覆蓋網(wǎng)絡構造方案，節(jié)點隨機地選擇 個節(jié)點作為鄰居節(jié)點，下文中以“rand”標識；④LTM方案，在隨機覆蓋網(wǎng)絡的基礎上進行LTM中的優(yōu)化操作，下文中以“LTM”標識。LTM方案中迭代的最大次數(shù)為200次，迭代終止條件為在一次迭代過程中優(yōu)化的連接數(shù)量小于整個覆蓋網(wǎng)絡連接數(shù)量的萬分之一。一次迭代過程指所有節(jié)點都向外泛洪一次探測報文并優(yōu)化連接。LTM中剪枝的截止系數(shù)設為1.6，也就是長邊長度至少是短邊的1.6倍時才被剪除；加邊的截止系數(shù)設為1.3，也就是增加的連接的長度最多不能超過現(xiàn)有相關連接的1.3倍。模擬實驗的硬件環(huán)境為普通桌面PC機，3.0GHz Pentium 4 CPU，2GB內(nèi)存，模擬軟件采用MATLAB 7.0。

6.2 實驗結果

圖6顯示了4種不同覆蓋網(wǎng)絡單跳邏輯連接長度的分布，可以看出best和SPF方案形成的覆蓋網(wǎng)絡中邊的長度比較集中且明顯比 LTM 和 rand方案中短。best方案較SPF方案優(yōu)勢更為明顯，但是 best方案中節(jié)點需要獲知全局網(wǎng)絡狀態(tài)信息，可擴展性差，網(wǎng)絡規(guī)模受到限制。LTM在迭代過程中每個節(jié)點平均調(diào)整 6.4條邏輯連接，其中平均增加邏輯連接 3.6條，剪除邏輯連接 2.8條（增加的邏輯連接比剪除的多是因為程序中放松了對節(jié)點度的限制）。圖7顯示了4種不同方案中節(jié)點之間邏輯路徑長度的累積分布，best方案中邏輯路徑平均長度最小且路徑長度分布范圍集中。SPF方案中路徑長度分布相對分散，不如其余三者集中，主要原因是選擇鄰居節(jié)點時由于預測誤差導致選取遠距離的節(jié)點。但是相比LTM和rand方案還是具有優(yōu)勢，特別是短路徑所占比例明顯高于后兩者。例如SPF中路徑長度小于500的占所有路徑數(shù)量的57.2%，而LTM中為27.7%，rand中僅為10.5%。

圖6 邏輯連接長度的分布

圖7 邏輯路徑長度的累積分布

圖8顯示了路徑匹配度的分布，SPF的表現(xiàn)好于LTM和rand方案，特別是路徑匹配度小于0.25的路徑在SPF方案中所占比例極小，可以忽略。相反在 LTM 和 rand方案中大量路徑的匹配度小于0.25。4種方案的拓撲匹配度分別為0.616、0.438、0.366、0.306。

圖8 路徑匹配度的分布

圖9顯示了拓撲匹配度隨系統(tǒng)規(guī)模的變化，best和SPF方案中略微增長，而LTM和rand方案中稍微有所下降。這是因為在保持節(jié)點度不變的情況下，隨著系統(tǒng)規(guī)模的增大，SPF中找到臨近節(jié)點的可能性增大，而 LTM 中邏輯路徑的跳數(shù)增加，需要更多的迭代次數(shù)才能保持匹配度不變。SPF方案相比LTM具有更好的擴展性。

圖9 拓撲匹配度隨系統(tǒng)規(guī)模的變化

假設鄰居節(jié)點數(shù)量為 k。best方案需要獲取全局信息，其通信開銷O(n2)。SPF通信開銷由2個主要部分組成，①測量到路標的網(wǎng)絡延遲，路標的數(shù)量為常數(shù)，測量開銷O(n)；②獲取臨近節(jié)點信息并與鄰居節(jié)點建立邏輯連接，通信開銷為O(kn)。LTM是在隨機網(wǎng)絡基礎上做局部優(yōu)化，建立隨機網(wǎng)絡的通信開銷為O(kn)；局部優(yōu)化時測量到2跳范圍內(nèi)節(jié)點的網(wǎng)絡延遲，測量開銷取決于鄰居節(jié)點的數(shù)量和迭代次數(shù)。圖10顯示SPF和LTM方案在不同的網(wǎng)絡規(guī)模下需要的通信消息數(shù)量。SPF的通信開銷遠小于 LTM，但是 SPF方案在篩選臨近節(jié)點時需要一定的計算量。

圖10 額外通信開銷的比較

7 結束語

P2P應用中消息沿著覆蓋網(wǎng)絡中的peer節(jié)點中繼傳輸，如果覆蓋網(wǎng)絡與底層物理網(wǎng)絡拓撲不相匹配，不僅增大消息的傳播延時，而且增加主干網(wǎng)的網(wǎng)絡流量。因此構建拓撲匹配的覆蓋網(wǎng)絡是提高大規(guī)模P2P應用系統(tǒng)性能的關鍵因素之一。若有網(wǎng)絡拓撲信息的指導，節(jié)點在加入覆蓋網(wǎng)絡時會找到更好的鄰居節(jié)點。本文提出短路徑優(yōu)先的覆蓋網(wǎng)絡構建策略，主要工作包括以下3個方面：①提出基于被動路標的網(wǎng)絡距離預測算法，提供節(jié)點間較為準確的網(wǎng)絡拓撲信息；②提出基于查表的對角線空間填充曲線快速映射算法，解決快速提取具有相關拓撲信息節(jié)點的問題；③綜合網(wǎng)絡距離預測算法和空間填充曲線技術提出拓撲匹配的覆蓋網(wǎng)絡構造算法SPF-overlay。實驗結果表明SPF-overlay方法構造的覆蓋網(wǎng)絡比隨機網(wǎng)絡和 LTM 算法能夠更好的匹配底層物理網(wǎng)絡；同時本文以計算開銷代替網(wǎng)絡開銷，使得SPF-overlay的額外網(wǎng)絡負載開銷更小，具備良好的可擴展性，能夠提高大規(guī)模分布式系統(tǒng)的性能。

[1] LUA E, GRIFFIN T, PIAS M. On the accuracy of embeddings for internet coordinate systems[C]. Proc of IMC05[C]. USENIX Association Berkeley, CA, USA, 2005. 1-11.

[2] SAGAN H, Space Filling Curves[M]. Berlin: Sprubger, 1994.

[3] RATNASAMY S, HANDLE M, SHENKER S. Topologically-aware overlay construction and server selection[A]. Proc of INFOCOM 2002[C]. New York, USA, 2002.1190-1199.

[4] MARCEL W, RINALDI R. Efficient topologyaware overlay net-work[J]. ACM Computer Communication Review, 2003, 33(1):101-106.

[5] XU Z, TANG C, ZHANG Z. Building topology-aware overlays using global soft-state[A]. Proc of the 23rd International Conference on Distributed Computing Systems[C]. Washington, DC, USA, 2003. 500-508.

[6] REN S, GUO L, ZHANG X. SAT-match: a self-adaptive topology matching method to achieve low lookup latency in structured P2P overlay networks[A]. Proc of the 18th International Parallel and Distributed Processing Symposium(IPDPS'04)[C]. 2004. 83-91.

[7] RATNASAMY R, FRANCIS P, KARP R. A scalable content-addressable network[A]. Proc of SIGCOMM2001[C]. San Diego, CA, USA, 2001.161-172.

[8] SUN M, ZHANG Z. Quasi-chord: physical topology aware structured P2P network[A]. Proc of the 11th Joint Conference on Information Sciences[C]. Shenzhen, China, 2008.

[9] EUGENE T, ZHANG H. Predicting internet network distance with coordinates-based approaches[A]. Proc of INFOCOM2002[C]. New York, USA, 2002.170-179.

[10] STIUCA I, MORRUS R, BAKARISHNAN H. Chord: a scalable peer-to-peer lookup service for internet applications[A]. Proc of SIGCOMM 2001[C]. San Deigo, CA, USA, 2001.149-160.

[11] LIU Y, LIU X, ZHANG X. Location-aware topology matching in P2P systems[A]. Proc of Infocom2004[C]. Hong Kong, China, 2004.2220-2230.

[12] PEANO G. sur une courbe qui remplit toute une air plaine[J].Mathiematishe Annalen, 1981, 96(1): 157-160.

[13] HILBERT D. Ueber stetige abbildung einer linie auf ein flashenstuck[J]. Mathiematishe Annalen, 1981, 96(3): 459-460.

[14] ZEGURA E, CALVERT K, BHATTACHARJEE S. How to model an internetwork[A]. Proc of INFOCOM96[C]. San Francisco, CA, USA,1996. 594-602.