結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)路由機(jī)制關(guān)鍵技術(shù)研究.pdf

1、結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)是一種采用純分布式的消息傳遞機(jī)制和根據(jù)關(guān)鍵字進(jìn)行查找的定位服務(wù)模型，目前在分布式存儲(chǔ)、應(yīng)用層多播、文件共享等領(lǐng)域已經(jīng)得到廣泛應(yīng)用。結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)路由算法研究面臨許多問(wèn)題，例如狀態(tài)和效率的折衷、拓?fù)涫洹⒉樵?xún)熱點(diǎn)、結(jié)點(diǎn)異構(gòu)等，如何解決這些問(wèn)題具有重要意義。本文針對(duì)結(jié)點(diǎn)異構(gòu)、查詢(xún)熱點(diǎn)、降低系統(tǒng)負(fù)載等關(guān)鍵技術(shù)問(wèn)題進(jìn)行了較為深入的研究，論文主要包括以下工作： (1)普遍認(rèn)為在結(jié)構(gòu)化P2P協(xié)議中實(shí)現(xiàn)能力感知會(huì)增加網(wǎng)絡(luò)開(kāi)銷(xiāo)，如

2、何建立高效、低開(kāi)銷(xiāo)的能力感知協(xié)議具有重要意義。分析了傳統(tǒng)的結(jié)點(diǎn)通過(guò)周期性交換路由表信息實(shí)現(xiàn)能力感知的算法，該算法收斂時(shí)間長(zhǎng)且不可避免增大網(wǎng)絡(luò)開(kāi)銷(xiāo)。提出一種高效的能力感知協(xié)議-HeteroChord，HeteroChord協(xié)議在結(jié)點(diǎn)的路由表建立算法、更新算法、路由表維護(hù)算法中實(shí)現(xiàn)能力感知。HeteroChord協(xié)議在新結(jié)點(diǎn)加入時(shí)即可計(jì)算出需要更新的其他結(jié)點(diǎn)，能力感知速度快、效率高。實(shí)驗(yàn)結(jié)果表明，建立同樣大小的網(wǎng)絡(luò)，HeteroChord中

3、結(jié)點(diǎn)更新算法產(chǎn)生的總開(kāi)銷(xiāo)遠(yuǎn)小于Chord；在動(dòng)態(tài)環(huán)境下，HeteroChord具有比Chord更小的維護(hù)開(kāi)銷(xiāo)。 (2)以HeteroChord為基礎(chǔ)建立了一種虛擬雙層結(jié)構(gòu)化模型Vring，Vring的外層是由所有結(jié)點(diǎn)組建的結(jié)構(gòu)化HeteroChord網(wǎng)絡(luò)，內(nèi)層是由超級(jí)結(jié)點(diǎn)組建的Chord網(wǎng)絡(luò)。Vring與目前典型的雙層結(jié)構(gòu)化網(wǎng)絡(luò)模型不同的是：超級(jí)結(jié)點(diǎn)具有和普通結(jié)點(diǎn)相同的路由表大小，僅比普通結(jié)點(diǎn)多維護(hù)一個(gè)超級(jí)葉子結(jié)點(diǎn)集，超級(jí)結(jié)點(diǎn)路

4、由表維護(hù)簡(jiǎn)單；單個(gè)超級(jí)結(jié)點(diǎn)失敗不會(huì)造成其他結(jié)點(diǎn)脫離網(wǎng)絡(luò)，不存在單點(diǎn)故障。建立了三種Vring的簡(jiǎn)單應(yīng)用系統(tǒng)，通過(guò)實(shí)驗(yàn)測(cè)試了基于本地索引的非DHT查找方式的數(shù)據(jù)共享系統(tǒng)的查詢(xún)特征。 (3)P2P系統(tǒng)是一種分布式系統(tǒng)，降低系統(tǒng)負(fù)載對(duì)提高P2P系統(tǒng)的擴(kuò)展性具有重要意義。目前結(jié)構(gòu)化P2P協(xié)議主要利用緩存方法解決查詢(xún)熱點(diǎn)問(wèn)題，這些緩存方法對(duì)數(shù)據(jù)緩存后的收益無(wú)法預(yù)測(cè)，是一種較盲目的緩存，往往導(dǎo)致系統(tǒng)負(fù)載加重。提出一種結(jié)構(gòu)化P2P協(xié)議中的緩存

5、計(jì)算模型，該模型以降低系統(tǒng)負(fù)載為目標(biāo)，結(jié)點(diǎn)采用一種文件訪問(wèn)統(tǒng)計(jì)方法跟蹤查詢(xún)本地文件的消息途經(jīng)鄰居結(jié)點(diǎn)的歷史次數(shù)，根據(jù)文件訪問(wèn)歷史統(tǒng)計(jì)記錄預(yù)測(cè)緩存該文件到鄰居結(jié)點(diǎn)可能減少的查詢(xún)負(fù)載，然后與緩存后可能產(chǎn)生的更新開(kāi)銷(xiāo)對(duì)比，進(jìn)而確定是否緩存文件到相應(yīng)的鄰居結(jié)點(diǎn)。實(shí)驗(yàn)表明，該緩存計(jì)算模型可以有效降低系統(tǒng)負(fù)載。 (4)僅采用虛擬服務(wù)器、多Hash技術(shù)或復(fù)制不能解決Zipf查詢(xún)環(huán)境下的負(fù)載均衡問(wèn)題。提出一種自適應(yīng)負(fù)載均衡方法，方法采用一種被動(dòng)

6、式結(jié)點(diǎn)負(fù)載統(tǒng)計(jì)方法生成局部負(fù)載視圖；采用一種文件訪問(wèn)統(tǒng)計(jì)方法生成局部文件訪問(wèn)視圖；當(dāng)系統(tǒng)內(nèi)結(jié)點(diǎn)負(fù)載存在差異，重載結(jié)點(diǎn)把指向自身的邏輯鏈路遷移至指向局部負(fù)載視圖中的輕載結(jié)點(diǎn)，通過(guò)減小重載結(jié)點(diǎn)入度和增加輕載結(jié)點(diǎn)入度來(lái)減小結(jié)點(diǎn)間負(fù)載差異；當(dāng)結(jié)點(diǎn)的請(qǐng)求負(fù)載較高時(shí)，通過(guò)局部文件訪問(wèn)視圖計(jì)算需要緩存的熱點(diǎn)文件及目標(biāo)結(jié)點(diǎn)，降低承載熱點(diǎn)文件的結(jié)點(diǎn)的請(qǐng)求負(fù)載。實(shí)驗(yàn)表明，在用戶查詢(xún)服從Zipf分布的環(huán)境下，自適應(yīng)負(fù)載均衡方法可使結(jié)點(diǎn)負(fù)載達(dá)到較好的均衡。