【正文】 大小，要注意沖突率和哈希值空間大小的配合。 哈希函數(shù)的分類(lèi)（1）單向Hash函數(shù)（oneway）給定一個(gè)Hash值y，如果尋找一個(gè)消息x，使得y=h (x)是計(jì)算上不可行的，則稱(chēng)h是單向Hash函數(shù). （2）弱抗碰撞Hash函數(shù)（weakly collisionfree）任給一個(gè)消息x，如果尋找另一個(gè)不同的消息x’，使得h(x) =h(x’)是計(jì)算上不可行的，則稱(chēng)h是弱抗碰撞Hash函數(shù). （3）強(qiáng)抗碰撞Hash函數(shù) （strongly collisionfree）如果尋找兩個(gè)不同的消息x和x’，使得h(x)=h(x’)是計(jì)算上不可行的，則稱(chēng)h是強(qiáng)抗碰撞Hash函數(shù). 安全Hash函數(shù)h應(yīng)具有以下性質(zhì)：① 對(duì)任意的消息x，計(jì)算h(x)是容易的；② h是單向的；③ h是弱抗碰撞的，或是強(qiáng)抗碰撞的。關(guān)鍵字通過(guò)hash函數(shù)得到相應(yīng)的hash值存儲(chǔ)在它的后繼節(jié)點(diǎn)上，在chord中的尋址也就是對(duì)服務(wù)IP地址的查找。而路由則是知道服務(wù)的地址后，怎么通過(guò)地址在網(wǎng)絡(luò)中找到服務(wù)，通過(guò)服務(wù)名字找到服務(wù)所在的地址的過(guò)程稱(chēng)為尋址。（1）身份標(biāo)識(shí)（ID）ID（Identifier）是網(wǎng)絡(luò)域內(nèi)服務(wù)的唯一標(biāo)識(shí)，服務(wù)的ID一旦產(chǎn)生或被分配，將不會(huì)改變且長(zhǎng)期有效。當(dāng)基于身份位置相分離來(lái)介紹未來(lái)因特網(wǎng)架構(gòu)，identifier必須滿(mǎn)足一些要求。服務(wù)提供商最終被Hash為一個(gè)64位的數(shù)。若要存儲(chǔ)200億個(gè)服務(wù)信息本身至少需要2TB，即為兩千GB的容量，而哈希表的存儲(chǔ)效率一般只為50%，那也就是需要4TB以上的空間，并且就算把這些服務(wù)全部存儲(chǔ)在計(jì)算機(jī)內(nèi)存中，由于服務(wù)字符串長(zhǎng)度的不固定，以字符串形式來(lái)進(jìn)行查找就需要依次比對(duì)，以最長(zhǎng)匹配原則來(lái)進(jìn)行篩選，這樣的效率會(huì)很低。Nname = 名字、版本、發(fā)布時(shí)間、有效日期、私有性、可遷移性SISPHashHashUIDNIDSID128 bit64 bit64 bit 服務(wù)名稱(chēng)哈希生成UID 將服務(wù)ID的128位哈希值UID模上2m（m=128），最后得到的值作為關(guān)鍵字標(biāo)識(shí)符，與chord環(huán)中的IP節(jié)點(diǎn)哈希值（EID）進(jìn)行匹配，選擇后繼節(jié)點(diǎn)為哪個(gè)具體的節(jié)點(diǎn)。以目前人類(lèi)的技術(shù)可以存儲(chǔ)至少295艾字節(jié)（exabytes）的信息，這個(gè)數(shù)字相當(dāng)于1后面有20個(gè)零。又因?yàn)橛挟?dāng)，有當(dāng)時(shí)，所以可以推出所以有①式所以?xún)蓚€(gè)元素相同的概率P=1，設(shè)為②式。由于M共有R個(gè)變形，所以M的全部變形都不與mi碰撞的概率是： 因?yàn)橄共有r個(gè)變形，因此m的變形與M的變形都不碰撞的概率是：m的變形與M的變形發(fā)生碰撞的概率是：一般認(rèn)為，對(duì)于n比特輸出的理想Hash函數(shù)，碰撞攻擊的復(fù)雜度上界為O（），對(duì)于隨機(jī)選取的個(gè)消息，當(dāng)r = R = 2n/2時(shí)，P(n) = 1e1187。對(duì)于出現(xiàn)的沖突，對(duì)于所有64位的哈希函數(shù)沖突率為這么大，結(jié)合存儲(chǔ)容量和查找時(shí)間復(fù)雜度考慮，我們認(rèn)為64位的MURMUR哈希函數(shù)是符合實(shí)驗(yàn)要求的。服務(wù)提供者再將自己的服務(wù)信息和服務(wù)所在原始位置信息添加到注冊(cè)表中。樹(shù)形結(jié)構(gòu)最大的好處是分級(jí)管理，有良好的容錯(cuò)能力和很好的擴(kuò)展性，但是根節(jié)點(diǎn)容易構(gòu)成瓶頸，造成通信堵塞；而扁平形結(jié)構(gòu)是采用集中相應(yīng)服務(wù)請(qǐng)求，安全性問(wèn)題相對(duì)比較容易解決，但是不易于實(shí)現(xiàn)訪(fǎng)問(wèn)分布。域名系統(tǒng)采用樹(shù)的結(jié)構(gòu)，最高為頂級(jí)域名，再每層往下分。名稱(chēng)時(shí)，DNS服務(wù)可以將此名稱(chēng)解析為與之相關(guān)的其他信息，如 IP 地址。每一個(gè)chord節(jié)點(diǎn)都需要維持一張表，是保存著服務(wù)名稱(chēng)經(jīng)過(guò)hash之后的UID值和對(duì)應(yīng)的服務(wù)locator之間的位置關(guān)系的服務(wù)信息存儲(chǔ)表。 chord折半查找算法在尋址系統(tǒng)中，每一次跳轉(zhuǎn)都chord環(huán)上地址空間總大小為 2m，這是由采用的hash函數(shù)決定的，m為哈希之后的標(biāo)識(shí)符的位數(shù)。 Distributed Operating System Group開(kāi)發(fā)的開(kāi)源項(xiàng)目，可以用于仿真結(jié)構(gòu)化P2P相關(guān)協(xié)議，現(xiàn)在的P2Psim已經(jīng)實(shí)現(xiàn)了對(duì)Kelips，Koorde，tapestry，chord和kademlia等結(jié)構(gòu)化的P2P網(wǎng)絡(luò)的仿真。 topology file must start with keyword topology topology {TOPOLOGY} [KEY=VAL [KEY=VAL [...]]] failure_model {FAILURE_MODEL} [KEY=VAL [KEY=VAL [...]]] empty line nodeid x,y nodeid x,y ... nodeid can39。很簡(jiǎn)單，只是加入了一個(gè)模擬結(jié)束的事件。中的type={join, crash, lookup, nodeevent},通過(guò)name2fn獲取, fn為P2PEvnet將要執(zhí)行的函數(shù)，args為fn執(zhí)行時(shí)的參數(shù)，Topologies文件中包含了很多網(wǎng)絡(luò)拓?fù)漕?lèi)型，可以選定任意一種在其網(wǎng)絡(luò)拓?fù)淠Ｐ椭羞M(jìn)行網(wǎng)絡(luò)模擬仿真。重慶郵電大學(xué)碩士論文 P2psim實(shí)現(xiàn)路由過(guò)程第五章 P2psim實(shí)現(xiàn)路由過(guò)程 仿真軟件p2psim介紹因?yàn)閏hord協(xié)議主要是應(yīng)用層上的協(xié)議，所以為了更好的仿真chord協(xié)議，本文中采用采用P2Psim[34]。如果新的位置屬于注冊(cè)中心B的范圍，則在A處更新了對(duì)應(yīng)關(guān)系之后同時(shí)在注冊(cè)中心B上添加SID到locator的信息，為S（UID：locatorlocator2）同理，若服務(wù)S再次遷移到其他位置屬于注冊(cè)中心C的范圍時(shí)，S再次向A和B匯報(bào)將自己的位置并將記錄更新為S（UID：locatorlocator2 、locator3），并同時(shí)將A、B、C三處的SID到locator的對(duì)應(yīng)信息都更新為S（UID：locatorlocator2 、locator3）。而DRMC管理中心的每一個(gè)節(jié)點(diǎn)相當(dāng)于一個(gè)區(qū)域的DRMC的匯總，主要負(fù)責(zé)管理這些DRMC的個(gè)數(shù)、位置和狀態(tài)。當(dāng)用戶(hù)在應(yīng)用程序中輸入它是由解析器以及域名服務(wù)器組成的，域名服務(wù)器是指保存有該網(wǎng)絡(luò)中所有主機(jī)的域名和其對(duì)應(yīng)的IP地址，并具有將域名轉(zhuǎn)換為IP地址功能的服務(wù)器。其中，最常用的是樹(shù)形拓?fù)浣Y(jié)構(gòu)（如DNS）和扁平結(jié)構(gòu)。從服務(wù)提供者ISP發(fā)布一個(gè)服務(wù)到用戶(hù)得到服務(wù)的過(guò)程中，有三個(gè)主要構(gòu)成元素，服務(wù)提供商，用戶(hù)和注冊(cè)中心。分段Hash后，*。將消息表示成變形消息的方法很多，例如增加空格、使用縮寫(xiě)、使用意義相同的單詞、去掉不必要的單詞等。 Hash函數(shù)碰撞 生日悖論推導(dǎo)生日悖論，至少需要多少人，才能保證至少有兩個(gè)人同一天生日的概率大于1/2？設(shè)S為有S個(gè)元素的集合，從S中隨機(jī)選取一個(gè)的選法有種，再選第二個(gè)和第一個(gè)沖突的概率為，再選第三個(gè)和前兩個(gè)沖突的概率為，從S中選取第r個(gè)元素和之前的元素相同的概率為。位數(shù)的確定是基于兩個(gè)不可反駁的事實(shí)：服務(wù)信息總量不會(huì)超過(guò)存儲(chǔ)總量，服務(wù)提供商的數(shù)量不會(huì)超過(guò)人口的數(shù)量。只要選擇的Hash函數(shù)足夠好，也可以保證不會(huì)產(chǎn)生兩個(gè)相同的服務(wù)ID指紋避免沖突。 服務(wù)名稱(chēng)的哈希處理對(duì)于每一個(gè)服務(wù)都有一個(gè)唯一的標(biāo)識(shí)，就像每個(gè)人都有自己唯一的指紋一樣。這些屬性都是由服務(wù)提供商來(lái)確定的，在這里統(tǒng)稱(chēng)為服務(wù)屬性。Locator只用于路由，而identifier只在應(yīng)用層負(fù)責(zé)對(duì)服務(wù)身份的判斷，不再與locator綁定用于路由。身份標(biāo)識(shí)一般就指服務(wù)ID，可以通過(guò)對(duì)服務(wù)的名稱(chēng)、屬性、操作及服務(wù)提供者等信息進(jìn)行hash獲得，由于服務(wù)遷移，服務(wù)ID與位置標(biāo)識(shí)可能存在一對(duì)多的映射關(guān)系。在網(wǎng)絡(luò)中，用戶(hù)所查找的資源的名字是相對(duì)不變的，因?yàn)橐坏┟指淖儯簿驼f(shuō)明這個(gè)服務(wù)消失或者有所變動(dòng)，就不再是原先的服務(wù)了。查找路線(xiàn)為N8—N42—N51—N56，節(jié)點(diǎn)N54的信息就存儲(chǔ)在離N54最近的后繼節(jié)點(diǎn)N56上。而處理沖突的方法有：①開(kāi)放地址法；②再哈希法；③鏈地址法；④建立一個(gè)公共溢出區(qū)。但是實(shí)際應(yīng)用中，由于選取哈希函數(shù)的不同，得到的哈希值的空間大小也就不一樣，就會(huì)造成不同的關(guān)鍵字通過(guò)哈希函數(shù)后得到相同的哈希值，就出現(xiàn)了沖突。第六章：總結(jié)了本文所做的工作，提出了下一步的研究開(kāi)發(fā)方向。④ Chord算法改進(jìn)對(duì)各種現(xiàn)有的chord改進(jìn)算法研究后根據(jù)本文的未來(lái)網(wǎng)絡(luò)架構(gòu)的特點(diǎn)，結(jié)合二分法提出了折半查找算法。當(dāng)前對(duì)chord算法的改進(jìn)主要是單純的對(duì)算法本身的改進(jìn)，改進(jìn)過(guò)后的chord算法仍需要在每個(gè)節(jié)點(diǎn)處對(duì)自己的finger表進(jìn)行查找匹配，并沒(méi)有完全跳出經(jīng)典chord算法的思維模式，本文中的chord算法改進(jìn)后，已經(jīng)不存在finger表，每個(gè)節(jié)點(diǎn)不光是chord環(huán)中的轉(zhuǎn)發(fā)節(jié)點(diǎn)，而是一個(gè)服務(wù)注冊(cè)中心，存儲(chǔ)有服務(wù)ID和服務(wù)所在IP地址的對(duì)應(yīng)信息，這部分在第四章有詳細(xì)的介紹。圖 （1） Fullchord中節(jié)點(diǎn)路由表例如從N8節(jié)點(diǎn)想要查找到key值等于54的后繼節(jié)點(diǎn)，在fullchord中從N8點(diǎn)可以直接通過(guò)公式(2)找到離54最近的節(jié)點(diǎn)為N51，再通過(guò)N51的后繼節(jié)點(diǎn)找到存儲(chǔ)有54的節(jié)點(diǎn)N56。德國(guó)慕尼黑技術(shù)大學(xué)提出了一種基于身份位置相分離的命名規(guī)則，Hiimap[30]的，這個(gè)規(guī)則不僅是針對(duì)網(wǎng)絡(luò)中的服務(wù)，而是一個(gè)通用式，如圖所示，一共由五部分組成，其中RP代表區(qū)域的前綴，剩下四部分為UID，UID定長(zhǎng)為128bit，分別由4位的類(lèi)型號(hào)，76位的服務(wù)名字哈希值，32位的Ext1和16位的Ext2組成。HRA【29】：層次式的標(biāo)識(shí)，采用層次路由機(jī)制解決路由可擴(kuò)展性問(wèn)題。FARA中用轉(zhuǎn)發(fā)指示(for warding directive)作為分組交換結(jié)構(gòu)的地址標(biāo)識(shí)。 而且是唯一分配的，一個(gè)節(jié)點(diǎn)雖然可能負(fù)責(zé)管理多個(gè)地址，但只能使用反映當(dāng)前網(wǎng)絡(luò)拓?fù)湮恢玫奈ㄒ坏刂窐?biāo)識(shí)。但PeerNet是一個(gè)全新的網(wǎng)絡(luò)層協(xié)議，它的目的是取代IP協(xié)議。Identifier到Locator的映射被稱(chēng)為T(mén)rigger，存儲(chǔ)在覆蓋服務(wù)中。層級(jí)邏輯部分：定義組織間的從屬關(guān)系，realm中對(duì)象的物理位置邏輯關(guān)系。但是用戶(hù)并不關(guān)系服務(wù)在什么位置，與自己所在網(wǎng)絡(luò)的遠(yuǎn)近，用戶(hù)對(duì)服務(wù)的需求是對(duì)服務(wù)本身的需求。據(jù)統(tǒng)計(jì)，目前網(wǎng)絡(luò)設(shè)備的使用引起每年高達(dá)6%的能源消耗，%，相當(dāng)于航空運(yùn)輸業(yè)的排放量。他將網(wǎng)絡(luò)的七層模型整合成了“網(wǎng)絡(luò)層”和“服務(wù)層”，網(wǎng)絡(luò)層著重于傳輸，服務(wù)層著重于應(yīng)用?，F(xiàn)在國(guó)際上對(duì)未來(lái)網(wǎng)絡(luò)主要由兩大陣營(yíng)，“革命式”[15][16]和“演進(jìn)式”。本文遵循身份位置相分離原則，網(wǎng)絡(luò)中的每一片服務(wù)都應(yīng)有自己的名字為服務(wù)設(shè)計(jì)了命名規(guī)則，并結(jié)合chord模型設(shè)計(jì)出更符合未來(lái)網(wǎng)絡(luò)的尋址模型，對(duì)其進(jìn)行尋址效率驗(yàn)證。樹(shù)形結(jié)構(gòu)最大的好處是分級(jí)管理，有良好的容錯(cuò)能力和很好的擴(kuò)展性，但是根節(jié)點(diǎn)容易構(gòu)成瓶頸，造成通信堵塞；而扁平形結(jié)構(gòu)是采用集中相應(yīng)服務(wù)請(qǐng)求，安全性問(wèn)題相對(duì)比較容易解決，但是不易于實(shí)現(xiàn)訪(fǎng)問(wèn)分布。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示謝意。（保密的學(xué)位論文在解密后適用本授權(quán)書(shū)）學(xué)位論文作者簽名： 導(dǎo)師簽名：簽字日期： 年 月 日 簽字日期： 年 月 日重慶郵電大學(xué)碩士論文 摘要摘 要當(dāng)前互聯(lián)網(wǎng)路由系統(tǒng)面臨著嚴(yán)峻的擴(kuò)展性問(wèn)題，產(chǎn)生這一問(wèn)題的根源在于IP地址語(yǔ)義過(guò)載，即IP地址既充當(dāng)節(jié)點(diǎn)身份標(biāo)識(shí)又代表了節(jié)點(diǎn)的位置標(biāo)識(shí)，同時(shí)也束縛了移動(dòng)性的實(shí)現(xiàn)。② 服務(wù)命名驗(yàn)證通過(guò)極值法對(duì)哈希函數(shù)的位數(shù)進(jìn)行驗(yàn)證，通過(guò)數(shù)學(xué)方法對(duì)所選用的哈希函數(shù)的沖突率進(jìn)行驗(yàn)證，結(jié)果證明本文中所選用的哈希函數(shù)完全能滿(mǎn)足。同時(shí)，網(wǎng)絡(luò)用戶(hù)也更加關(guān)心如何獲取服務(wù)而不是服務(wù)所處的位置。其中TRIAD是2000年斯坦福大學(xué)提出的支持名字路由的網(wǎng)絡(luò)路由架構(gòu)，在網(wǎng)絡(luò)架構(gòu)中新增了一個(gè)“內(nèi)容層”，內(nèi)容通過(guò)內(nèi)容路由器進(jìn)行選路，需要在現(xiàn)有的internet協(xié)議上增加新協(xié)議，增加協(xié)議后的路由器是同時(shí)支持內(nèi)容路由和IP路由。主流思想都是將網(wǎng)絡(luò)中的主體由地址變?yōu)閮?nèi)容，因?yàn)橛脩?hù)對(duì)網(wǎng)絡(luò)的需求是對(duì)網(wǎng)絡(luò)上服務(wù)的需求，用戶(hù)關(guān)心的是服務(wù)的內(nèi)容而不是服務(wù)的位置，所以很有必要提出的是一種以服務(wù)為核心，面向服務(wù)的網(wǎng)絡(luò)，將重點(diǎn)轉(zhuǎn)移到服務(wù)的內(nèi)容。是否盡早開(kāi)展未來(lái)互聯(lián)網(wǎng)領(lǐng)域的研究，將關(guān)系到我們能否在未來(lái)互聯(lián)網(wǎng)的發(fā)展演進(jìn)以及產(chǎn)業(yè)競(jìng)爭(zhēng)格局中是否擁有先機(jī)和話(huà)語(yǔ)權(quán)，也關(guān)系到我們的信息技術(shù)水平是否可以支撐國(guó)家產(chǎn)業(yè)戰(zhàn)略調(diào)整和經(jīng)濟(jì)增長(zhǎng)方式的轉(zhuǎn)變。直接對(duì)網(wǎng)絡(luò)中服務(wù)命名的很少。更者，DNS名字只是用于應(yīng)用層，而HUI同樣用于傳輸層和網(wǎng)絡(luò)層。HIP將位置(IP)與端節(jié)點(diǎn)標(biāo)識(shí)相互分離，在傳輸層和網(wǎng)絡(luò)層之間加入了主機(jī)標(biāo)識(shí)層(host identity)，高層應(yīng)用中，表示主機(jī)身份的IP地址被HIT（Host Identity Tag）替換，用HIT作為固定的主機(jī)標(biāo)識(shí)符，應(yīng)用層通信也基于HIT，IP地址僅僅用于路由轉(zhuǎn)發(fā)而不再用來(lái)標(biāo)識(shí)主機(jī)身份。地址標(biāo)識(shí)則嚴(yán)格地反映節(jié)點(diǎn)在網(wǎng)絡(luò)中的當(dāng)前位置，當(dāng)節(jié)點(diǎn)移動(dòng)時(shí)，節(jié)點(diǎn)的地址標(biāo)識(shí)隨之動(dòng)態(tài)改變。 其次，由于每個(gè)節(jié)點(diǎn)只能使用反映當(dāng)前網(wǎng)絡(luò)拓?fù)涞奈ㄒ坏刂?，PeerNet不能支持Multihoming。而且對(duì)于如何進(jìn)行移動(dòng)切換、保證通信安全等許多問(wèn)題，F(xiàn)ARA中并沒(méi)有具體的實(shí)現(xiàn)機(jī)制。其中，HIT是HI的hash值與AD ID(administrative domain ID)的結(jié)合。Fullchord[23]的提出使得每個(gè)節(jié)點(diǎn)的路由信息都包含了兩個(gè)路由表，分別是正向的路由表和逆向的路由表。三階chord路由表公式為：ID+3k1mod N 1≤ k≤mID+2*3k1mod N 1≤ k≤m三階chord的路由表指針模型為：圖 （3） 三階chord