基于Ｐ２Ｐ的自組織網絡路由算法研究

(1.電子科技大學計算機科學與工程學院，成都 610054; 2. Dept. of Mathematics Computer Sciences， Eindhoven University of Technology， Eindhoven， the Netherlands)

摘 要：

針對傳統的P2P采用泛洪的信息傳輸方式，網絡帶寬開銷耗費較大，而結構化P2P覆蓋網又難以在開銷和效率方面做到較好的權衡。根據網絡的動態性，有效地建立起一個可分層的樹型自治系統，詳細描述了該系統的構建目標和體系結構，并基于P2P計算模式動態構建該模型，給出相應的路由發現和更新算法。在理論及仿真實驗的基礎上對該路由模型的性能進行了驗證。結果表明，該網絡是一種可運行于任何環境，不受限于系統規模大小、節點能力強弱、節點出入頻率，可通過動態調節保證路由效率的廣域分布式系統。

關鍵詞：對等網絡; 網絡結構;動態性;路由算法

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

文章編號：10013695(2009)01030605

New selforganizing P2P network and routing algorithm

YE Jianhong1，2， SUN Shixin1， ZHANG Yunsheng1， ZHOU Yimin1

(1. School of Computer Science Engineering， University of Electronic Science Technology of China，Chengdu 610054，China; 2. Dept. of Mathematics Computer Sciences， Eindhoven University of Technology， Eindhoven， the Netherlands)

Abstract:In traditional P2P nets，the flooding transmission isaccompanied with greatness communication cost. Structured overlay P2P network is also hard to balance expense and efficiency. This paper presented a hierarchical selforganizing dynamic network， described the target and architecture of this model， as well as a detailed description of the P2P decentralized compute model， route discovering and updating algorithm. Theory analysis and simulation results testify the performance of the network， which shows it is a general structure overlay network that can be deployed in any environments， not matter what the system size is， how dynamic the nodes are， and what the nodecapacity distribution is like.

Key words：P2P (peer to peer); structured network; dynamic; routing algorithm



0 引言

P2P節點系統[1，2]以飛快的速度發展為Internet中最重要的應用系統之一，其體系結構也逐步演變為由Napster的集中查詢向Kazaa的偏向強節點的自由連接。由于自由連接的隨意性，數據查詢必須依靠廣播(flooding)來完成，其耗費了大量的網絡帶寬資源，系統的可擴展性受到嚴重限制。近年來，關于結構化覆蓋網(structured overlay network，SON)的分布式哈希表(distributed hash table，DHT)算法研究成為熱點。已有的結構化覆蓋網路由算法分為兩類。第一類算法中每個節點只記錄一小部分其他節點的指針，算法保證消息路由在一定的跳數內完成。以Pastry[3]為例，典型的Pastry的消息路由在logN2b跳數內完成(其中：N為總節點數；b為系統常數)。這類算法的特點是系統開銷小，且相對于非結構化覆蓋網(unstructured overlay network)，路由效率有大幅度提高；但與節點之間直接消息通信相比，仍然較慢。第二類算法中每個節點記錄所有其他節點的指針，使得絕大多數(99%以上)消息通信可以直接完成。該算法的路由效率非常高，但存在帶寬要求大、可擴展性差、啟動時間長等缺點[4]。這些算法均沒有考慮網絡實際拓撲結構，因而即使是鄰近的兩個節點仍有可能因為雜湊(hashing)的結果，必須經過很長的搜尋路徑才能取得數據，降低了路由的效率[5]。 

本文將SON的P2P路由技術和自組織網絡路由技術研究有效地結合，提出分級集中式自組織網絡模型。該模型是一個基于Internet拓撲架構和P2P計算模式的自組織網絡，構建該模型的目的是為了搭建一個應用于廣域網絡(WAN)的高性能、高可用、負載均衡、動態的自組織網絡平臺。該平臺位于應用層，通過在Internet物理拓撲基礎上建立一層基于P2P覆蓋網絡的虛擬拓撲結構，并在其上使用基于P2P計算模式的路由協議，有效地建立起一個具有完全分布式結構的自組織網絡路由模型。與已有模型相比，新的模型通過動態分層保證了節點維護路由表的開銷總在可承受的范圍之內，并獲得了比結構化覆蓋網的兩類路由算法更高的效率。同時，該模型與CDN(content delivery network)技術融合，還可以在效率及硬件開銷方面取得較好的平衡。限于篇幅，這方面的研究將在另文中加以闡述。

1 基于P2P的自組織網絡

1. 1 基本定義

為了簡化敘述，假令系統內一定存有需要的路由節點、無法搜索到的節點，很容易設定時限閾值。該假設不影響整個網絡的構建。以下給出描述系統結構所需的幾個定義:

定義1 系統中拓撲結構呈現樹型結構的用戶機(peer)的集合稱為一個自治系統(autonomyarea)。

定義2 自治系統中用戶機分為超級節點(super peer)、副主節點(slave peer)和普通節點(common peer)三個身份級別。每個節點的身份級別并不惟一。

定義3 一個超級節點與隸屬于它的一個副主節點和若干普通節點構成自治系統中的地區區域(local area)。

定義4 每個節點具有若干個屬性，通過對它們進行均勻的哈希算法SHA1[6]，賦予每個節點一個惟一標志NodeID(NodeID長128 bit)。

1. 2 架構設計

鑒于描述上的完整性，本文給出了基于P2P的自組織網絡與CDN相結合的一個完整的網絡邏輯結構（圖1）。本文只關注自治層，即基于P2P的自組織網絡，其他層次的描述將在另文中加以闡述。自治層由若干個自治系統構成，每一個自治系統由多個大小不等的地區所構成；每個地區只有兩層，父節點位于上層，子節點位于下層。

網絡構建初期，每個自治系統內只有第0層，隨著加入的用戶數量的逐漸增多，那些在線性能優良的普通節點將升級為超級節點或副主節點，并重新向下遞推構建新的層次。自治系統內的層次隨著節點數的多少而增減，這樣的拓撲結構符合局部性原理(small world)。

2 算法描述

基于低層網絡的動態性(測試Gnutella和Napster網絡表明，節點的平均在線時間是60 min[7])，一方面，在頻繁上下線的用戶間采用結構化的hash算法是不明智的，每一個節點的進出均將破壞算法的拓撲結構，頻繁的計算拓撲結構的開銷是驚人的，而且還應當考慮用戶帶寬的差異性；另一方面，完全的非中央集權式(decentralized)的網，如freenet，由于沒有中央服務器，在搜尋數據時是以flooding的方式將消息散布在網絡上，存在著消息泛濫的問題，也使得系統的可擴展性(scalability)無法提升。鑒于此，本文的自組織網絡采用類似于非結構化混合P2P模式的樹型路由方法。

21 自治系統內路由算法

與Pastry及Chord不同的是，自治系統中的每個節點均有級別(0，1，2…)屬性，以標志其強弱(0為最強，級別最高)，級別作為節點的基本屬性與IP、端口一起被記入指針。同時規定節點在自治系統中所處的層次以小為高，大為低。 

定義5 節點M的特征串為k+NodeID+IP+端口號+l。其中：NodeID為標志；k是節點的級別；l為節點的層次。節點M的特征串中，關鍵字是NodeID。

自治系統中的節點路由需維護兩個存儲結構，定義如下:

a)typedef struct{

char FatherNodeID;/*存放當前節點的父節點NodeID+IP+端口號+l*/

char BrotherNodeID;/*該節點的同父兄弟節點NodeID+IP+端口號*/

} OrdinaryRroutingTable;(普通路由表)



b)typedef struct{

char SonLowerSuperNodeID;/*層次為l的節點作為第l+1層的超級節點，它的子節點又作為第l+2層超級節點的NodeID，組成該項*/

char SonNodeID;/*由該節點所管轄地區中的子節點由k+NodeID+IP+端口號+l組成，對其長子節點的NodeID與其他子節點分開記錄*/

} SuperRoutingTable(超級路由表)



每個節點均需維護自身的普通路由表。如果該節點還是下一層的超級節點，則需額外維護超級路由表。這兩個存儲結構中除OrdinaryRroutingTable的FatherNodeID外，均采用二叉排序樹(binary sort tree)的存儲方式。

每個自治系統節點的數據結構如下定義:

typedef struct{

Element NodeID;

Element OrdinaryRroutingTable;

Element SuperRoutingTable;

} Node;



自治系統內路由算法(DynamicIRa)的詳細描述如下。該算法中的信息可有選擇地擴散，防止了信息的無限循環轉發）。

輸入:第l層級別為k的節點M對節點S的路由搜索;

輸出:節點S的NodeID。

Element RouteSearchTree(Node X，Node S)/*搜索以X為根的樹中路由*/

{if(SearchBST(X.SuperRoutingTable.Son-NodeID，S.NodeID)!=NULL)

return S.NodeID;

else for Every Ni=X.SuperRoutingTable.Son-LowerSuperNodeID， in Parallel do

RouteSearchTree(Ni，S);

until(Every Ni.SuperRoutingTable.Son-LowerSuperNodeID==NULL);

}

Element RouteSearchBrother(Node Y，Node S)

//搜索Y的兄弟節點中路由

{for Every Ri=Y.OrdinaryRroutingTable.Brother-NodeID，in Parallel do

if(Ri.SuperRoutingTable!=NULL)

RouteSearchTree(Ri，S);

Until (Every Ri Not Found S );

}

Element RouteSearchFather(Node Z，Node S)

//搜索Z的父親節點中路由

{A=Z.OrdinaryRroutingTable.Father-NodeID;

if(SearchBST(A.OrdinaryRroutingTable.Brother-NodeID，S.NodeID)!=NULL)

Return S.NodeID;

else do

{RouteSearchBrother(A，S);

A=A.OrdinaryRroutingTable.Father-NodeID;

}

until (A.OrdinaryRroutingTable.Father-NodeID is Proxy);

}

Element DynamicIra(Node M，Node S)

//節點M發起的對S的路由搜索

{if(SearchBST(A.OrdinaryRroutingTable，S.NodeID)!=NULL)

return S.NodeID;

else{RouteSearchTree(M，S);

RouteSearchBrother(M，S);

RouteSearchFather(M，S);

}

SendRouteRequest(M，S) to Proxy;/*將請求遞交給代理服務器，調用代理服務器的路由算法*/

}



搜索到的目的節點地址依原路，與發起節點M建立IP連接，算法結束。其中：SearchBST()表示調用二叉排序樹的查找算法;for …in Parallel do…until表示執行的一個并行算法直至約束條件成立。

最壞情況下DynamicIRa算法需遍歷該自治系統內所有非葉節點方可找到目的節點，故整個算法的時間復雜度為O（(num/β)×(1+logβ2)）=O((num/β)×logβ2)。其中:num為某個自治系統內的節點個數;β為每個超級節點的平均服務率。

為了敘述上的簡潔， DynamicIRa算法略去了對用戶最大等待時間tdeadline的描述。

2. 2 節點的動態加入和退出

每個新加入網絡的節點，其初始級別總是同父兄弟節點中最低的(max{k}+1)，其實際級別隨著該節點的運行逐步提高或降低，以達到最佳狀態，這個過程稱為慢啟動。不妨假設現有一新加入節點X。

定義6 X當前級別k的計算公式為

α=kX+logwX/WX #8226;ni=1ci/CX#8226;γj=1mj/MX#8226;5/tonline2; k=「α α＞00α≤0

(1)

其中：kX為X的初始級別; wX為統計X近期運行中節點占用的帶寬;WX為網絡中規定X能用的帶寬;CX為X的計算能力;ci為每個進程占用的CPU資源，1≤i≤n;MX為X的存儲能力; mj為每個文件占用的存儲容量， 1≤j≤γ; tonline是X到目前為止的在線時間。

由文獻[8]，式(1)中的常數5解釋為20%的發起節點能在線5 h以上，將其作為一個衡量節點在線時間長短的基準。節點在運行過程中，不斷調整自己的級別并及時將變更通知自己的父節點。級別越高，越有可能在父節點失效時升級為副主節點直至超級節點；級別越高，也說明該節點的能力越強，以此節點為根的子樹也越龐大。

定義7 節點X在當前所承受的負載之外還可額外接受負載的能力稱為剩余負載能力，標記為loadXrest。衡量節點X的剩余負載能力的指標為

loadX-rest=「log2（(WX-wX)×102/WX）×((CX-

∑ni=1ci)×102/CX)×((MX-∑γj=1mj)×102/MX)×(tonline/5)(2)



式(2)中每一小項乘102是利于討論中取整。一般情況下，如果一個節點X的WX、CX、MX剩余值超過總數的20％，在線時間≥5 h，則認為該節點有充裕的剩余負載資源，在不影響本機運行的前提下可作為超級節點或副主節點。此時的剩余負載能力為loadX-rest=「log8032=18。故算法中采用18作為衡量一個節點剩余負載能力的分界點(turningpoint)。

節點的動態加入算法(IntersertTree algorithm)詳細描述如下:

輸入:新節點X;

輸出: X加入某個自治系統。

VOID IntersertNode (Node X，Node A)//節點X加入以A為根的網

{send(X，A， JoinMessage); //X向A發出加入申請

if(loadArest≥18)

{X.OrdinaryRroutingTable.Father-NodeID=A;

//X將節點A作為父節點

X.OrdinaryRroutingTable.BrotherNodeID=A.SuperRoutingTable.Son-NodeID;//X將節點A的所有子節點作為自己的兄弟

X.NodeID(l)=A.NodeID(l)+1;//X層次為節點A的層次加1

if(A.SuperRoutingTable==NULL)

X.NodeID(k)=A.NodeID(k)+1;//若X是A的第一個子節點，則X的級別為A的級別加1

else X.NodeID(k)=max(A.SuperRoutingTable.Son-NodeID.NodeID(k))+1;

//否則，令X的級別為所有A的子節點中級別最大的再加1

APPEND(A.SuperRoutingTable.Son-NodeID，X);

//A將X添加進超級路由表

Every Ai=A.SuperRoutingTable.Son-NodeID， in Parallel do{

APPEND(Ai.OrdinaryRroutingTable.Brother-NodeID， X);}

//所有A的子節點將X作為兄弟節點加入自身普通路由表

}

else if(A.SuperRoutingTable!=NULL) 

{for Every Ai=A.SuperRoutingTable.Son-LowerSuperNodeID， in Parallel do

IntersertNode (X，Ai);

Until (Every Ai Reject X);}

}

VOID IntersertTree (Node X)//X申請加入某個自治系統

{ Broadcast(JoinMessage);//X向全網廣播一條“加入”信息

Z=min(time(ReturnMessage)); /*Z是響應X請求時間最短的節點，選取Z作為X加入網絡的引導節點(Bootstrap節點)*/

while(clock

{A=Z.OrdinaryRroutingTable.Father-NodeID;

IntersertNode(X，A);

Z=A;//A替代Z作為X新的引導節點

}

Y=Z.OrdinaryRroutingTable.Father-NodeID;

//Y是Z的父節點(代理服務器)

send(X，Y，JoinMessage);//X直接向代理服務器發出加入申請

}



若加入該自治系統的申請得到滿足，最壞情況下，一個新節點的加入請求需遍歷該自治系統中所有的節點，IntersertTree算法的時間復雜性度為O(num)。其中：num為自治系統內的節點個數，每個節點根據自身的剩余負載能力動態調整接受負載的能力，對網絡做出的貢獻都控制在自身的能力范圍之內。系統內的節點自動調整層次和級別，適應網絡情況的變化。 

節點離開系統分為兩種情況，即正常離開和非正常掉線。不妨假設現有一節點X離開網絡，則有:

a)若X為普通節點，X發送離線信息通知其父節點修改超級路由。X通知其兄弟節點修改各自普通路由表的BrotherNodeID表項。

b)若X為超級節點，X通知其副主節點Y升級為超級節點;Y通知所有的兄弟節點將自己作為新的父節點并相應修改各自的普通路由表;Y通知X的父節點Z修改其所擁有的超級路由表，同時Y將Z作為自己新的父節點。Y從Z的超級路由表處下載子節點NodeID作為自身普通路由表BrotherNodeID中的內容。在現在Y的子節點中選取一個級別最大的節點作為Y的副主節點;修改Y的超級路由表，并將超級路由表復制一份存儲在Y的副主節點中。

系統為了檢測到節點在沒有發送任何消息的情況下意外中斷離開的狀況，規定每個子節點需周期性地向它們的父節點發送一個字節的心跳消息，每個超級節點也需要周期性地與副主節點聯系心跳信息，說明自己工作正常。如果某個節點在幾個周期內均沒有收到另一個節點正常的消息，則認為該節點已非正常離開。以下描述節點X非正常離開的路由的維護:若X為普通節點，X的父節點A判定X已非正常離開，A修改自身超級路由表。A通知其子節點修改各自普通路由表的BrotherNodeID表項中的內容;若X為超級節點，X的副主節點Y判定X已非正常離開，Y自動升級為超級節點;其他相應的操作類似正常離開的情況b)。

23 自治系統內性能分析

首先作如下假設，以便建立數學模型:

a)設某個自治系統內的節點個數為num， βi為超級節點i的服務率， β為所有超級節點的平均服務率。M=num/β， M為該系統內平均擁有超級節點的個數，取β=100。

β的取值根據對10 000個節點的實驗數據取期望E(β)獲得。文獻[9，10]研究表明，大部分的網絡節點瓶頸在于通信時的帶寬，其計算和存儲能力相比帶寬約束可以忽略。假設子節點與父節點的通信需耗費的帶寬為50 kbps，則最壞情況下節點帶寬達3 Mbps時有min(β)=(3 Mbps×20%)/50 kbps=12，最好情況下節點帶寬達100 Mbps時有max(β)=(100 Mbps×20%)/50 kbps=400。

b)節點在不相交的時間間隔內加入速率λ(t)，離開速率β(t)滿足非齊次Poisson過程，λ(t)、β(t)的數值可在實驗中獲得。

c)設每個節點平均每秒發送q個請求。

d)每個查詢消息所需經過的跳數h最多為h=O(M)。

1）自治系統內節點數

λ(t)、β(t)均是周期為24的函數，λ(t)=λ(mod(t，24))， β(t)=β(mod(t，24))。λ(t)、β(t)的函數參數如表3所示。

表3 λ、β函數參數

tλ(t)β(t)

(0，8]Z0Y0

(8，11]Z0+ (Zmax-Z0)×(t-8)/3Y0-(Y0-Ymin)×(t-8)/3

(11，15]ZmaxYmin

(15，18]Zmax-(Zmax-Z1)×(t-15)/3Ymin+ (Y1-Ymin)×(t-15)/3

(18，20]Z1+ (ZMAX-Z1)×(t-18)/2Y1-(Y1-YMIN)×(t-18)/2

(20，23]ZMAXYMIN

(23，24]ZMAX–(ZMAX-Z0)×(t-23) YMIN +(Y0-YMIN)×(t-23)

Zi(i=0，1，max，MAX)、Yj（j=0，1，min，MIN）均可在網絡運行的相應時刻測得，也可通過一段時間的數據取為常數。曲線如圖2所示。

定理1 單位時間內新加入及離開網絡的用戶數服從關于λ、β的積分函數，且Nin-t0=∫t0+Δtt0λ(s)ds/3600， Nout-t0=∫t0+Δtt0β(s)ds/3600。

證明 根據Poisson分布，從t0時刻起的Δt時刻內有n個節點加入的概率為P{[N(t0+Δt)-N(t0)]=n}={[m(t0+Δt0)-m(t0)]m/n!}e-[m(t0+Δt)-m(t0)]。其中：m(t)=∫t0λj(s)ds。在(t0，t0+Δt)時刻內加入網絡的節點均值為m(t0+Δt)-m(t0)=∫t0+Δt0λj(s)ds-∫t00λi(s)ds；λi(t)、λj(t)的取值由分段函數決定。當Δt充分小時(假令Δt =1 s)，只要t0不取在函數的分界點處均可認為λ(t)的取值相同。故t0時刻起每一秒的單位時間內新加入網絡的用戶數Nin-t0=∫t0+Δtt0λ(s)ds/3600。其中有Min-t0=Nin-t0/β個新加入的節點成為網絡的超級節點。同理可證，從t0時刻起單位時間內離開網絡的用戶數Nout-t0=∫t0+Δtt0β(s)ds/3600。其中有Mout-t0=Nout-t0/β個超級節點離開網絡。

2)每個節點需存儲表項的大小

每個節點需維護普通路由表15 KB，如果還具有超級節點的身份，則需額外多維護超級路由表30 KB，路由表中存儲每條NodeID所需字節數小于150 bit。根據假設已知，每個節點至多有100個兄弟節點(β=100)。

3)維護表項的數據量及網絡開銷

a)新節點加入需維護數據量c×num+15 Kb×2;帶寬W=(c×num+15 KB×2)×Nin-t0。其中:c為每個加入申請數據包的大小；Nin-t0為t0到t0+1s時刻內新加入的用戶數。一個加入申請最壞情況下需轉發Z′=c×num次，新節點需從父節點處下載15 KB的數據作為自己的普通路由表中兄弟表項;與兄弟節點間傳遞小于15 KB的數據。

假設c=200 bit，num =10 000，則一個新節點的加入需傳送的數據總量為2 MB，當t0=5，λ(5)=8 000個/h，所需提供的帶寬為4.4 Mbps。

b)維護節點的離開所需維護數據量及網絡開銷。每個普通節點的正常或非正常離開需維護的數據量為15 KB。其中，包括維護父節點的150 bit的超級路由表以及15 KB的兄弟節點的普通路由表。

節點X是超級節點，其離開所需維護的數據量約為60 KB。其中，包括45 KB的升級其副主節點Y為超級節點，并構造Y表項的開銷; X的父節點Z修改自身的超級路由表和管轄域資源表的開銷為150 bit;Y通知自己的子節點(原來的兄弟節點)修改各自普通路由表的開銷為15 KB。

選定某個時刻t0，則t0到t0+1s內系統需為節點的離開提供的帶寬為W=(Nout-t0-Mout-t0)×15 KB+Mout-t0×45 KB。假令t0=5，β(5)=10 000個/h，則W=45 Kbps。

4）自治系統內路由查詢所需的處理代價及網絡開銷

節點的路由查詢消息主要在超級節點間轉發，集中考慮對超級節點查詢的處理代價及網絡開銷。每個超級節點均維護其管轄的索引，并處理收到的查詢請求。平均每秒需處理的數目是Q=β×q；每個超級節點每秒需轉發的消息為Z″=q×h=q×M，h為轉發的跳數。轉發所需的帶寬為W=Z″×c；c為每個查詢消息數據包的大小。

假設c=200 bit，q=1/s， M=100，得W=20 Kbps，每個超級節點需要處理Q=100個/s的查詢請求。

5）節點間維護心跳所需網絡開銷

每個節點傳遞的心跳消息cheartbeat=1bit，則1s內采樣心跳信息需的帶寬為W=fresource×cheartbeat×num。

假設num=10 000，取fresource =1次/s，得W=10 Kbps。

3 實驗仿真

以OPNET Modeler10為仿真平臺，開發了兩個原型系統，即傳統基于重定向服務器(DNS)的CDN(DNS_CDN)及以圖1為網絡架構的基于P2P的自組織網絡(P2P_CDN)，以觀測不同負載、不同網絡節點數的條件下路由算法的平均網絡延時。在實驗中，網絡節點數最多時達到1 000。

為了評價兩種網絡結構下的路由效率，讓網絡中節點逐漸增多，每個節點的路由請求數逐漸增大。圖3中X軸表示實驗模擬時間；Y軸表示平均路由延時。圖3(a)(b)分別代表DNS_CDN及P2P_CDN的實驗數據，各曲線所代表參數分別如表4(a)(b)所示。

表4 各實驗曲線參數

(a) DNS_CDN

曲線網絡中節點數每個節點單位時間內發起的路由請求

DNS_CDNApplication1500以Uniform_int函數每秒隨機發送1~5個

DNS_CDNApplication21 000以Uniform_int函數每秒隨機發送1~5個

DNS_CDNApplication31 000以Uniform_int函數每秒隨機發送10~20個

(b) P2P_CDN

曲線網絡中節點數每個節點單位時間內發起的路由請求

P2P_CDNProject11 000以固定速率每秒發送50個

P2P_CDNProject21 000以Uniform_int函數每秒隨機發送15~20個

P2P_CDNProject31 000以Uniform_int函數每秒隨機發送10~15個

P2P_CDNProject41 000以Uniform_int函數每秒隨機發送1~5個

P2P_CDNProject5500以Uniform_int函數每秒隨機發送1~5個

P2P_CDNProject6300以Uniform_int函數每秒隨機發送1~5個

從圖3(a)可以看出，隨著網絡節點數及每個節點路由請求的增多，重定向服務器逐漸成為新的網絡瓶頸，造成所有網絡節點平均路由延遲快速從0.001 2增加到0.09 s。從圖3(b)可以看出，除非在極端情況下，給予節點數1 000的網絡以較大固定速率的路由請求，其延遲達到0.27 s。其他不同節點數、不同隨機函數的路由搜索延遲均相對較穩定，平均值取014 s。從圖中可以看出，當網絡中節點數較少時，DNS_CDN的路由效率要優于P2P_CDN。但隨著節點數或每個節點的路由請求的增加，前一種網絡的路由效率顯著下降，后一種網絡則呈現了良好的穩定性。

實驗中還獲得了與2.3節理論分析值基本吻合的實驗數據，限于篇幅，本文在此不再羅列。

4 結束語

本文提出一種新的基于P2P的自組織網絡，其特點包括以下幾個方面:a)系統的動態分層;b)節點的級別可隨著網絡情況的變化而調整;

c)每個節點均可以加入系統，對節點沒有帶寬等任何方面的要求，每個節點根據自身的能力提供剩余資源服務于網絡;d)自治系統的路由采用樹型設計，避免路由中產生數據冗余;e)整個網絡具有高可擴展性。后續研究工作包括更合理的系統結構、更高效的路由方案。

致謝：在此，向朱濤，陳勇，劉松，鄧江等表示感謝，他們為本文提供了詳盡的實驗數據，為完善理論研究提供了有益的幫助。

參考文獻：

[1]DONG Yingfei， KUSMIEREK E， DUAN Zhenhai， et al. A hybrid clientassisted streaming architecture: modeling and analysis[C]//Proc of the 8th International Conference on Internet and Multimedia Systems and Applications.Calgary: ACTA Press，2004:217222.

[2]HEFEEDA M M，BHARGAV B K，YAU D K Y. A hybrid architecture for costeffective ondemand media streaming[J]. Computer Networks， 2004，44(3):353382.

[3]ROWSTRON A， DRUSCHEL P. Pastry:scalable，distributed object location and routing for largescale peertopeer system[C]//Proc of the 18th IFIP/ACM International Conference on Distribute Systems Platforms.Berlin: SpringerVerlag， 2001:329350.

[4]胡進鋒，黎明，鄭緯民，等.帶寬自適應的P2P網絡路由協議[J].軟件學報， 2005，16(5):991999.

[5]DABEK F， KAASHOEK M F， KARGER D， et al. Widearea cooperative storage with CFS[C]//Proc of the 18th ACM Symposium on Operating Systems Principles.New York: ACM Press， 2001:344352.

[6]BOSSELAERS A， GOVAERTS R， VANDEWALLE J. SHA: a design for parallel architectures?[C]//Proc of International Conference on the Theory and Application of Cryptographic Techniques.Berlin:SpringerVerlag， 1997:348362.

[7]SAROIU S， GUMMADI P K， GRIBBLE S D. A measurement study of peertopeer file sharing systems[C]//Proc of Multimedia Computing and Networking Conferences.New York:ACM Press， 2002:156170.

[8]DSS Inc.Genutella: to the bandwidth barrier and beyond[EB/OL]. [20070910]. http://dss.clip2.com/gnutella.html.

[9]GE Zihui， FIGUEIREDO D R JAISWAI S， et al. Modeling peerpeer file sharing systems[C]//Proc of the 22nd Annual Joint Conference on IEEE Computer and Communications Societies.San Francisco: IEEE Press，2003:21882198.

[10]XU Zhiyong， HU Yiming. SBARC: a supernode based peertopeer file sharing system[C]//Proc of the 8th IEEE Symposium on Computers and Communications.Washington DC: IEEE Computer Society， 2003:10531058.