【正文】 點，這些節(jié)點會相應(yīng)調(diào)整路由表并通知對象服務(wù)器該節(jié)點已經(jīng)退出網(wǎng)絡(luò)。 節(jié)點加入和退出 Tapestry的節(jié)點加入算法和Pastry類似。也就是說每個節(jié)點可以同時具有客戶、服務(wù)器和路由器的功能。當(dāng)一條查找消息到達(dá)傳遞過程中的第n個節(jié)點時，該節(jié)點和目的節(jié)點的共同前綴長度至少大于n。Tapestry中的每個節(jié)點都保存有鄰居映射表。 Tapestry的設(shè)計Tapestry從一個標(biāo)識符空間中為每個節(jié)點隨機(jī)分配一個節(jié)點標(biāo)識符nodeID，對象也從同一個標(biāo)識符空間中分配一個全局唯一標(biāo)識符GUID（globally unique identifier）。在特殊情況下，還有可能出現(xiàn)多個相鄰的節(jié)點同時失效的情況。正常情況下，每個節(jié)點向其所有鄰居節(jié)點發(fā)送周期性的更新消息，消息中包括自身的區(qū)域范圍、它的鄰居列表以及這些鄰居節(jié)點負(fù)責(zé)的區(qū)域范圍。整個過程分為以下三步：1. 新節(jié)點首先找到一個已經(jīng)在CAN中的節(jié)點。路由時節(jié)點只要朝著目標(biāo)節(jié)點的方向把消息轉(zhuǎn)發(fā)給自己的鄰居節(jié)點即可。當(dāng)需要查詢關(guān)鍵字K1對應(yīng)的值時，任何節(jié)點都可以使用同樣的哈希函數(shù)找到K1對應(yīng)的點P，然后從該點對應(yīng)的節(jié)點取出相應(yīng)的值V1。在任何時候，整個坐標(biāo)空間動態(tài)地分配給系統(tǒng)中的所有節(jié)點，每個節(jié)點負(fù)責(zé)維護(hù)獨立的互不相交的一塊區(qū)域。一旦節(jié)點檢測出其葉子節(jié)點集L中的某個節(jié)點失效，它就會請求該集合中nodeId最大或最小的節(jié)點把其葉子節(jié)點集L’發(fā)送過來。假定新加入節(jié)點的nodeId為X，同時假定X在加入Pastry之前知道系統(tǒng)中和自己距離相近的節(jié)點A。 Pastry的路由Pastry的路由過程是：節(jié)點收到一條查詢消息時，首先檢查該消息的關(guān)鍵字是否落在葉子節(jié)點集范圍內(nèi)。第n行的2b1個表項中，每個節(jié)點nodeId的前n個數(shù)位和當(dāng)前節(jié)點nodeId的前n個數(shù)位相同，而第n＋1個數(shù)位和當(dāng)前節(jié)點不同。如果找不到這樣的鄰居節(jié)點，消息將轉(zhuǎn)發(fā)給前綴長度相同但是節(jié)點號數(shù)值更接近關(guān)鍵字的節(jié)點。 Pastry的設(shè)計 Pastry是自組織的重疊網(wǎng)絡(luò)，每個節(jié)點都被分配一個128位的nodeId。為了保證節(jié)點n的失效不影響系統(tǒng)中正在進(jìn)行的查詢過程，每個Chord節(jié)點都維護(hù)一張包括r個最近后繼節(jié)點的后繼列表。同理節(jié)點42也按照這個規(guī)則把請求轉(zhuǎn)發(fā)給節(jié)點51，節(jié)點51發(fā)現(xiàn)54落在它和它的后繼節(jié)點標(biāo)識56之間，因而就把節(jié)點56的標(biāo)識和IP地址等信息返回給節(jié)點8。但是，對于任意一個關(guān)鍵字K，節(jié)點通常無法根據(jù)自身的指針表確定的K的后繼節(jié)點。為此，每個節(jié)點需要維護(hù)一個路由表，稱為指針表（finger table）。有了這張表，Chord就可以在環(huán)上任意兩點間進(jìn)行尋路。因為successor(10)=14，所以關(guān)鍵字10存儲到節(jié)點14上。本文在第三章以Chord作為示例，介紹作者在改善DHT路由性能方面所做的工作。從這個節(jié)點上取得文件索引(K, V)對后，再從V中讀出真正存儲文件的節(jié)點IP地址。在這個大規(guī)模的分布式系統(tǒng)中，如何不引入目錄服務(wù)器就能高效快速地找到指定的數(shù)據(jù)則是研究中的核心問題。但是目前DHT還面臨許多問題，Sylvia Ratnasamy 等人在總結(jié)現(xiàn)有的DHT路由算法的基礎(chǔ)之上【27】提出了結(jié)構(gòu)化對等網(wǎng)絡(luò)面臨著十五個主要問題。這里面有個很重要的問題，就是節(jié)點要按照一定的規(guī)則來分割整體的哈希表，進(jìn)而也就決定了節(jié)點要維護(hù)特定的鄰居節(jié)點，以便路由能順利進(jìn)行。然而其缺點也是明顯的：在網(wǎng)絡(luò)中廣播查詢報文加重了網(wǎng)絡(luò)通信負(fù)擔(dān)，其查詢機(jī)制在系統(tǒng)規(guī)模擴(kuò)大時不具有可擴(kuò)展性?；谀夸浄?wù)器的P2P系統(tǒng)在查找目錄的時候，簡單高效，但由于依賴集中式的目錄服務(wù)器，隨著用戶節(jié)點數(shù)目的增加，服務(wù)器將遭遇瓶頸問題，而且會成為系統(tǒng)的單一故障點，系統(tǒng)的可擴(kuò)展性差。 如何實現(xiàn)P2P讓對等節(jié)點之間進(jìn)行數(shù)據(jù)通信，本身不是難點，完全可以通過現(xiàn)有的網(wǎng)絡(luò)編程技術(shù)實現(xiàn)，而如何穿越NAT（Network Address Translater）和防火墻也只是一些技術(shù)細(xì)節(jié)問題。由于單一計算單元的計算能力總是有限的，因此人們一般采用并行技術(shù)、分布式技術(shù)將多個計算單元節(jié)點聯(lián)合起來共同完成大規(guī)模的計算任務(wù)，同時目前網(wǎng)絡(luò)中的計算機(jī)的計算能力一直利用的不是很充分，人們期望能夠充分利用網(wǎng)絡(luò)中的閑散計算能力來完成大規(guī)模的計算任務(wù)，這樣將會使得網(wǎng)絡(luò)中所蘊含的海量計算能力得到更加充分的利用。所有人都共享了他們認(rèn)為最有價值的東西，這將使互聯(lián)網(wǎng)上信息的價值得到極大的提升。ICQ、OICQ、AIM，MSN等是典型的實時通信系統(tǒng)，這些系統(tǒng)也包含好友列表等基本功能。網(wǎng)絡(luò)規(guī)模越來越大，連入網(wǎng)絡(luò)中的設(shè)備以及計算單元的數(shù)量和種類也越來越多，然而這些設(shè)備以及計算單元并沒有得到充分的利用，如果能夠?qū)⑦@些設(shè)備以及計算單元的處理器計算能力、磁盤存儲能力以及網(wǎng)絡(luò)帶寬資源等進(jìn)行充分利用將會有效緩解目前互聯(lián)網(wǎng)所面臨的一些問題。所以，對等節(jié)點越多，網(wǎng)絡(luò)的可靠性也就越高。P2P技術(shù)避免了C/S結(jié)構(gòu)帶來的單點失效和性能瓶頸等問題，它不依賴或盡可能不依賴中央服務(wù)器，使得每個參與節(jié)點既能作為服務(wù)器，也可成為客戶機(jī)。無論服務(wù)器性能多么優(yōu)越，它的存儲容量都是有限的，硬盤讀寫速度和網(wǎng)絡(luò)接口都有一定的限制，CPU處理能力也只能滿足一定的要求。另一種則是不引入任何服務(wù)器的完全對等的純P2P結(jié)構(gòu)，(b)所示。 什么是P2PP2P中文稱為對等網(wǎng)絡(luò)，是指分布式系統(tǒng)中的各個節(jié)點是邏輯對等的，與目前互連網(wǎng)上比較流行的C/S計算模型不同的是：P2P計算模型中不再區(qū)別服務(wù)器以及客戶端，系統(tǒng)中的各個節(jié)點之間可以直接進(jìn)行數(shù)據(jù)通信而不需要通過中間的服務(wù)器。同時，隨著近年來計算機(jī)通信技術(shù)的飛速發(fā)展，大量的個人計算機(jī)接入Internet，從而導(dǎo)致Internet規(guī)模不斷擴(kuò)大，Internet入網(wǎng)的主機(jī)數(shù)、上網(wǎng)的人數(shù)都在飛速增長。這樣，路由可以先在本地DHT中進(jìn)行，必要時經(jīng)由全局DHT，從而避免多次跨域路由。我們注意到IPv6地址分配的層次性，同一自治域內(nèi)的主機(jī)通常具有一定長度的相同的網(wǎng)絡(luò)前綴，因而DHT系統(tǒng)中的節(jié)點可以從自己的IPv6地址前綴中獲取位置信息。因為路由算法是DHT的核心，所以提高DHT尋路效率是當(dāng)前基于DHT的P2P研究的重點，具有很重要的意義。然而第一代的P2P系統(tǒng)都沒有很好地解決這個問題。作者簽名： 日期： 年 月 日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。碩士學(xué)位論文論文題目基于DHT的P2P研究研究生姓名導(dǎo)師姓名專業(yè)論文完成時間畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。本人完全意識到本聲明的法律后果由本人承擔(dān)。在大規(guī)模的P2P系統(tǒng)中，如何高效地查找到指定的數(shù)據(jù)是一個非常關(guān)鍵的問題。但是目前DHT還面臨許多問題，最大的問題之一就是DHT在初始設(shè)計時忽略了參與節(jié)點在物理網(wǎng)絡(luò)上的鄰近性，導(dǎo)致重疊網(wǎng)絡(luò)和物理網(wǎng)絡(luò)脫節(jié)，即DHT未能充分利用底層物理網(wǎng)絡(luò)的拓?fù)湫畔?，從而造成實際的尋路效率低下。本文的主要工作和創(chuàng)新點如下：1. 提出了從IPv6地址前綴中提取節(jié)點位置信息的方法。本文創(chuàng)新性的提出把節(jié)點的位置信息也存儲到DHT系統(tǒng)中，新加入的節(jié)點可以通過DHT查詢到具有相同位置信息的全部節(jié)點列表，從而在物理網(wǎng)絡(luò)上臨近的節(jié)點之間構(gòu)造內(nèi)嵌于全局DHT中的本地DHT。關(guān)鍵字：P2P，DHT，Chord，查找，尋路，IPv6，拓?fù)?，層次化，文件共享５７中國科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 AbstractAbstractWith the great improvement of PC performance and the fast growth of Internet users, there emerges a vast quantity of puting and storage resources on the Internet edge. P2P (peertopeer) technology can be an effective means to harness these resources, which accounts for the fact that P2P applications are being more and more popular these days. In a P2P system, all peers are identical regarding functionality. Unlike the traditional C/S (client/server) model, there are no dedicated servers and peers can directly municate with each other for data transmission. P2P can solve the problems of single point failure and performance bottle encountered by C/S model. A fundamental problem that confronts a largescale P2P system is the efficient location of the node that stores the desired date item. However, the first generation of P2P systems did not address the problem well. Napster has a centralized index server where scalability can be limited by the machine power and the network bandwidth of the central point. Gnutella employs a messaging mechanism that is based on flooding, which can impose heavy burden on networks and thus promise its scalability. To address the problem, several research groups independently proposed DHT (distributed hash table) systems, which include Chord, CAN, Pastry and Tapestry. DHTs reorganize peers into an overlay in the application level, distribute file indexes into the network, and route queries through the overlay. DHTs are robust in the face of failures, attacks and unexpectedly high loads. They are scalable, achieving large system sizes without incurring undue overhead. They are selfconfiguring, automatically incorporating new nodes without manual intervention or oversight. They provide a simple and flexible interface and are simultaneously usable by many applications.However, DHTs are still faced with many problems, one of which is the fact that most DHTs do not take into account physical network topology in their original design, thus resulting in high routing latency and low efficiency. Therefore, to improve routing performance is an important direction for research on DHTbased P2P. While centering on the issue of routing enhancement, the author has conducted an indepth research on how to extract topology information and how to utilize that information to construct topologyaware DHT systems. In Chapter 3, we propose three solutions, which are called DHT with hierarchical identifiers, embedded DHT and hierarchical DHT. To illustrate our solutions, we build Chord6, eChord and hChord all upon the original Chord system. Analysis and simulation results