【文章內(nèi)容簡(jiǎn)介】 之后的分段哈希處理做了詳細(xì)的敘述，對(duì)所用到的哈希函數(shù)位數(shù)的合理性和哈希之后的沖突率通過(guò)數(shù)學(xué)方法進(jìn)行驗(yàn)證。第四章：尋址部分，提出了未來(lái)網(wǎng)絡(luò)體系結(jié)構(gòu)，提出了一種新的路由算法。第五章：對(duì)改進(jìn)后的路由算法進(jìn)行驗(yàn)證，使用實(shí)驗(yàn)平臺(tái)對(duì)路由算法進(jìn)行了功能和性能測(cè)試，最后分析了測(cè)試結(jié)果。第六章：總結(jié)了本文所做的工作，提出了下一步的研究開發(fā)方向。重慶郵電大學(xué)碩士論文 關(guān)鍵技術(shù)介紹第二章 關(guān)鍵技術(shù)介紹 哈希算法介紹本文中對(duì)服務(wù)的名字定義后需要通過(guò)哈希函數(shù)來(lái)對(duì)服務(wù)名字進(jìn)行分段處理，以便進(jìn)行存儲(chǔ)和查找，通過(guò)分段哈希也大大降低了哈希后的沖突率。通過(guò)哈希處理后的服務(wù)名字具有區(qū)域唯一性，在查找時(shí)，不需要進(jìn)行任何對(duì)比，可以一次性找到所需要的服務(wù)所對(duì)應(yīng)的地址，使對(duì)服務(wù)地址的查找更加高效。 哈希算法定義哈希算法也稱為散列算法，是通過(guò)關(guān)鍵字（key值）來(lái)進(jìn)行訪問(wèn)的一種數(shù)據(jù)結(jié)構(gòu)，具有高效匹配特性。Hash函數(shù)定義：Hash函數(shù)是一個(gè)將任意長(zhǎng)度的消息（message）映射成固定長(zhǎng)度消息的函數(shù)。，關(guān)鍵字（v1，v2，…v8）通過(guò)哈希函數(shù)H（v.）生成哈希值（H（v1），H（v2）…H（v8）），這個(gè)過(guò)程就是一個(gè)哈希過(guò)程。哈希的結(jié)果是一個(gè)哈希列表，是關(guān)鍵字通過(guò)哈希函數(shù)處理后得到哈希值的一個(gè)對(duì)應(yīng)關(guān)系表，在理想情況下，關(guān)鍵字與哈希值是一個(gè)一一對(duì)應(yīng)關(guān)系，不會(huì)存在重復(fù)的情況，所以讀取時(shí)一次就可以成功讀取到想要的數(shù)據(jù)，哈希之后的散列表中可以進(jìn)行直接尋址，可以在O（1）的時(shí)間內(nèi)訪問(wèn)表中任意元素。當(dāng)采用合適的哈希函數(shù)時(shí)，生成的哈希值與關(guān)鍵字是一對(duì)一的關(guān)系，沒有重復(fù)的哈希值，這樣的哈希函數(shù)成為完美哈希。但是實(shí)際應(yīng)用中，由于選取哈希函數(shù)的不同，得到的哈希值的空間大小也就不一樣，就會(huì)造成不同的關(guān)鍵字通過(guò)哈希函數(shù)后得到相同的哈希值，就出現(xiàn)了沖突。 哈希函數(shù)實(shí)例沖突也稱為哈希函數(shù)的碰撞，設(shè)x、x’是兩個(gè)不同的消息，如果 h(x) = h(x’)則稱x和x’是Hash函數(shù)h的一個(gè)（對(duì)）碰撞。在對(duì)哈希函數(shù)的選用時(shí)也需要注意關(guān)鍵字空間的大小，要注意沖突率和哈希值空間大小的配合。比如說(shuō)關(guān)鍵字有64位，最大值就是2^64，一共需要對(duì)1000個(gè)這樣的關(guān)鍵字進(jìn)行哈希，如果選取64位的哈希函數(shù)的話，固然可以實(shí)現(xiàn)一一對(duì)應(yīng)，使得沖突率為0，提高查找效率，但是也同時(shí)浪費(fèi)了巨大的存儲(chǔ)空間；若哈希函數(shù)位數(shù)選的過(guò)于小，又會(huì)造成大量的哈希值沖突，使得查詢效率降低，所以需要根據(jù)關(guān)鍵字的位數(shù)來(lái)選擇合適的哈希函數(shù)。減少?zèng)_突需要注意的除了哈希函數(shù)的位數(shù)外還需要注意該哈希函數(shù)是否為均勻哈希函數(shù)。若對(duì)于關(guān)鍵字集合中任一個(gè)關(guān)鍵字，經(jīng)過(guò)哈希函數(shù)映像到地址集合中任何一個(gè)地址的概率是相等的，則此類哈希函數(shù)稱之為均勻的哈希函數(shù)。也就是說(shuō)，使關(guān)鍵字經(jīng)過(guò)焊錫函數(shù)得到一個(gè)“隨機(jī)的地址”，以便使關(guān)鍵字的哈希地址均勻的分布在整個(gè)地址區(qū)間中，從而減少?zèng)_突。常見的哈希函數(shù)構(gòu)造法有：①直接定址法；②數(shù)字分析法；③平方去中法；④折疊法；⑤除留余數(shù)法。而處理沖突的方法有：①開放地址法；②再哈希法；③鏈地址法；④建立一個(gè)公共溢出區(qū)。在本文中，哈希函數(shù)的選取也是研究的一個(gè)重點(diǎn)，通過(guò)選取適當(dāng)?shù)墓：瘮?shù)，盡可能的使沖突率降低到可以忽略不計(jì)的程度，所以本文并沒有對(duì)采用怎樣的沖突處理方法進(jìn)行描述。 哈希函數(shù)的分類（1）單向Hash函數(shù)（oneway）給定一個(gè)Hash值y，如果尋找一個(gè)消息x，使得y=h (x)是計(jì)算上不可行的，則稱h是單向Hash函數(shù). （2）弱抗碰撞Hash函數(shù)（weakly collisionfree）任給一個(gè)消息x，如果尋找另一個(gè)不同的消息x’，使得h(x) =h(x’)是計(jì)算上不可行的，則稱h是弱抗碰撞Hash函數(shù). （3）強(qiáng)抗碰撞Hash函數(shù) （strongly collisionfree）如果尋找兩個(gè)不同的消息x和x’，使得h(x)=h(x’)是計(jì)算上不可行的，則稱h是強(qiáng)抗碰撞Hash函數(shù). 安全Hash函數(shù)h應(yīng)具有以下性質(zhì)：① 對(duì)任意的消息x，計(jì)算h(x)是容易的；② h是單向的；③ h是弱抗碰撞的，或是強(qiáng)抗碰撞的。 經(jīng)典chord算法介紹Chord[10]環(huán)為第三代結(jié)構(gòu)化P2P網(wǎng)絡(luò)，是一個(gè)分布式系統(tǒng)，提供數(shù)據(jù)對(duì)象的緩存、查詢、復(fù)制和存儲(chǔ)等功能，作為分布式散列表，chord幾乎具有最優(yōu)的路由效率[11]。Chord算法采用相容哈希函數(shù)對(duì)關(guān)鍵字和節(jié)點(diǎn)IP進(jìn)行哈希，生成m位字符的標(biāo)識(shí)符，哈希的結(jié)果都是盡可能的平均分布在chord環(huán)上。在chord中每個(gè)關(guān)鍵字的路由信息都是保存在它的后繼節(jié)點(diǎn)中，每個(gè)節(jié)點(diǎn)最多保存m條路由信息，稱為finger表。Chord查找路由過(guò)程中，每一個(gè)節(jié)點(diǎn)只需要知道它在chord環(huán)中的后繼節(jié)點(diǎn)，環(huán)中每個(gè)節(jié)點(diǎn)的路由法則就是按照f(shuō)inger表來(lái)進(jìn)行，每個(gè)節(jié)點(diǎn)的查找公式為：fingeri=n+2i1mod 2m, 1≤i≤m 如圖，節(jié)點(diǎn)N8上的路由信息表，N8+2i1，1≤i≤m，當(dāng)m=6時(shí)，節(jié)點(diǎn)N8上一共有6條路由信息，finger表第一列表示要查詢的節(jié)點(diǎn)的范圍，第二列則表示要查詢的節(jié)點(diǎn)的信息在哪個(gè)具體的節(jié)點(diǎn)上。圖 （1） Chord查找實(shí)例例如，給出節(jié)點(diǎn)ID為54，則先在N8的finger表上，查詢到N54是屬于N8+32，N42以后的節(jié)點(diǎn)，則先通過(guò)m=6的最后一行找到N40的節(jié)點(diǎn)所在的后繼節(jié)點(diǎn)N42，再在N42節(jié)點(diǎn)上比較N54和表中每個(gè)節(jié)點(diǎn)的大小來(lái)確定下一個(gè)查找節(jié)點(diǎn)是誰(shuí)，直至查找到N54為止。查找路線為N8—N42—N51—N56，節(jié)點(diǎn)N54的信息就存儲(chǔ)在離N54最近的后繼節(jié)點(diǎn)N56上。在我們的尋址系統(tǒng)中，將每個(gè)節(jié)點(diǎn)處的內(nèi)容索引抽象為K，V對(duì)，K是內(nèi)容關(guān)鍵字的Hash摘要，即為服務(wù)名稱的哈希值，K = Hash（服務(wù)名稱）；V是存放服務(wù)內(nèi)容的實(shí)際位置即為IP地址，V = IP，K，V =（hash（key），IP）。關(guān)鍵字通過(guò)hash函數(shù)得到相應(yīng)的hash值存儲(chǔ)在它的后繼節(jié)點(diǎn)上，在chord中的尋址也就是對(duì)服務(wù)IP地址的查找。K，V對(duì)組成一張Hash表，因此該表存儲(chǔ)了所有服務(wù)SID到服務(wù)位置的對(duì)應(yīng)信息。注意，這里存儲(chǔ)的只是服務(wù)名字與服務(wù)所在地址的對(duì)應(yīng)關(guān)系，并不是服務(wù)本身。N1N48N16N32N8k vk v Vk v Vk v Vk v圖 （2） Chord環(huán)中的K，V對(duì) 小結(jié)本章介紹了本文中用到的關(guān)鍵技術(shù)，哈希函數(shù)基本理論和經(jīng)典chord算法的尋址原理，為后面介紹本文提出的命名規(guī)則和類chord算法改進(jìn)算法奠下了基礎(chǔ)。重慶郵電大學(xué)碩士論文 尋址體系與算法研究第三章 未來(lái)網(wǎng)絡(luò)服務(wù)命名方法（機(jī)制？） 課題分析互聯(lián)網(wǎng)絡(luò)上數(shù)據(jù)通信的實(shí)質(zhì)是數(shù)據(jù)包的轉(zhuǎn)發(fā)，這里就涉及到兩個(gè)問(wèn)題——對(duì)象和地址，轉(zhuǎn)發(fā)的對(duì)象（who）、轉(zhuǎn)發(fā)對(duì)象所在的地址（where）和轉(zhuǎn)發(fā)的目的地址。在互聯(lián)網(wǎng)命名與尋址中一共涉及四個(gè)概念：名字、地址、路由以及尋址。在網(wǎng)絡(luò)中，用戶所查找的資源的名字是相對(duì)不變的，因?yàn)橐坏┟指淖?，也就說(shuō)明這個(gè)服務(wù)消失或者有所變動(dòng)，就不再是原先的服務(wù)了。但是服務(wù)的地址是相對(duì)變化的，當(dāng)服務(wù)經(jīng)過(guò)遷移后，同一個(gè)服務(wù)可能同時(shí)存在于多個(gè)地方，也就出現(xiàn)了一個(gè)服務(wù)名字對(duì)應(yīng)多個(gè)服務(wù)地址的現(xiàn)象。而路由則是知道服務(wù)的地址后，怎么通過(guò)地址在網(wǎng)絡(luò)中找到服務(wù)，通過(guò)服務(wù)名字找到服務(wù)所在的地址的過(guò)程稱為尋址。簡(jiǎn)單的說(shuō)四者之間的關(guān)系就是，名字是你要找什么，地址是你在哪里可以找得到，路由是通過(guò)怎樣的路徑可以得到這個(gè)服務(wù)，通過(guò)檢索服務(wù)名字從而得到服務(wù)地址的過(guò)程稱為尋址。本文中，按照身份位置相分離原則，提出服務(wù)身份的命名規(guī)則，服務(wù)所在的地址依舊采用IP地址，將服務(wù)名字通過(guò)分段哈希算法后得到域內(nèi)唯一的哈希值，通過(guò)唯一的域內(nèi)哈希值可以在服務(wù)注冊(cè)中心處找到相對(duì)應(yīng)的服務(wù)所在IP地址，通過(guò)提出新的路由算法，在域內(nèi)或者域間快速找到目的地址。 身份標(biāo)識(shí)與位置標(biāo)識(shí)網(wǎng)絡(luò)信息傳輸中需要知道被傳輸對(duì)象是什么以及服務(wù)所在地和傳輸?shù)哪康牡卦谀睦?，傳輸?duì)象就是服務(wù)的身份標(biāo)識(shí)，而服務(wù)所在地和傳輸?shù)哪康牡鼐褪俏恢脴?biāo)識(shí)。其中，身份標(biāo)識(shí)是網(wǎng)絡(luò)區(qū)域內(nèi)服務(wù)唯一的標(biāo)識(shí)，具有區(qū)域唯一性和不變性。位置標(biāo)識(shí)是服務(wù)所在的位置，不具有唯一性。身份標(biāo)識(shí)一般就指服務(wù)ID，可以通過(guò)對(duì)服務(wù)的名稱、屬性、操作及服務(wù)提供者等信息進(jìn)行hash獲得，由于服務(wù)遷移，服務(wù)ID與位置標(biāo)識(shí)可能存在一對(duì)多的映射關(guān)系。而位置標(biāo)識(shí)一般指服務(wù)所在的IP地址，可以通過(guò)對(duì)服務(wù)IP進(jìn)行hash獲得，代表節(jié)點(diǎn)或服務(wù)在網(wǎng)絡(luò)拓?fù)渲械奈恢谩＃?）身份標(biāo)識(shí)（ID）ID（Identifier）是網(wǎng)絡(luò)域內(nèi)服務(wù)的唯一標(biāo)識(shí)，服務(wù)的ID一旦產(chǎn)生或被分配，將不會(huì)改變且長(zhǎng)期有效。服務(wù)ID主要用于應(yīng)用層及傳輸層，即時(shí)的、端到端、可遷移的場(chǎng)景，如服務(wù)的分布式存儲(chǔ)，同時(shí)服務(wù)ID與服務(wù)所在位置可能是一對(duì)多的映射關(guān)系，服務(wù)ID可以通過(guò)對(duì)服務(wù)的名稱、屬性、操作及服務(wù)提供者等信息進(jìn)行hash獲得。（2）位置標(biāo)識(shí)（locator）位置標(biāo)識(shí)（Locator）主要是指服務(wù)所在的IP地址，多數(shù)情況下，位置標(biāo)識(shí)是不可變的，但是由于服務(wù)進(jìn)過(guò)服務(wù)遷移會(huì)存在于多個(gè)位置上，所以一般而言，服務(wù)ID一般對(duì)于多個(gè)位置標(biāo)識(shí)，但一個(gè)位置標(biāo)識(shí)只對(duì)應(yīng)于一個(gè)服務(wù)ID。節(jié)點(diǎn)ID與節(jié)點(diǎn)位置是一一對(duì)應(yīng)映射關(guān)系，節(jié)點(diǎn)ID可以通過(guò)對(duì)節(jié)點(diǎn)IP地址進(jìn)行hash得到， 基于身份位置相分離的服務(wù)命名方法本文認(rèn)同NDN[2]（Named Data Networking）思想，認(rèn)為每一片服務(wù)都有自己的名字，并針對(duì)服務(wù)對(duì)服務(wù)的identity進(jìn)行命名。基于身份位置相分離，得到的服務(wù)名字和服務(wù)的位置是一種對(duì)應(yīng)關(guān)系，有一個(gè)名字位置對(duì)（pair）， SID：locator。這意味著，每一個(gè)服務(wù)ID至少有一個(gè)locator與之對(duì)應(yīng)。Locator只用于路由，而identifier只在應(yīng)用層負(fù)責(zé)對(duì)服務(wù)身份的判斷，不再與locator綁定用于路由。將服務(wù)的identifier與locator分離，服務(wù)的identifier是不會(huì)隨著服務(wù)遷移后的位置的變化而改變，通信不會(huì)發(fā)生中斷可很好的解決移動(dòng)性問(wèn)題。當(dāng)基于身份位置相分離來(lái)介紹未來(lái)因特網(wǎng)架構(gòu)，identifier必須滿足一些要求。以下是根據(jù)ITU[3]的提議總結(jié)的一些通常的要求：l 服務(wù)的名字可以與多個(gè)服務(wù)位置相關(guān)聯(lián)并且不隨位置變化而變化；l 服務(wù)的名字是在應(yīng)用層；l 與服務(wù)名字有關(guān)的session不會(huì)因?yàn)榉?wù)位置的變動(dòng)而中斷；l 服務(wù)的名字在一個(gè)指定范圍內(nèi)是全球唯一的；用戶對(duì)名字的關(guān)心問(wèn)題[12]有三點(diǎn)不變性、可達(dá)性和可信性。不變性是指不管服務(wù)遷移到任何地方，服務(wù)的名字始終唯一；可達(dá)性是指即使網(wǎng)絡(luò)和服務(wù)失敗名字的內(nèi)容或者服務(wù)也達(dá)；可信性是指用戶不考慮內(nèi)容在哪兒，但是希望內(nèi)容是可信的。在未來(lái)網(wǎng)絡(luò)架構(gòu)中，服務(wù)命名基于以上設(shè)計(jì)原則和用戶所關(guān)心的問(wèn)題，提出名字由兩部分組成，服務(wù)屬性和服務(wù)提供商。其中服務(wù)的屬性是一個(gè)六元組，S = N、V、Ts、Te、P、M，分別由字母和數(shù)字組成。 服務(wù)屬性六元組N為服務(wù)的名字，是對(duì)服務(wù)的描述性名字，不需要唯一，可以同一個(gè)名字對(duì)應(yīng)多個(gè)服務(wù)，也可以一個(gè)服務(wù)對(duì)應(yīng)多個(gè)描述名字；V為服務(wù)的版本號(hào)；Ts為服務(wù)發(fā)布時(shí)間；Te為服務(wù)的有效時(shí)間，在這個(gè)時(shí)間內(nèi)服務(wù)是可用的，過(guò)了有效時(shí)間，則需要重新發(fā)布或者更新服務(wù)；P為服務(wù)的私有性，表示該服務(wù)是否屬于私有，是否允許訪問(wèn)；M表示是否允許遷移，因?yàn)橛行┓?wù)雖然不是私有，但是也不允許遷移，所以需要將私有性和可遷移性區(qū)別對(duì)待。這些屬性都是由服務(wù)提供商來(lái)確定的，在這里統(tǒng)稱為服務(wù)屬性。在服務(wù)名字中，因特網(wǎng)服務(wù)提供商（SISP）由字母和數(shù)字組成。服務(wù)提供商最終被Hash為一個(gè)64位的數(shù)。服務(wù)屬性也同樣是被分段Hash為一個(gè)64位的值。這兩部分的64位值再組合，就得到了最終的128位的UID（unique identifier），這是一個(gè)全球唯一的服務(wù)ID，保證了服務(wù)SID的全球唯一性。Nname和SISP之間的關(guān)系為，一個(gè)SISP可以提供多個(gè)Nname，一個(gè)Nname也可以是由多個(gè)SISP提供的。例子： XXXnews /… sina其中的XXXnews為服務(wù)的名字，后面接著是服務(wù)發(fā)布時(shí)間等，允許服務(wù)屬性中的項(xiàng)為空值。用戶描述的服務(wù)名字與服務(wù)屬性進(jìn)行匹配，服務(wù)屬性和提供商也通過(guò)分段哈希得到唯一標(biāo)識(shí)符UID，從而對(duì)服務(wù)IP進(jìn)行查找。 服務(wù)名稱的哈希處理對(duì)于每一個(gè)服務(wù)都有一個(gè)唯一的標(biāo)識(shí)，就像每個(gè)人都有自己唯一的指紋一樣。為了避免重復(fù)存儲(chǔ)同一個(gè)服務(wù)，每當(dāng)新發(fā)布一個(gè)服務(wù)時(shí)，新服務(wù)在服務(wù)注冊(cè)表中就會(huì)有相應(yīng)的記錄，來(lái)表示這些已經(jīng)發(fā)布的服務(wù)，但是若是在服務(wù)注冊(cè)表中，直接以字符串的形式存儲(chǔ)，既費(fèi)內(nèi)存又費(fèi)查找時(shí)間，因?yàn)榉?wù)的ID字符串是不定長(zhǎng)的。若要存儲(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ì)很低。所以，本文使用Hash函數(shù)，將服務(wù)ID的每一部分隨機(jī)的映射為一個(gè)64位二進(jìn)制即8個(gè)字節(jié)的整數(shù)空間，服務(wù)的兩段標(biāo)識(shí)總共需要128位16字節(jié)的整數(shù)空間，這樣大大的節(jié)省了存儲(chǔ)服務(wù)信息所需要的存儲(chǔ)空間，這128位二進(jìn)制就相當(dāng)于服務(wù)ID的指紋[4]。并且，哈希函數(shù)能夠保證數(shù)據(jù)的完整性和認(rèn)證性。當(dāng)一個(gè)服務(wù)發(fā)布到該注冊(cè)中心時(shí)，先在Hash表中查找是否有這個(gè)服務(wù)對(duì)應(yīng)的服務(wù)ID指紋，來(lái)決定是否要發(fā)布這個(gè)服務(wù)。對(duì)Hash之后的值查找的速度要比直接對(duì)字符串查找的速度快幾倍到幾十倍。本文結(jié)合結(jié)構(gòu)化P2P網(wǎng)絡(luò)信息搜索方式來(lái)進(jìn)行名字與位置關(guān)系搜索，利用chord[5]算法來(lái)實(shí)