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

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

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

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

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