（計(jì)算機(jī)應(yīng)用技術(shù)專(zhuān)業(yè)論文）基于小世界特性的p2p網(wǎng)絡(luò)搜索優(yōu)化技術(shù)的研究.pdf

c iii 心 j l 本人聲 作及取得的研究成果 據(jù)我所知 除了文中特別加以標(biāo)注和致謝的地 方外 論文中不包含其他入已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果 也不包含 為獲得電子科技大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的材料 與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明 確的說(shuō)明并表示謝意 簽名 日期 z 年f 月可日 論文使用授權(quán) 本學(xué)位論文作者完全了解電子科技大學(xué)有關(guān)保留 使用學(xué)位論文 的規(guī)定 有權(quán)保留并向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和磁 盤(pán) 允許論文被查閱和借閱 本人授權(quán)電子科技大學(xué)可以將學(xué)位論文 的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索 可以采用影印 縮印或 掃描等復(fù)制手段保存 匯編學(xué)位論文 保密的學(xué)位論文在解密后應(yīng)遵守此規(guī)定 簽名 掣詈簍 二 主群 f 1 卜 摘要 摘要 隨著信息技術(shù)的發(fā)展以及網(wǎng)絡(luò)的普及 網(wǎng)絡(luò)中的許多資源都需要共享 傳統(tǒng) c s 模式的架構(gòu)幾乎不能承受住高并發(fā)量的客戶(hù)訪問(wèn) 而且伴隨共享資源的增多 對(duì)服務(wù)器的存儲(chǔ)能力也提出了嚴(yán)峻的挑戰(zhàn) 在對(duì)等網(wǎng)絡(luò)中 每個(gè)結(jié)點(diǎn)參與了任務(wù) 的執(zhí)行 解決了集中式網(wǎng)絡(luò)的單點(diǎn)失效和網(wǎng)絡(luò)帶寬的利用率 在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中 資源搜索的效率是1 0 9 n 雖然這種方式比集中式c s 模式的效率要低 但是它解決了集中式網(wǎng)絡(luò)中對(duì)中心結(jié)點(diǎn)的依賴(lài)性 那么怎樣提 高現(xiàn)有的結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)的資源搜索效率成了一個(gè)研究的方向 本文通過(guò)對(duì)小世 界網(wǎng)絡(luò)的分析 發(fā)現(xiàn)小世界網(wǎng)絡(luò)具有縮短整個(gè)網(wǎng)絡(luò)直徑的特點(diǎn) 所以如果能夠在 結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中構(gòu)建小世界網(wǎng)絡(luò) 那么資源搜索的效率就會(huì)因?yàn)樾∈澜缇W(wǎng)絡(luò)的 特性而得到很大程度的提高 本文因此提出了在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中建立具有小世 界網(wǎng)絡(luò)特性的算法 并以數(shù)學(xué)的理論嚴(yán)格地證明了算法的正確性和優(yōu)越性 算法 的思想在于利用數(shù)據(jù)包路由的過(guò)程 按照一定的概率重建途經(jīng)的結(jié)點(diǎn)的短鏈鏈接 使得整個(gè)對(duì)等網(wǎng)絡(luò)具有小世界網(wǎng)絡(luò)的特性 從而降低了數(shù)據(jù)包在路由過(guò)程中轉(zhuǎn)發(fā) 的跳數(shù) 因此提高了資源搜索的效率 而且整個(gè)建立的過(guò)程需要比較小的額外開(kāi) 銷(xiāo) 同時(shí) 在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中 為了對(duì)資源進(jìn)行搜索 在應(yīng)用層建立了一個(gè)邏 輯結(jié)構(gòu) 那么當(dāng)結(jié)點(diǎn)在對(duì)多個(gè)結(jié)點(diǎn)選擇時(shí) 便會(huì)按照這種邏輯上的拓?fù)浣Y(jié)構(gòu)進(jìn)行 結(jié)點(diǎn)的選擇 但是邏輯上結(jié)點(diǎn)之間的距離并不能代表物理網(wǎng)絡(luò)中結(jié)點(diǎn)之間的距離 即邏輯上相鄰的結(jié)點(diǎn)在實(shí)際的物理網(wǎng)絡(luò)中并不是相鄰的結(jié)點(diǎn) 甚至可能是相隔非 常遠(yuǎn)的結(jié)點(diǎn) 這便造成了邏輯層上結(jié)點(diǎn)之間傳輸數(shù)據(jù)所表現(xiàn)的高效性在實(shí)際的物 理網(wǎng)絡(luò)中卻是效率最低的 本文提出了對(duì)結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)進(jìn)行物理區(qū)域劃分的思 想 將整個(gè)對(duì)等網(wǎng)絡(luò)在物理拓?fù)涞膶用鎰澐譃椴煌膮^(qū)域 然后當(dāng)結(jié)點(diǎn)加入網(wǎng)絡(luò) 時(shí) 首先確定結(jié)點(diǎn)所屬的區(qū)域并保存該信息 當(dāng)有結(jié)點(diǎn)需要對(duì)多個(gè)結(jié)點(diǎn)選擇時(shí) 便可以根據(jù)每個(gè)結(jié)點(diǎn)所保存的區(qū)域信息來(lái)判斷結(jié)點(diǎn)之間的相鄰程度 找出距離源 結(jié)點(diǎn)最為接近的結(jié)點(diǎn)作為目標(biāo)結(jié)點(diǎn) 從而解決了對(duì)等網(wǎng)絡(luò)中結(jié)點(diǎn)在邏輯應(yīng)用層的 結(jié)構(gòu)與物理網(wǎng)絡(luò)中的結(jié)構(gòu)的矛盾 有效地提高了結(jié)點(diǎn)之間數(shù)據(jù)傳輸?shù)男?關(guān)鍵詞 小世界網(wǎng)絡(luò) 對(duì)等網(wǎng)絡(luò) 區(qū)域向量 l s 鋤et i m e t l l es h a r e dr e s o u r c e s盯ec o n s t 鋤n y i i l c r e 嬲i 1 1 9 w m c hp o s e s as e v e r c c h a l l e n g et 0t l l ec 印a c i t yo f 廿l es e r y 既h 1p e e rt op e e rn 咖o r k e a c hn o d ej o i n si n 廿l e e x e 伽t i o no ft 勰l w k c hr c s o i v e st l l ef a i l u r eo ft l l ec e l l t e rn o d e 吼de 1 1 1 a r g em e u t i l i z a t i o no f b a n d w i d m i i lm es 仃u c t u r e dp e e rt op e 盱n e t l o r k 也eq u e 巧e 街c i e n c yi sl o g n v h i c hi sl e s s e 伍c i e n tn l 鋤m et r a l d i t i o n a l c sm o d e l b u ti th 嬲r e s 0 1 v e dm ed 印e 1 1 d e l l c e t 0 吐l e c e n t e rn o d ei nc o n c e n 仃a t e dn 咖o f k nh a sb e c o m ear e s e a r c hd i r e c t i o nt oh o wt 0 i i l l p r 0 v e 廿l ee x i s t i n gq u e 叮e 壤c i 朗c yi nt l l es 仃u c 唰p e e rt 0p e e rn e t i r o r k t h r o u g l l t l l e 鋤a l y s i st o 也es m a l lw o 訂d i ti sf o l l l l d 也a tm e 湖a 1 1n e t o r kh 觴t 1 1 ec h a r a c t i 耐s t i co f r e d u c i n gt l l ed i a m e t e ro fm en e 礎(chǔ) s oi fw ec 鋤b u i l da 跚1 a l ln e t w o r ki n n l e s 仃u c t u r e dp e 盱t op e e rn e 鉚o r k 廿1 eq u e d re 伍c i c i l c yw i l lb e i m p r o v e d 伊e a t l y 1 1 1o r d e rt 0e n l a 瑪em ee 伍c i 肌c yo fm es e a r c h w ee s t a b l i s ha1 0 百c a ls 仇l c 臼毗 ei n m e a p p l i c a t i o nl a y 既w h e nan o d ec h o o s e 廿l ea p p r o p d a t eo n e 丘 0 mm u l t i p l en o d e s i t w i uc o n s i d 日也el o 西c a lr e l a t i o n s l l i pb e 觚e 饑 l en o d e s u s u a l l ym el o 百c a ld i s t 吼 b e t w e 饑t 1 1 en o d e sd o n l tr e p r e s 吼tp h y s i c a ld i s t a n c e w k c hi 1 1 d i c a t e st 1 1 a tl o 百c a l l y a d j a c e l l tn o d e sm a yb e 陸a p 砒i nt 1 1 ea a c u a l lp h y s i c a ln e 嘶o r k 砧lo ft l l e s e 們l lc a u s e 1 a tt 1 1 ea c t u a le 伍c i 髓c yi i lp h y s i c a ln e m o r ki si i l c o n s i s t e n t 舶ml o 西a 1p e r f 0 r m 觚c e h l 也i sp 印 m er e 百o no ft l l ep e 盯t 0p e e rn e 鉚o r k 謝1 lb e 印d e v i d e d n l 既an o d ej o i n s 廿l e n 咖o r k t 1 1 en o d ef i n d si t sr e 西o na n ds a v em ei n f 0 肌a t i o n w h n o d en e c dt oc h o o s e t l l ea p i p r o p n a t en o d e 丘 o mo m e rn o d e s i tw i l lc h o o s em ep r o p 盱n o d eb 觴e do nt l l e a d j a c e n te x t e n tb e m e n o d e st 0e i l l l a l l c e 廿l ee f f i c i 鋤c yo fd a t a 的n s m i s s i o n 刪c h s o l v e st h ec o n 仃a d i c i o nb e 似e 鋤n l ea p p l i c a t i o n1 a y e r 粕dt h ep h y s i c a l1 a y 既 k e yw o r d s s m a ll w o r l dn e t w o r k s p e e rt op e e rn e t w o r k r e g io n a lv e c t o r 一 第 1 2 研究現(xiàn)狀 3 1 2 1 完全分布式非結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò) 4 1 2 2 完全分布式結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò) 6 1 2 3 混合式p 2 p 網(wǎng)絡(luò) 7 1 3 研究目的和內(nèi)容 8 1 4 論文結(jié)構(gòu) 1 0 1 5 本章小結(jié) 1 1 第二章相關(guān)算法分析 1 2 2 1p 2 p 的搜索技術(shù) 1 2 2 2c h o r d l3 2 3 c j m 1 6 2 4 i a p e s 缸y 17 2 5 k a z a a 18 2 6 本章小結(jié) 18 第三章對(duì)等網(wǎng)絡(luò)中s m a u w o r m 的構(gòu)造算法設(shè)計(jì) 2 0 3 1 問(wèn)題探索 2 0 3 2 s m a l l w o 訂d 特性分析 2 1 3 3 對(duì)等網(wǎng)絡(luò)中s m a l l w o r l d 的構(gòu)造 2 5 3 4 算法設(shè)計(jì) 2 7 3 5 搜索過(guò)程 3 0 3 6 算法的正確性證明 3 2 3 7 本章小結(jié) 3 5 第四章對(duì)等網(wǎng)絡(luò)中拓?fù)涫涞慕鉀Q方案 3 8 4 1 問(wèn)題探索 3 8 4 2 界標(biāo)分區(qū)的分析 4 0 4 3 對(duì)等網(wǎng)絡(luò)中分區(qū)的構(gòu)造 4 3 l l i 目錄 4 4 核心算法設(shè)計(jì) 4 7 4 5 本章小結(jié) 5 0 第五章實(shí)驗(yàn)分析 5 2 5 1 實(shí)驗(yàn)平臺(tái)的搭建 5 2 5 2 對(duì)等網(wǎng)絡(luò)中構(gòu)建s m a l l w o r l d 的優(yōu)越性 5 2 5 3 對(duì)等網(wǎng)絡(luò)中區(qū)域劃分的可行性 5 6 5 4 本章小結(jié) 6 0 第六章總結(jié)與展望 6 1 6 1 總結(jié) 6 1 6 2 展望 6 3 致謝 6 4 參考文獻(xiàn) 6 5 在校期間研究成果 6 9 第一章引言 1 1 研究背景 第一章引言 網(wǎng)絡(luò)資源的共享給予了對(duì)等網(wǎng)絡(luò)的存在價(jià)值和意義 它解決了當(dāng)今互聯(lián)網(wǎng)發(fā) 展的所遇到的一些問(wèn)題 例如 怎樣在網(wǎng)絡(luò)中能夠高效地提高資源的共享率 并 且能夠很大程度上的提高用戶(hù)這種需求的響應(yīng)時(shí)間 這對(duì)于網(wǎng)絡(luò)的應(yīng)用來(lái)說(shuō)是一 個(gè)非常具有挑戰(zhàn)的意義 的確計(jì)算機(jī)的發(fā)展是隨著大家所熟知的摩爾定理在默默 地提高著計(jì)算機(jī)的性能 但是計(jì)算機(jī)的性能不管怎么提高也是隨著應(yīng)用的需求的 情況下才得以提高的 而且通常情況下 需求都是首先提出 然后才相應(yīng)的去想 辦法去解決這些問(wèn)題 那么怎樣以一種方法可以緩解這種問(wèn)題昵 眾所周知 整 個(gè)互聯(lián)網(wǎng)上有豐富的計(jì)算機(jī)資源和網(wǎng)絡(luò)帶寬資源 那么如果將這些資源加以整合 然后將要完成的任務(wù)分別變成一些的小的任務(wù)模塊 分別將這些小模塊分發(fā)給這 些閑散的計(jì)算機(jī) 讓它們?nèi)ソ鉀Q這個(gè)問(wèn)題 那么便可以大大的提高計(jì)算機(jī)的資源 利用率 而且也解決了對(duì)某一種超級(jí)計(jì)算機(jī)資源的依賴(lài)和所有網(wǎng)絡(luò)資源的利用 分布式網(wǎng)絡(luò)就是這種情況下應(yīng)運(yùn)而生的 其中對(duì)等網(wǎng)絡(luò)就是其中的一種 它讓整 個(gè)網(wǎng)絡(luò)中的計(jì)算機(jī)都被調(diào)動(dòng)起來(lái) 統(tǒng)一地相互協(xié)作地完成一個(gè)任務(wù) l 卅 在對(duì)等式網(wǎng)絡(luò)中 每一臺(tái)網(wǎng)絡(luò)中的計(jì)算機(jī)之間沒(méi)有所謂的主次之分 各自在 從網(wǎng)絡(luò)上獲取資源的同時(shí)也在為網(wǎng)絡(luò)中的其它計(jì)算機(jī)提供服務(wù) 這種互惠互利的 思想完整地被用在了對(duì)等網(wǎng)絡(luò)中 這便變相的調(diào)動(dòng)了網(wǎng)絡(luò)中的所有參與的計(jì)算機(jī) 使他們齊心協(xié)力地為整個(gè)網(wǎng)絡(luò)中的計(jì)算機(jī)提供服務(wù) 這種 人人為我 我為人人 的思想將資源的利用率得到了極大的提高 同時(shí) 傳統(tǒng)集中式網(wǎng)絡(luò)應(yīng)用中的對(duì)超 級(jí)計(jì)算機(jī)的依賴(lài)性 因?yàn)檫@種模式的網(wǎng)絡(luò)的產(chǎn)生而得到了解決 而且這種方式可 以解決核心骨干網(wǎng)絡(luò)的帶寬可以得到更大用處的利用 因?yàn)閭鹘y(tǒng)方式的集中式的 網(wǎng)絡(luò)中 客戶(hù)端為了獲取資源必須從處于遠(yuǎn)方的服務(wù)器上的資源經(jīng)過(guò)骨干網(wǎng)絡(luò)傳 輸才能得到 那么如果同時(shí)同一個(gè)區(qū)域的計(jì)算機(jī)對(duì)這樣的資源的請(qǐng)求 就會(huì)造成 這種資源的重復(fù)的傳輸 相反 如果采用對(duì)等網(wǎng)絡(luò) 那么結(jié)點(diǎn)便會(huì)從周?chē)Y(jié)點(diǎn)獲 取相應(yīng)的資源進(jìn)行數(shù)據(jù)的傳輸 從而減小了骨干網(wǎng)絡(luò)的壓力 增大了邊緣網(wǎng)絡(luò)中 的帶寬的利用率 5 8 對(duì)等網(wǎng)絡(luò)的另外一個(gè)優(yōu)勢(shì)是在對(duì)等網(wǎng)絡(luò)中 整個(gè)對(duì)等網(wǎng)絡(luò)中有一個(gè)應(yīng)用層的 電子科技大學(xué)碩士學(xué)位論文 結(jié)構(gòu) 9 這個(gè)結(jié)構(gòu)是按照某種方式生成的 比如高位的h a s h 1 0 的方式 這樣當(dāng)網(wǎng) 絡(luò)中有資源需要共享時(shí) 首先將該資源通過(guò)這種h 砒的方式將這些資源放置在距 離該資源i d 最為接近的結(jié)點(diǎn)上 這樣當(dāng)網(wǎng)絡(luò)中的結(jié)點(diǎn)在查詢(xún)這個(gè)資源時(shí) 就可以 根據(jù)這種放置的關(guān)系和這個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)行搜索 相對(duì)于無(wú)結(jié)構(gòu)式的對(duì)等網(wǎng)絡(luò)的 洪泛式搜索 搜索的效率提高了很多 而且這種方式對(duì)于結(jié)點(diǎn)的加入或者退出 都可以很容易地進(jìn)行擴(kuò)展和調(diào)整 目前基于這種思路的結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)的路由算 法也相應(yīng)的出現(xiàn) 比如 c h o r d 1 1 1 t a p e s 時(shí) 1 2 1 p a s d l 3 這些路由算法的核心 都是基于一種d h t 1 4 的方式 即分布式哈希表的方式 讓整個(gè)網(wǎng)絡(luò)中所有結(jié)點(diǎn)和 共享的資源都被部署在這個(gè)很大的h a s h 表上面 然后根據(jù)不同的規(guī)則進(jìn)行劃分和 路由 通常這種方式構(gòu)成的對(duì)等網(wǎng)絡(luò)中 路由的跳數(shù)都在o o g n 其中n 為該對(duì) 等網(wǎng)絡(luò)中結(jié)點(diǎn)的總個(gè)數(shù) 目前 因?yàn)閷?duì)等網(wǎng)絡(luò)的這些有利的條件和優(yōu)勢(shì) 在實(shí)際的網(wǎng)絡(luò)應(yīng)用 對(duì)等網(wǎng) 絡(luò)的應(yīng)用隨處可見(jiàn) 比如最為熟悉的網(wǎng)絡(luò)下載工具中的b t 和電驢以及迅雷 這些 都是利用了對(duì)等網(wǎng)絡(luò)最為基本的核心的思想 人人為我 我為人人 它們這種資 源共享的方式正體現(xiàn)了對(duì)等網(wǎng)絡(luò)的優(yōu)良特性 在對(duì)等網(wǎng)絡(luò)中 結(jié)點(diǎn)之間通過(guò)互相知道周?chē)徑慕Y(jié)點(diǎn)的消息 那么正是利 用這方面的條件下 網(wǎng)絡(luò)中的數(shù)據(jù)包在轉(zhuǎn)發(fā)的過(guò)程中 每一個(gè)結(jié)點(diǎn)都會(huì)通過(guò)自身 所知道的網(wǎng)絡(luò)中的鄰近的結(jié)點(diǎn)信息進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā) 從而保證消息包的正確到 達(dá) 這與傳統(tǒng)的計(jì)算機(jī)網(wǎng)絡(luò)中的網(wǎng)絡(luò)層的路由一樣 但是 這種轉(zhuǎn)發(fā)的效率還能 夠得到提高嗎 通過(guò)對(duì)小世界網(wǎng)絡(luò)中的短鏈存在效應(yīng)的影響 可以發(fā)現(xiàn) 如果在 結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中建立小世界網(wǎng)絡(luò) 那么在轉(zhuǎn)發(fā)數(shù)據(jù)包的時(shí)候 同時(shí)也利用這個(gè) 特性 那么數(shù)據(jù)的轉(zhuǎn)發(fā)效率將會(huì)得到很大的提高 本文中的第三章就是基于這種 思路的影響下 構(gòu)造出了怎樣在基于c h o r d 路由算法的條件下構(gòu)造出這種特性的 網(wǎng)絡(luò) 同時(shí) 大家都知道 在對(duì)等式網(wǎng)絡(luò)中 結(jié)點(diǎn)之間在應(yīng)用層面有一個(gè)邏輯的 結(jié)構(gòu) 而且大部分的考慮的因素都會(huì)基于這種邏輯的結(jié)構(gòu)進(jìn)行分析 那么這就可 能會(huì)造成在實(shí)際應(yīng)用中 這種應(yīng)用層面的結(jié)構(gòu)和實(shí)際的物理結(jié)構(gòu)的異構(gòu)性所帶來(lái) 的性能的影響 1 5 0 6 例如 當(dāng)結(jié)點(diǎn)之間需要傳輸數(shù)據(jù) 而此時(shí)有多個(gè)結(jié)點(diǎn)有這個(gè) 資源 其中有一個(gè)結(jié)點(diǎn)是該結(jié)點(diǎn)的物理鄰居結(jié)點(diǎn) 其他結(jié)點(diǎn)都是它的遠(yuǎn)程結(jié)點(diǎn) 但是邏輯結(jié)構(gòu)上 這種關(guān)系剛好反過(guò)來(lái) 那么此時(shí) 如果結(jié)點(diǎn)按照應(yīng)用層面的結(jié) 構(gòu)選擇了遠(yuǎn)程結(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸時(shí) 那么結(jié)點(diǎn)之間的數(shù)據(jù)的傳輸將會(huì)大大地打折 扣 本文就提出了一種對(duì)結(jié)點(diǎn)進(jìn)行分區(qū)的思想 將每一個(gè)結(jié)點(diǎn)的物理位置進(jìn)行劃 分 為以后結(jié)點(diǎn)的選擇中提供選擇的依據(jù) 第四章就是基于這種思路 完整地描 2 第一章引言 述了怎樣對(duì)結(jié)點(diǎn)進(jìn)行分區(qū)的思想和結(jié)點(diǎn)的選擇的方法 1 2 研究現(xiàn)狀 在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中 每個(gè)結(jié)點(diǎn)的的作用消除了普通網(wǎng)絡(luò)中依賴(lài)部分結(jié)點(diǎn)的 依賴(lài)性 同時(shí)也將網(wǎng)絡(luò)中邊緣網(wǎng)絡(luò)上的帶寬的利用率得到了有效地利用 隨著對(duì) 等網(wǎng)絡(luò)的應(yīng)用的不斷深入 學(xué)者對(duì)于該技術(shù)的研究也在不斷的深化過(guò)程中 伴隨 著這些研究 相應(yīng)的對(duì)等網(wǎng)絡(luò)也經(jīng)歷了多個(gè)發(fā)展階段 通常可以將對(duì)等網(wǎng)絡(luò)的發(fā) 展劃分為這么幾個(gè)過(guò)程 集中式p 2 p 網(wǎng)絡(luò) 完全分布式非結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò) 完全分布 式結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò) 混合式p 2 p 網(wǎng)絡(luò) 這些結(jié)構(gòu)的對(duì)等網(wǎng)絡(luò)也有相應(yīng)的商業(yè)的產(chǎn) 物 比如曾經(jīng)流行一時(shí)的音樂(lè)共享軟件n a p s t d r 7 1 因?yàn)榘鏅?quán)的問(wèn)題最終面臨倒閉 國(guó)外而且也有許多這些方面的研究和應(yīng)用 比如國(guó)外的o c e a i l s t o r e 系統(tǒng)等 國(guó)內(nèi)也 有不少對(duì)等網(wǎng)絡(luò)的產(chǎn)物 比如商業(yè)化的p p l i v e 和華中科大的a n y s e e 視屏直播系統(tǒng) 北京大學(xué)的m a z e 文件共享系統(tǒng)等 圖l 1 集中式p 2 p 網(wǎng)絡(luò) 集中式的p 2 p 網(wǎng)絡(luò)如圖1 1 通過(guò)一個(gè)索引服務(wù)器和若干終端結(jié)點(diǎn)以一種星型邏 輯的結(jié)構(gòu)所構(gòu)成 在集中式p 2 p 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中 中央索引服務(wù)器存放資源文件 的索引信息 而終端結(jié)點(diǎn)才真正的保存資源文件 這樣每當(dāng)終端結(jié)點(diǎn)需要某個(gè)資 源的時(shí)候 終端結(jié)點(diǎn)便通過(guò)與索引服務(wù)器通信 查詢(xún)此資源文件所在的客戶(hù)端的 位置 一旦獲取了資源的位置信息后 客戶(hù)端便與資源所在的客戶(hù)端進(jìn)行通訊 從而獲取該資源文件 因此中央服務(wù)器只是起著供客戶(hù)端查詢(xún)資源的作用 并沒(méi) 有真正地存儲(chǔ)所需要的資源文件 而且客戶(hù)端不僅與服務(wù)器端進(jìn)行通訊還要和其 它客戶(hù)端進(jìn)行通訊以便得到所需要的資源文件 集中式的p 2 p 的不足仍然和傳統(tǒng) 3 電子科技大學(xué)碩士學(xué)位論文 的c s 模式一樣 終端結(jié)點(diǎn)非常依賴(lài)中央索引服務(wù)器 同樣存在單點(diǎn)失效的問(wèn)題 和性能瓶頸的問(wèn)題 1 8 19 1 而傳統(tǒng)的c s 模型中如圖1 2 服務(wù)器上擁有整個(gè)網(wǎng)絡(luò)所需要的資源文件 當(dāng) 客戶(hù)端需要資源時(shí) 客戶(hù)端首先和服務(wù)器進(jìn)行交互 當(dāng)服務(wù)器查詢(xún)本機(jī)的資源和 授權(quán)以后便將資源傳送給客戶(hù)端 這種架構(gòu)就說(shuō)明 服務(wù)器端必須全天候2 4 小時(shí) 的正常運(yùn)作 否則整個(gè)對(duì)外提供的服務(wù)將會(huì)中斷 而且這種結(jié)構(gòu)也決定了服務(wù)器 必須有容納所有客戶(hù)端需要的資源的容量和足夠的計(jì)算能力 帶寬能力才能保障 對(duì)客戶(hù)端的高效的服務(wù) 圖1 2 集中式p 2 p 網(wǎng)絡(luò) 集中式p 2 p 網(wǎng)絡(luò)的典型應(yīng)用代表是n a p s t 曾經(jīng)n 印s t e r 流行一時(shí) 它通過(guò)基 于集中式的p 2 p 網(wǎng)絡(luò)的模型來(lái)構(gòu)建 但是由于n a p s t e r 所索引的文件涉及到了知識(shí) 版權(quán)的問(wèn)題 最終導(dǎo)致n a p s t e r 停止運(yùn)行 但是n a p s t e r 的停止運(yùn)行并沒(méi)有阻止p 2 p 的廣泛應(yīng)用潛力和前景 更沒(méi)有阻擋p 2 p 技術(shù)的發(fā)展 相反產(chǎn)生了完全分布式非 結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò) 1 2 1 完全分布式非結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò) 完全分布式非結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò)結(jié)構(gòu)如圖1 3 從該結(jié)構(gòu)圖可以看出這種網(wǎng)絡(luò)是 通過(guò)結(jié)點(diǎn)之間的任意的鏈接而形成 整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與一個(gè)網(wǎng)狀的結(jié)構(gòu)很相似 這種拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)對(duì)于結(jié)點(diǎn)的加入或者退出的頻率不會(huì)有很大的影響 具有很 好的適應(yīng)性 而且在該網(wǎng)絡(luò)中 結(jié)點(diǎn)之間可以像普通的i n t e r n e t 一樣 對(duì)資源進(jìn) 行模糊查詢(xún) 4 第一章引言 圖1 3 完全分布式非結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò) 完全分布式非結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò)的最好代表是g n u t e l l a 2 0 與n a p s t e r 的最大區(qū) 別就是 g n u t e l l a 不像n a p s t e r 那樣需要一個(gè)中心的索引服務(wù)器 在g n u t e l l a 中 每個(gè)結(jié)點(diǎn)既是客戶(hù)端又是服務(wù)器 從而沒(méi)有n a p s t e r 的那種單點(diǎn)失效的問(wèn)題 在 g n u t e l l a 中 每當(dāng)對(duì)等結(jié)點(diǎn)需要查詢(xún)資源文件的時(shí)候 是通過(guò)隨機(jī)洪泛的方式來(lái) 進(jìn)行傳播請(qǐng)求的 為了避免有很多請(qǐng)求一直在網(wǎng)絡(luò)中為 g n u t e l l a 也仿照t c p i p 協(xié)議通過(guò)采用t t l 2 1 的方式來(lái)進(jìn)行請(qǐng)求消息的控制 g n u t e l l a 的查詢(xún)流程如圖 1 4 查詢(xún)流 辱耐 下載流 一弗 圖1 4 c h u t e l l a 的查詢(xún)流程 在完全分布式非結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò)中 當(dāng)結(jié)點(diǎn)的個(gè)數(shù)很少的時(shí)候可以很快的查詢(xún) 到所需要的資源 當(dāng)隨著結(jié)點(diǎn)個(gè)數(shù)的增加的時(shí)候 查詢(xún)資源所需要的時(shí)間就會(huì)隨 著結(jié)點(diǎn)的個(gè)數(shù)的增加而增加 而且由于是采用隨機(jī)洪泛的方式來(lái)進(jìn)行查詢(xún)的 所 以一旦網(wǎng)絡(luò)規(guī)模變大后 網(wǎng)絡(luò)中的查詢(xún)數(shù)據(jù)請(qǐng)求會(huì)逐漸增多 嚴(yán)重的影響網(wǎng)絡(luò)的 負(fù)載 此外 由于網(wǎng)絡(luò)沒(méi)有確定的拓?fù)浣Y(jié)構(gòu) 查詢(xún)采用的是隨機(jī)的方式 這樣便 可能會(huì)造成有些資源的漏查 由此便導(dǎo)致了網(wǎng)絡(luò)的可擴(kuò)展性降低 2 2 2 3 電子科技大學(xué)碩士學(xué)位論文 1 2 2 完全分布式結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò) 由于完全分布式非結(jié)構(gòu)化網(wǎng)絡(luò)中對(duì)于資源的搜索可能會(huì)造成漏搜以及這種搜 索方式的不可靠性 同時(shí)網(wǎng)絡(luò)中可能會(huì)存在著過(guò)多的搜索請(qǐng)求 研究者就開(kāi)始研 究如何構(gòu)造一個(gè)p 2 p 的對(duì)等網(wǎng)絡(luò)來(lái)解決這些問(wèn)題 目前 學(xué)者們研究如何構(gòu)造結(jié) 構(gòu)化的對(duì)等網(wǎng)絡(luò)來(lái)有效地提高查找資源信息 經(jīng)過(guò)研究發(fā)現(xiàn)是基于 d h t d i s t r i b u t e dh a s h1 a b l e 2 4 彩 分布式h a s h 表的方式來(lái)構(gòu)造整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu) 形成一個(gè)結(jié)構(gòu)化的對(duì)等網(wǎng)絡(luò) 然后結(jié)點(diǎn)通過(guò)這個(gè)分布式h a s h 表來(lái)將自身散列到這 張表上 同時(shí)需要共享的資源也通過(guò)這張哈希表將資源信息散列到相應(yīng)的結(jié)點(diǎn)上 當(dāng)結(jié)點(diǎn)剛剛加入這個(gè)結(jié)構(gòu)化的對(duì)等網(wǎng)絡(luò)時(shí) 首先可以根據(jù)這個(gè)結(jié)點(diǎn)的特有信息 比如i p 地址 將這些信息通過(guò)散列函數(shù) 映射成一個(gè)n o d e i d 然后根據(jù)這個(gè) n o d e i d 這個(gè)結(jié)點(diǎn)就散列到了這個(gè)h a s h 表上面 從而便在這個(gè)邏輯的拓?fù)浣Y(jié)構(gòu)上 有了自己的位置 然后這個(gè)結(jié)點(diǎn)通過(guò)某種方式獲取基于這個(gè)邏輯拓?fù)浣Y(jié)構(gòu)上的周 圍一些結(jié)點(diǎn) 以便能夠?qū)⑦@些結(jié)點(diǎn)和自身聯(lián)系起來(lái) 便于形成一個(gè)路由表 這類(lèi) 似于t c p 口中的路由表 周?chē)慕Y(jié)點(diǎn)也可以通過(guò)這種方式感應(yīng)到周?chē)辛诵陆Y(jié)點(diǎn) 已經(jīng)加入這個(gè)結(jié)構(gòu)化的p 2 p 網(wǎng)絡(luò) 于是便更新自身的路由表 從而保持整個(gè)p 2 p 網(wǎng)絡(luò)處于最新的拓?fù)浣Y(jié)構(gòu) 當(dāng)周?chē)薪Y(jié)點(diǎn)退出這個(gè)網(wǎng)絡(luò)的時(shí)候 周?chē)慕Y(jié)點(diǎn)可以 通過(guò)周期性的探測(cè)周?chē)慕Y(jié)點(diǎn)來(lái)發(fā)現(xiàn)這些退出的結(jié)點(diǎn) 然后將這些退出的結(jié)點(diǎn)從 自身的路由表中移除 從而保證整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的正確性 通過(guò)以時(shí)間的方 式來(lái)?yè)Q取網(wǎng)絡(luò)的正確性見(jiàn)圖1 5 對(duì)于某個(gè)結(jié)點(diǎn)若要共享某個(gè)資源 那么首先通過(guò) 這個(gè)h 礎(chǔ)表 根據(jù)這個(gè)對(duì)象的一些屬性例如文件名 將這個(gè)對(duì)象映射成一個(gè) 0 i b j e c t i d 然后在之前已經(jīng)建立的那個(gè)h a s h 表上面找出最為接近這個(gè)o b j e c t i d 的 n o d e i d 然后將這個(gè)文件的一些屬性信息比如擁有這個(gè)文件的結(jié)點(diǎn)的口地址 文件 大小等告訴給n o d e i d 所在的結(jié)點(diǎn) 這樣 這個(gè)結(jié)點(diǎn)便就有了這個(gè)文件的信息 當(dāng) 有某個(gè)結(jié)點(diǎn)想要查詢(xún)這個(gè)文件的時(shí)候 首先通過(guò)摘取這個(gè)文件的關(guān)鍵信息 比如 文件名 然后通過(guò)h a s h 的方式獲取該文件的散列值o b j e c t i d 此時(shí)這個(gè)結(jié)點(diǎn)便通 過(guò)結(jié)點(diǎn)所存儲(chǔ)的路由表的信息的方式來(lái)查詢(xún)擁有o b i e c t d 的結(jié)點(diǎn)i 當(dāng)查詢(xún)信息到 達(dá)該結(jié)點(diǎn)后 那么該結(jié)點(diǎn)將這個(gè)文件的一些信息例如存儲(chǔ)該結(jié)點(diǎn)的i p 地址和端口 號(hào)告訴給客戶(hù)端 6 基于h 韶h 方式是網(wǎng)絡(luò)中的所有結(jié)點(diǎn)統(tǒng)一地按照這種方式將結(jié)點(diǎn)和資源部署到 這個(gè)表中 因此 隨著結(jié)點(diǎn)數(shù)目的增多 表也在不斷地?cái)U(kuò)大 哈希表中的每一個(gè) 結(jié)點(diǎn)可以負(fù)責(zé)一些資源的保存和維護(hù) 通過(guò)按照結(jié)點(diǎn)m 和資源對(duì)象i d 相近原則 只要找出與資源i d 最為接近的結(jié)點(diǎn) 然后將這些資源的維護(hù)都賦予給該結(jié)點(diǎn) 那 么便可實(shí)現(xiàn)資源和結(jié)點(diǎn)的共存 按照這種方式 每個(gè)結(jié)點(diǎn)可以負(fù)責(zé)一個(gè)段的資源 的保存 當(dāng)網(wǎng)絡(luò)中有結(jié)點(diǎn)加入或者退出網(wǎng)絡(luò)時(shí) 便可以將資源的信息正確地轉(zhuǎn)移 到相應(yīng)的結(jié)點(diǎn)即可 從而保證此方法的可擴(kuò)展性 基于d h t 的網(wǎng)絡(luò)的最大缺點(diǎn)在于網(wǎng)絡(luò)中突然某個(gè)時(shí)間段有大量的結(jié)點(diǎn)的加入 和退出 這個(gè)時(shí)候由于網(wǎng)絡(luò)沒(méi)辦法能夠及時(shí)地通知其他結(jié)點(diǎn)當(dāng)前的網(wǎng)絡(luò)的正確的 拓?fù)浣Y(jié)構(gòu) 而造成網(wǎng)絡(luò)服務(wù)的不可用 即所謂的網(wǎng)絡(luò)擾動(dòng)問(wèn)題 2 純刀 另外一個(gè)問(wèn) 題是基于d h t 的查找不能夠?qū)λ璧馁Y源進(jìn)行模糊查找 2 8 同時(shí) 對(duì)等網(wǎng)絡(luò)中的 還沒(méi)有形成一個(gè)很好的安全檢測(cè)機(jī)制 2 9 1 從而有效地避免不良用戶(hù)對(duì)整個(gè)對(duì)等網(wǎng) 絡(luò)的攻擊 目前已有的結(jié)構(gòu)化結(jié)構(gòu)的對(duì)等網(wǎng)絡(luò)的構(gòu)造算法有 c h o r d 3 0 1 c 鋤 3 1 1 p 懿咄1 a p e s t y 1 2 3 混合式p 2 p 網(wǎng)絡(luò) 常規(guī)意義上 集中式的網(wǎng)絡(luò)對(duì)于資源的快速搜索有很好的優(yōu)勢(shì) 但是一旦入 侵者攻擊集中式網(wǎng)絡(luò)中的中心服務(wù)器 那么毫無(wú)疑問(wèn) 集中式網(wǎng)絡(luò)將中斷所有的 7 電子科技大學(xué)碩士學(xué)位論文 服務(wù) 而且集中式網(wǎng)絡(luò)根本上就沒(méi)有將網(wǎng)絡(luò)中邊緣網(wǎng)絡(luò)的帶寬利用 而分布式網(wǎng) 絡(luò)雖然解決了中心服務(wù)器的單點(diǎn)失效的問(wèn)題 但是卻在網(wǎng)絡(luò)中對(duì)于資源的搜索速 度上卻下降了下去 而且為了確保整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的準(zhǔn)確性 不得不花費(fèi)很 大的開(kāi)銷(xiāo)來(lái)維持整個(gè)網(wǎng)絡(luò) 圖1 6 混合式p 2 p 網(wǎng)絡(luò) 為了結(jié)合集中式和分布式網(wǎng)絡(luò)的優(yōu)點(diǎn) 同時(shí)彌補(bǔ)他們的缺點(diǎn) 混合式p 2 p 網(wǎng)絡(luò)由此誕生見(jiàn)圖1 6 混合式網(wǎng)絡(luò)結(jié)合兩者的長(zhǎng)處 在混合式網(wǎng)絡(luò)中 結(jié)點(diǎn) 按照功能分為三類(lèi) 其中一類(lèi)為索引結(jié)點(diǎn) 一類(lèi)為搜索結(jié)點(diǎn) 另外一類(lèi)為普通的 終端結(jié)點(diǎn) 其中索引結(jié)點(diǎn)維持著網(wǎng)絡(luò)中搜索結(jié)點(diǎn)的信息 搜索結(jié)點(diǎn)管理著文件列 表的信息 而終端結(jié)點(diǎn)即為存儲(chǔ)了資源文件的普通結(jié)點(diǎn) 當(dāng)有新結(jié)點(diǎn)加入該網(wǎng)絡(luò) 時(shí) 終端結(jié)點(diǎn)便找到一個(gè)結(jié)點(diǎn)作為它的搜索結(jié)點(diǎn) 然后該普通結(jié)點(diǎn)便將自己需要 共享的資源文件的信息列表發(fā)送給該搜索結(jié)點(diǎn) 每當(dāng)結(jié)點(diǎn)需要搜索某個(gè)資源文件 時(shí) 便首先通過(guò)索引結(jié)點(diǎn)找到首個(gè)為此次查詢(xún)服務(wù)的搜索結(jié)點(diǎn) 然后搜索結(jié)點(diǎn)便 通過(guò)查找自身存儲(chǔ)的資源文件的列表來(lái)查找是否有該資源的信息 如果沒(méi)有便將 該查詢(xún)隨機(jī)洪泛式地轉(zhuǎn)發(fā)到另外的相鄰的搜索結(jié)點(diǎn) 直到某個(gè)搜索結(jié)點(diǎn)獲取該資 源文件的信息并將該信息傳輸給查詢(xún)?cè)唇Y(jié)點(diǎn) 如果一直都沒(méi)有找到該資源文件那 么便通知源查詢(xún)結(jié)點(diǎn) 1 3 研究目的和內(nèi)容 第一章引言 結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)是在物理網(wǎng)絡(luò)的基礎(chǔ)上按照某種邏輯方式構(gòu)建一個(gè)邏輯拓?fù)?結(jié)構(gòu) 因此邏輯上相鄰的結(jié)點(diǎn)可能在實(shí)際的物理網(wǎng)絡(luò)上相距甚遠(yuǎn) 即所謂的拓?fù)?失配見(jiàn)圖1 7 3 2 即如果諸多p c 結(jié)點(diǎn)通過(guò)i i l t 鋤e t 網(wǎng)絡(luò)互連 相互間通過(guò)i i l t e m e t 便 形成了物理拓?fù)浣Y(jié)構(gòu)上的網(wǎng)絡(luò) 然后這些結(jié)點(diǎn)通過(guò)相應(yīng)的某種方式建立某種邏輯拓 撲結(jié)構(gòu) 此時(shí)物理拓?fù)浣Y(jié)構(gòu)上的p c 結(jié)點(diǎn)便與其它位置的p c 結(jié)點(diǎn)組成了某個(gè)邏輯上 的拓?fù)浣Y(jié)構(gòu) 當(dāng)某個(gè)p c 結(jié)點(diǎn)需要查詢(xún)某個(gè)資源時(shí) 此時(shí)可能擁有這個(gè)資源的結(jié)點(diǎn) 有多個(gè) 當(dāng)該查詢(xún)結(jié)點(diǎn)查到了多個(gè)擁有該資源的信息時(shí) 該怎么選擇哪個(gè)結(jié)點(diǎn)進(jìn) 行傳輸呢 可能查詢(xún)結(jié)點(diǎn)會(huì)從中選擇一個(gè)結(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸 默認(rèn)情況 結(jié)點(diǎn)一 般都會(huì)選擇在邏輯拓?fù)渖舷噜彽慕Y(jié)點(diǎn)作為傳輸?shù)慕Y(jié)點(diǎn) 那么就會(huì)造成結(jié)點(diǎn)間的延 時(shí)變大 p c 4p c 5 圖1 7 網(wǎng)絡(luò)物理拓?fù)渑c邏輯拓?fù)涫?例如結(jié)點(diǎn)p c 3 想要下載某個(gè)資源文件a 結(jié)果資源文件a 在結(jié)點(diǎn)p c 4 和p c 5 都擁 有 但是默認(rèn)情況下結(jié)點(diǎn)p c 3 應(yīng)該會(huì)選擇結(jié)點(diǎn)p c 4 進(jìn)行通訊 然后便進(jìn)行數(shù)據(jù)的交 互 但是雖然邏輯拓?fù)渖辖Y(jié)點(diǎn)p c 3 與結(jié)點(diǎn)p c 4 彼此相鄰 但是實(shí)際物理拓?fù)浣Y(jié)構(gòu)上 結(jié)點(diǎn)p c 3 與結(jié)點(diǎn)p c 4 可能相差甚遠(yuǎn) 比如結(jié)點(diǎn)p c 3 位置在成都 結(jié)點(diǎn)p c 5 位置在北京 然后結(jié)點(diǎn)p c 4 位置在紐約 如果這時(shí)結(jié)點(diǎn)p c 4 與結(jié)點(diǎn)p c 3 進(jìn)行通訊肯定比結(jié)點(diǎn)p c 3 與結(jié)點(diǎn)p c 5 的時(shí)延大的多 這就是所謂的邏輯拓?fù)涫?所以 如果能夠找到某種 9 電子科技大學(xué)碩士學(xué)位論文 方式將這些結(jié)點(diǎn)的物理的大概位置結(jié)合起來(lái) 那么綜合考慮這些因素 然后找出 一個(gè)最優(yōu)的結(jié)點(diǎn)進(jìn)行傳輸 對(duì)于剛才這樣的這種情況 結(jié)點(diǎn)p c 3 則應(yīng)該要選擇結(jié)點(diǎn) p c 5 進(jìn)行數(shù)據(jù)通訊 那么對(duì)于延時(shí)的情況就會(huì)有很大的改善 這便大大提高了用戶(hù) 的響應(yīng)速度 因此在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中 怎樣按照某種方式來(lái)彌補(bǔ)這種物理上和邏輯上結(jié) 構(gòu)的差異性所帶來(lái)的性能的降低 本文通過(guò)在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)的基礎(chǔ)上 通過(guò)在 該網(wǎng)絡(luò)中 當(dāng)新結(jié)點(diǎn)加入這個(gè)網(wǎng)絡(luò)時(shí) 便首先通過(guò)將該結(jié)點(diǎn)與網(wǎng)絡(luò)中的參照結(jié)點(diǎn) 進(jìn)行距離的測(cè)試 來(lái)找出結(jié)點(diǎn)的相對(duì)位置 并將該位置存儲(chǔ)在每個(gè)結(jié)點(diǎn)上面 當(dāng) 網(wǎng)絡(luò)中有結(jié)點(diǎn)在選擇其他結(jié)點(diǎn)時(shí) 那么便可以通過(guò)比較不同的結(jié)點(diǎn)與選擇結(jié)點(diǎn)的 物理位置的相隔距離來(lái)找出最為接近查詢(xún)結(jié)點(diǎn)的目標(biāo)結(jié)點(diǎn) 從而實(shí)現(xiàn)數(shù)據(jù)資源的 高速傳輸 在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中 通常結(jié)點(diǎn)之間按照某種算法將將彼此之間連接起來(lái) 然后按照相應(yīng)的方式對(duì)資源數(shù)據(jù)進(jìn)行查詢(xún) 像這樣的算法已經(jīng)有了很多 比如 c h o r d c a n 等 通常這些算法實(shí)現(xiàn)的數(shù)據(jù)的查詢(xún)的效率都是將近l o g n 那么有沒(méi)有 一種更好的方法來(lái)提高這個(gè)已有的資源的搜索的效率昵 并且這種方法相對(duì)于比 較獨(dú)立而且不需要過(guò)多的開(kāi)銷(xiāo) 本文就通過(guò)了結(jié)合小世界的效應(yīng)的方式通過(guò)如何 在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中構(gòu)建一個(gè)小世界網(wǎng)絡(luò)的形式來(lái)提高結(jié)點(diǎn)之間的數(shù)據(jù)的傳輸效 率 一旦結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中建立起了小世界網(wǎng)絡(luò)后 那么結(jié)點(diǎn)便可以利用小世界 的特性來(lái)對(duì)資源進(jìn)行高效的數(shù)據(jù)傳輸 因?yàn)樵谛∈澜缇W(wǎng)絡(luò)中 結(jié)點(diǎn)之間會(huì)有小世 界所特有的短鏈鏈接 這種鏈接將整個(gè)網(wǎng)絡(luò)的結(jié)點(diǎn)之間的距離縮小 從而提高了 結(jié)點(diǎn)之間的數(shù)據(jù)傳輸?shù)男?1 4 論文結(jié)構(gòu) 本文總共分為五個(gè)部分 第一部分首先通過(guò)對(duì)論文中所研究的對(duì)等網(wǎng)絡(luò)的整 個(gè)發(fā)展過(guò)程進(jìn)行介紹 并對(duì)每個(gè)階段的對(duì)等網(wǎng)絡(luò)進(jìn)行分析 然后對(duì)該論文的的研 究目的和內(nèi)容進(jìn)行論述 第二章對(duì)這種網(wǎng)絡(luò)中的相關(guān)的路由進(jìn)行描述 同時(shí)也指 出了在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中的當(dāng)前一些問(wèn)題 第三章通過(guò)在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中提出 了怎樣提高數(shù)據(jù)的轉(zhuǎn)發(fā)速度的方法 通過(guò)對(duì)小世界特性和結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中的結(jié) 合 提出了一種如何在結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中建立一種小世界網(wǎng)絡(luò)的方法來(lái)解決這個(gè) 問(wèn)題 然后描述 分析 證明了建立這種模型的整個(gè)過(guò)程 第四章首先分析了在 結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中 結(jié)點(diǎn)之間在應(yīng)用層的結(jié)構(gòu)關(guān)系與結(jié)點(diǎn)在實(shí)際的物理網(wǎng)絡(luò)中的 l o 第一章引言 結(jié)構(gòu)關(guān)系的異構(gòu)性 然后分析了這種問(wèn)題將會(huì)帶來(lái)的問(wèn)題 然后提出了在結(jié)點(diǎn)加 入結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)時(shí) 將該結(jié)點(diǎn)進(jìn)行歸宿地的劃分 并且將該結(jié)點(diǎn)的歸宿地的劃 分存儲(chǔ)在每個(gè)結(jié)點(diǎn)上面 那么在以后的對(duì)結(jié)點(diǎn)的選擇的過(guò)程中 便可以通過(guò)這些 數(shù)據(jù) 首先找到距離源結(jié)點(diǎn)最為接近的區(qū)域結(jié)點(diǎn) 然后再在相同距離的區(qū)域中找 出更接近源結(jié)點(diǎn)的目標(biāo)結(jié)點(diǎn) 這便解決了應(yīng)用層的邏輯結(jié)構(gòu)與實(shí)際網(wǎng)絡(luò)中的結(jié)構(gòu) 的不一致性的問(wèn)題 這些方法都在第四章完整地描述了整個(gè)過(guò)程 第五章對(duì)整個(gè) 對(duì)等網(wǎng)絡(luò)中的當(dāng)前存在的問(wèn)題進(jìn)行了分析和描述 并說(shuō)明了整個(gè)互聯(lián)網(wǎng)中對(duì)等網(wǎng) 絡(luò)的應(yīng)用的程度和以后對(duì)等網(wǎng)絡(luò)的應(yīng)用趨勢(shì) 1 5 本章小結(jié) 網(wǎng)絡(luò)資源的共享給予了對(duì)等網(wǎng)絡(luò)的存在的價(jià)值和意義 它解決了當(dāng)今互聯(lián)網(wǎng) 發(fā)展的所遇到的一些問(wèn)題 例如 怎樣在網(wǎng)絡(luò)中能夠高效地提高資源的共享率 并且能夠很大程度上的提高用戶(hù)這種需求的響應(yīng)時(shí)間 這對(duì)于網(wǎng)絡(luò)的應(yīng)用來(lái)說(shuō)是 一個(gè)非常具有挑戰(zhàn)的意義 的確計(jì)算機(jī)的發(fā)展是隨著大家所熟知的摩爾定理在默 默地提高著計(jì)算機(jī)的性能 但是計(jì)算機(jī)的性能不管怎么提高也是隨著應(yīng)用的需求 的情況下才得以提高的 而且通常情況下 需求都是首先提出 然后才相應(yīng)的去 想辦法去解決這些問(wèn)題 那么怎樣以一種方法來(lái)可以緩解這種問(wèn)題呢 總所周知 整個(gè)互聯(lián)網(wǎng)上有豐富的閑置的計(jì)算機(jī)資源 那么如果將這些閑散的計(jì)算機(jī)資源加 以整合 然后將任務(wù)分別變成一些的小的任務(wù)模塊 分別將這些小模塊分發(fā)給這 些閑散的計(jì)算機(jī) 讓它們?nèi)ソ鉀Q這個(gè)問(wèn)題 那么便可以大大的提高計(jì)算機(jī)的資源 利用率 而且也解決了對(duì)某一種超級(jí)計(jì)算機(jī)資源的依賴(lài) 那么對(duì)等網(wǎng)絡(luò)就是這種 情況下應(yīng)運(yùn)而生的 它讓整個(gè)網(wǎng)絡(luò)中的計(jì)算機(jī)都被調(diào)動(dòng)起來(lái) 統(tǒng)一地相互協(xié)作地 完成一個(gè)任務(wù) 9 1 這種網(wǎng)絡(luò)稱(chēng)之為對(duì)等式網(wǎng)絡(luò) 而對(duì)等網(wǎng)絡(luò)恰好是這種網(wǎng)絡(luò)中的一 種 整個(gè)對(duì)等網(wǎng)絡(luò)在發(fā)展的過(guò)程中經(jīng)歷了很多個(gè)階段 正如第二節(jié)所介紹的那樣 這些發(fā)展都是基本圍繞著整個(gè)對(duì)等式網(wǎng)絡(luò)中所遇到的問(wèn)題而提出的解決方案 因 為大家都知道 在對(duì)等式網(wǎng)絡(luò)中針對(duì)如何提高網(wǎng)絡(luò)中資源的查詢(xún)的效率 一直是 對(duì)等網(wǎng)絡(luò)中很核心和關(guān)鍵的問(wèn)題 所以這些對(duì)等網(wǎng)絡(luò)的發(fā)展也就是隨著這個(gè)問(wèn)題 的改善而提出的 電子科技大學(xué)碩士學(xué)位論文 2 1p 2 p 的搜索技術(shù) 第二章相關(guān)算法分析 在結(jié)構(gòu)化的對(duì)等網(wǎng)絡(luò)中 每一個(gè)網(wǎng)絡(luò)中的計(jì)算機(jī)被稱(chēng)為一個(gè)對(duì)等結(jié)點(diǎn) 每一個(gè) 需要共享的資源文件稱(chēng)為對(duì)象 通常情況下 結(jié)點(diǎn)計(jì)算機(jī)和共享的資源文件都需 要在整個(gè)結(jié)構(gòu)會(huì)對(duì)等網(wǎng)絡(luò)中被部署 那么按照什么方式將這些結(jié)點(diǎn)和資源文件部 署呢 最為成熟的做法是 將每一個(gè)計(jì)算機(jī)和共享的資源按照它們的某個(gè)比較唯 一的屬性 然后將這個(gè)屬性值轉(zhuǎn)化成一個(gè)標(biāo)示符 這樣不同的計(jì)算機(jī)和資源就可 以對(duì)應(yīng)到不同的標(biāo)識(shí)符 從而保證其唯一性 首先對(duì)于一臺(tái)計(jì)算機(jī)而言 因?yàn)橛?jì) 算機(jī)進(jìn)入了h t 鋤e t 所以每一臺(tái)計(jì)算機(jī)都有一個(gè)才口地址 因?yàn)槊恳慌_(tái)計(jì)算機(jī)的 i p 地址都不同 所以可以利用計(jì)算機(jī)的口地址將每一臺(tái)計(jì)算機(jī)映射到一個(gè)相應(yīng)的 標(biāo)識(shí)符 從而使得與不同的計(jì)算機(jī)有所區(qū)別 對(duì)于資源來(lái)說(shuō) 因?yàn)槊恳粋€(gè)資源都 有相應(yīng)的關(guān)鍵字信息 那么可以通過(guò)每個(gè)資源的關(guān)鍵字或者資源的文件名映射為 一個(gè)標(biāo)識(shí)符 然后根據(jù)這個(gè)相應(yīng)的標(biāo)識(shí)符來(lái)區(qū)別不同的資源 將結(jié)點(diǎn)和資源映射 為一個(gè)標(biāo)識(shí)符以后 便可以按照某種分配的策略 將結(jié)點(diǎn)和共享的資源分配到標(biāo) 識(shí)符空間中 因?yàn)椴煌姆椒?都會(huì)使得每一個(gè)結(jié)點(diǎn)負(fù)責(zé)一部分的資源的信息 也就是將一個(gè)標(biāo)識(shí)符空間分割為不同大小的段 其中每一個(gè)結(jié)點(diǎn)負(fù)責(zé)不同的段 然后將每一個(gè)資源分配到相應(yīng)的段 然后負(fù)責(zé)這個(gè)段的結(jié)點(diǎn)便將資源的信息保存 即標(biāo)識(shí)符 h a s h 名字 由此結(jié)點(diǎn)的標(biāo)識(shí)符 h a s h 結(jié)點(diǎn)的i p 資源文件的標(biāo)示符 h a s h 資源文件的名字或者關(guān)鍵值 通常散列函數(shù)會(huì)給每一個(gè)不同的計(jì)算機(jī)和資源分配一個(gè)標(biāo)識(shí)符 然后根據(jù)不同 的標(biāo)識(shí)符來(lái)構(gòu)造對(duì)等網(wǎng)絡(luò)的結(jié)構(gòu) 但是有可能是不同的結(jié)點(diǎn)或者資源而散列到相 同的標(biāo)識(shí)符 這便是散列函數(shù)里面的沖突 因?yàn)檫@種沖突是不可避免的 那么怎 樣解決這種沖突呢 通常的做法是將散列函數(shù)的空間擴(kuò)大 保證散列函數(shù)的值空 間的大小和結(jié)點(diǎn)與資源的個(gè)數(shù)規(guī)模相當(dāng) 然后這樣便可以實(shí)現(xiàn)不同的結(jié)點(diǎn)和資源 有不同的標(biāo)識(shí)符 結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)p 2 p 中 每個(gè)結(jié)點(diǎn)都會(huì)對(duì)應(yīng)到這個(gè)散列函數(shù)值空間的一部分 這樣以后 假設(shè)某個(gè)資源文件通過(guò)散列函數(shù)獲得的散列值落入這個(gè)結(jié)點(diǎn)所管轄的 空間中 那么這個(gè)結(jié)點(diǎn)便會(huì)負(fù)責(zé)保存這個(gè)資源文件的一些基本信息 比如這個(gè)資 1 2 第二章相關(guān)算法分析 源文件的名字 大小 以及擁有這個(gè)資源文件的客戶(hù)端的i p 地址等 那么當(dāng)某個(gè) 客戶(hù)端結(jié)點(diǎn)要查詢(xún)這個(gè)資源文件時(shí) 便通過(guò)這個(gè)文件的標(biāo)識(shí)符來(lái)查詢(xún) 通過(guò)所構(gòu) 造的對(duì)等網(wǎng)絡(luò)的路由算法來(lái)搜索該標(biāo)識(shí)符 當(dāng)搜索到了這個(gè)結(jié)點(diǎn)后 便發(fā)現(xiàn)該結(jié) 點(diǎn)上存儲(chǔ)這個(gè)資源文件的一些基本信息 于是便將該文件的這些基本信息發(fā)送到 查詢(xún)結(jié)點(diǎn) 然后查詢(xún)結(jié)點(diǎn)便可以通過(guò)這些信息來(lái)獲取這個(gè)資源文件 基于d h t 網(wǎng)絡(luò)中的搜索實(shí)現(xiàn)主要有以下幾點(diǎn) 第一 每個(gè)結(jié)點(diǎn)都擁有一個(gè) 表 這樣就可以保證當(dāng)查詢(xún)數(shù)據(jù)包到來(lái)時(shí) 便可以 通過(guò)這表來(lái)獲取需要下一跳的結(jié)點(diǎn)的地址是哪一個(gè) 通常查詢(xún)數(shù)據(jù)包的格式是這 樣的 應(yīng)該是 這樣這個(gè)標(biāo)識(shí)符被陸續(xù) 的在整個(gè)對(duì)等網(wǎng)絡(luò)中進(jìn)行傳輸 經(jīng)過(guò)的結(jié)點(diǎn)也清楚地知道需要查詢(xún)哪個(gè)資源文件 而每個(gè)結(jié)點(diǎn)都會(huì)保存它所負(fù)責(zé)的資源文件的信息 一般來(lái)說(shuō)都是保存資源文件的 標(biāo)識(shí)符最為接近該結(jié)點(diǎn)的標(biāo)識(shí)符 這樣在查詢(xún)?cè)撡Y源文件的時(shí)候 通過(guò)這個(gè)文件 的標(biāo)識(shí)符便對(duì)應(yīng)到查詢(xún)?cè)摻Y(jié)點(diǎn)的標(biāo)識(shí)符 從而從文件查詢(xún)轉(zhuǎn)移到了結(jié)點(diǎn)的查詢(xún) 對(duì)于當(dāng)有新結(jié)點(diǎn)或者新的資源文件加入對(duì)等網(wǎng)絡(luò)時(shí) 便可以通過(guò)將新加入的資源 文件的標(biāo)識(shí)符信息保存在對(duì)應(yīng)的結(jié)點(diǎn)上 或者將應(yīng)該轉(zhuǎn)移的資源信息轉(zhuǎn)移到新加 入的結(jié)點(diǎn)上 對(duì)于當(dāng)有結(jié)點(diǎn)移出時(shí) 此時(shí)可以講該結(jié)點(diǎn)所擁有的資源文件的信息 轉(zhuǎn)移到臨近的結(jié)點(diǎn)上 2 2c h o r d 2 2 1c h o r d 的結(jié)構(gòu) c h o r d 算法在2 0 0 1 年是由麻省理工大學(xué)的s t o i c a 等人提出 它的思想主要是 為了能夠解決在對(duì)等網(wǎng)絡(luò)中怎樣搜索對(duì)等網(wǎng)絡(luò)中的資源文件 它的完美性源自于 它的簡(jiǎn)單性和伸縮性 d h t 是通過(guò)將相應(yīng)的字符串等信息轉(zhuǎn)換成一個(gè)標(biāo)識(shí)符 這 樣每個(gè)結(jié)點(diǎn)或者資源文件便可以映射到這個(gè)標(biāo)識(shí)符 這個(gè)標(biāo)識(shí)符是在一個(gè)lo 2 一li 區(qū)間中的整數(shù) 這樣便可以將每個(gè)結(jié)點(diǎn)和資源文件的標(biāo)識(shí)符對(duì)應(yīng)在一個(gè)一維的對(duì)2 取模的標(biāo)識(shí)符環(huán)上面 取值范圍為 2 一1 o c h o r d 是最簡(jiǎn)單 最精確的環(huán)形p 2 p 模型 由此 o r d 便形成了一個(gè)具有環(huán)形拓?fù)浣Y(jié)構(gòu)的環(huán) 每一個(gè)結(jié)點(diǎn)都可以通過(guò) 散列函數(shù)將結(jié)點(diǎn)映射到這個(gè)環(huán)上 每一個(gè)資源文件也可以通過(guò)散列函數(shù)將這個(gè)資 源文件映射出一個(gè)標(biāo)識(shí)符 從而對(duì)應(yīng)到相應(yīng)的這個(gè)環(huán)上的某個(gè)位置上去 c h o r d 通過(guò)散列函數(shù)如s h a 給每個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)和每個(gè)數(shù)據(jù)對(duì)象分配唯一的i d 即n o d e i d h n o d e 的屬性 h 為散列函數(shù) n o d e 的屬性可以包括該結(jié)點(diǎn)的口地址 1 3 電子科技大學(xué)碩士學(xué)位論文 端口號(hào) 或者他們的組合 這樣便可以確定一個(gè)結(jié)點(diǎn)的i d 同時(shí)o b j e c t i d h o b j e c t 屬性 o b j e c t 屬性可以是數(shù)據(jù)對(duì)象的名稱(chēng) 內(nèi)容 大小 發(fā)布者或者他們的組合 等 由于s h a 散列函數(shù)的h a s h 值的長(zhǎng)度m 一般大于等于1 6 0 這樣就可以保證了 結(jié)點(diǎn)的d 或者對(duì)象的i d 不可能出現(xiàn)重復(fù) 通過(guò)使用結(jié)點(diǎn)的關(guān)鍵信息將該結(jié)點(diǎn)和標(biāo)識(shí)符相關(guān)聯(lián) 同時(shí)資源對(duì)象也按照這種 方式與標(biāo)識(shí)符相關(guān)聯(lián) 那么一個(gè)資源對(duì)象就可以用 相關(guān)聯(lián)表示 那么 這個(gè) 對(duì)于是便可以由其結(jié)點(diǎn)的n o d e i d 大于或者等于k 的結(jié)點(diǎn)所擁有 那么因 此稱(chēng)這樣的一個(gè)結(jié)點(diǎn)為關(guān)鍵字k 的后繼結(jié)點(diǎn) 即在一個(gè)c h o r d 環(huán)中具有順時(shí)針?lè)?向增長(zhǎng)i d 的一個(gè)結(jié)點(diǎn)負(fù)責(zé)其逆時(shí)針?lè)较蛑暗乃嘘P(guān)鍵字 k 4 n 3 6k 2 8 k 1 5 8 n 1 0 n 8 的f i i l g e r t a b l e i d 目的d后繼 on 8 1n l o 1n 8 2 n 1 0 2n 8 4n 3 6 3n 8 8n 3 6 4n 8 1 6n 3 6 5n 8 3 2n 4 8 圖2 lc h o r d 環(huán) 圖2 1c h o r d 環(huán)繪出了一個(gè)已經(jīng)建立好了的c h o r d 環(huán) 在c h o r d 環(huán)上面已經(jīng)標(biāo) 識(shí)了每一個(gè)結(jié)點(diǎn)的標(biāo)識(shí)符以及資源文件的標(biāo)識(shí)符 而這些結(jié)點(diǎn)的n o d e i d 都是以順 時(shí)針的方向從小到大的順序排列在一個(gè)環(huán)上 數(shù)據(jù)對(duì)象k 被分配到環(huán)上按照順時(shí) 針?lè)较蚓o隨k 包括k 的第一個(gè)結(jié)點(diǎn) 其中在這個(gè)c h o r d 環(huán)上其中l(wèi) 6 表示總共 有6 4 個(gè)標(biāo)識(shí)符 其中有6 個(gè)結(jié)點(diǎn)和4 個(gè)資源 關(guān)鍵字k 5 的后繼結(jié)點(diǎn)按照順時(shí)針 的方向那么應(yīng)該就是為n 8 關(guān)鍵字 同理 關(guān)鍵字k 1 5 的后繼結(jié)點(diǎn)偉n 3 6 關(guān)鍵字 k 2 8 的后繼結(jié)點(diǎn)為n 3 6 關(guān)鍵字k 4 9 的后繼結(jié)點(diǎn)為n 5 2 在該c h o r d 環(huán)上每個(gè)結(jié)點(diǎn) 都有個(gè)f i n g e r t a b l e 在這張表上該結(jié)點(diǎn)記錄了在對(duì)等網(wǎng)絡(luò)中的距離該結(jié)點(diǎn)的距離的 相應(yīng)的結(jié)點(diǎn)信息 便于以后消息的跳轉(zhuǎn)和資源的定位 每個(gè)c h o r d 結(jié)點(diǎn)也有其后 繼 結(jié)點(diǎn)n 的后繼是在c h o r d 環(huán)上緊隨n 不等于n 的第一個(gè)結(jié)點(diǎn) 記做n s u c c 懿s o r 請(qǐng)注意結(jié)點(diǎn)后繼和對(duì)象后繼有著明顯的區(qū)別 2 2 2c h o r d 的路由過(guò)程 基于c h o r d 協(xié)議所建立的結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中 結(jié)點(diǎn)和資源通過(guò)高位的h a s h 處 1 4 第二章相關(guān)算法分析 理 將每個(gè)網(wǎng)絡(luò)中的結(jié)點(diǎn)和資源部署在這個(gè)網(wǎng)絡(luò)中的某個(gè)相應(yīng)的位置 這樣便形成 了整個(gè)結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)的雛形 那么以后結(jié)點(diǎn)需要查詢(xún)某個(gè)資源時(shí) 就會(huì)根據(jù)結(jié) 點(diǎn)和資源映射的方法建立相應(yīng)的搜索方式進(jìn)行數(shù)據(jù)的查詢(xún) 當(dāng)有結(jié)點(diǎn)需要對(duì)某個(gè) 資源進(jìn)行查找時(shí) 首先此結(jié)點(diǎn)先對(duì)該資源進(jìn)行h a s h 的處理 獲取這個(gè)資源相對(duì)應(yīng) 的i d 然后查詢(xún)結(jié)點(diǎn)通過(guò)之前建立結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)的方法搜索該i d 搜索的過(guò)程 是這樣的 首先查詢(xún)結(jié)點(diǎn)對(duì)該資源進(jìn)行一個(gè)數(shù)據(jù)查詢(xún)包的封裝 然后查詢(xún)結(jié)點(diǎn)分 析自己的路由表 找出順時(shí)針?lè)较蚓嚯x該對(duì)象i d 最為接近的結(jié)點(diǎn) 同時(shí)查詢(xún)結(jié)點(diǎn) 獲取該目標(biāo)結(jié)點(diǎn)的d 地址和端口之類(lèi)的信息 查詢(xún)結(jié)點(diǎn)便開(kāi)始通過(guò)網(wǎng)絡(luò)首先鏈接 到該目標(biāo)結(jié)點(diǎn) 然后將封裝好的查詢(xún)包發(fā)送給該目標(biāo)結(jié)點(diǎn) 目標(biāo)結(jié)點(diǎn)收到數(shù)據(jù)包 后 首先分析數(shù)據(jù)查詢(xún)包得到查詢(xún)結(jié)點(diǎn)需要尋找的對(duì)象資源 然后目標(biāo)結(jié)點(diǎn)按照 查詢(xún)結(jié)點(diǎn)同樣的方式 即搜索自己的路由表找出距離資源對(duì)象i d 最為接近的結(jié)點(diǎn) 為下一個(gè)目標(biāo)結(jié)點(diǎn) 然后再將該數(shù)據(jù)查詢(xún)包轉(zhuǎn)發(fā)給它 通過(guò)上述的這些步驟 最 終查詢(xún)結(jié)點(diǎn)都會(huì)在中間結(jié)點(diǎn)的幫助下到達(dá)最終的目標(biāo)結(jié)點(diǎn) 目標(biāo)結(jié)點(diǎn)在獲取到這 個(gè)查詢(xún)包后 便將該資源對(duì)應(yīng)的存儲(chǔ)該資源的結(jié)點(diǎn)的相應(yīng)的信息組裝成數(shù)據(jù)包發(fā) 送給查詢(xún)結(jié)點(diǎn) 查詢(xún)結(jié)點(diǎn)獲取到該響應(yīng)數(shù)據(jù)包后 便提取出存儲(chǔ)結(jié)點(diǎn)的信息 然 后通過(guò)與目標(biāo)結(jié)點(diǎn)的通訊得到所想要的資源文件 k 4 9 n 3 6k 2 8 k 1 5 f i n g e rt a b l e i d c目的i d后繼 0n 8 ln 1 0 1n 8 2n 1 0 2n 8 4n 3 6 3 n 8 8 n 3 6 4n 8 1 6n 3 6 5n 8 3 2n 4 8 叩 k 4 9 圖2 2 c h o r d 環(huán)的路由過(guò)程 如圖2 2 所示 該圖展示一個(gè)基于c h o r d 環(huán)所產(chǎn)生的數(shù)據(jù)包的路由的過(guò)程 該圖展示了一個(gè)位數(shù)為6 位的結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò) 那么根據(jù)c h o r d 算法可以知道 每個(gè)結(jié)點(diǎn)都有一個(gè)f i n g c rt a b l e 即所謂的結(jié)點(diǎn)的路由表 其中表中展示了一個(gè)結(jié)點(diǎn) 的i d 為n 8 的結(jié)點(diǎn)的路由表 在c h o r d 環(huán)中 每個(gè)結(jié)點(diǎn)有m 項(xiàng)路由表項(xiàng) 因?yàn)樵?結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)是6 位 所以該網(wǎng)絡(luò)中的每個(gè)結(jié)點(diǎn)就應(yīng)該有6 項(xiàng)路由表的數(shù)據(jù) 1 5 電子科技大學(xué)碩士學(xué)位論文 這個(gè)路由表記錄的是n o d e i d 2 的對(duì)象d 是存放在哪一節(jié)結(jié)點(diǎn)i d 上面的 圖中 展示了結(jié)點(diǎn)n 8 需要查詢(xún)某個(gè)資源 而該資源的d 為k 4 9 然后該結(jié)點(diǎn)搜尋自己 的路由表發(fā)現(xiàn) 距離該資源i d 為l 9 的最為接近的結(jié)點(diǎn)是n 4 8 所以此時(shí)結(jié)點(diǎn)將 n 4 8 的相關(guān)信息得到 例如i p 地址 端口等信息 然后結(jié)點(diǎn)n 8 將這些信息打包然 后發(fā)送到結(jié)點(diǎn)n 4 8 當(dāng)結(jié)點(diǎn)n 4 8 接收到這個(gè)數(shù)據(jù)包后 首先拆分這個(gè)數(shù)據(jù)包 從中