[發(fā)明專(zhuān)利]P2P對(duì)等網(wǎng)絡(luò)中節(jié)點(diǎn)失效后的路由更新方法、設(shè)備及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 200710188100.1
• 申請(qǐng)日: 2007-11-22
• 公開(kāi)（公告）號(hào): CN101442479A
• 公開(kāi)（公告）日: 2009-05-27
• 發(fā)明（設(shè)計(jì)）人: 施廣宇;陳堅(jiān);龔皓
• 申請(qǐng)（專(zhuān)利權(quán)）人: 華為技術(shù)有限公司
• 主分類(lèi)號(hào): H04L12/56
• 分類(lèi)號(hào): H04L12/56;H04L12/28
• 代理公司: 北京同達(dá)信恒知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 黃志華

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

本發(fā)明涉及通信技術(shù)領(lǐng)域，尤其涉及P2P對(duì)等網(wǎng)絡(luò)中節(jié)點(diǎn)失效后的路由更新方法、設(shè)備及系統(tǒng)。

背景技術(shù)

P2P(Peer-to-Peer，表示對(duì)等體之間的一種對(duì)等關(guān)系)系統(tǒng)與傳統(tǒng)的客戶(hù)機(jī)/服務(wù)器模式系統(tǒng)不同，在對(duì)等體之間進(jìn)行操作，每個(gè)對(duì)等體(節(jié)點(diǎn))即P2P系統(tǒng)中每個(gè)實(shí)體可稱(chēng)為Peer，每一個(gè)Peer既可以為其他節(jié)點(diǎn)提供服務(wù)，又可以接受其他節(jié)點(diǎn)提供的服務(wù)。P2P系統(tǒng)可以按照其拓?fù)浣Y(jié)構(gòu)進(jìn)行分類(lèi)。一般分為：集中化拓?fù)?Centralized?Topology)、全分布式非結(jié)構(gòu)化拓?fù)?Decentralized?Unstructured?Topology)、全分布式結(jié)構(gòu)化拓?fù)?Decentralized?Structured?Topology，也稱(chēng)作DHT網(wǎng)絡(luò))和混合型拓?fù)洹?/p>

近幾年來(lái)，P2P網(wǎng)絡(luò)的主要拓?fù)浣Y(jié)構(gòu)為：結(jié)構(gòu)化拓?fù)銬HT(Distributed?Hash?Table，分布式哈希表)網(wǎng)絡(luò)。P2P網(wǎng)絡(luò)中的很大部分應(yīng)用都是基于DHT網(wǎng)絡(luò)所構(gòu)成的。在這些系統(tǒng)中，節(jié)點(diǎn)通過(guò)它的一些唯一屬性，如IP地址，哈希得到唯一標(biāo)識(shí)NodeId，標(biāo)識(shí)對(duì)應(yīng)的數(shù)據(jù)項(xiàng)以鍵值對(duì)<key，value>的方式表示，其中鍵key是對(duì)于數(shù)據(jù)項(xiàng)的索引，而值value可以是數(shù)據(jù)項(xiàng)的定位地址如IP或者URL。通過(guò)哈希賦予數(shù)據(jù)索引鍵以唯一標(biāo)識(shí)，并將此鍵對(duì)應(yīng)的鍵值對(duì)存儲(chǔ)到與此鍵標(biāo)識(shí)最鄰近的節(jié)點(diǎn)。查詢(xún)時(shí)，可以通過(guò)將查詢(xún)的鍵哈希得到唯一標(biāo)識(shí)，并通過(guò)此唯一標(biāo)識(shí)找到與之最鄰近的節(jié)點(diǎn)(此節(jié)點(diǎn)存儲(chǔ)了數(shù)據(jù)項(xiàng)所在的地址)。

另一方面，P2P系統(tǒng)同時(shí)也是一種自組織形態(tài)的網(wǎng)絡(luò)，在該網(wǎng)絡(luò)中，節(jié)點(diǎn)可以隨意加入或退出，這種隨意性會(huì)造成資源定位的不準(zhǔn)確和網(wǎng)絡(luò)的擾動(dòng)，網(wǎng)絡(luò)擾動(dòng)的程度大小直接影響路由發(fā)現(xiàn)方法的效率。網(wǎng)絡(luò)擾動(dòng)(Churn、fluctuation?of?network)包括節(jié)點(diǎn)的加入、退出、失敗、遷移、并發(fā)加入過(guò)程、網(wǎng)絡(luò)分割等。P2P網(wǎng)絡(luò)的DHT路由查找方法如何處理不同的網(wǎng)絡(luò)擾動(dòng)churn，將直接影響整個(gè)P2P網(wǎng)絡(luò)的路由效率和負(fù)載開(kāi)銷(xiāo)。

現(xiàn)有技術(shù)中給出如下兩種方式解決P2P網(wǎng)絡(luò)擾動(dòng)問(wèn)題：

現(xiàn)有技術(shù)一

在DHT網(wǎng)絡(luò)中解決churn問(wèn)題時(shí)，考慮三個(gè)重要因素：快速的替代節(jié)點(diǎn)、超時(shí)檢測(cè)和最近鄰居節(jié)點(diǎn)選擇。該技術(shù)對(duì)于網(wǎng)絡(luò)擾動(dòng)的直接對(duì)抗方法是：通過(guò)P2P?NodeId空間中的順序K個(gè)節(jié)點(diǎn)互相PING，來(lái)保持節(jié)點(diǎn)之間不斷連。

在P2P網(wǎng)絡(luò)的運(yùn)行過(guò)程中，每個(gè)節(jié)點(diǎn)每隔一段時(shí)間向它周邊順序K個(gè)節(jié)點(diǎn)發(fā)送PING維護(hù)信息，這順序K個(gè)節(jié)點(diǎn)接收到源節(jié)點(diǎn)所發(fā)過(guò)來(lái)的PING消息后，立刻反饋一個(gè)信息告知源節(jié)點(diǎn)自己正常存活，源節(jié)點(diǎn)的路由表不用做任何修改。而當(dāng)網(wǎng)絡(luò)中某節(jié)點(diǎn)失效時(shí)，其周邊的鄰居節(jié)點(diǎn)能夠通過(guò)這種主動(dòng)探測(cè)PING的方式來(lái)發(fā)現(xiàn)這種節(jié)點(diǎn)擾動(dòng)行為，找出失效節(jié)點(diǎn)，并廣播該失效信息給順序K個(gè)節(jié)點(diǎn)更新其路由表鏈接。

發(fā)明人在實(shí)現(xiàn)本發(fā)明的過(guò)程中，發(fā)現(xiàn)現(xiàn)有技術(shù)一存在如下不足：

現(xiàn)有技術(shù)一中，通過(guò)P2P?NodeId空間中的順序K個(gè)節(jié)點(diǎn)互相PING來(lái)保持節(jié)點(diǎn)之間不斷連，也就是說(shuō)，只有連續(xù)K個(gè)鄰居節(jié)點(diǎn)互相保持不斷連，維護(hù)信息只在K個(gè)鄰居節(jié)點(diǎn)間傳遞。當(dāng)網(wǎng)絡(luò)中存在節(jié)點(diǎn)失效行為時(shí)，由于路由表信息只能保持K段連續(xù)，因此在網(wǎng)絡(luò)中查找一個(gè)節(jié)點(diǎn)時(shí)，很可能會(huì)出現(xiàn)不同程度的“爬行”現(xiàn)象，即由于原本指向失效節(jié)點(diǎn)的peer節(jié)點(diǎn)路由表信息均失效，遠(yuǎn)方的節(jié)點(diǎn)只能通過(guò)再次遞歸查找的方式才能找到失效節(jié)點(diǎn)的替代節(jié)點(diǎn)。兩個(gè)節(jié)點(diǎn)之間的距離相隔越遠(yuǎn)，這個(gè)問(wèn)題就越嚴(yán)重，失效后節(jié)點(diǎn)間遞歸查找的次數(shù)也就越多。當(dāng)網(wǎng)絡(luò)中churn問(wèn)題很劇烈時(shí)，假如一條P2P路徑中的多個(gè)關(guān)鍵路由節(jié)點(diǎn)都失效了，那么路由表信息在網(wǎng)絡(luò)中的“爬行”現(xiàn)象將會(huì)十分明顯，節(jié)點(diǎn)在路由時(shí)必須通過(guò)逐K跳逐K跳來(lái)查找下一步路由。

并且，在P2P網(wǎng)絡(luò)中，churn現(xiàn)象和“爬行”行為還存在累計(jì)效應(yīng)，當(dāng)網(wǎng)絡(luò)中失效節(jié)點(diǎn)數(shù)目不斷遞增時(shí)，由于失效信息得不到有效廣播，大部分節(jié)點(diǎn)仍維持原有的失效路由表，而導(dǎo)致“爬行”的次數(shù)將會(huì)不斷增多，“爬行”的時(shí)間也越來(lái)越長(zhǎng)，最?lèi)毫拥那闆r下查找一個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度會(huì)達(dá)到O(N)次(N為P2P?Overlay中節(jié)點(diǎn)數(shù)目)，嚴(yán)重影響了P2P網(wǎng)絡(luò)的路由查找效率。

現(xiàn)有技術(shù)二