[發(fā)明專利]基于點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)的環(huán)模型及其路由算法

有效

• 申請(qǐng)?zhí)枺?/td>: 200910071909.5
• 申請(qǐng)日: 2009-04-29
• 公開(kāi)（公告）號(hào): CN101605094A
• 公開(kāi)（公告）日: 2009-12-16
• 發(fā)明（設(shè)計(jì)）人: 姚念民;邵美晶
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工程大學(xué)
• 主分類號(hào): H04L12/56
• 分類號(hào): H04L12/56;H04L12/46
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

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

本發(fā)明涉及的是P2P(Peer-to-Peer)網(wǎng)絡(luò)，也涉及P2P網(wǎng)絡(luò)的路由算法。

(二)背景技術(shù)

所謂P2P(Peer-to-Peer)網(wǎng)絡(luò)就是點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)，也稱為對(duì)等網(wǎng)絡(luò)。它是指 沒(méi)有中心服務(wù)器的控制，所有參與的節(jié)點(diǎn)地位都是平等的，每個(gè)節(jié)點(diǎn)可以在任 意時(shí)刻加入或退出P2P網(wǎng)絡(luò)。取消了客戶機(jī)與服務(wù)器之分，每個(gè)節(jié)點(diǎn)即可以是 客戶機(jī)，可以從別的節(jié)點(diǎn)處獲得服務(wù)，同時(shí)也是服務(wù)器，要向其他節(jié)點(diǎn)提供服 務(wù)。這種網(wǎng)絡(luò)模式能夠克服傳統(tǒng)C/S網(wǎng)絡(luò)模式的缺點(diǎn)，即使有很多節(jié)點(diǎn)同時(shí)請(qǐng) 求同一數(shù)據(jù)，也不會(huì)像C/S網(wǎng)絡(luò)模式那樣服務(wù)器會(huì)發(fā)生性能瓶頸。然而，P2P網(wǎng) 絡(luò)也有它自己的缺點(diǎn)。由于沒(méi)有中心服務(wù)器的控制，如何發(fā)現(xiàn)和定位資源就成 為P2P網(wǎng)絡(luò)發(fā)展的關(guān)鍵。在這個(gè)問(wèn)題的研究中，已經(jīng)有幾種優(yōu)秀的算法，如CAN、 Chord、Pastry、Tapestry等，但都存在著種種不足。如Chord算法沒(méi)有考慮物 理網(wǎng)絡(luò)和虛擬覆蓋網(wǎng)絡(luò)之間的差別，致使資源查詢速度緩慢，而用戶是無(wú)法容 忍一個(gè)查詢速度非常慢的系統(tǒng)的。因此提高P2P網(wǎng)絡(luò)資源定位速度就成為P2P 網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)問(wèn)題。本發(fā)明就是根據(jù)Chord算法的不足，提出一種新的 Chord模型來(lái)提高Chord算法的查詢速度。

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

本發(fā)明的目的在于提供一種可以提高Chord的查詢速度的基于P2P的Chord 模型。本發(fā)明的目的還在于提供一種能更好的滿足用戶對(duì)查詢速度的要求的基 于點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)的環(huán)模型的路由算法。

本發(fā)明的基于P2P的Chord模型由一種保留原Chord環(huán)的特性作為主要框 架結(jié)構(gòu)的inter?Chord和一種物理鄰近的節(jié)點(diǎn)組成的附屬于inter?Chord中的 某一個(gè)節(jié)點(diǎn)的環(huán)intra?Chord構(gòu)成；物理鄰近節(jié)點(diǎn)的RTT(Round?Trip?Time)滿 足事先設(shè)定的一個(gè)值threshold，只有兩個(gè)節(jié)點(diǎn)間的RTT值小于這個(gè)值的時(shí)候， 才能在一個(gè)intra?Chord環(huán)中；Intra?Chord與inter?Chord相交處的那個(gè)節(jié) 點(diǎn)為leader節(jié)點(diǎn)，它負(fù)責(zé)在intra?Chord和inter?Chord中進(jìn)行查詢，保證 整個(gè)網(wǎng)絡(luò)的連通，它還維護(hù)一個(gè)在intra?Chord中與自身有最大RTT值的節(jié)點(diǎn)； 每個(gè)intra?Chord中的節(jié)點(diǎn)都有最大個(gè)數(shù)的限制，當(dāng)達(dá)到了最大節(jié)點(diǎn)數(shù)時(shí)，再 有節(jié)點(diǎn)請(qǐng)求加入，則比較請(qǐng)求加入的節(jié)點(diǎn)與leader節(jié)點(diǎn)之間的RTT值和leader 節(jié)點(diǎn)維護(hù)的最大RTT值的大小；如果小于，刪除與leader節(jié)點(diǎn)有最大RTT值的 節(jié)點(diǎn)，加入新節(jié)點(diǎn)，被刪除的節(jié)點(diǎn)重新加入到inter?Chord中；如果大于，leader 節(jié)點(diǎn)拒絕新節(jié)點(diǎn)的加入請(qǐng)求，新節(jié)點(diǎn)加入到inter?Chord中，以后也可以成為 一個(gè)intra?Chord環(huán)的leader節(jié)點(diǎn)；其節(jié)點(diǎn)ID由inter?NodeID和intra?NodeID 兩部分組成，前一部分繼承原Chord算法節(jié)點(diǎn)ID的產(chǎn)生方法生成，用來(lái)在inter Chord中進(jìn)行查詢；另一部分由intra?Chord環(huán)上的leader節(jié)點(diǎn)分配，與leader 節(jié)點(diǎn)有共同的前綴，用于在intra?Chord環(huán)上查詢。

本發(fā)明的基于P2P的Chord模型的路由方法為：

節(jié)點(diǎn)首先加入到系統(tǒng)中形成一個(gè)Chord網(wǎng)絡(luò)，節(jié)點(diǎn)n加入到系統(tǒng)中的步驟 為：

(1)n首先發(fā)送一個(gè)廣播消息到系統(tǒng)中；

(2)如果是inter?Chord中的節(jié)點(diǎn)收到這個(gè)廣播，轉(zhuǎn)到步驟(3)，如果收 到廣播消息的是intra?Chord中的節(jié)點(diǎn)，不做任何處理；

(3)發(fā)送自己的IP地址給節(jié)點(diǎn)n，轉(zhuǎn)到步驟(4)；

(4)節(jié)點(diǎn)n收到一定數(shù)量的應(yīng)答消息后，向它收到的IP地址發(fā)送ping消 息來(lái)探測(cè)自己與其之間的RTT，探測(cè)完成后，n選擇一個(gè)有最小RTT 值的節(jié)點(diǎn)發(fā)送join請(qǐng)求；

(5)收到加入請(qǐng)求的節(jié)點(diǎn)查看自己的intra?Chord中節(jié)點(diǎn)數(shù)是否達(dá)到預(yù)先 設(shè)定的最大值，如果達(dá)到最大值，轉(zhuǎn)到步驟(6)，否則，轉(zhuǎn)到步驟(9)；

(6)比較n與自己之間的RTT值和自己維護(hù)的那個(gè)最大RTT值，如果小于， 轉(zhuǎn)到步驟(7)，如果大于，轉(zhuǎn)到步驟(8)；

(7)刪除與自己有最大RTT值的節(jié)點(diǎn)，被刪除的節(jié)點(diǎn)重新執(zhí)行加入到系統(tǒng) 中的過(guò)程，轉(zhuǎn)到步驟(9)；