對等網絡中分散式查找的研究及其應用.pdf

1、本文首先介紹了對等網絡的背景知識,然后在第二章介紹分散式查找算法的一些基本理論,并分析了FreeNet、GnutellaG兩種非結構化查找算法和Chord、CAN(Content Addressable Network)、pastry、Tapestry、D2B、Koorde和Viceroy等幾種基于分布式哈希表(DHT)的分散式查找算法,并分析和比較了它們各自的缺點.在本文第三章中,通過將對等網絡抽象為一個d維笛卡兒空間,網絡中的節(jié)點抽

2、象成空間中的點,可以將網絡中兩個節(jié)點之間的查找(路由)抽象為d維笛卡兒空間中兩點之間的查找問題,并由此提出了分散式查找的數學模型.Chord、CAN、pastry和KoordeSifter),等幾種看似完全不同的分散式查找算法,都可以由該數學模型來詮釋.該模型可用于設計、分析和評價分散式查找算法.第四章根據分散式查找數學模型的基本原理,提出了三種不同的分散式查找算法(ChordPlus、Isotope和它們適用于不同的應用背景.其中,C

3、hordPlus 算法是Chord算法的改進版,它很好地繼承了Chord算法的優(yōu)點,如簡單性、可證明的正確性和性能等.此外,它具備更好的查找性能和容錯性,可以用來改進彩Chord算法構建的對等網絡;Isotope是一種具有多路查找能力的分散式查找算法,擁有高效的查找與路由性能、良好的位置意識特性和快遞適應網絡變化的能力.Isotope適用于規(guī)模大、動態(tài)性強和異構的對等網絡環(huán)境;Sifter是一種具有常數級時間復雜度的分散式查找算法.在本

4、算法中,單個節(jié)點需要維護O(n<'1/c>))個其他節(jié)點的鏈接信息以便在O(1)個邏輯路由跳內找到目的數據.本算法適用于網絡動態(tài)性不大,但是對查找的實時性要求較高的應用背景.本文第五章提出了一種混合式查找方案.該方案既有高容錯性、可擴展性和自組織性好等分散式查找方案的優(yōu)點,又有查找效率高、易于集中管理和控制、安全性好等集中式查找方案的優(yōu)勢.仿真實驗結果表明,該方案的相對延遲(RDP)指標要優(yōu)于常規(guī)的分散式查找方案,實際查詢時間(開銷)更