[發(fā)明專利]一種對(duì)等網(wǎng)絡(luò)中流行資源副本的優(yōu)化放置方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310232484.8
• 申請(qǐng)日: 2013-06-13
• 公開(kāi)（公告）號(hào): CN103491128A
• 公開(kāi)（公告）日: 2014-01-01
• 發(fā)明（設(shè)計(jì)）人: 楊文國(guó);高隨祥;吳鴿鵬;鄧浩江;郭田德;趙彤;安然;姜志鵬;孫靜;王慎娜
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院大學(xué)
• 主分類號(hào): H04L29/08
• 分類號(hào): H04L29/08;H04L12/911
• 代理公司: 北京科迪生專利代理有限責(zé)任公司 11251
• 代理人: 成金玉;賈玉忠

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)通信領(lǐng)域，特別是對(duì)等網(wǎng)絡(luò)搜索優(yōu)化和資源放置優(yōu)化問(wèn)題。

背景技術(shù)

對(duì)等網(wǎng)絡(luò)是下一代網(wǎng)絡(luò)的核心概念，與傳統(tǒng)的中心服務(wù)器與客戶端模式不同。在對(duì)等網(wǎng)絡(luò)中，各個(gè)節(jié)點(diǎn)既從其余節(jié)點(diǎn)獲得自己想要的資源，也向其余的節(jié)點(diǎn)提供自己共享的資源。在對(duì)等網(wǎng)絡(luò)的實(shí)現(xiàn)中，由于不存在中心服務(wù)器，如何快速的定位各種資源和服務(wù)是一個(gè)關(guān)鍵技術(shù)。

當(dāng)前關(guān)于對(duì)等網(wǎng)中快速搜索的研究將對(duì)等網(wǎng)分為了結(jié)構(gòu)對(duì)等網(wǎng)和無(wú)結(jié)構(gòu)對(duì)等網(wǎng)。無(wú)結(jié)構(gòu)對(duì)等網(wǎng)較之于使用分布式哈希表（Distributed?Hash?Table）的結(jié)構(gòu)對(duì)等網(wǎng)，搜索效率偏低，但是其自身維護(hù)開(kāi)銷顯著減少，具有良好的擴(kuò)展性，便于大范圍內(nèi)組網(wǎng)。

在無(wú)結(jié)構(gòu)對(duì)等網(wǎng)中，信息的搜索分為盲目搜索和導(dǎo)向性搜索。盲目搜索以泛洪（Flooding）搜索為基礎(chǔ)，節(jié)點(diǎn)將搜索信息無(wú)差別的，或是隨機(jī)的選擇若干個(gè)鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，搜索具有盲目性；導(dǎo)向性搜索的常用技術(shù)是根據(jù)一些指導(dǎo)信息將查詢請(qǐng)求轉(zhuǎn)發(fā)到搜索成功率更高的節(jié)點(diǎn)上。

導(dǎo)向性搜索中指導(dǎo)查詢請(qǐng)求轉(zhuǎn)發(fā)的信息可以是節(jié)點(diǎn)的搜索歷史或是內(nèi)容相似性等，因此其轉(zhuǎn)發(fā)節(jié)點(diǎn)往往跟查詢節(jié)點(diǎn)具有一些相同的性質(zhì)，比如擁有相似的存儲(chǔ)內(nèi)容，或是相似的在線時(shí)間等等。在一定程度上導(dǎo)向性搜索比盲目搜索的成功率要大，同時(shí)減少了網(wǎng)絡(luò)中的信息冗余增長(zhǎng)。但經(jīng)過(guò)一段時(shí)間后，由于網(wǎng)絡(luò)中部分節(jié)點(diǎn)其維護(hù)的內(nèi)容較多，且服務(wù)能力好（例如，一個(gè)局部地區(qū)的小型服務(wù)器），使其漸漸的成為周邊節(jié)點(diǎn)的共同轉(zhuǎn)發(fā)節(jié)點(diǎn)。這樣就形成了對(duì)等網(wǎng)中的一些過(guò)熱節(jié)點(diǎn)或者稱之為超級(jí)節(jié)點(diǎn)，它們承擔(dān)著網(wǎng)絡(luò)中很大一部分搜索信息的處理和轉(zhuǎn)發(fā)。

對(duì)等網(wǎng)中過(guò)熱節(jié)點(diǎn)的存在是一個(gè)隱患。過(guò)熱節(jié)點(diǎn)由于承載著過(guò)多的搜索信息的處理和轉(zhuǎn)發(fā)，有可能會(huì)出現(xiàn)過(guò)載的情況，導(dǎo)致網(wǎng)絡(luò)中部分區(qū)域出現(xiàn)信息堵塞等情況。從而通過(guò)此超級(jí)節(jié)點(diǎn)享受服務(wù)的葉子節(jié)點(diǎn)可能會(huì)遭遇到搜索響應(yīng)延遲的情況。因此需要盡可能的減少超級(jí)節(jié)點(diǎn)的開(kāi)銷，使其能更好的為周圍葉子節(jié)點(diǎn)服務(wù)。

為了解決流行資源訪問(wèn)量過(guò)大造成的節(jié)點(diǎn)過(guò)熱現(xiàn)象，當(dāng)前的常用技術(shù)是合理緩存流行資源的副本，從而減少過(guò)熱節(jié)點(diǎn)的開(kāi)銷。該技術(shù)的基本原理是將流行資源的副本存儲(chǔ)在網(wǎng)絡(luò)中部分節(jié)點(diǎn)上，當(dāng)有相同的搜索信息轉(zhuǎn)發(fā)到這些節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)發(fā)現(xiàn)此搜索信息請(qǐng)求的資源與自身緩存的副本相同，則直接與查詢節(jié)點(diǎn)建立連接并進(jìn)行副本的傳輸。這種技術(shù)可以有效地減少過(guò)熱節(jié)點(diǎn)的開(kāi)銷并提高了服務(wù)的響應(yīng)時(shí)間（圖2）。

現(xiàn)有的副本放置技術(shù)已經(jīng)有了不少研究成果。有的根據(jù)資源的被查詢頻率對(duì)資源進(jìn)行相應(yīng)的復(fù)制，通過(guò)更多的節(jié)點(diǎn)來(lái)滿足查詢以減少搜索通信開(kāi)銷，取得了不錯(cuò)的效果。

副本緩存技術(shù)的一個(gè)關(guān)鍵問(wèn)題是要保證副本放置的有效性，即緩存副本的節(jié)點(diǎn)要與對(duì)應(yīng)的超級(jí)節(jié)點(diǎn)具有一定的行為相似度特征，從而可以有效減少超級(jí)節(jié)點(diǎn)的開(kāi)銷。當(dāng)前的常用技術(shù)是設(shè)置緩存時(shí)間來(lái)確保副本的有效性。

此外，目前的技術(shù)在實(shí)現(xiàn)的過(guò)程中存在著副本冗余放置的現(xiàn)象。在小規(guī)模局域網(wǎng)中，由于節(jié)點(diǎn)和資源都相對(duì)較少，冗余放置不會(huì)對(duì)節(jié)點(diǎn)產(chǎn)生很大影響。而在大范圍組網(wǎng)中，尤其是稠密的網(wǎng)絡(luò)中，節(jié)點(diǎn)可能由于承載過(guò)多的存儲(chǔ)需求而導(dǎo)致崩潰，影響了網(wǎng)絡(luò)的可擴(kuò)展性。

發(fā)明內(nèi)容

本發(fā)明的技術(shù)解決的問(wèn)題：克服現(xiàn)有技術(shù)的不足，提供一種對(duì)等網(wǎng)絡(luò)中流行資源副本的優(yōu)化放置方法，該方法可以有效減少網(wǎng)絡(luò)中存儲(chǔ)流行資源的超級(jí)節(jié)點(diǎn)開(kāi)銷，提高網(wǎng)絡(luò)搜索算法的可擴(kuò)展性。

本發(fā)明的技術(shù)解決方案：一種對(duì)等網(wǎng)絡(luò)中流行資源副本的優(yōu)化放置方法，實(shí)現(xiàn)步驟如圖1所示，具體如下：

A.在對(duì)等網(wǎng)絡(luò)每一個(gè)運(yùn)行周期開(kāi)始時(shí)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)統(tǒng)計(jì)上一個(gè)周期內(nèi)的自身被訪問(wèn)的次數(shù)；

B.每個(gè)節(jié)點(diǎn)根據(jù)訪問(wèn)次數(shù)確定自己為葉子節(jié)點(diǎn)或者超級(jí)節(jié)點(diǎn)，訪問(wèn)次數(shù)超過(guò)設(shè)定閾值的節(jié)點(diǎn)定義為熱門(mén)節(jié)點(diǎn)，也稱之為超級(jí)節(jié)點(diǎn)，訪問(wèn)次數(shù)沒(méi)達(dá)到閾值的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)；所有的節(jié)點(diǎn)向其周圍的節(jié)點(diǎn)發(fā)送一個(gè)表明自己身份的信息，從而網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都知道周圍的超級(jí)節(jié)點(diǎn)和葉子節(jié)點(diǎn)；

C.超級(jí)節(jié)點(diǎn)根據(jù)自己接收到的步驟B中所述身份信息，統(tǒng)計(jì)出自己路由表里的葉子節(jié)點(diǎn)，并計(jì)算所述這些葉子節(jié)點(diǎn)與自己的行為相似性；所述葉子節(jié)點(diǎn)與超級(jí)節(jié)點(diǎn)間的行為相似性是指上個(gè)周期內(nèi)葉子節(jié)點(diǎn)與超級(jí)節(jié)點(diǎn)共同在線時(shí)間的比重。此外，超級(jí)節(jié)點(diǎn)統(tǒng)計(jì)上一周期內(nèi)自身的資源訪問(wèn)次數(shù)，將訪問(wèn)次數(shù)高于設(shè)定閾值的資源定義為流行資源；

D.所述葉子節(jié)點(diǎn)將自身可以提供的存儲(chǔ)容量和路由表信息發(fā)送給超級(jí)節(jié)點(diǎn)。所述超級(jí)節(jié)點(diǎn)根據(jù)接收到的葉子節(jié)點(diǎn)的信息，統(tǒng)計(jì)出這些葉子節(jié)點(diǎn)之間的連通度；