對(duì)等網(wǎng)絡(luò)內(nèi)容搜索及索引緩存研究.pdf

1、近年來，對(duì)等網(wǎng)絡(luò)日益成為Internet一個(gè)重要應(yīng)用。對(duì)等網(wǎng)絡(luò)將Intemet邊緣節(jié)點(diǎn)的資源收集起來，提供強(qiáng)大的計(jì)算與存儲(chǔ)能力。無結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)由于查詢的靈活性和對(duì)動(dòng)態(tài)環(huán)境的適應(yīng)性，得到大力部署，成為對(duì)等網(wǎng)絡(luò)的主流。但無結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)存在網(wǎng)絡(luò)性能低下等困難，這使搜索算法一直是無結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)的研究重點(diǎn)。 本論文研究無結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)的內(nèi)容搜索算法和分布式索引緩存算法，主要研究內(nèi)容和創(chuàng)新成果如下： 1)提出了一個(gè)基于查詢代理的自適應(yīng)無

2、結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)盲搜索算法(QAA，Que叫AgentAlgorithm)。盲搜索算法的主要目標(biāo)是控制查詢規(guī)模，降低冗余開銷，但現(xiàn)有算法缺少對(duì)網(wǎng)絡(luò)狀況的感知能力，難以自適應(yīng)地根據(jù)查詢及網(wǎng)絡(luò)情況調(diào)整查詢規(guī)模。 QAA通過查詢代理不斷發(fā)杖子查詢來完成查詢工作，其核心思想是通過子查詢探測(cè)網(wǎng)絡(luò)狀況，再利用這些信息指導(dǎo)后續(xù)子查詢規(guī)模，從而有效降低冗余開銷，其規(guī)則是：離查詢成功越近，查詢規(guī)模越小。利用這種探測(cè)過程，QAA避免了現(xiàn)有算法的參數(shù)優(yōu)化

3、難題。 本論文將QAA與現(xiàn)有盲搜索算法進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果表明，對(duì)uni-uni模式及Zipf-sqrt模式，QAA即使在高查詢滿足率條件下，也實(shí)現(xiàn)了有效冗余開銷控制。其結(jié)果冗余率分別為1.1和1.4，是幾個(gè)實(shí)驗(yàn)算法中最低的，并且兩個(gè)模式下的結(jié)果冗余率提高也是最低的，這說明QAA有更好的網(wǎng)絡(luò)適應(yīng)性。 2)提出了一個(gè)基于緩存生命期(TTL)的分布式索引緩存模型。分布式索引緩存方法的基本思想是以較低代價(jià)擴(kuò)大網(wǎng)絡(luò)中信息數(shù)量，以

4、此提高網(wǎng)絡(luò)搜索性能，因此索引緩存密度在影響對(duì)等網(wǎng)絡(luò)的搜索性能上占據(jù)核心地位，但目前對(duì)此的研究工作還很少見報(bào)道。 本論文分析了查詢到達(dá)對(duì)緩存索引擴(kuò)散的驅(qū)動(dòng)作用以及緩存生命期超時(shí)對(duì)緩存索引的消滅作用，發(fā)現(xiàn)網(wǎng)絡(luò)索引緩存密度在這兩個(gè)因素影響下可以維持一定的穩(wěn)定軼態(tài)，這葸昧看，口]以通過一些簡單的參數(shù)來模型網(wǎng)絡(luò)搜索性能。 基于上述發(fā)現(xiàn)本論文研究了兩個(gè)具代表性的基本節(jié)點(diǎn)發(fā)現(xiàn)算法——Gnutella算法與竺蛩掌游算法，其分別具有最短和

5、最長的緩存路徑。我們研究了這兩個(gè)算法的索引緩殺密度如伺受查詢到達(dá)速率以及緩存生命期時(shí)長的影響，發(fā)現(xiàn)在Gnutella算法下，查詢；釜尊蘭苧磬孽生命期時(shí)長對(duì)緩存密度表現(xiàn)出明顯的線性關(guān)系，而在隨機(jī)漫游算法下，衾論文進(jìn)一步研究了查詢到達(dá)速率及緩存生命期兩個(gè)因素如何影響網(wǎng)絡(luò)的搜索性能，發(fā)現(xiàn)在Gnutella算法下，平均查詢開銷和這兩個(gè)因素有線性關(guān)系，而在隨機(jī)漫游算法下，這是一個(gè)對(duì)數(shù)關(guān)系。　　 3)研究了目前分布式索引緩存方法存在的問題，

6、包括網(wǎng)絡(luò)動(dòng)態(tài)性所導(dǎo)致的索引緩存失效問題以及多對(duì)一映射所導(dǎo)致的負(fù)載均衡問題。 在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下，由于索引與共享內(nèi)容相分離，當(dāng)共享內(nèi)容變化時(shí)，會(huì)使相關(guān)索引信息失效。目前算法中使用的緩存生命期機(jī)制沒能保證索引信息的有效性，分析發(fā)現(xiàn)，失效索引信息會(huì)在對(duì)等網(wǎng)絡(luò)中擴(kuò)散，對(duì)查詢?cè)斐筛蓴_。我們提出通過檢測(cè)索引信息有效性來阻止無效索引信息擴(kuò)散，并進(jìn)一步提出了檢測(cè)-重生方法，該方法執(zhí)行了對(duì)命中條目緩存生命期的重設(shè)操作。研究結(jié)果表明，使用檢測(cè)方法會(huì)引

7、起對(duì)等網(wǎng)絡(luò)緩存密度最多44％的降低，但可以將無效緩存索引降低4～7倍。 索引緩存方法擴(kuò)大了網(wǎng)絡(luò)中索引信息數(shù)量，但不影響相應(yīng)的共享內(nèi)容，這種多對(duì)一映射的不均勻會(huì)使得負(fù)載均衡問題發(fā)生，影響網(wǎng)絡(luò)服務(wù)能力。我們提出共享內(nèi)容關(guān)聯(lián)方法(SCAA，Shared Content Associated Algorithm)來緩解這一問題。SCAA關(guān)聯(lián)共享內(nèi)容，分擔(dān)內(nèi)容請(qǐng)求，以此來緩解負(fù)載均衡問題。我們研究了SCAA在不同負(fù)載壓力下的效果，發(fā)現(xiàn)在中