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