大規(guī)模分布資源查找覆蓋網(wǎng)拓?fù)浣Y(jié)構(gòu)的研究.pdf

1、本文探討對等計算與網(wǎng)格計算的一個結(jié)合點:大規(guī)模分布資源的查找.論文的研究工作如下.首先,論文詳細(xì)總結(jié)了資源查找所涉及的關(guān)鍵問題、影響因素和性能評價參數(shù).我們分析了隨機圖、規(guī)則圖、Power-law圖三種拓?fù)浣Y(jié)構(gòu)下各種路由機制對查找性能的影響.得出兩個結(jié)論:一、隨機圖比較適合作為資源覆蓋網(wǎng)的拓?fù)浣Y(jié)構(gòu).二、在各種路由轉(zhuǎn)發(fā)機制中,學(xué)習(xí)法路由機制的查找性能是最佳的.基于上述結(jié)論,定義了資源查找基本模型,并為模型選定了查找機制.對采用學(xué)習(xí)法路由轉(zhuǎn)

2、發(fā)、LRU路由替換算法機制下形成的覆蓋網(wǎng)進(jìn)行模擬,結(jié)果顯示:網(wǎng)絡(luò)的平均查找路徑長度相對小,簇系數(shù)較大,結(jié)點連通度分布符合Power-law分布.因此得出以下結(jié)論:采用選定的認(rèn)為是好的查找機制形成的拓?fù)浣Y(jié)構(gòu)是Power-law圖,而不是希望的隨機圖.其次,論文提出主動形成拓?fù)涮匦?提出形成小世界拓?fù)湟蕴岣卟檎颐新?希望網(wǎng)絡(luò)中有很多簇,大部分邊連接簇內(nèi)結(jié)點,少部分邊連接簇與簇之間的結(jié)點.這樣一個小世界網(wǎng)絡(luò)可以使大部分的查找請求在簇內(nèi)得到響

3、應(yīng)從而提高查找命中率.為此,對LRU路由表替換算法進(jìn)行改進(jìn),并在此基礎(chǔ)上提出一個分組查找模型,實驗結(jié)果表明:分組查找機制在平均查找路徑和查找命中率方面優(yōu)于純分布式的查找機制.為減輕負(fù)載,提出一個使網(wǎng)絡(luò)拓?fù)渲鲃映尸F(xiàn)隨機圖的成員協(xié)議.在網(wǎng)絡(luò)中引入Host結(jié)點,Host結(jié)點負(fù)責(zé)記錄信息結(jié)點的狀態(tài)并對結(jié)點加入、更換鄰居和退出時的連接給予指導(dǎo).為了防止單點失效,我們提出的成員協(xié)議允許多個Host結(jié)點同時工作.實驗結(jié)果表明:協(xié)議能控制結(jié)點的度,維持

4、網(wǎng)絡(luò)的小直徑且保持網(wǎng)絡(luò)的連通性.協(xié)議中的更換連接規(guī)則使很多查找機制都可以在此基礎(chǔ)上實現(xiàn).最后,分析構(gòu)造自適應(yīng)拓?fù)涞年P(guān)鍵因素.通過對查找網(wǎng)絡(luò)中結(jié)點之間的連接關(guān)系以及結(jié)點的行為屬性的抽象化,發(fā)現(xiàn)可以將結(jié)點間的連接邊分為索引邊和查找邊.結(jié)點的行為主要分為查詢轉(zhuǎn)發(fā)和查詢結(jié)果緩存兩種.據(jù)此定義了一個通用而簡單的結(jié)構(gòu)模型:QIL模型(Query/Index Link).模型對查找網(wǎng)的拓?fù)浣Y(jié)構(gòu)的冗余度進(jìn)行分析,指出通過避免一條邊回路、交叉或環(huán)可以消除