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

c iii 心 j l 本人聲 作及取得的研究成果 據(jù)我所知 除了文中特別加以標(biāo)注和致謝的地 方外 論文中不包含其他入已經(jīng)發(fā)表或撰寫過的研究成果 也不包含 為獲得電子科技大學(xué)或其它教育機構(gòu)的學(xué)位或證書而使用過的材料 與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了明 確的說明并表示謝意 簽名 日期 z 年f 月可日 論文使用授權(quán) 本學(xué)位論文作者完全了解電子科技大學(xué)有關(guān)保留 使用學(xué)位論文 的規(guī)定 有權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和磁 盤 允許論文被查閱和借閱 本人授權(quán)電子科技大學(xué)可以將學(xué)位論文 的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索 可以采用影印 縮印或 掃描等復(fù)制手段保存 匯編學(xué)位論文 保密的學(xué)位論文在解密后應(yīng)遵守此規(guī)定 簽名 掣詈簍 二 主群 f 1 卜 摘要 摘要 隨著信息技術(shù)的發(fā)展以及網(wǎng)絡(luò)的普及 網(wǎng)絡(luò)中的許多資源都需要共享 傳統(tǒng) c s 模式的架構(gòu)幾乎不能承受住高并發(fā)量的客戶訪問 而且伴隨共享資源的增多 對服務(wù)器的存儲能力也提出了嚴(yán)峻的挑戰(zhàn) 在對等網(wǎng)絡(luò)中 每個結(jié)點參與了任務(wù) 的執(zhí)行 解決了集中式網(wǎng)絡(luò)的單點失效和網(wǎng)絡(luò)帶寬的利用率 在結(jié)構(gòu)化對等網(wǎng)絡(luò)中 資源搜索的效率是1 0 9 n 雖然這種方式比集中式c s 模式的效率要低 但是它解決了集中式網(wǎng)絡(luò)中對中心結(jié)點的依賴性 那么怎樣提 高現(xiàn)有的結(jié)構(gòu)化對等網(wǎng)絡(luò)的資源搜索效率成了一個研究的方向 本文通過對小世 界網(wǎng)絡(luò)的分析 發(fā)現(xiàn)小世界網(wǎng)絡(luò)具有縮短整個網(wǎng)絡(luò)直徑的特點 所以如果能夠在 結(jié)構(gòu)化對等網(wǎng)絡(luò)中構(gòu)建小世界網(wǎng)絡(luò) 那么資源搜索的效率就會因為小世界網(wǎng)絡(luò)的 特性而得到很大程度的提高 本文因此提出了在結(jié)構(gòu)化對等網(wǎng)絡(luò)中建立具有小世 界網(wǎng)絡(luò)特性的算法 并以數(shù)學(xué)的理論嚴(yán)格地證明了算法的正確性和優(yōu)越性 算法 的思想在于利用數(shù)據(jù)包路由的過程 按照一定的概率重建途經(jīng)的結(jié)點的短鏈鏈接 使得整個對等網(wǎng)絡(luò)具有小世界網(wǎng)絡(luò)的特性 從而降低了數(shù)據(jù)包在路由過程中轉(zhuǎn)發(fā) 的跳數(shù) 因此提高了資源搜索的效率 而且整個建立的過程需要比較小的額外開 銷 同時 在結(jié)構(gòu)化對等網(wǎng)絡(luò)中 為了對資源進行搜索 在應(yīng)用層建立了一個邏 輯結(jié)構(gòu) 那么當(dāng)結(jié)點在對多個結(jié)點選擇時 便會按照這種邏輯上的拓?fù)浣Y(jié)構(gòu)進行 結(jié)點的選擇 但是邏輯上結(jié)點之間的距離并不能代表物理網(wǎng)絡(luò)中結(jié)點之間的距離 即邏輯上相鄰的結(jié)點在實際的物理網(wǎng)絡(luò)中并不是相鄰的結(jié)點 甚至可能是相隔非 常遠(yuǎn)的結(jié)點 這便造成了邏輯層上結(jié)點之間傳輸數(shù)據(jù)所表現(xiàn)的高效性在實際的物 理網(wǎng)絡(luò)中卻是效率最低的 本文提出了對結(jié)構(gòu)化對等網(wǎng)絡(luò)進行物理區(qū)域劃分的思 想 將整個對等網(wǎng)絡(luò)在物理拓?fù)涞膶用鎰澐譃椴煌膮^(qū)域 然后當(dāng)結(jié)點加入網(wǎng)絡(luò) 時 首先確定結(jié)點所屬的區(qū)域并保存該信息 當(dāng)有結(jié)點需要對多個結(jié)點選擇時 便可以根據(jù)每個結(jié)點所保存的區(qū)域信息來判斷結(jié)點之間的相鄰程度 找出距離源 結(jié)點最為接近的結(jié)點作為目標(biāo)結(jié)點 從而解決了對等網(wǎng)絡(luò)中結(jié)點在邏輯應(yīng)用層的 結(jié)構(gòu)與物理網(wǎng)絡(luò)中的結(jié)構(gòu)的矛盾 有效地提高了結(jié)點之間數(shù)據(jù)傳輸?shù)男?關(guān)鍵詞 小世界網(wǎng)絡(luò) 對等網(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 第三章對等網(wǎng)絡(luò)中s m a u w o r m 的構(gòu)造算法設(shè)計 2 0 3 1 問題探索 2 0 3 2 s m a l l w o 訂d 特性分析 2 1 3 3 對等網(wǎng)絡(luò)中s m a l l w o r l d 的構(gòu)造 2 5 3 4 算法設(shè)計 2 7 3 5 搜索過程 3 0 3 6 算法的正確性證明 3 2 3 7 本章小結(jié) 3 5 第四章對等網(wǎng)絡(luò)中拓?fù)涫涞慕鉀Q方案 3 8 4 1 問題探索 3 8 4 2 界標(biāo)分區(qū)的分析 4 0 4 3 對等網(wǎng)絡(luò)中分區(qū)的構(gòu)造 4 3 l l i 目錄 4 4 核心算法設(shè)計 4 7 4 5 本章小結(jié) 5 0 第五章實驗分析 5 2 5 1 實驗平臺的搭建 5 2 5 2 對等網(wǎng)絡(luò)中構(gòu)建s m a l l w o r l d 的優(yōu)越性 5 2 5 3 對等網(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 參考文獻 6 5 在校期間研究成果 6 9 第一章引言 1 1 研究背景 第一章引言 網(wǎng)絡(luò)資源的共享給予了對等網(wǎng)絡(luò)的存在價值和意義 它解決了當(dāng)今互聯(lián)網(wǎng)發(fā) 展的所遇到的一些問題 例如 怎樣在網(wǎng)絡(luò)中能夠高效地提高資源的共享率 并 且能夠很大程度上的提高用戶這種需求的響應(yīng)時間 這對于網(wǎng)絡(luò)的應(yīng)用來說是一 個非常具有挑戰(zhàn)的意義 的確計算機的發(fā)展是隨著大家所熟知的摩爾定理在默默 地提高著計算機的性能 但是計算機的性能不管怎么提高也是隨著應(yīng)用的需求的 情況下才得以提高的 而且通常情況下 需求都是首先提出 然后才相應(yīng)的去想 辦法去解決這些問題 那么怎樣以一種方法可以緩解這種問題昵 眾所周知 整 個互聯(lián)網(wǎng)上有豐富的計算機資源和網(wǎng)絡(luò)帶寬資源 那么如果將這些資源加以整合 然后將要完成的任務(wù)分別變成一些的小的任務(wù)模塊 分別將這些小模塊分發(fā)給這 些閑散的計算機 讓它們?nèi)ソ鉀Q這個問題 那么便可以大大的提高計算機的資源 利用率 而且也解決了對某一種超級計算機資源的依賴和所有網(wǎng)絡(luò)資源的利用 分布式網(wǎng)絡(luò)就是這種情況下應(yīng)運而生的 其中對等網(wǎng)絡(luò)就是其中的一種 它讓整 個網(wǎng)絡(luò)中的計算機都被調(diào)動起來 統(tǒng)一地相互協(xié)作地完成一個任務(wù) l 卅 在對等式網(wǎng)絡(luò)中 每一臺網(wǎng)絡(luò)中的計算機之間沒有所謂的主次之分 各自在 從網(wǎng)絡(luò)上獲取資源的同時也在為網(wǎng)絡(luò)中的其它計算機提供服務(wù) 這種互惠互利的 思想完整地被用在了對等網(wǎng)絡(luò)中 這便變相的調(diào)動了網(wǎng)絡(luò)中的所有參與的計算機 使他們齊心協(xié)力地為整個網(wǎng)絡(luò)中的計算機提供服務(wù) 這種 人人為我 我為人人 的思想將資源的利用率得到了極大的提高 同時 傳統(tǒng)集中式網(wǎng)絡(luò)應(yīng)用中的對超 級計算機的依賴性 因為這種模式的網(wǎng)絡(luò)的產(chǎn)生而得到了解決 而且這種方式可 以解決核心骨干網(wǎng)絡(luò)的帶寬可以得到更大用處的利用 因為傳統(tǒng)方式的集中式的 網(wǎng)絡(luò)中 客戶端為了獲取資源必須從處于遠(yuǎn)方的服務(wù)器上的資源經(jīng)過骨干網(wǎng)絡(luò)傳 輸才能得到 那么如果同時同一個區(qū)域的計算機對這樣的資源的請求 就會造成 這種資源的重復(fù)的傳輸 相反 如果采用對等網(wǎng)絡(luò) 那么結(jié)點便會從周圍結(jié)點獲 取相應(yīng)的資源進行數(shù)據(jù)的傳輸 從而減小了骨干網(wǎng)絡(luò)的壓力 增大了邊緣網(wǎng)絡(luò)中 的帶寬的利用率 5 8 對等網(wǎng)絡(luò)的另外一個優(yōu)勢是在對等網(wǎng)絡(luò)中 整個對等網(wǎng)絡(luò)中有一個應(yīng)用層的 電子科技大學(xué)碩士學(xué)位論文 結(jié)構(gòu) 9 這個結(jié)構(gòu)是按照某種方式生成的 比如高位的h a s h 1 0 的方式 這樣當(dāng)網(wǎng) 絡(luò)中有資源需要共享時 首先將該資源通過這種h 砒的方式將這些資源放置在距 離該資源i d 最為接近的結(jié)點上 這樣當(dāng)網(wǎng)絡(luò)中的結(jié)點在查詢這個資源時 就可以 根據(jù)這種放置的關(guān)系和這個網(wǎng)絡(luò)的結(jié)構(gòu)進行搜索 相對于無結(jié)構(gòu)式的對等網(wǎng)絡(luò)的 洪泛式搜索 搜索的效率提高了很多 而且這種方式對于結(jié)點的加入或者退出 都可以很容易地進行擴展和調(diào)整 目前基于這種思路的結(jié)構(gòu)化對等網(wǎng)絡(luò)的路由算 法也相應(yīng)的出現(xiàn) 比如 c h o r d 1 1 1 t a p e s 時 1 2 1 p a s d l 3 這些路由算法的核心 都是基于一種d h t 1 4 的方式 即分布式哈希表的方式 讓整個網(wǎng)絡(luò)中所有結(jié)點和 共享的資源都被部署在這個很大的h a s h 表上面 然后根據(jù)不同的規(guī)則進行劃分和 路由 通常這種方式構(gòu)成的對等網(wǎng)絡(luò)中 路由的跳數(shù)都在o o g n 其中n 為該對 等網(wǎng)絡(luò)中結(jié)點的總個數(shù) 目前 因為對等網(wǎng)絡(luò)的這些有利的條件和優(yōu)勢 在實際的網(wǎng)絡(luò)應(yīng)用 對等網(wǎng) 絡(luò)的應(yīng)用隨處可見 比如最為熟悉的網(wǎng)絡(luò)下載工具中的b t 和電驢以及迅雷 這些 都是利用了對等網(wǎng)絡(luò)最為基本的核心的思想 人人為我 我為人人 它們這種資 源共享的方式正體現(xiàn)了對等網(wǎng)絡(luò)的優(yōu)良特性 在對等網(wǎng)絡(luò)中 結(jié)點之間通過互相知道周圍鄰近的結(jié)點的消息 那么正是利 用這方面的條件下 網(wǎng)絡(luò)中的數(shù)據(jù)包在轉(zhuǎn)發(fā)的過程中 每一個結(jié)點都會通過自身 所知道的網(wǎng)絡(luò)中的鄰近的結(jié)點信息進行數(shù)據(jù)包的轉(zhuǎn)發(fā) 從而保證消息包的正確到 達 這與傳統(tǒng)的計算機網(wǎng)絡(luò)中的網(wǎng)絡(luò)層的路由一樣 但是 這種轉(zhuǎn)發(fā)的效率還能 夠得到提高嗎 通過對小世界網(wǎng)絡(luò)中的短鏈存在效應(yīng)的影響 可以發(fā)現(xiàn) 如果在 結(jié)構(gòu)化對等網(wǎng)絡(luò)中建立小世界網(wǎng)絡(luò) 那么在轉(zhuǎn)發(fā)數(shù)據(jù)包的時候 同時也利用這個 特性 那么數(shù)據(jù)的轉(zhuǎn)發(fā)效率將會得到很大的提高 本文中的第三章就是基于這種 思路的影響下 構(gòu)造出了怎樣在基于c h o r d 路由算法的條件下構(gòu)造出這種特性的 網(wǎng)絡(luò) 同時 大家都知道 在對等式網(wǎng)絡(luò)中 結(jié)點之間在應(yīng)用層面有一個邏輯的 結(jié)構(gòu) 而且大部分的考慮的因素都會基于這種邏輯的結(jié)構(gòu)進行分析 那么這就可 能會造成在實際應(yīng)用中 這種應(yīng)用層面的結(jié)構(gòu)和實際的物理結(jié)構(gòu)的異構(gòu)性所帶來 的性能的影響 1 5 0 6 例如 當(dāng)結(jié)點之間需要傳輸數(shù)據(jù) 而此時有多個結(jié)點有這個 資源 其中有一個結(jié)點是該結(jié)點的物理鄰居結(jié)點 其他結(jié)點都是它的遠(yuǎn)程結(jié)點 但是邏輯結(jié)構(gòu)上 這種關(guān)系剛好反過來 那么此時 如果結(jié)點按照應(yīng)用層面的結(jié) 構(gòu)選擇了遠(yuǎn)程結(jié)點進行數(shù)據(jù)傳輸時 那么結(jié)點之間的數(shù)據(jù)的傳輸將會大大地打折 扣 本文就提出了一種對結(jié)點進行分區(qū)的思想 將每一個結(jié)點的物理位置進行劃 分 為以后結(jié)點的選擇中提供選擇的依據(jù) 第四章就是基于這種思路 完整地描 2 第一章引言 述了怎樣對結(jié)點進行分區(qū)的思想和結(jié)點的選擇的方法 1 2 研究現(xiàn)狀 在結(jié)構(gòu)化對等網(wǎng)絡(luò)中 每個結(jié)點的的作用消除了普通網(wǎng)絡(luò)中依賴部分結(jié)點的 依賴性 同時也將網(wǎng)絡(luò)中邊緣網(wǎng)絡(luò)上的帶寬的利用率得到了有效地利用 隨著對 等網(wǎng)絡(luò)的應(yīng)用的不斷深入 學(xué)者對于該技術(shù)的研究也在不斷的深化過程中 伴隨 著這些研究 相應(yīng)的對等網(wǎng)絡(luò)也經(jīng)歷了多個發(fā)展階段 通?？梢詫Φ染W(wǎng)絡(luò)的發(fā) 展劃分為這么幾個過程 集中式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)的對等網(wǎng)絡(luò)也有相應(yīng)的商業(yè)的產(chǎn) 物 比如曾經(jīng)流行一時的音樂共享軟件n a p s t d r 7 1 因為版權(quán)的問題最終面臨倒閉 國外而且也有許多這些方面的研究和應(yīng)用 比如國外的o c e a i l s t o r e 系統(tǒng)等 國內(nèi)也 有不少對等網(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 通過一個索引服務(wù)器和若干終端結(jié)點以一種星型邏 輯的結(jié)構(gòu)所構(gòu)成 在集中式p 2 p 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中 中央索引服務(wù)器存放資源文件 的索引信息 而終端結(jié)點才真正的保存資源文件 這樣每當(dāng)終端結(jié)點需要某個資 源的時候 終端結(jié)點便通過與索引服務(wù)器通信 查詢此資源文件所在的客戶端的 位置 一旦獲取了資源的位置信息后 客戶端便與資源所在的客戶端進行通訊 從而獲取該資源文件 因此中央服務(wù)器只是起著供客戶端查詢資源的作用 并沒 有真正地存儲所需要的資源文件 而且客戶端不僅與服務(wù)器端進行通訊還要和其 它客戶端進行通訊以便得到所需要的資源文件 集中式的p 2 p 的不足仍然和傳統(tǒng) 3 電子科技大學(xué)碩士學(xué)位論文 的c s 模式一樣 終端結(jié)點非常依賴中央索引服務(wù)器 同樣存在單點失效的問題 和性能瓶頸的問題 1 8 19 1 而傳統(tǒng)的c s 模型中如圖1 2 服務(wù)器上擁有整個網(wǎng)絡(luò)所需要的資源文件 當(dāng) 客戶端需要資源時 客戶端首先和服務(wù)器進行交互 當(dāng)服務(wù)器查詢本機的資源和 授權(quán)以后便將資源傳送給客戶端 這種架構(gòu)就說明 服務(wù)器端必須全天候2 4 小時 的正常運作 否則整個對外提供的服務(wù)將會中斷 而且這種結(jié)構(gòu)也決定了服務(wù)器 必須有容納所有客戶端需要的資源的容量和足夠的計算能力 帶寬能力才能保障 對客戶端的高效的服務(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 流行一時 它通過基 于集中式的p 2 p 網(wǎng)絡(luò)的模型來構(gòu)建 但是由于n a p s t e r 所索引的文件涉及到了知識 版權(quán)的問題 最終導(dǎo)致n a p s t e r 停止運行 但是n a p s t e r 的停止運行并沒有阻止p 2 p 的廣泛應(yīng)用潛力和前景 更沒有阻擋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ò)是 通過結(jié)點之間的任意的鏈接而形成 整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與一個網(wǎng)狀的結(jié)構(gòu)很相似 這種拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)對于結(jié)點的加入或者退出的頻率不會有很大的影響 具有很 好的適應(yīng)性 而且在該網(wǎng)絡(luò)中 結(jié)點之間可以像普通的i n t e r n e t 一樣 對資源進 行模糊查詢 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 那樣需要一個中心的索引服務(wù)器 在g n u t e l l a 中 每個結(jié)點既是客戶端又是服務(wù)器 從而沒有n a p s t e r 的那種單點失效的問題 在 g n u t e l l a 中 每當(dāng)對等結(jié)點需要查詢資源文件的時候 是通過隨機洪泛的方式來 進行傳播請求的 為了避免有很多請求一直在網(wǎng)絡(luò)中為 g n u t e l l a 也仿照t c p i p 協(xié)議通過采用t t l 2 1 的方式來進行請求消息的控制 g n u t e l l a 的查詢流程如圖 1 4 查詢流 辱耐 下載流 一弗 圖1 4 c h u t e l l a 的查詢流程 在完全分布式非結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò)中 當(dāng)結(jié)點的個數(shù)很少的時候可以很快的查詢 到所需要的資源 當(dāng)隨著結(jié)點個數(shù)的增加的時候 查詢資源所需要的時間就會隨 著結(jié)點的個數(shù)的增加而增加 而且由于是采用隨機洪泛的方式來進行查詢的 所 以一旦網(wǎng)絡(luò)規(guī)模變大后 網(wǎng)絡(luò)中的查詢數(shù)據(jù)請求會逐漸增多 嚴(yán)重的影響網(wǎng)絡(luò)的 負(fù)載 此外 由于網(wǎng)絡(luò)沒有確定的拓?fù)浣Y(jié)構(gòu) 查詢采用的是隨機的方式 這樣便 可能會造成有些資源的漏查 由此便導(dǎo)致了網(wǎng)絡(luò)的可擴展性降低 2 2 2 3 電子科技大學(xué)碩士學(xué)位論文 1 2 2 完全分布式結(jié)構(gòu)化p 2 p 網(wǎng)絡(luò) 由于完全分布式非結(jié)構(gòu)化網(wǎng)絡(luò)中對于資源的搜索可能會造成漏搜以及這種搜 索方式的不可靠性 同時網(wǎng)絡(luò)中可能會存在著過多的搜索請求 研究者就開始研 究如何構(gòu)造一個p 2 p 的對等網(wǎng)絡(luò)來解決這些問題 目前 學(xué)者們研究如何構(gòu)造結(jié) 構(gòu)化的對等網(wǎng)絡(luò)來有效地提高查找資源信息 經(jīng)過研究發(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 表的方式來構(gòu)造整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu) 形成一個結(jié)構(gòu)化的對等網(wǎng)絡(luò) 然后結(jié)點通過這個分布式h a s h 表來將自身散列到這 張表上 同時需要共享的資源也通過這張哈希表將資源信息散列到相應(yīng)的結(jié)點上 當(dāng)結(jié)點剛剛加入這個結(jié)構(gòu)化的對等網(wǎng)絡(luò)時 首先可以根據(jù)這個結(jié)點的特有信息 比如i p 地址 將這些信息通過散列函數(shù) 映射成一個n o d e i d 然后根據(jù)這個 n o d e i d 這個結(jié)點就散列到了這個h a s h 表上面 從而便在這個邏輯的拓?fù)浣Y(jié)構(gòu)上 有了自己的位置 然后這個結(jié)點通過某種方式獲取基于這個邏輯拓?fù)浣Y(jié)構(gòu)上的周 圍一些結(jié)點 以便能夠?qū)⑦@些結(jié)點和自身聯(lián)系起來 便于形成一個路由表 這類 似于t c p 口中的路由表 周圍的結(jié)點也可以通過這種方式感應(yīng)到周圍有了新結(jié)點 已經(jīng)加入這個結(jié)構(gòu)化的p 2 p 網(wǎng)絡(luò) 于是便更新自身的路由表 從而保持整個p 2 p 網(wǎng)絡(luò)處于最新的拓?fù)浣Y(jié)構(gòu) 當(dāng)周圍有結(jié)點退出這個網(wǎng)絡(luò)的時候 周圍的結(jié)點可以 通過周期性的探測周圍的結(jié)點來發(fā)現(xiàn)這些退出的結(jié)點 然后將這些退出的結(jié)點從 自身的路由表中移除 從而保證整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的正確性 通過以時間的方 式來換取網(wǎng)絡(luò)的正確性見圖1 5 對于某個結(jié)點若要共享某個資源 那么首先通過 這個h 礎(chǔ)表 根據(jù)這個對象的一些屬性例如文件名 將這個對象映射成一個 0 i b j e c t i d 然后在之前已經(jīng)建立的那個h a s h 表上面找出最為接近這個o b j e c t i d 的 n o d e i d 然后將這個文件的一些屬性信息比如擁有這個文件的結(jié)點的口地址 文件 大小等告訴給n o d e i d 所在的結(jié)點 這樣 這個結(jié)點便就有了這個文件的信息 當(dāng) 有某個結(jié)點想要查詢這個文件的時候 首先通過摘取這個文件的關(guān)鍵信息 比如 文件名 然后通過h a s h 的方式獲取該文件的散列值o b j e c t i d 此時這個結(jié)點便通 過結(jié)點所存儲的路由表的信息的方式來查詢擁有o b i e c t d 的結(jié)點i 當(dāng)查詢信息到 達該結(jié)點后 那么該結(jié)點將這個文件的一些信息例如存儲該結(jié)點的i p 地址和端口 號告訴給客戶端 6 基于h 韶h 方式是網(wǎng)絡(luò)中的所有結(jié)點統(tǒng)一地按照這種方式將結(jié)點和資源部署到 這個表中 因此 隨著結(jié)點數(shù)目的增多 表也在不斷地擴大 哈希表中的每一個 結(jié)點可以負(fù)責(zé)一些資源的保存和維護 通過按照結(jié)點m 和資源對象i d 相近原則 只要找出與資源i d 最為接近的結(jié)點 然后將這些資源的維護都賦予給該結(jié)點 那 么便可實現(xiàn)資源和結(jié)點的共存 按照這種方式 每個結(jié)點可以負(fù)責(zé)一個段的資源 的保存 當(dāng)網(wǎng)絡(luò)中有結(jié)點加入或者退出網(wǎng)絡(luò)時 便可以將資源的信息正確地轉(zhuǎn)移 到相應(yīng)的結(jié)點即可 從而保證此方法的可擴展性 基于d h t 的網(wǎng)絡(luò)的最大缺點在于網(wǎng)絡(luò)中突然某個時間段有大量的結(jié)點的加入 和退出 這個時候由于網(wǎng)絡(luò)沒辦法能夠及時地通知其他結(jié)點當(dāng)前的網(wǎng)絡(luò)的正確的 拓?fù)浣Y(jié)構(gòu) 而造成網(wǎng)絡(luò)服務(wù)的不可用 即所謂的網(wǎng)絡(luò)擾動問題 2 純刀 另外一個問 題是基于d h t 的查找不能夠?qū)λ璧馁Y源進行模糊查找 2 8 同時 對等網(wǎng)絡(luò)中的 還沒有形成一個很好的安全檢測機制 2 9 1 從而有效地避免不良用戶對整個對等網(wǎng) 絡(luò)的攻擊 目前已有的結(jié)構(gòu)化結(jié)構(gòu)的對等網(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ò)對于資源的快速搜索有很好的優(yōu)勢 但是一旦入 侵者攻擊集中式網(wǎng)絡(luò)中的中心服務(wù)器 那么毫無疑問 集中式網(wǎng)絡(luò)將中斷所有的 7 電子科技大學(xué)碩士學(xué)位論文 服務(wù) 而且集中式網(wǎng)絡(luò)根本上就沒有將網(wǎng)絡(luò)中邊緣網(wǎng)絡(luò)的帶寬利用 而分布式網(wǎng) 絡(luò)雖然解決了中心服務(wù)器的單點失效的問題 但是卻在網(wǎng)絡(luò)中對于資源的搜索速 度上卻下降了下去 而且為了確保整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的準(zhǔn)確性 不得不花費很 大的開銷來維持整個網(wǎng)絡(luò) 圖1 6 混合式p 2 p 網(wǎng)絡(luò) 為了結(jié)合集中式和分布式網(wǎng)絡(luò)的優(yōu)點 同時彌補他們的缺點 混合式p 2 p 網(wǎng)絡(luò)由此誕生見圖1 6 混合式網(wǎng)絡(luò)結(jié)合兩者的長處 在混合式網(wǎng)絡(luò)中 結(jié)點 按照功能分為三類 其中一類為索引結(jié)點 一類為搜索結(jié)點 另外一類為普通的 終端結(jié)點 其中索引結(jié)點維持著網(wǎng)絡(luò)中搜索結(jié)點的信息 搜索結(jié)點管理著文件列 表的信息 而終端結(jié)點即為存儲了資源文件的普通結(jié)點 當(dāng)有新結(jié)點加入該網(wǎng)絡(luò) 時 終端結(jié)點便找到一個結(jié)點作為它的搜索結(jié)點 然后該普通結(jié)點便將自己需要 共享的資源文件的信息列表發(fā)送給該搜索結(jié)點 每當(dāng)結(jié)點需要搜索某個資源文件 時 便首先通過索引結(jié)點找到首個為此次查詢服務(wù)的搜索結(jié)點 然后搜索結(jié)點便 通過查找自身存儲的資源文件的列表來查找是否有該資源的信息 如果沒有便將 該查詢隨機洪泛式地轉(zhuǎn)發(fā)到另外的相鄰的搜索結(jié)點 直到某個搜索結(jié)點獲取該資 源文件的信息并將該信息傳輸給查詢源結(jié)點 如果一直都沒有找到該資源文件那 么便通知源查詢結(jié)點 1 3 研究目的和內(nèi)容 第一章引言 結(jié)構(gòu)化對等網(wǎng)絡(luò)是在物理網(wǎng)絡(luò)的基礎(chǔ)上按照某種邏輯方式構(gòu)建一個邏輯拓?fù)?結(jié)構(gòu) 因此邏輯上相鄰的結(jié)點可能在實際的物理網(wǎng)絡(luò)上相距甚遠(yuǎn) 即所謂的拓?fù)?失配見圖1 7 3 2 即如果諸多p c 結(jié)點通過i i l t 鋤e t 網(wǎng)絡(luò)互連 相互間通過i i l t e m e t 便 形成了物理拓?fù)浣Y(jié)構(gòu)上的網(wǎng)絡(luò) 然后這些結(jié)點通過相應(yīng)的某種方式建立某種邏輯拓 撲結(jié)構(gòu) 此時物理拓?fù)浣Y(jié)構(gòu)上的p c 結(jié)點便與其它位置的p c 結(jié)點組成了某個邏輯上 的拓?fù)浣Y(jié)構(gòu) 當(dāng)某個p c 結(jié)點需要查詢某個資源時 此時可能擁有這個資源的結(jié)點 有多個 當(dāng)該查詢結(jié)點查到了多個擁有該資源的信息時 該怎么選擇哪個結(jié)點進 行傳輸呢 可能查詢結(jié)點會從中選擇一個結(jié)點進行數(shù)據(jù)傳輸 默認(rèn)情況 結(jié)點一 般都會選擇在邏輯拓?fù)渖舷噜彽慕Y(jié)點作為傳輸?shù)慕Y(jié)點 那么就會造成結(jié)點間的延 時變大 p c 4p c 5 圖1 7 網(wǎng)絡(luò)物理拓?fù)渑c邏輯拓?fù)涫?例如結(jié)點p c 3 想要下載某個資源文件a 結(jié)果資源文件a 在結(jié)點p c 4 和p c 5 都擁 有 但是默認(rèn)情況下結(jié)點p c 3 應(yīng)該會選擇結(jié)點p c 4 進行通訊 然后便進行數(shù)據(jù)的交 互 但是雖然邏輯拓?fù)渖辖Y(jié)點p c 3 與結(jié)點p c 4 彼此相鄰 但是實際物理拓?fù)浣Y(jié)構(gòu)上 結(jié)點p c 3 與結(jié)點p c 4 可能相差甚遠(yuǎn) 比如結(jié)點p c 3 位置在成都 結(jié)點p c 5 位置在北京 然后結(jié)點p c 4 位置在紐約 如果這時結(jié)點p c 4 與結(jié)點p c 3 進行通訊肯定比結(jié)點p c 3 與結(jié)點p c 5 的時延大的多 這就是所謂的邏輯拓?fù)涫?所以 如果能夠找到某種 9 電子科技大學(xué)碩士學(xué)位論文 方式將這些結(jié)點的物理的大概位置結(jié)合起來 那么綜合考慮這些因素 然后找出 一個最優(yōu)的結(jié)點進行傳輸 對于剛才這樣的這種情況 結(jié)點p c 3 則應(yīng)該要選擇結(jié)點 p c 5 進行數(shù)據(jù)通訊 那么對于延時的情況就會有很大的改善 這便大大提高了用戶 的響應(yīng)速度 因此在結(jié)構(gòu)化對等網(wǎng)絡(luò)中 怎樣按照某種方式來彌補這種物理上和邏輯上結(jié) 構(gòu)的差異性所帶來的性能的降低 本文通過在結(jié)構(gòu)化對等網(wǎng)絡(luò)的基礎(chǔ)上 通過在 該網(wǎng)絡(luò)中 當(dāng)新結(jié)點加入這個網(wǎng)絡(luò)時 便首先通過將該結(jié)點與網(wǎng)絡(luò)中的參照結(jié)點 進行距離的測試 來找出結(jié)點的相對位置 并將該位置存儲在每個結(jié)點上面 當(dāng) 網(wǎng)絡(luò)中有結(jié)點在選擇其他結(jié)點時 那么便可以通過比較不同的結(jié)點與選擇結(jié)點的 物理位置的相隔距離來找出最為接近查詢結(jié)點的目標(biāo)結(jié)點 從而實現(xiàn)數(shù)據(jù)資源的 高速傳輸 在結(jié)構(gòu)化對等網(wǎng)絡(luò)中 通常結(jié)點之間按照某種算法將將彼此之間連接起來 然后按照相應(yīng)的方式對資源數(shù)據(jù)進行查詢 像這樣的算法已經(jīng)有了很多 比如 c h o r d c a n 等 通常這些算法實現(xiàn)的數(shù)據(jù)的查詢的效率都是將近l o g n 那么有沒有 一種更好的方法來提高這個已有的資源的搜索的效率昵 并且這種方法相對于比 較獨立而且不需要過多的開銷 本文就通過了結(jié)合小世界的效應(yīng)的方式通過如何 在結(jié)構(gòu)化對等網(wǎng)絡(luò)中構(gòu)建一個小世界網(wǎng)絡(luò)的形式來提高結(jié)點之間的數(shù)據(jù)的傳輸效 率 一旦結(jié)構(gòu)化對等網(wǎng)絡(luò)中建立起了小世界網(wǎng)絡(luò)后 那么結(jié)點便可以利用小世界 的特性來對資源進行高效的數(shù)據(jù)傳輸 因為在小世界網(wǎng)絡(luò)中 結(jié)點之間會有小世 界所特有的短鏈鏈接 這種鏈接將整個網(wǎng)絡(luò)的結(jié)點之間的距離縮小 從而提高了 結(jié)點之間的數(shù)據(jù)傳輸?shù)男?1 4 論文結(jié)構(gòu) 本文總共分為五個部分 第一部分首先通過對論文中所研究的對等網(wǎng)絡(luò)的整 個發(fā)展過程進行介紹 并對每個階段的對等網(wǎng)絡(luò)進行分析 然后對該論文的的研 究目的和內(nèi)容進行論述 第二章對這種網(wǎng)絡(luò)中的相關(guān)的路由進行描述 同時也指 出了在結(jié)構(gòu)化對等網(wǎng)絡(luò)中的當(dāng)前一些問題 第三章通過在結(jié)構(gòu)化對等網(wǎng)絡(luò)中提出 了怎樣提高數(shù)據(jù)的轉(zhuǎn)發(fā)速度的方法 通過對小世界特性和結(jié)構(gòu)化對等網(wǎng)絡(luò)中的結(jié) 合 提出了一種如何在結(jié)構(gòu)化對等網(wǎng)絡(luò)中建立一種小世界網(wǎng)絡(luò)的方法來解決這個 問題 然后描述 分析 證明了建立這種模型的整個過程 第四章首先分析了在 結(jié)構(gòu)化對等網(wǎng)絡(luò)中 結(jié)點之間在應(yīng)用層的結(jié)構(gòu)關(guān)系與結(jié)點在實際的物理網(wǎng)絡(luò)中的 l o 第一章引言 結(jié)構(gòu)關(guān)系的異構(gòu)性 然后分析了這種問題將會帶來的問題 然后提出了在結(jié)點加 入結(jié)構(gòu)化對等網(wǎng)絡(luò)時 將該結(jié)點進行歸宿地的劃分 并且將該結(jié)點的歸宿地的劃 分存儲在每個結(jié)點上面 那么在以后的對結(jié)點的選擇的過程中 便可以通過這些 數(shù)據(jù) 首先找到距離源結(jié)點最為接近的區(qū)域結(jié)點 然后再在相同距離的區(qū)域中找 出更接近源結(jié)點的目標(biāo)結(jié)點 這便解決了應(yīng)用層的邏輯結(jié)構(gòu)與實際網(wǎng)絡(luò)中的結(jié)構(gòu) 的不一致性的問題 這些方法都在第四章完整地描述了整個過程 第五章對整個 對等網(wǎng)絡(luò)中的當(dāng)前存在的問題進行了分析和描述 并說明了整個互聯(lián)網(wǎng)中對等網(wǎng) 絡(luò)的應(yīng)用的程度和以后對等網(wǎng)絡(luò)的應(yīng)用趨勢 1 5 本章小結(jié) 網(wǎng)絡(luò)資源的共享給予了對等網(wǎng)絡(luò)的存在的價值和意義 它解決了當(dāng)今互聯(lián)網(wǎng) 發(fā)展的所遇到的一些問題 例如 怎樣在網(wǎng)絡(luò)中能夠高效地提高資源的共享率 并且能夠很大程度上的提高用戶這種需求的響應(yīng)時間 這對于網(wǎng)絡(luò)的應(yīng)用來說是 一個非常具有挑戰(zhàn)的意義 的確計算機的發(fā)展是隨著大家所熟知的摩爾定理在默 默地提高著計算機的性能 但是計算機的性能不管怎么提高也是隨著應(yīng)用的需求 的情況下才得以提高的 而且通常情況下 需求都是首先提出 然后才相應(yīng)的去 想辦法去解決這些問題 那么怎樣以一種方法來可以緩解這種問題呢 總所周知 整個互聯(lián)網(wǎng)上有豐富的閑置的計算機資源 那么如果將這些閑散的計算機資源加 以整合 然后將任務(wù)分別變成一些的小的任務(wù)模塊 分別將這些小模塊分發(fā)給這 些閑散的計算機 讓它們?nèi)ソ鉀Q這個問題 那么便可以大大的提高計算機的資源 利用率 而且也解決了對某一種超級計算機資源的依賴 那么對等網(wǎng)絡(luò)就是這種 情況下應(yīng)運而生的 它讓整個網(wǎng)絡(luò)中的計算機都被調(diào)動起來 統(tǒng)一地相互協(xié)作地 完成一個任務(wù) 9 1 這種網(wǎng)絡(luò)稱之為對等式網(wǎng)絡(luò) 而對等網(wǎng)絡(luò)恰好是這種網(wǎng)絡(luò)中的一 種 整個對等網(wǎng)絡(luò)在發(fā)展的過程中經(jīng)歷了很多個階段 正如第二節(jié)所介紹的那樣 這些發(fā)展都是基本圍繞著整個對等式網(wǎng)絡(luò)中所遇到的問題而提出的解決方案 因 為大家都知道 在對等式網(wǎng)絡(luò)中針對如何提高網(wǎng)絡(luò)中資源的查詢的效率 一直是 對等網(wǎng)絡(luò)中很核心和關(guān)鍵的問題 所以這些對等網(wǎng)絡(luò)的發(fā)展也就是隨著這個問題 的改善而提出的 電子科技大學(xué)碩士學(xué)位論文 2 1p 2 p 的搜索技術(shù) 第二章相關(guān)算法分析 在結(jié)構(gòu)化的對等網(wǎng)絡(luò)中 每一個網(wǎng)絡(luò)中的計算機被稱為一個對等結(jié)點 每一個 需要共享的資源文件稱為對象 通常情況下 結(jié)點計算機和共享的資源文件都需 要在整個結(jié)構(gòu)會對等網(wǎng)絡(luò)中被部署 那么按照什么方式將這些結(jié)點和資源文件部 署呢 最為成熟的做法是 將每一個計算機和共享的資源按照它們的某個比較唯 一的屬性 然后將這個屬性值轉(zhuǎn)化成一個標(biāo)示符 這樣不同的計算機和資源就可 以對應(yīng)到不同的標(biāo)識符 從而保證其唯一性 首先對于一臺計算機而言 因為計 算機進入了h t 鋤e t 所以每一臺計算機都有一個才口地址 因為每一臺計算機的 i p 地址都不同 所以可以利用計算機的口地址將每一臺計算機映射到一個相應(yīng)的 標(biāo)識符 從而使得與不同的計算機有所區(qū)別 對于資源來說 因為每一個資源都 有相應(yīng)的關(guān)鍵字信息 那么可以通過每個資源的關(guān)鍵字或者資源的文件名映射為 一個標(biāo)識符 然后根據(jù)這個相應(yīng)的標(biāo)識符來區(qū)別不同的資源 將結(jié)點和資源映射 為一個標(biāo)識符以后 便可以按照某種分配的策略 將結(jié)點和共享的資源分配到標(biāo) 識符空間中 因為不同的方法 都會使得每一個結(jié)點負(fù)責(zé)一部分的資源的信息 也就是將一個標(biāo)識符空間分割為不同大小的段 其中每一個結(jié)點負(fù)責(zé)不同的段 然后將每一個資源分配到相應(yīng)的段 然后負(fù)責(zé)這個段的結(jié)點便將資源的信息保存 即標(biāo)識符 h a s h 名字 由此結(jié)點的標(biāo)識符 h a s h 結(jié)點的i p 資源文件的標(biāo)示符 h a s h 資源文件的名字或者關(guān)鍵值 通常散列函數(shù)會給每一個不同的計算機和資源分配一個標(biāo)識符 然后根據(jù)不同 的標(biāo)識符來構(gòu)造對等網(wǎng)絡(luò)的結(jié)構(gòu) 但是有可能是不同的結(jié)點或者資源而散列到相 同的標(biāo)識符 這便是散列函數(shù)里面的沖突 因為這種沖突是不可避免的 那么怎 樣解決這種沖突呢 通常的做法是將散列函數(shù)的空間擴大 保證散列函數(shù)的值空 間的大小和結(jié)點與資源的個數(shù)規(guī)模相當(dāng) 然后這樣便可以實現(xiàn)不同的結(jié)點和資源 有不同的標(biāo)識符 結(jié)構(gòu)化對等網(wǎng)絡(luò)p 2 p 中 每個結(jié)點都會對應(yīng)到這個散列函數(shù)值空間的一部分 這樣以后 假設(shè)某個資源文件通過散列函數(shù)獲得的散列值落入這個結(jié)點所管轄的 空間中 那么這個結(jié)點便會負(fù)責(zé)保存這個資源文件的一些基本信息 比如這個資 1 2 第二章相關(guān)算法分析 源文件的名字 大小 以及擁有這個資源文件的客戶端的i p 地址等 那么當(dāng)某個 客戶端結(jié)點要查詢這個資源文件時 便通過這個文件的標(biāo)識符來查詢 通過所構(gòu) 造的對等網(wǎng)絡(luò)的路由算法來搜索該標(biāo)識符 當(dāng)搜索到了這個結(jié)點后 便發(fā)現(xiàn)該結(jié) 點上存儲這個資源文件的一些基本信息 于是便將該文件的這些基本信息發(fā)送到 查詢結(jié)點 然后查詢結(jié)點便可以通過這些信息來獲取這個資源文件 基于d h t 網(wǎng)絡(luò)中的搜索實現(xiàn)主要有以下幾點 第一 每個結(jié)點都擁有一個 表 這樣就可以保證當(dāng)查詢數(shù)據(jù)包到來時 便可以 通過這表來獲取需要下一跳的結(jié)點的地址是哪一個 通常查詢數(shù)據(jù)包的格式是這 樣的 應(yīng)該是 這樣這個標(biāo)識符被陸續(xù) 的在整個對等網(wǎng)絡(luò)中進行傳輸 經(jīng)過的結(jié)點也清楚地知道需要查詢哪個資源文件 而每個結(jié)點都會保存它所負(fù)責(zé)的資源文件的信息 一般來說都是保存資源文件的 標(biāo)識符最為接近該結(jié)點的標(biāo)識符 這樣在查詢該資源文件的時候 通過這個文件 的標(biāo)識符便對應(yīng)到查詢該結(jié)點的標(biāo)識符 從而從文件查詢轉(zhuǎn)移到了結(jié)點的查詢 對于當(dāng)有新結(jié)點或者新的資源文件加入對等網(wǎng)絡(luò)時 便可以通過將新加入的資源 文件的標(biāo)識符信息保存在對應(yīng)的結(jié)點上 或者將應(yīng)該轉(zhuǎn)移的資源信息轉(zhuǎn)移到新加 入的結(jié)點上 對于當(dāng)有結(jié)點移出時 此時可以講該結(jié)點所擁有的資源文件的信息 轉(zhuǎn)移到臨近的結(jié)點上 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 等人提出 它的思想主要是 為了能夠解決在對等網(wǎng)絡(luò)中怎樣搜索對等網(wǎng)絡(luò)中的資源文件 它的完美性源自于 它的簡單性和伸縮性 d h t 是通過將相應(yīng)的字符串等信息轉(zhuǎn)換成一個標(biāo)識符 這 樣每個結(jié)點或者資源文件便可以映射到這個標(biāo)識符 這個標(biāo)識符是在一個lo 2 一li 區(qū)間中的整數(shù) 這樣便可以將每個結(jié)點和資源文件的標(biāo)識符對應(yīng)在一個一維的對2 取模的標(biāo)識符環(huán)上面 取值范圍為 2 一1 o c h o r d 是最簡單 最精確的環(huán)形p 2 p 模型 由此 o r d 便形成了一個具有環(huán)形拓?fù)浣Y(jié)構(gòu)的環(huán) 每一個結(jié)點都可以通過 散列函數(shù)將結(jié)點映射到這個環(huán)上 每一個資源文件也可以通過散列函數(shù)將這個資 源文件映射出一個標(biāo)識符 從而對應(yīng)到相應(yīng)的這個環(huán)上的某個位置上去 c h o r d 通過散列函數(shù)如s h a 給每個網(wǎng)絡(luò)結(jié)點和每個數(shù)據(jù)對象分配唯一的i d 即n o d e i d h n o d e 的屬性 h 為散列函數(shù) n o d e 的屬性可以包括該結(jié)點的口地址 1 3 電子科技大學(xué)碩士學(xué)位論文 端口號 或者他們的組合 這樣便可以確定一個結(jié)點的i d 同時o b j e c t i d h o b j e c t 屬性 o b j e c t 屬性可以是數(shù)據(jù)對象的名稱 內(nèi)容 大小 發(fā)布者或者他們的組合 等 由于s h a 散列函數(shù)的h a s h 值的長度m 一般大于等于1 6 0 這樣就可以保證了 結(jié)點的d 或者對象的i d 不可能出現(xiàn)重復(fù) 通過使用結(jié)點的關(guān)鍵信息將該結(jié)點和標(biāo)識符相關(guān)聯(lián) 同時資源對象也按照這種 方式與標(biāo)識符相關(guān)聯(lián) 那么一個資源對象就可以用 相關(guān)聯(lián)表示 那么 這個 對于是便可以由其結(jié)點的n o d e i d 大于或者等于k 的結(jié)點所擁有 那么因 此稱這樣的一個結(jié)點為關(guān)鍵字k 的后繼結(jié)點 即在一個c h o r d 環(huán)中具有順時針方 向增長i d 的一個結(jié)點負(fù)責(zé)其逆時針方向之前的所有關(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)繪出了一個已經(jīng)建立好了的c h o r d 環(huán) 在c h o r d 環(huán)上面已經(jīng)標(biāo) 識了每一個結(jié)點的標(biāo)識符以及資源文件的標(biāo)識符 而這些結(jié)點的n o d e i d 都是以順 時針的方向從小到大的順序排列在一個環(huán)上 數(shù)據(jù)對象k 被分配到環(huán)上按照順時 針方向緊隨k 包括k 的第一個結(jié)點 其中在這個c h o r d 環(huán)上其中l(wèi) 6 表示總共 有6 4 個標(biāo)識符 其中有6 個結(jié)點和4 個資源 關(guān)鍵字k 5 的后繼結(jié)點按照順時針 的方向那么應(yīng)該就是為n 8 關(guān)鍵字 同理 關(guān)鍵字k 1 5 的后繼結(jié)點偉n 3 6 關(guān)鍵字 k 2 8 的后繼結(jié)點為n 3 6 關(guān)鍵字k 4 9 的后繼結(jié)點為n 5 2 在該c h o r d 環(huán)上每個結(jié)點 都有個f i n g e r t a b l e 在這張表上該結(jié)點記錄了在對等網(wǎng)絡(luò)中的距離該結(jié)點的距離的 相應(yīng)的結(jié)點信息 便于以后消息的跳轉(zhuǎn)和資源的定位 每個c h o r d 結(jié)點也有其后 繼 結(jié)點n 的后繼是在c h o r d 環(huán)上緊隨n 不等于n 的第一個結(jié)點 記做n s u c c 懿s o r 請注意結(jié)點后繼和對象后繼有著明顯的區(qū)別 2 2 2c h o r d 的路由過程 基于c h o r d 協(xié)議所建立的結(jié)構(gòu)化對等網(wǎng)絡(luò)中 結(jié)點和資源通過高位的h a s h 處 1 4 第二章相關(guān)算法分析 理 將每個網(wǎng)絡(luò)中的結(jié)點和資源部署在這個網(wǎng)絡(luò)中的某個相應(yīng)的位置 這樣便形成 了整個結(jié)構(gòu)化對等網(wǎng)絡(luò)的雛形 那么以后結(jié)點需要查詢某個資源時 就會根據(jù)結(jié) 點和資源映射的方法建立相應(yīng)的搜索方式進行數(shù)據(jù)的查詢 當(dāng)有結(jié)點需要對某個 資源進行查找時 首先此結(jié)點先對該資源進行h a s h 的處理 獲取這個資源相對應(yīng) 的i d 然后查詢結(jié)點通過之前建立結(jié)構(gòu)化對等網(wǎng)絡(luò)的方法搜索該i d 搜索的過程 是這樣的 首先查詢結(jié)點對該資源進行一個數(shù)據(jù)查詢包的封裝 然后查詢結(jié)點分 析自己的路由表 找出順時針方向距離該對象i d 最為接近的結(jié)點 同時查詢結(jié)點 獲取該目標(biāo)結(jié)點的d 地址和端口之類的信息 查詢結(jié)點便開始通過網(wǎng)絡(luò)首先鏈接 到該目標(biāo)結(jié)點 然后將封裝好的查詢包發(fā)送給該目標(biāo)結(jié)點 目標(biāo)結(jié)點收到數(shù)據(jù)包 后 首先分析數(shù)據(jù)查詢包得到查詢結(jié)點需要尋找的對象資源 然后目標(biāo)結(jié)點按照 查詢結(jié)點同樣的方式 即搜索自己的路由表找出距離資源對象i d 最為接近的結(jié)點 為下一個目標(biāo)結(jié)點 然后再將該數(shù)據(jù)查詢包轉(zhuǎn)發(fā)給它 通過上述的這些步驟 最 終查詢結(jié)點都會在中間結(jié)點的幫助下到達最終的目標(biāo)結(jié)點 目標(biāo)結(jié)點在獲取到這 個查詢包后 便將該資源對應(yīng)的存儲該資源的結(jié)點的相應(yīng)的信息組裝成數(shù)據(jù)包發(fā) 送給查詢結(jié)點 查詢結(jié)點獲取到該響應(yīng)數(shù)據(jù)包后 便提取出存儲結(jié)點的信息 然 后通過與目標(biāo)結(jié)點的通訊得到所想要的資源文件 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)的路由過程 如圖2 2 所示 該圖展示一個基于c h o r d 環(huán)所產(chǎn)生的數(shù)據(jù)包的路由的過程 該圖展示了一個位數(shù)為6 位的結(jié)構(gòu)化對等網(wǎng)絡(luò) 那么根據(jù)c h o r d 算法可以知道 每個結(jié)點都有一個f i n g c rt a b l e 即所謂的結(jié)點的路由表 其中表中展示了一個結(jié)點 的i d 為n 8 的結(jié)點的路由表 在c h o r d 環(huán)中 每個結(jié)點有m 項路由表項 因為該 結(jié)構(gòu)化對等網(wǎng)絡(luò)是6 位 所以該網(wǎng)絡(luò)中的每個結(jié)點就應(yīng)該有6 項路由表的數(shù)據(jù) 1 5 電子科技大學(xué)碩士學(xué)位論文 這個路由表記錄的是n o d e i d 2 的對象d 是存放在哪一節(jié)結(jié)點i d 上面的 圖中 展示了結(jié)點n 8 需要查詢某個資源 而該資源的d 為k 4 9 然后該結(jié)點搜尋自己 的路由表發(fā)現(xiàn) 距離該資源i d 為l 9 的最為接近的結(jié)點是n 4 8 所以此時結(jié)點將 n 4 8 的相關(guān)信息得到 例如i p 地址 端口等信息 然后結(jié)點n 8 將這些信息打包然 后發(fā)送到結(jié)點n 4 8 當(dāng)結(jié)點n 4 8 接收到這個數(shù)據(jù)包后 首先拆分這個數(shù)據(jù)包 從中