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

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

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

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

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

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

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

7、起對等網(wǎng)絡(luò)緩存密度最多44％的降低，但可以將無效緩存索引降低4～7倍。 索引緩存方法擴大了網(wǎng)絡(luò)中索引信息數(shù)量，但不影響相應(yīng)的共享內(nèi)容，這種多對一映射的不均勻會使得負載均衡問題發(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)容請求，以此來緩解負載均衡問題。我們研究了SCAA在不同負載壓力下的效果，發(fā)現(xiàn)在中