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

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

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

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

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