NetShot 算法設計與模擬馬振

1、 NetShot 算法設計與模擬 馬 振 2002. 6. 17Overviewn1. Peer-to-Peer技術n2. Peer-to-Peer系統(tǒng)的定位和路由算法 n3. NetShot路由算法n4. NetShot算法模擬n5. NetShot節(jié)點出錯時的可靠性和策略1. Peer-to-Peer技術nProblem of traditional client-server modelnSingle point of failure nNot ScalablenWhy P2P? - Hosts connect to peers directly nIts completely dece

2、ntralized model enables the development of application with:nHigh-availabilitynFault-tolorancenScalabilitynP2P is not limited in file-sharingnDistributed computingnCollaboration tools2. Peer-to-Peer系統(tǒng)的定位和路由算法 Napster: 具有中心節(jié)點，數(shù)據(jù)存儲于各節(jié)點，每個節(jié)點通過查詢中心節(jié)點獲得所需數(shù)據(jù)的存儲位置。2. Peer-to-Peer系統(tǒng)的定位和路由算法Gnutella: 取消了中心節(jié)點

3、，查找資源時采用了Flooding機制。Problem: Napster, Gnutella不具有好的可擴展性Solution: 在Overlay網(wǎng)絡層上定義P2P的拓撲結(jié)構和路由系統(tǒng)n幾何分割的拓撲結(jié)構： CAN, Gridn環(huán)形的拓撲結(jié)構： Tapestry, Pastry, Chord 和NetShot3. NetShot路由算法1.命名：動態(tài)長度的0,1字符串，分割0,1空間來進行命名。2.節(jié)點鄰接關系：每個節(jié)點具有路由表和引入表來維護它與系統(tǒng)中部分節(jié)點的鄰接關系。3.路由策略：根據(jù)節(jié)點間的鄰接關系前遞請求。4.支持節(jié)點動態(tài)加入和離開。 動態(tài)大小的命名機制使系統(tǒng)具有很高的可擴展性；動態(tài)

4、大小的命名機制使系統(tǒng)具有很高的可擴展性；路由表和引入表的雙向查找提供了高效可靠的路由表和引入表的雙向查找提供了高效可靠的路由查找機制。路由查找機制。NetShot AlgorithmName Format 10101000，10101100)4. NetShot算法模擬n構建了NetShot算法的靜態(tài)模擬程序 1.模塊BinaryOperation: 名字空間的分割，產(chǎn)生和合并操作 2.模塊InnerNode: 模擬消息傳遞，節(jié)點加入，節(jié)點離開操作 3.模塊StartSimulation: 生成NetShot路由環(huán)，設置不同的模擬參數(shù)4. NetShot算法模擬消息傳送的邏輯路徑長度消息傳送的

5、邏輯路徑長度 O(logN)4. NetShot算法模擬 節(jié)點加入時的節(jié)點加入時的Hop數(shù)數(shù) O(log2N)4. NetShot算法模擬節(jié)點離開時的節(jié)點離開時的Hop數(shù)數(shù)O(log2N)4. NetShot算法模擬節(jié)點出錯的情況下新節(jié)點加入所需平均Hop數(shù) (系統(tǒng)規(guī)模是1024個節(jié)點）5. NetShot節(jié)點出錯時的可靠性和策略假設每個節(jié)點的出錯概率為p，NetShot系統(tǒng)中節(jié)點的總數(shù)量為N，那么整個NetShot路由系統(tǒng)的可靠性為 1 Npr+i L證明： 當任意一個節(jié)點的所有路由表和引入表中的節(jié)點都出錯的時候，那么整個NetShot系統(tǒng)就被分成了兩個不可達的部分。某個節(jié)點的所有路由表和引

6、入表中的節(jié)點都出錯的概率是pr+i 。令F為NetShot系統(tǒng)出錯的概率，則F pr+i Npr+i所以整個NetShot路由系統(tǒng)的可靠性為1 Npr+i 。 5. NetShot節(jié)點出錯時的可靠性和策略NetShot路由系統(tǒng)的可靠性為1 Npr+i 。 當N = 1,024, r = i = logN, p = 1/2 時，NetShot路由系統(tǒng)的可靠性為99.9023%。 當N = 1,000,000, r = i = logN, p = 1/2 時，NetShot路由系統(tǒng)的可靠性為99.9999%。5. NetShot節(jié)點出錯時的可靠性和策略為什么要設計恢復策略？ 部分節(jié)點出錯，當有新節(jié)

7、點加入時，路由表 和引入表的錯誤很容易擴散 通過對節(jié)點出錯的模擬發(fā)現(xiàn)，部分節(jié)點出錯后，查找效率將明顯下降5. NetShot節(jié)點出錯時的可靠性和策略被動的恢復策略：被動的恢復策略： 當消息被前遞到一個出錯的節(jié)點時，調(diào)用depart()函數(shù)，將該節(jié)點強制離開系統(tǒng)。 1. 降低部分節(jié)點的查找效率 2. 對各節(jié)點不公平 5. NetShot節(jié)點出錯時的可靠性和策略主動的恢復策略主動的恢復策略 每個節(jié)點在后臺運行一個恢復線程，每六十秒鐘運行一次。它將更新所有的路由表項和引入表項。 1. 公平，有效 2.2. 增加了系統(tǒng)的額外開銷，但是可以容忍 5. NetShot節(jié)點出錯時的可靠性和策略n系統(tǒng)的額外開

8、銷系統(tǒng)的額外開銷n1. 錯誤的修復可以抵消錯誤存在時查詢的額外開銷n2.估算：每個節(jié)點維護著一個大小為r的路由表和一個大小為i的引入表。每個查詢操作將訪問O(logN)個節(jié)點。所以每秒用于修復所需要的開銷 Overhead = (r+i)logN/60 packets。n如果r = i = logN；N = 100,000，則 Overhead = 9.196 packets。n假設一個packet由64個字節(jié)組成。則Overhead = 0.6Kb/Sec。這樣的開銷是不可忽略的，但是對于任何一個調(diào)制解調(diào)器都是可以容忍的。 Outlinen詳細分析比較了典型的詳細分析比較了典型的P2P路由和定位算法，路由和定位算法，說明了說明了NetShot算法的特點和優(yōu)勢。算法的特點和優(yōu)勢。n構