基于Chord的P2P路由算法的研究與改進(jìn).pdf

1、最近幾年，Peer-to-Peer（對(duì)等計(jì)算，簡(jiǎn)稱P2P）迅速成為計(jì)算機(jī)界關(guān)注的熱門話題之一，財(cái)富雜志更將P2P列為影響Internet未來(lái)的四項(xiàng)科技之一。
　　 P2P網(wǎng)絡(luò)的核心機(jī)制，是在應(yīng)用層建立邏輯上的覆蓋網(wǎng)絡(luò)（overlay network）。從2001年開(kāi)始，學(xué)術(shù)界提出了結(jié)構(gòu)化P2P領(lǐng)域最具代表性的幾個(gè)經(jīng)典模型，比如Chord、CAN、Tapestry和Pastry。結(jié)構(gòu)化P2P網(wǎng)絡(luò)在應(yīng)用層構(gòu)建了一個(gè)有嚴(yán)格拓?fù)浣Y(jié)構(gòu)的覆

2、蓋網(wǎng)，并且通常使用基于一致性散列函數(shù)的分布式散列表（DHT），將網(wǎng)絡(luò)中結(jié)點(diǎn)或者數(shù)據(jù)對(duì)象高效、均勻地映射到覆蓋網(wǎng)中。
　　 同時(shí)也要看到覆蓋網(wǎng)的拓?fù)浣Y(jié)構(gòu)有可能與底層物理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不一致的情況，因而在路由過(guò)程中并不能獲得很好的物理時(shí)延。
　　 為避免高延遲的hop，在構(gòu)造覆蓋網(wǎng)絡(luò)，或者路由選擇時(shí)整合底層物理網(wǎng)絡(luò)的拓?fù)湫畔?lái)提高實(shí)際路由性能。論文分析了傳統(tǒng)Chord算法，Chord路由表只是根據(jù)結(jié)點(diǎn)在覆蓋網(wǎng)中的ID鄰近信息

3、來(lái)構(gòu)建，而且Chord路由表中各表項(xiàng)鄰居結(jié)點(diǎn)的選擇非常靈活，結(jié)點(diǎn)n的第i個(gè)路由表項(xiàng)的選擇范圍是[n+2i-1，n+2i-1]，共有2i-1種選擇。本論文在路由表構(gòu)建上使用啟發(fā)式的PNS（K）方法，即在區(qū)間[n+2i-1，n+2i-1]選擇前K個(gè)結(jié)點(diǎn)，然后找出與結(jié)點(diǎn)n時(shí)延最小的那個(gè)結(jié)點(diǎn)作為其路由表的第i個(gè)表項(xiàng)。
　　 這時(shí)將問(wèn)題進(jìn)一步轉(zhuǎn)化為如何來(lái)收集物理網(wǎng)絡(luò)拓?fù)湫畔?。分析常用整合底層物理網(wǎng)絡(luò)拓?fù)湫畔⒌姆椒ê?，選擇了Ratnasam

4、y等提出一種分布式binning的方法，即彼此網(wǎng)絡(luò)延遲很近的結(jié)點(diǎn)將被分到同一個(gè)bin里。不同bin的劃分是借助分布于Internet上的已知的landmark機(jī)器，結(jié)點(diǎn)分別測(cè)量與這些已知landmarks的距離，比如，round-trip time，然后根據(jù)這些測(cè)量距離獨(dú)立地選擇一個(gè)特別bin。
　　 通過(guò)使用p2psim模擬器得到的定量模擬數(shù)據(jù)，改進(jìn)后的chord，在路由表的創(chuàng)建和路由時(shí)每一跳的選擇上整合底層物理拓?fù)湫畔ⅲ梢?/p>