對等網(wǎng)絡(luò)中分散式查找的研究及其應(yīng)用.pdf

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

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

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

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