【正文】 產(chǎn)生P2PEvent和SimEvent, 仿真實(shí)現(xiàn)P2psim 仿真結(jié)果分析 小結(jié)重慶郵電大學(xué)碩士論文 總結(jié)與展望第六章 總結(jié)與展望 總結(jié)本文在身份位置相分離的命名原則下對(duì)服務(wù)名字提出了一套新的命名方法，并驗(yàn)證了其位數(shù)的合理性，在chord模型的基礎(chǔ)上，結(jié)合了二分法提出了在chord環(huán)上的折半查找路由算法，大大的降低了查找時(shí)間提高了查找效率。很簡(jiǎn)單，只是加入了一個(gè)模擬結(jié)束的事件。中的type={join, crash, lookup, nodeevent},通過(guò)name2fn獲取, fn為P2PEvnet將要執(zhí)行的函數(shù)，args為fn執(zhí)行時(shí)的參數(shù)，P2PEvent，SimEvent；根類：Event（產(chǎn)生事件的時(shí)間，事件名稱，事件ID）Event類中有個(gè)_fork標(biāo)識(shí)，如果_fork為真，事件的采用線程方式激活，調(diào)用taskcreate，這種事件難道是立即執(zhí)行嗎？如果_fork為假，事件直接調(diào)用執(zhí)行函數(shù)execute,注意在event類中execute為純虛函數(shù)，會(huì)動(dòng)態(tài)綁定子類的execute函數(shù)Event中的name={“NetEvent”, “P2PEvent”, “SimEvent”}NetEventEvents中主要設(shè)置了所需要的協(xié)議和開始時(shí)間、結(jié)束時(shí)間。其中，Euclidean類支持通過(guò)歐幾里德空間坐標(biāo)定義節(jié)點(diǎn)之間的關(guān)系。 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。Topologies文件中包含了很多網(wǎng)絡(luò)拓?fù)漕愋?，可以選定任意一種在其網(wǎng)絡(luò)拓?fù)淠Ｐ椭羞M(jìn)行網(wǎng)絡(luò)模擬仿真。上層的實(shí)現(xiàn)利用C++的面向?qū)ο髾C(jī)制，使得代碼易讀性和靈活性、可重用性大幅度提高。STL能夠提供比C++中class機(jī)制高很多的運(yùn)行效率。 Distributed Operating System Group開發(fā)的開源項(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ò)的仿真。重慶郵電大學(xué)碩士論文 P2psim實(shí)現(xiàn)路由過(guò)程第五章 P2psim實(shí)現(xiàn)路由過(guò)程 仿真軟件p2psim介紹因?yàn)閏hord協(xié)議主要是應(yīng)用層上的協(xié)議，所以為了更好的仿真chord協(xié)議，本文中采用采用P2Psim[34]。2nimod 2n, 1≤i≤n N目的ID時(shí)，為+；N目的ID時(shí)，為，其中i為跳轉(zhuǎn)的次數(shù)。結(jié)合chord環(huán)模型和二分法得到折半查找算法，具體如下：其中i為跳轉(zhuǎn)的次數(shù)：1 ID177。 chord折半查找算法在尋址系統(tǒng)中，每一次跳轉(zhuǎn)都chord環(huán)上地址空間總大小為 2m，這是由采用的hash函數(shù)決定的，m為哈希之后的標(biāo)識(shí)符的位數(shù)。如果新的位置屬于注冊(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）。當(dāng)服務(wù)S被服務(wù)提供商發(fā)布到一個(gè)注冊(cè)中心A時(shí)，這個(gè)注冊(cè)中心就是這個(gè)服務(wù)S的原始節(jié)點(diǎn)，服務(wù)S在注冊(cè)中心A中所存儲(chǔ)的身份和位置的對(duì)應(yīng)關(guān)系為S（UID：locator1），locator1是服務(wù)S所在的具體位置。值得注意的是，這里chord的每個(gè)節(jié)點(diǎn)中只存在一張表，沒有經(jīng)典chord環(huán)里節(jié)點(diǎn)間用于路由查找的finger表，每個(gè)節(jié)點(diǎn)都是只按照一個(gè)路由算法進(jìn)行選路。每一個(gè)chord節(jié)點(diǎn)都需要維持一張表，是保存著服務(wù)名稱經(jīng)過(guò)hash之后的UID值和對(duì)應(yīng)的服務(wù)locator之間的位置關(guān)系的服務(wù)信息存儲(chǔ)表。而DRMC管理中心的每一個(gè)節(jié)點(diǎn)相當(dāng)于一個(gè)區(qū)域的DRMC的匯總，主要負(fù)責(zé)管理這些DRMC的個(gè)數(shù)、位置和狀態(tài)。這就是傳統(tǒng)互聯(lián)網(wǎng)中，由用戶發(fā)送一個(gè)服務(wù)請(qǐng)求到找到服務(wù)IP地址的解析過(guò)程。其實(shí)，域名的最終指向是IP。名稱時(shí)，DNS服務(wù)可以將此名稱解析為與之相關(guān)的其他信息，如 IP 地址。當(dāng)用戶在應(yīng)用程序中輸入Internet的在Internet上域名與IP地址之間是一對(duì)一（或者多對(duì)一）的，也可采用DNS輪詢實(shí)現(xiàn)一對(duì)多，域名雖然便于人們記憶，但機(jī)器之間只認(rèn)IP地址，它們之間的轉(zhuǎn)換工作稱為域名解析，域名解析需要由專門的域名解析服務(wù)器來(lái)完成，DNS就是進(jìn)行域名解析的服務(wù)器。域名系統(tǒng)采用樹的結(jié)構(gòu)，最高為頂級(jí)域名，再每層往下分。它是由解析器以及域名服務(wù)器組成的，域名服務(wù)器是指保存有該網(wǎng)絡(luò)中所有主機(jī)的域名和其對(duì)應(yīng)的IP地址，并具有將域名轉(zhuǎn)換為IP地址功能的服務(wù)器。圖 (2) 尋址體系介紹 經(jīng)典尋址技術(shù)介紹傳統(tǒng)互聯(lián)網(wǎng)中的尋址主要是指DNS（Domain Name System）到IP地址的解析，這個(gè)過(guò)程稱為域名解析過(guò)程。這里我們采用DHT模型中的chord模型來(lái)仿真節(jié)點(diǎn)間的選擇尋路過(guò)程，每個(gè)節(jié)點(diǎn)處的路由算法是將二分法與chord模型相結(jié)合之后的新的尋址算法。樹形結(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)訪問(wèn)分布。其中，最常用的是樹形拓?fù)浣Y(jié)構(gòu)（如DNS）和扁平結(jié)構(gòu)?，F(xiàn)有的尋址系統(tǒng)多是采用分布式結(jié)構(gòu)模型，一個(gè)設(shè)計(jì)較好的分布式系統(tǒng)能夠有效的支持尋址系統(tǒng)的解析，提高解析效率。第五步當(dāng)用戶得到服務(wù)的位置信息后，即這項(xiàng)服務(wù)的提供者位置信息，再向服務(wù)提供者發(fā)出服務(wù)請(qǐng)求；第六步，服務(wù)提供者相應(yīng)用戶的請(qǐng)求。服務(wù)提供者再將自己的服務(wù)信息和服務(wù)所在原始位置信息添加到注冊(cè)表中。從服務(wù)提供者ISP發(fā)布一個(gè)服務(wù)到用戶得到服務(wù)的過(guò)程中，有三個(gè)主要構(gòu)成元素，服務(wù)提供商，用戶和注冊(cè)中心。由此可得出數(shù)據(jù)存儲(chǔ)方式和數(shù)據(jù)的查詢檢索方式這兩部分共同構(gòu)成了計(jì)算機(jī)服務(wù)尋址系統(tǒng)[9]。第四章 尋址體系與尋址算法研究 尋址課題分析計(jì)算機(jī)中服務(wù)的尋址是指“從服務(wù)的名稱到服務(wù)所在的地址的一個(gè)完整的解析過(guò)程”。對(duì)于出現(xiàn)的沖突，對(duì)于所有64位的哈希函數(shù)沖突率為這么大，結(jié)合存儲(chǔ)容量和查找時(shí)間復(fù)雜度考慮，我們認(rèn)為64位的MURMUR哈希函數(shù)是符合實(shí)驗(yàn)要求的。分段Hash后，*。其實(shí)也可以直接利用②式來(lái)得到碰撞概率，MURMUR為64位的Hash函數(shù)，n=64，即S=，r=代入②式。對(duì)于Hash值長(zhǎng)度為64比特的Hash函數(shù)，它有種可能的散列值，要想100%地找到一組碰撞，就需要+1次約等于次攻擊。由于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。將消息表示成變形消息的方法很多，例如增加空格、使用縮寫、使用意義相同的單詞、去掉不必要的單詞等。設(shè)Hash函數(shù)值有n個(gè)比特，m是真消息，M是偽造的假消息，分別把消息m和M表示成r和R個(gè)變形的消息。這比我們直觀想象的值要小的多。又因?yàn)橛挟?dāng)，有當(dāng)時(shí)，所以可以推出所以有①式所以兩個(gè)元素相同的概率P=1，設(shè)為②式。 Hash函數(shù)碰撞 生日悖論推導(dǎo)生日悖論，至少需要多少人，才能保證至少有兩個(gè)人同一天生日的概率大于1/2？設(shè)S為有S個(gè)元素的集合，從S中隨機(jī)選取一個(gè)的選法有種，再選第二個(gè)和第一個(gè)沖突的概率為，再選第三個(gè)和前兩個(gè)沖突的概率為，從S中選取第r個(gè)元素和之前的元素相同的概率為。對(duì)于服務(wù)提供商而言，如果說(shuō)如果地球上有100億的人口（實(shí)際上人口不足70億），那么每個(gè)人都可以同時(shí)作為1844674407這么多個(gè)ISP，這是不現(xiàn)實(shí)的，因?yàn)镮SP的數(shù)量是絕對(duì)比人口的數(shù)量少的，不可能每個(gè)人都是一個(gè)ISP，更不可能每個(gè)人同時(shí)作為1844674407這么大數(shù)量的ISP，所以，64位的空間對(duì)ISP來(lái)說(shuō)是綽綽有余的。對(duì)于服務(wù)提供商，設(shè)服務(wù)提供商有N個(gè)，總?cè)丝跀?shù)量為70億，N 70億 所以服務(wù)提供商的數(shù)量是絕對(duì)遠(yuǎn)小于這么多的。以目前人類的技術(shù)可以存儲(chǔ)至少295艾字節(jié)（exabytes）的信息，這個(gè)數(shù)字相當(dāng)于1后面有20個(gè)零。位數(shù)的確定是基于兩個(gè)不可反駁的事實(shí)：服務(wù)信息總量不會(huì)超過(guò)存儲(chǔ)總量，服務(wù)提供商的數(shù)量不會(huì)超過(guò)人口的數(shù)量。 哈希服務(wù)ID所需位數(shù)驗(yàn)證服務(wù)ID由服務(wù)名字和服務(wù)提供商這兩部分組成。比如說(shuō)，一個(gè)服務(wù)ID的UID取模后得到的數(shù)值為45，則它就在chord環(huán)上查找EID取模后的值，離45最近的一個(gè)節(jié)點(diǎn)作為這個(gè)服務(wù)的后繼節(jié)點(diǎn)。Nname = 名字、版本、發(fā)布時(shí)間、有效日期、私有性、可遷移性SISPHashHashUIDNIDSID128 bit64 bit64 bit 服務(wù)名稱哈希生成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)。只要選擇的Hash函數(shù)足夠好，也可以保證不會(huì)產(chǎn)生兩個(gè)相同的服務(wù)ID指紋避免沖突。對(duì)Hash之后的值查找的速度要比直接對(duì)字符串查找的速度快幾倍到幾十倍。并且，哈希函數(shù)能夠保證數(shù)據(jù)的完整性和認(rèn)證性。若要存儲(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ì)很低。 服務(wù)名稱的哈希處理對(duì)于每一個(gè)服務(wù)都有一個(gè)唯一的標(biāo)識(shí)，就像每個(gè)人都有自己唯一的指紋一樣。例子： XXXnews /… sina其中的XXXnews為服務(wù)的名字，后面接著是服務(wù)發(fā)布時(shí)間等，允許服務(wù)屬性中的項(xiàng)為空值。這兩部分的64位值再組合，就得到了最終的128位的UID（unique identifier），這是一個(gè)全球唯一的服務(wù)ID，保證了服務(wù)SID的全球唯一性。服務(wù)提供商最終被Hash為一個(gè)64位的數(shù)。這些屬性都是由服務(wù)提供商來(lái)確定的，在這里統(tǒng)稱為服務(wù)屬性。其中服務(wù)的屬性是一個(gè)六元組，S = N、V、Ts、Te、P、M，分別由字母和數(shù)字組成。不變性是指不管服務(wù)遷移到任何地方，服務(wù)的名字始終唯一；可達(dá)性是指即使網(wǎng)絡(luò)和服務(wù)失敗名字的內(nèi)容或者服務(wù)也達(dá)；可信性是指用戶不考慮內(nèi)容在哪兒，但是希望內(nèi)容是可信的。當(dāng)基于身份位置相分離來(lái)介紹未來(lái)因特網(wǎng)架構(gòu)，identifier必須滿足一些要求。Locator只用于路由，而identifier只在應(yīng)用層負(fù)責(zé)對(duì)服務(wù)身份的判斷，不再與locator綁定用于路由。基于身份位置相分離，得到的服務(wù)名字和服務(wù)的位置是一種對(duì)應(yīng)關(guān)系，有一個(gè)名字位置對(duì)（pair）， SID：locator。（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。（1）身份標(biāo)識(shí)（ID）ID（Identifier）是網(wǎng)絡(luò)域內(nèi)服務(wù)的唯一標(biāo)識(shí)，服務(wù)的ID一旦產(chǎn)生或被分配，將不會(huì)改變且長(zhǎng)期有效。身份標(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ǎng)絡(luò)區(qū)域內(nèi)服務(wù)唯一的標(biāo)識(shí)，具有區(qū)域唯一性和不變性。本文中，按照身份位置相分離原則，提出服務(wù)身份的命名規(guī)則，服務(wù)所在的地址依舊采用IP地址，將服務(wù)名字通過(guò)分段哈希算法后得到域內(nèi)唯一的哈希值，通過(guò)唯一的域內(nèi)哈希值可以在服務(wù)注冊(cè)中心處找到相對(duì)應(yīng)的服務(wù)所在IP地址，通過(guò)提出新的路由算法，在域內(nèi)或者域間快速找到目的地址。而路由則是知道服務(wù)的地址后，怎么通過(guò)地址在網(wǎng)絡(luò)中找到服務(wù)，通過(guò)服務(wù)名字找到服務(wù)所在的地址的過(guò)程稱為尋址。在網(wǎng)絡(luò)中，用戶所查找的資源的名字是相對(duì)不變的，因?yàn)橐坏┟指淖?，也就說(shuō)明這個(gè)服務(wù)消失或者有所變動(dòng)，就不再是原先的服務(wù)了。重慶郵電大學(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ā)的目的地址。注意，這里存儲(chǔ)的只是服務(wù)名字與服務(wù)所在地址的對(duì)應(yīng)關(guān)系，并不是服務(wù)本身。關(guān)鍵字通過(guò)hash函數(shù)得到相應(yīng)的hash值存儲(chǔ)在它的后繼節(jié)點(diǎn)上，在chord中的尋址也就是對(duì)服務(wù)IP地址的查找。查找路線為N8—N42—N51—N56，節(jié)點(diǎn)N54的信息就存儲(chǔ)在離N54最近的后繼節(jié)點(diǎn)N56上。Chord查找路由過(guò)