[發(fā)明專(zhuān)利]一種常數(shù)復(fù)雜度的對(duì)等網(wǎng)絡(luò)目的資源定位方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210322936.7
• 申請(qǐng)日: 2012-09-04
• 公開(kāi)（公告）號(hào): CN102833169A
• 公開(kāi)（公告）日: 2012-12-19
• 發(fā)明（設(shè)計(jì)）人: 黃桂敏;周婭;劉斯韻
• 申請(qǐng)（專(zhuān)利權(quán)）人: 桂林電子科技大學(xué)
• 主分類(lèi)號(hào): H04L12/56
• 分類(lèi)號(hào): H04L12/56;H04L29/08
• 代理公司: 桂林市華杰專(zhuān)利商標(biāo)事務(wù)所有限責(zé)任公司 45112
• 代理人: 滕杰鋒

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

本發(fā)明涉及到互聯(lián)網(wǎng)中分布式資源的搜索與定位技術(shù)，主要涉及到一種在對(duì)等網(wǎng)絡(luò)中通過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)之間常數(shù)跳的網(wǎng)絡(luò)路由快速查找所需網(wǎng)絡(luò)資源的定位方法。

背景技術(shù)

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)和互聯(lián)網(wǎng)的高速發(fā)展，世界各地的人們都可以通過(guò)互聯(lián)網(wǎng)分享所需的資源，互聯(lián)網(wǎng)絡(luò)縮短了人與人之間的距離。然而，隨著互聯(lián)網(wǎng)應(yīng)用的不斷深入，日常生活中各種資源信息與互聯(lián)網(wǎng)的關(guān)系日益密切，人們對(duì)資源共享和資源交換的需求也越來(lái)越廣泛，為了滿足人們?nèi)找嬖鲩L(zhǎng)的資源共享與交流的需求，快速而又有效地定位目標(biāo)資源已成為人們迫切需要解決的問(wèn)題。對(duì)等網(wǎng)絡(luò)技術(shù)的產(chǎn)生和發(fā)展，在解決這一問(wèn)題上起到了積極的作用。對(duì)等網(wǎng)絡(luò)技術(shù)是上個(gè)世紀(jì)末發(fā)展起來(lái)的一種計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，它強(qiáng)調(diào)所有網(wǎng)絡(luò)節(jié)點(diǎn)（如計(jì)算機(jī)、數(shù)字終端等，簡(jiǎn)稱“節(jié)點(diǎn)”）都是對(duì)等的實(shí)體，每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)既可以是資源與服務(wù)的提供者，又可以是資源與服務(wù)的接受者。對(duì)等網(wǎng)絡(luò)技術(shù)與傳統(tǒng)網(wǎng)絡(luò)技術(shù)（如客戶端/服務(wù)器）不同，對(duì)等網(wǎng)絡(luò)技術(shù)擁有充分利用邊緣、閑雜、零碎的網(wǎng)絡(luò)、存儲(chǔ)和計(jì)算資源的能力，具有高度的擴(kuò)展性與容錯(cuò)性，它可以有效避免服務(wù)過(guò)載、資源瓶頸等問(wèn)題，在學(xué)術(shù)界、工業(yè)界、用戶中都受到廣泛關(guān)注和普遍歡迎。

現(xiàn)行的對(duì)等網(wǎng)絡(luò)技術(shù)，大多數(shù)采用分布式哈希表，采用這種技術(shù)的對(duì)等網(wǎng)絡(luò)沒(méi)有設(shè)置主控服務(wù)器，所有的網(wǎng)絡(luò)路由都由節(jié)點(diǎn)完成，其中每個(gè)節(jié)點(diǎn)只需要負(fù)責(zé)網(wǎng)絡(luò)中所知道的路由選擇、部分信息存儲(chǔ)與查詢，通過(guò)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的共同努力來(lái)完成整個(gè)網(wǎng)絡(luò)所需的路由選擇和信息存儲(chǔ)與查詢。分布式哈希表技術(shù)具有如下主要特點(diǎn)：

分布性：網(wǎng)絡(luò)中節(jié)點(diǎn)間沒(méi)有集中式和中央式的控制機(jī)制。

擴(kuò)展性：網(wǎng)絡(luò)可以擁有從幾十個(gè)節(jié)點(diǎn)到千萬(wàn)個(gè)節(jié)點(diǎn)不等規(guī)模，網(wǎng)絡(luò)具有較好的可擴(kuò)展性。

容錯(cuò)性：網(wǎng)絡(luò)在節(jié)點(diǎn)不斷加入、離開(kāi)、故障的動(dòng)態(tài)變化情況下，仍然能保證網(wǎng)絡(luò)可靠有效地工作。

現(xiàn)在大多數(shù)對(duì)等網(wǎng)絡(luò)協(xié)議都是采用分布式哈希表，例如Chord、Pastry、CAN、Kademlia等，其中最流行的是Kademlia協(xié)議，采用它的對(duì)等網(wǎng)絡(luò)應(yīng)用系統(tǒng)主要有：eMule、BitTorrent、BitComet、BitSpirit、迅雷、快車(chē)等。雖然現(xiàn)在大多數(shù)對(duì)等網(wǎng)絡(luò)協(xié)議在高動(dòng)態(tài)變化的網(wǎng)絡(luò)中擁有一定的分布性、擴(kuò)展性、容錯(cuò)性，但是它們?cè)诙ㄎ毁Y源的時(shí)候的查詢次數(shù)與網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量成正比，即：節(jié)點(diǎn)越多，查詢次數(shù)也就越多；節(jié)點(diǎn)越少，查詢次數(shù)也就越少。在一個(gè)大規(guī)模的網(wǎng)絡(luò)中，這些協(xié)議需要多次查詢才能找到目標(biāo)資源，在目標(biāo)資源查詢過(guò)程中耗費(fèi)大量的網(wǎng)絡(luò)帶寬資源，容易產(chǎn)生大量網(wǎng)絡(luò)流量，造成網(wǎng)絡(luò)局部擁塞現(xiàn)象的出現(xiàn)。

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

本發(fā)明的目的是為了克服上述現(xiàn)有技術(shù)的不足，提供一種常數(shù)跳對(duì)等網(wǎng)絡(luò)目標(biāo)資源定位方法，應(yīng)用于大規(guī)模的網(wǎng)絡(luò)中，能減少網(wǎng)絡(luò)目標(biāo)資源定位時(shí)的查詢的次數(shù)，實(shí)現(xiàn)在在高度動(dòng)態(tài)變化的互聯(lián)網(wǎng)中通過(guò)常數(shù)復(fù)雜度的路由過(guò)程就可以快速定位到網(wǎng)絡(luò)中分布式目標(biāo)資源，在大部分情況下只需要一次查詢就能完成目標(biāo)資源的定位，同時(shí)只需要很少網(wǎng)絡(luò)開(kāi)銷(xiāo)來(lái)定位資源和維護(hù)整個(gè)對(duì)等網(wǎng)絡(luò)。

為實(shí)現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案如下：

一種常數(shù)復(fù)雜度的對(duì)等網(wǎng)絡(luò)目的資源定位方法，其特征是，在對(duì)等網(wǎng)絡(luò)中，節(jié)點(diǎn)N1進(jìn)行資源定位的步驟包括：

1）節(jié)點(diǎn)N1在自己路由表中搜索距離所求資源最近的節(jié)點(diǎn)N2，然后節(jié)點(diǎn)N1向節(jié)點(diǎn)N2發(fā)送資源查詢的請(qǐng)求；

2）如果節(jié)點(diǎn)N2在線并且節(jié)點(diǎn)N2存儲(chǔ)有所求資源信息，則由節(jié)點(diǎn)N2發(fā)送所求資源信息給N1，完成資源定位，否則執(zhí)行步驟3），資源信息至少由資源標(biāo)識(shí)符ID和資源索引value組成，資源標(biāo)識(shí)符ID為對(duì)等網(wǎng)絡(luò)上資源的標(biāo)識(shí)符，需要保證每個(gè)資源的資源標(biāo)識(shí)符ID都是唯一的；資源索引value?是記錄擁有資源的節(jié)點(diǎn)信息的文件，節(jié)點(diǎn)信息指節(jié)點(diǎn)和資源的標(biāo)識(shí)符ID、網(wǎng)絡(luò)IP地址、網(wǎng)絡(luò)通訊使用的端口等信息；

3）如果節(jié)點(diǎn)N2在線，則由節(jié)點(diǎn)N2發(fā)送一個(gè)或多個(gè)最接近所求資源的節(jié)點(diǎn)信息給節(jié)點(diǎn)N1，讓節(jié)點(diǎn)N1更新自己的路由表；?

4）如果節(jié)點(diǎn)N1接收不到節(jié)點(diǎn)N2的返回信息，節(jié)點(diǎn)N1將從自己的路由表中搜索沒(méi)有搜索過(guò)的距離所求資源最近的節(jié)點(diǎn)N3，并向節(jié)點(diǎn)N3發(fā)送資源查詢的請(qǐng)求；

5）如果節(jié)點(diǎn)N2返回的信息中沒(méi)有所求資源信息，而只有節(jié)點(diǎn)信息，則節(jié)點(diǎn)N1從這些節(jié)點(diǎn)信息和路由表中選出沒(méi)有搜索過(guò)的距離所求資源最近的節(jié)點(diǎn)N3，并向節(jié)點(diǎn)N3發(fā)送資源查詢的請(qǐng)求；

6）節(jié)點(diǎn)N1將重復(fù)這個(gè)過(guò)程，直到定位到資源或者查詢過(guò)K個(gè)節(jié)點(diǎn)都沒(méi)有定位成功，則不再繼續(xù)向其他節(jié)點(diǎn)發(fā)送查詢資源的請(qǐng)求，其中，K為規(guī)定的常數(shù)，即查詢路由的跳數(shù)，其取值范圍為2至20；