基于Chord的P2P路由算法的研究與改進.pdf

1、最近幾年，Peer-to-Peer（對等計算，簡稱P2P）迅速成為計算機界關注的熱門話題之一，財富雜志更將P2P列為影響Internet未來的四項科技之一。
　　 P2P網絡的核心機制，是在應用層建立邏輯上的覆蓋網絡（overlay network）。從2001年開始，學術界提出了結構化P2P領域最具代表性的幾個經典模型，比如Chord、CAN、Tapestry和Pastry。結構化P2P網絡在應用層構建了一個有嚴格拓撲結構的覆

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

3、來構建，而且Chord路由表中各表項鄰居結點的選擇非常靈活，結點n的第i個路由表項的選擇范圍是[n+2i-1，n+2i-1]，共有2i-1種選擇。本論文在路由表構建上使用啟發(fā)式的PNS（K）方法，即在區(qū)間[n+2i-1，n+2i-1]選擇前K個結點，然后找出與結點n時延最小的那個結點作為其路由表的第i個表項。
　　 這時將問題進一步轉化為如何來收集物理網絡拓撲信息。分析常用整合底層物理網絡拓撲信息的方法后，選擇了Ratnasam

4、y等提出一種分布式binning的方法，即彼此網絡延遲很近的結點將被分到同一個bin里。不同bin的劃分是借助分布于Internet上的已知的landmark機器，結點分別測量與這些已知landmarks的距離，比如，round-trip time，然后根據這些測量距離獨立地選擇一個特別bin。
　　 通過使用p2psim模擬器得到的定量模擬數(shù)據，改進后的chord，在路由表的創(chuàng)建和路由時每一跳的選擇上整合底層物理拓撲信息，可以