P2P覆蓋網中的聚類研究綜述

摘 要:首先對P2P覆蓋網中的聚類技術進行了分類，在此基礎上介紹了各種典型的聚類方法并進行了對比分析;最后指出了P2P覆蓋網中聚類技術的未來研究趨勢。

關鍵詞:對等網絡; 網絡聚類; 網絡簇結構; 覆蓋網; 網絡距離

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-0806-05

doi:10.3969/j.issn.1001-3695.2010.03.002

Survey on P2P overlay clustering technology research

ZHENG Li-ming1a，2， LI Xiao-dong1b， LI Xiao-yong2， SUN Wei-dong2

(1. a.Information Technology Teaching Researching Section， b.Research Section， Chengdu Commanding College of the CAPF， Chengdu 610213， China; 2. National Key Laboratory for Parallel Distributed Processing， School of Computer， National University of Defense Technology， Changsha 410073， China)

Abstract:Firstly， this paper reviewed the classification of the clustering methods in P2P overlay， and based on which， introduced and compared many typical methods. Lastly， reviewed the future research trends of clustering methods in P2P overlay.

Key words:P2P; network clustering; network community structure; overlay; network distance

對于網絡聚類的研究已經有較長的歷史，幾十年來，其重要性及與其他研究方向的交叉特性得到人們的肯定。聚類是數據挖掘、模式識別、分布式網絡等研究方向的重要研究內容之一。對等網絡(peer-to-peer network，P2P網絡)作為一種新興的計算機網絡結構，已經成為當前互聯網研究的熱點方向[1~5]。然而，隨著P2P技術的迅猛發展、需求與應用的不斷拓展、用戶數量的急劇增加以及交互方式的日益多樣化，P2P網絡本身及其所處的網絡環境均呈現出爆炸式的復雜性增長趨勢。面對這種情形，當前用于構造P2P系統的思想、方法和技術正面臨著嚴峻的挑戰，P2P網絡安全問題也愈加突出，急需從新的角度理解網絡的結構與網絡行為之間的關系，進而考慮改善網絡的行為，使之一方面能夠真實反映和正確利用網絡的結構特征，另一方面能夠更好地適應這種爆炸式的復雜性增長趨勢。

P2P覆蓋網是一種通過網絡節點自組織形成的并構建于物理網絡之上的分布式應用層網絡，是由節點和邏輯鏈路組成的一種虛擬的網絡。近年來對P2P覆蓋網的研究已經成為P2P領域的研究熱點之一。目前已涌現出一大批基于覆蓋網的應用，如Napster、Gnutella、OceanStore[6]、Kademlia[7]等文件共享系統;SplitStream[8]、PROMISE[9]、Bullet[10]等大型數據分發系統;基于分布式哈希表(DHT)的結構化P2P[1，4，5，11，12]應用以及內容分發網絡(CDN)等。上述應用利用基于拓撲感知的相關技術，如覆蓋網路由[13]、應用層組播[14，15]、拓撲聚合[16]、最近服務器選擇[17~19]、拓撲感知覆蓋網構建[19~21]等，均能夠顯著地提高性能，因此研究拓撲感知具有明顯的現實意義。P2P覆蓋網中聚類技術的研究則是研究拓撲感知技術的關鍵，性能優越的聚類方法能夠有效支撐覆蓋網路由、應用層組播、資源有效放置、感知拓撲構建等，極大地提高了P2P網絡的性能。因此，研究P2P覆蓋網中的聚類方法具有深遠的理論意義和現實應用價值。

1 P2P覆蓋網聚類方法分類

對等網絡作為當前計算機網絡中的重要研究領域，不僅P2P網絡中的節點規模龐大，而且網絡節點存在較大的異構性，如節點的地理位置、處理能力和網絡路徑等存在差異。在P2P網絡中，通常采用的聚類方式是通過研究網絡節點之間的距離來進行聚類，網絡距離是一種抽象概念，通常是指網絡延遲，一般以RTT(round-trip time)表示。根據所獲得的距離信息進行聚類，是一種常用的聚類研究思想。

從P2P網絡的特殊性出發，根據網絡距離信息獲取方式以及聚類策略的不同，可將P2P網絡中基于距離信息的聚類方法劃分為基于參考點的方法、基于網絡層協助的方法、基于等級模式的方法、基于網絡坐標的方法以及基于距離抽樣的方法五類。基于參考點的方法是指為了獲取節點之間的網絡距離信息，通過直接或間接地引入相關的輔助節點或服務器以支持距離獲取的方法;基于網絡坐標的方法是指利用對網絡節點進行數學空間建模，通過網絡坐標的形式定位坐標空間中的節點，并通過節點之間的坐標信息獲得網絡距離，并加以聚類的方法;基于距離抽樣的方法是指在已探測網絡距離的基礎上，通過距離抽樣的方式，利用一定的迭代搜索策略獲取鄰近節點，從而實現節點聚類的方法。整個P2P網絡中聚類方法的分類如圖1所示。

2 基于網絡距離的聚類方法

在P2P覆蓋網中，拓撲感知的目的在于降低覆蓋網的延遲伸展率(latency stretch，定義為在邏輯覆蓋網中節點間的延遲與在物理網絡中對應節點間的延遲之比)，從而需要可擴展地獲取底層物理網絡節點之間的延遲信息。可見，網絡距離是實現拓撲感知的基礎。利用相關的距離信息進行聚類是一種有效的重要的方式。對于距離較小的節點或者相對鄰近的節點可將其劃分于相應的簇中，此為基于網絡距離的聚類方法的根本出發點。對于網絡距離的研究，根據網絡距離值或者鄰近性等計算或獲得方式的不同，可將基于網絡距離的聚類方法分為基于參考點、基于網絡層協助、基于等級模式、基于網絡坐標以及基于距離抽樣五種聚類方法。

2.1 基于參考點的方法

基于參考點的方法是為了避免進行完全測量(即對所有節點之間距離的測量)，增強鄰近搜索的可擴展性，主動引入一些測量參考點用于收集測量信息。這些測量參考點主要包括地標(Landmark[22]、Beacon[23]、Tracer[24]、Lighthouse node[25]、index node[26]等)、中間路由器(intermediate routers，稱做Milestones[27])、內容分發網絡(CDN)中的副本服務器[19]等。這類方法一般利用測量參考點收集的信息，采用集中式的策略進行搜索。Guyton等人[28]為這類方法提供了經典的范例。假定N個地標分別為Bi(1≤i≤N)，任意一個服務器S的坐標表示為一個N元組(由Hotz定義):S=〈s1，s2，…，sN〉，表示si到第i個地標的距離(跳數);類似地定義一個客戶端C的坐標:C=〈c1，c2，…，cN〉。這樣，S與C之間的網絡距離表示為

avg(S，C)=(max(S，C)+min(S，C))/2

其中:max(S，C)、min(S，C)分別定義為min(s1+c1，…，sN+cN)和max(|s1-c1|，…，|sN-cN|)。

每個地標測量到每個服務器的距離，并且發送給三角測量服務器(triangulation server)。在搜集了每個地標的結果后，任意一個服務器S的坐標就已經確定。當客戶端C需要定位最近的服務器，每個地標測量到C的距離并發送給三角測量服務器。三角測量服務器依據avg函數值的大小將最近的服務器返回給C。

通過額外部署代理節點的方式以實現聚類(或距離估計)的典型方法有IDMaps[24]方法和Internet Iso-bar[29]方法。IDMaps通過tracer維護局部AS圖、利用HOPS服務器維護全局Internet虛擬拓撲圖;Internet Iso-bar通過monitor維護局部拓撲圖，并通過距離的相似性分簇。原理圖分別如圖2、3所示。

2002年Ratnasamy等人[19]引入裝箱(Binning)思想對網絡節點進行分簇，其分簇思想在于，首先選定一組參考節點，然后新加入節點探測至參考節點之間的距離，并根據探測距離值獲得簇號信息;對所有節點進行相同操作，并獲得所有節點的簇號信息，具有相同簇號的節點劃分于同一簇中。其具體分簇原理如圖4所示。

Beaconing使用少量的地標實現鄰近搜索，劃分簇結構。系統中的每個節點周期性地測量與地標之間的距離并反饋給地標，地標維護這些距離信息。欲加入系統的目標節點T測量與每個地標B之間的距離d并反饋給地標B，B將離它自己d±δ的節點返回給目標節點，并以此獲得多個結果。最后，對交集進行處理，找出K個最近鄰，從而實現分簇。其局限性在于TIV問題，是由于其破壞了歐式空間中的三角不等性原理。其原理示意圖如圖5所示。

惠普實驗室的Sharma等人2006年提出的Netvigator方法通過探測小數目的地標節點和中間路由器來檢測最近的節點。該方法的創新之處在于通過增加探測節點路徑上的milestones信息來避免如Binning等方法中的錯誤分簇(1 clustering，源于具有相同地標向量的節點為鄰近節點所致)問題，因此提高了局部網絡特征信息的精度。其檢測原理如圖6所示。

CRP是一種基于CDN重定向的相對網絡定位方法，并不關注準確的網絡拓撲信息，而是基于如下假設:若CDN中兩臺主機的請求經常被導向相同的鄰近服務器集合，則它們很可能相對比較鄰近，即位于相同簇中。CRP根據大規模內容分發網絡收集的重定向信息，計算節點的重定向向量(redirection vector);然后通過比較節點重定向向量之間的相似性來估計其鄰近性。其原理如圖7所示。其缺點在于查詢節點需要集中式處理節點重定向向量并且精確性在一定程度上依賴于副本服務器的實際位置。

綜上所述，各種基于測量參考點的方法對比如表1所示。

2.2 基于網絡坐標的方法

網絡坐標方法目前已成為距離預測技術研究的主流方法，它通過將網絡中的節點映射到一定的幾何空間中，利用坐標來定位網絡中的節點在幾何空間中的位置，并且根據節點的坐標信息來計算節點間的距離。利用坐標計算方式預測網絡距離的是2002年卡內基#8226;梅隆大學的Ng等人[22]提出的GNP方法。自從該方法提出以后，網絡坐標計算正式成為距離預測技術研究的熱點，從而也為網絡節點的精確聚類提供了可靠的依據。GNP將Internet建模為一定維度的幾何空間(圖8)，將網絡中的主機節點映射為歐氏空間中的點，通過絕對坐標計算方法來預測網絡距離。其坐標計算分為兩步:首先計算地標節點的坐標，然后依據地標節點的坐標和至地標的探測距離計算普通節點的坐標。坐標計算的實質為求解估計誤差與實際測量誤差的一般多維全局最小化問題，目前有很多方法可進行近似求解，GNP中利用simplex downhill方法[30]計算其坐標。GNP方法采用網絡坐標的方式預測距離，與非坐標預測方法相比，大大減少了探測的開銷以及實際部署開銷，預測精度也較高。然而，它也面臨著諸如集中式地標帶來的單點失效以及非線性計算開銷較大等問題。

表1 不同的基于參考點的聚類方法之間的對比

schemeinfrastructurerequiredpermissiblemetricaccuracyquerylatencycontroloverheads

triangulation-basedUnicast-only，deploymentof few beaconsanymoderatelowhigh

IDMapsUnicast-only，deploymentof some trackersanymoderatelowlow

Internet Iso-barUnicast-only，deploymentof a few monitorsanymoderatelowlow

BeaconingUnicast-only，deploymentof few beaconsanymoderatelowhigh

NetvigatorUnicast-only，deploymentof few milestonesanyhighlowhigh

CRPUnicast-only，existenceof CDNanyhighlowlow

與GNP不同，2003年韓國首爾國立大學的Lim等人[23]提出的ICS以及波士頓大學Tang等人[31]提出的虛擬地標(virtual landmark)方法采用相對坐標方法計算網絡坐標。在ICS和virtual landmarks中，普通節點首先獲得到地標節點的距離矩陣信息并以距離向量形式表示，向量的維度等于地標節點的數目;其次在基于Lipschiz嵌入的基礎上采用PCA(principle component analysis)技術來降低維度以提高計算效率。

Lipschiz嵌入是歐式嵌入的一種特殊類型，對于任意節點i的坐標向量xi∈Rn，則xi的第j個元素為i到地標j的距離。Lipschiz 嵌入的本質是以距離作為坐標的元素，其結果的精確性源于在度量空間中的兩個相近的節點具有到其他對象的相似距離[23]。此外，針對PIC提出的精度不一致性問題，2006年美國普渡大學的Zhang等人以及2007年南京大學Xing等人分別提出了Hierarchical method[32]和HNDP[33]方法。

Hierarchical method采用一種層次式方法利用多個地標集合計算多個坐標集，每一個坐標和地標集合對應不同的距離范圍。例如一個節點使用一個坐標來估計到遠節點的距離，而另一個坐標來估計到近節點的距離。如若發現一組坐標對近距離預測精確，而另一組對遠距離是精確的，則根據感興趣的范圍綜合選擇合適的坐標集合以最高的整體預測精度。HNDP提出另一種層次式的預測方法，它將Internet劃分成多個獨立的區域(如edge、core、region、dual等)，在各個區域內分別采用最近地標選擇策略計算坐標，最后節點間的預測距離通過累加不同區域內的距離得出。

最典型的是2006年賓夕法尼亞大學的Mao等人[34]提出的IDES方法，該方法通過采用SVD(singular value decomposition)和NMF(non-negative matrix factorization)兩種矩陣分解技術來建模子優化和非對稱路由策略;為每個節點賦予一個入向量和出向量，根據出向量和入向量的內積確定網絡距離。該方法擺脫了對稱性和三角不等性的約束，然而它假設距離矩陣中存在大量線性相關的向量，即利用分簇性原理，當出現錯誤分簇時，IDES的預測精度會明顯降低。

此外，不少研究人員還提出了一些模擬物理過程的坐標計算方法，如BBS(big-bang simulation)[35~37]、Vivaldi[38]、PCoord[39，40]等。BBS方法模擬了粒子在由于嵌入誤差所產生的力場中的爆炸行為，它將網絡中的所有節點視做一個粒子集合，粒子之間可能相互吸引或者排斥，可能由于力場的作用加速，也可能由于摩擦力作用而減速。Vivaldi方法則模擬了節點在嵌入誤差產生的彈簧力場作用下的運動過程，它假定任意兩個節點之間都存在一根彈簧，通過節點間彈力的作用來修正節點的坐標。PCoord方法則在坐標更新的過程中引入摩擦力機制來提高坐標的收斂速度，從而提高坐標的精確性和可用性。綜合以上各種基于網絡坐標的聚類方法，從方法對應的主要技術、地標分布性、分簇的精確性、計算開銷、TIV問題的解決以及安全性檢測方面歸納為表2。

表2 不同的網絡坐標聚類方法的對比

propertiesmaintechniquecentra-lizedembed-ding typeaccu-racyphysicalprocesscomputecostsolvingTIVsecu-rity

GNPabsolute coordinatesimplex downhillyesEuc-lideanmode-ratenobignoignore

ICSPCA and LipschizembeddingyesLip-schizmode-ratenosmallnoignore

virtuallandmarkPCA andLipschizyesLip-schizmode-ratenosmallnoignore

lighthouseGram-Schmidt，vector basetranslationyesEuc-lideanmode-ratenosmallnoignore

BBSsimulate particleexplosionnoEuclidean/Hyperbolicmode-rateyesmediumyesignore

VivaldiSimulate springforce field andpiggy-backcommunicationnoEuc-lidean/with highvectorhighyessmallyesignore

PICimprove GNP withdifferent landmarkselection strategiesnoEuc-lideanhighnosmallnocheck

PCoordactive exchangeinformation;sample weight，force of friction，Damping mechanismnoEuc-lideanmode-rateyesbignoignore

IDESmatrixfactorization:SVD and NMFnoEuc-lideanhighnosmallyesignore

Hierarchicalmethodmulti-coordinatesnoEuc-lideanhighnobignoignore

HNDPdivide Internetinto many diffe-rent regionsnoEuc-lideanmode-ratenobignoignore

2.3 基于距離抽樣的方法

基于距離抽樣的方法，通過隨機選取一些節點作為鄰居，并且根據距離遠近將其部署在某種數據結構中。采用鄰近搜索貪心策略，通過不斷追溯當前最近鄰的鄰居來發現更近的節點，直至結束。

Meridian[41]利用基于直接測量形成的松散結構的同心環狀覆蓋網結構，結合Gossip協議來交換節點間的信息，以迭代轉發查詢匹配信息的方式來定位最優的鄰近節點。從某種意義上說，Meridian設計了一種“小世界”，通過不斷追溯當前最近鄰的鄰居的貪心路由方式，以O(log N)的跳數尋找到最近鄰。盡管Meridian考慮了同心環成員多樣化的問題，仍然難以避免搜索過程陷入局部最優。其查詢原理如圖9所示，client節點向覆蓋網節點A發出請求，尋找目標節點T的最近鄰。A先探測與T的距離d，然后要求離自己(1-β)d→(1+β)d之間的環成員節點探測與T的距離，并反饋給A，查詢將轉發給當前最近鄰。

Mithos[42]在覆蓋網構造階段，新節點通過接觸bootstrap node得到自己的候選鄰居，然后獲取這些候選鄰居的直接鄰居，探測到所有這些鄰居的延遲以尋找更近的鄰居，同時作為新的候選鄰居。這個過程迭代進行，直至沒有進展。當然，上述過程容易陷入局部最優。Castro等人提出一種在Pastry中尋找鄰近種子節點(seed node)的分布式算法PNS-CG。它充分利用由Pastry節點維護的葉集和路由表，沿著路由表各層自底向上進行搜索，不斷向最近的節點逼近。這種方法不需要額外的維護開銷。

3 未來研究趨勢

P2P覆蓋網中的聚類方法，對于覆蓋網路由、應用層組播、拓撲聚合、最近服務器選擇、拓撲感知覆蓋網構建等P2P優化技術具有強烈的支撐作用，對提高P2P網絡的性能具有直接的、重大的理論意義和應用價值。本文從P2P覆蓋網中聚類方法的特殊性出發，從P2P網絡的角度探討P2P網絡中的聚類方法，將相關技術的優缺點進行對比并對于具體應用具體分析，是研究聚類方法的重點，也是計算機學科中P2P網絡研究中的關鍵技術。根據P2P覆蓋網的特殊性，利用P2P網絡專有的特點，根據P2P覆蓋網的相關度量屬性進行有效聚類是研究P2P覆蓋網的重點手段。目前P2P網絡中的聚類研究已取得了不小的進步，但是同樣存在不少需要解決的問題，主要包括如下幾個方面:

a)網絡嵌入模型的研究。Internet建模能對聚類提供有效支持，目前很多聚類方法都使用了相關的模型。然而，對Internet建模是一項復雜的任務，因為現實Internet環境中存在諸多如高度動態性[43]、網絡節點不可達性[44]以及TIV等特征。目前雖然已有歐式空間、雙曲空間以及Lee等人[45]提出的混合空間等嵌入模型用于P2P聚類的建模計算，但是這些模型均不能很精確地描述現實Internet的特征。因此，研究如何對Internet環境建模，尋找一種最優的空間模型是數學界和計算機界共同需要解決的問題。

b)高效穩定的聚類方法研究。由前面分析可知，要實現高效穩定的網絡聚類方法，需要考查技術的可擴展性、計算開銷、通信開銷、精確性、穩定性、收斂性、安全性等諸多方面。而與之密切相關的研究主要包括坐標類型選擇、計算過程模擬、分簇算法、現實部署性等。在網絡坐標計算方法中，采用非線性方法進行絕對坐標計算其收斂性好，但是開銷大;采用線性方法進行相對坐標計算其計算開銷小，卻需要節點的分簇性假設;采用模擬物理過程的方法如Vivaldi，其計算和通信開銷小，但是收斂速度慢且不能保證能夠收斂到穩定狀態，不便于實際應用。在基于參考點的方法中，代理節點或者服務器節點部署的數目、方式以及開銷等現實部署性問題，以及尋找最優的分簇算法仍然值得深究。

c)安全性方面的研究。安全性方面的研究主要針對于基于網絡坐標的聚類方法，當前許多對網絡坐標安全性的研究[46~50]表明，網絡坐標系統在面對實際Internet時是很脆弱的，極易遭受來自各方面的攻擊。網絡的動態性和異構性等復雜特征使得惡意節點的攻擊形式多樣化，使得對網絡坐標安全性的研究是極其復雜。為此Kaafar等人[46，48，49]在最近幾年內進行了嘗試，他們將惡意節點的攻擊分為擾亂(disorder)、隔離(isolation)、排斥(repulsion)、系統控制(system control)四種情形來考察坐標系統的安全性，并提出利用檢查員基礎設施(surveyor infrastructure)來檢測惡意節點的行為，此方法在一定程度上增強了坐標系統的安全性。然而，安全性研究目前還處在研究的初級階段，由于坐標安全性研究的復雜性和必要性，決定了對此方面的研究將是一個長期的過程。

4 結束語

P2P網絡中的聚類技術研究作為P2P網絡中新興的熱點研究領域，是一個融合了復雜系統、計算機、數學、物理學、生物學、社會學等多個學科的技術研究。從整體上講，目前在P2P網絡中的聚類技術研究還不夠成熟，尚未建立起一套完整的理論體系和方法體系，而且從技術理論的完善到真正聚類系統可靠的部署應用還距離甚遠。本文回顧了當前學術界在P2P網絡中聚類技術研究領域的主要研究成果，從P2P網絡自身的特殊性方面介紹了P2P網絡中的聚類技術研究的多種方法和關鍵技術，在分類的基礎上分析比較了各種具有代表性的聚類方法，最后指出了未來研究的趨勢。

參考文獻:

[1]ROWSTRON A，DRUSCHEL P. Pastry:scalable，distributed object location and routing for large-scale peer-to-peer systems[C]//Proc ofthe 18th IFIP/ACM International Conference on Distributed Systems Platforms. 2001.

[2]CLARKE I，SANDBERG O，WILEY B，et al. Freenet: a distributed anonymous information storage and retrieval system[C]//Proc of Workshop on Design Issues in Anonymity and Unobservability. 2001:339-344.

[3]KNUTSSON B， LU Hong-hui， XU Wei，et al. Peer-to-peer support for massively multiplayer games[C]//Proc of the 23rd Annual Conference on Computer and Communications Societies. 2004:34-44.

[4]STOICA I， MORRIS R， LIBEN-NOWELL D，et al. Chord: a scalable peer-to-peer lookup protocolfor Internet applications[J]. IEEE/ACM Trans on Networking， 2003，11(1):17-32.

[5]RATNASAMY S， FRANCIS P， HANDLEY EA M. A scalable content-addressable network[C]//Proc of Conference on Applications， Technologies，Architectures，and Protocols for Computer Communication. New York: ACM Press， 2001:149-160.

[6]KUBIATOWICZ J， WEIMER W， WELLS C， et al. OceanStore: an architecture for global-scale persistent storage[J]. ACM SIGPLAN Notices， 2000，35(11):190-201.

[7]MAYMOUNKOV P， MAZIERES D. Kademlia:a peer-to-peer information system based on the XOR metric[C]//Proc ofIPTPS. 2002:53-65.

[8]CASTRO M， DRUSCHEL P， KERMARREC A M， et al. SplitStream: high-bandwidth content distribution in a cooperative environment[C]//Proc of IPTPS. 2003:298-313.

[9]HEFEEDA M， HABIB A， BOTEV B，et al. PROMISE: peer-to-peer media streaming using CollectCast[C]//Proc of the 11th ACM International Conference on Multimedia.2003:45-54.

[10]KOSTIC D， RODRIGUEZ A， ALBRECHT J，et al. Bullet: high bandwidth data dissemination using an overlay mesh[J]. ACM SIGOPS Operating Systems Review， 2003，37(5):282-297.

[11]ZHAO B Y， HUANG Ling， STRIBLING J，et al. Tapestry: a resilient global-scale overlay for service deployment[J]. IEEE Journal on Selected Areas in Communications， 2004，22(1):41-53.

[12]MALKHI D， NAOR M， RATAJCZAK D. Viceroy:a scalable and dynamic emulation of the butterfly[C]//Proc of the 21st ACM Sympo-sium on Principles of Distributed Computing. 2002:183-192.

[13]REWASKAR S， KAUR J. Testing the scalability of overlay routing infrastructures[C]//Proc of the 5th Workshop on Passive and Active Network Measurement. 2004:33-42.

[14]CHU Yang-hua， RAO S G， SESHAN S， et al. A case for end system multicast[J]. IEEE Journal on Selected Areas in Communications，2002，20(8):1456-1471.

[15]LIEBEHERR J， NAHAS M， SI Wei-sheng. Application-layer multicasting with delaunay triangulation overlays[J]. IEEE Journal on Selected Areas in Communications， 2002，20(8):1472-1488.

[16]AWERBUCH B， SHAVITT Y. Topology aggregation for directed graphs[J]. IEEE/ACM Trans on Networking， 2001，9(1):82-90.

[17]JAMIN S， JIN Cheng， KURC A R，et al. Constrained mirror placement on the Internet[C]//Proc of the 20th Annual Joint Conference on IEEE Computer and Communications Societies. 2001:31-40.

[18]THEILMANN W， ROTHERMEL K. Dynamic distance maps of the Internet[C]//Proc of the 19th International Conference on IEEE Computer and Communications Societies. 2000:275-284.

[19]RATNASAMY S， HANDLEY M， KARP R，et al. Topologically-aware overlay construction and server selection[C]//Proc of the 21st International Conference on IEEE Computer and Communications Societies. 2002.

[20]WINTER R， ZAHN T， SCHILLER J. Topology-aware overlay construction in dynamic networks[C]//Proc of IEEE International Conference on Networking. 2004.

[21]WANG Wen-jie， JIN Cheng， JAMIN S. Network overlay construction under limited end-to-end reachability[C]//Proc of the 24th International Conference on IEEE Computer and Communications Societies. 2005:2124-2134.

[22]NG T S， ZHANG Hui. Predicting internet network distance with coordinates-based approaches[C]//Proc of the 21st International Conference on IEEE Computer and Communications Societies. 2002:170-179.

[23]LIM H， HOU J C， CHOI C H. Constructing Internet coordinate system based on delay measurement[C]//Proc of ACM SIGCOMM Conference on Internet Measurement. 2003:129-142.

[24]FRANCIS P， JAMIN S， JIN Cheng， et al. IDMaps: a global Internet host distance estimation service[J]. IEEE/ACM Trans on Networking， 2001，9(5):525-540.

[25]PIAS M， CROWCROFT J， WILBUR S，et al. Lighthouses for scalable distributed location[C]//Proc of the 2nd International Conference on P2P System. 2003:278-291.

[26]NG T S， ZHANG Hui. A network positioning system for the Internet[C]//Proc of USENIX Annual Technical Conference. 2004:11.

[27]SHARMA P， XU Zhi-chen， BANERJEE S，et al. Estimating network proximity and latency[J]. ACM SIGCOMM Computer Communication Review， 2006，36(3):39-50.

[28]GUYTON J D， SCHWARTZ M F. Locating nearby copies of replicated Internet servers[J]. ACM SIGCOMM Computer Communication Review， 1995，25(4):288-298.

[29]CHEN Yan， LIM K H， KATZ R H，et al. On the stability of network distance estimation[J]. ACM SIGMETRICS Performance Eva-luation Review， 2002，30(2):21-30.

[30]NELDER J A， MEAD R. A simplex method for function minimization[J]. The Computer Journal， 1965，7(4): 308-313.

[31]TANG Li-ying， CROVELLA M. Virtual landmarks for the Internet[C]//Proc of the 3rd ACM SIGCOMM Conference on Internet Mea-surement. New York:ACM Press， 2003:143-152.

[32]ZHANG Rong-mei， HU C， LIN Xiao-jun，et al. A hierarchical approach to Internet distance prediction[C]//Proc of the 26th IEEE Conference on Distributed Computing Systems. 2006:73.

[33]XING Chang-you， CHEN Ming. HNDP: a novel network distance prediction mechanism[C]//Proc of the 27th IEEE Conference on Distributed Computing Systems. 2007.

[34]MAO Y， SAUL L K， SMITH J M. IDES:an Internet distance estimation service for large networks[J]. IEEE Journal on Selected Areas in Communications， 2006，24(12):2273-2284.

[35]SHAVITT Y， TANKEL T. Big-bang simulation for embedding network distances in Euclidean space[J]. IEEE/ACM Trans on Networking， 2004，12(6):993-1006.

[36]SHAVITT Y， TANKEL T. On the curvature of the Internet and its usage for overlay construction and distance estimation[C]//Proc of the 23rd International Conference on IEEE Computer and Communications Societies. 2004:384.

[37]SHAVITT Y， TANKEL T. On Internet embedding in hyperbolic spaces for overlay construction and distance estimation[EB/OL]. (2005). http://www.eng.tau.ac.il~tankel/pub/HypEmp05v2.pdf.

[38]DABEK F， COX R， KAASHOEK F，et al. Vivaldi: a decentralized network coordinate system[C]//Proc of Conference on Applications，Technologies，Arichitectures，and Protocols for Computer Communications. 2004:15-26.

[39]LEHMAN L， LERMAN S. PCoord: network position estimation using peer-to-peer measurements[C]//Proc of the 3rd IEEE International Symposium on Network Computing and Applications. 2004: 15-24.

[40]LEHMAN L， LERMAN S. A decentralized network coordinate system for robust Internet distance[C]//Proc of the 3rd International Confe-rence on Information Technology:New Generations. 2006.

[41]WONG B， SLIVKINS A， SIRER E G. Meridian: a lightweight network location service without virtual coordinates[C]//Proc of Confe-rence on Applications，Technologies，Arichitectures，and Protocols for Computer Communications. 2005:85-96.

[42]WALDVOGEL M， RINALDI R. Efficient topology-aware overlay network[J]. ACM SIGCOMM Computer Communication Review， 2003，33(1):101-106.

[43]STUTZBACH D， REJAIE R. Capturing accurate snapshots of the Gnutella network[C]//Proc of the 24th International Conference on IEEE Computer and Communications Societies. 2005:127-132.

[44]STUTZBACH D R R. Characterizing today’s Gutella topology， CIS-TR-04-02[R].Eagene: University or Oregon， 2004.

[45]LEE S， ZHANG Zhi-li， SAHU S，et al. On suitability of Euclidean embedding of internet hosts[C]//Proc of the Joint International Conference on Measurement and Modeling of Computer Systems. New York:ACM Press， 2006:157-168.

[46]KAAFAR M A， MATHY L， TURLETTI T，et al. Real attacks on virtual networks: vivaldi out of tune[C]//Proc of SIGCOMM Workshop on Large-Scale Attack Defense. 2006:139-146.

[47]LEDLIE J， GARDNER P， SELTZER M. Network coordinates in the wild[C]//Proc of USENIX NSDI. 2007.

[48]KAAFAR M A， MATHY L， BARAKAT C，et al. Securing Internet coordinate system:embedding phase[C]//Proc of Conference on Applications，Technologyies， Arichitectures，and Protocols for Computer Communications. 2007:61-72.

[49]KAAFAR M A， MATHY L， TURLETTI T，et al. Virtual networks under attack: disrupting Internet coordinate systems[C]//Proc of ACM CoNEXT Conference.New York:ACM Press， 2006.

[50]COSTA M， CASTRO M， ROWSTRON R， et al. PIC: practical Internet coordinates for distance estimation[C]//Proc ofthe 24th International Conference on Distributed Computing Systems. 2004:178-187.