通信與信息系統(tǒng)專業(yè)碩士學(xué)位論文：基于DHT的P研究檔

1、碩士學(xué)位論文論文題目基于DHT的P2P研究研究生姓名導(dǎo)師姓名教授專業(yè)通信與信息系統(tǒng)論文完成時間2005年5月摘要隨著個人計算機性能的提高和互連網(wǎng)用戶的急劇增長，在網(wǎng)絡(luò)邊緣出現(xiàn)了大量的閑散計算和存儲資源，而網(wǎng)絡(luò)帶寬的大幅提高也使得開發(fā)和利用這些潛在的計算資源成為可能。如何有效利用這些大量的計算資源已成為一個熱點問題，P2P研究正是在這種背景下展開的。P2P中文稱為對等網(wǎng)絡(luò)，是指分布式系統(tǒng)中的各個節(jié)點是邏輯對等的，與目前互連網(wǎng)上比較流行的C/S計算模型不同的是：P2P計算模型中不再區(qū)分服務(wù)器和客戶端，系統(tǒng)中的各個節(jié)點之間可以直接進行數(shù)據(jù)通信而不需要通過中間的服務(wù)器。P2P可以解決傳統(tǒng)的C/S模型下

2、服務(wù)器帶來的性能瓶頸和單一故障點等問題，能夠充分利用互聯(lián)網(wǎng)邊緣所蘊含的潛在計算和存儲資源。在大規(guī)模的P2P系統(tǒng)中，如何高效地查找到指定的數(shù)據(jù)是一個非常關(guān)鍵的問題。然而第一代的P2P系統(tǒng)都沒有很好地解決這個問題。Napster為了查找音樂文件而配置的目錄服務(wù)器在用戶增多時將成為系統(tǒng)的瓶頸和單一故障點。Gnutella所采用的泛洪查詢報文的方法在系統(tǒng)規(guī)模擴大時會給網(wǎng)絡(luò)造成較大的負擔(dān)，因而同樣不具有可擴展性。為了解決P2P系統(tǒng)中可擴展的數(shù)據(jù)檢索問題，國際上幾個研究小組獨立地提出了Chord、CAN、Pastry和Tapestry等基于DHT的結(jié)構(gòu)化P2P系統(tǒng)。DHT在應(yīng)用層上把所有的P2P節(jié)點組織成

3、一個結(jié)構(gòu)化的重疊網(wǎng)絡(luò)，文件索引分布其中，查詢報文將通過這個重疊網(wǎng)絡(luò)路由。DHT在節(jié)點失效、遭受攻擊和突發(fā)性高負載面前都能表現(xiàn)出很好的健壯性；它具有良好的可擴展性，能以較低系統(tǒng)開銷獲得較大的系統(tǒng)規(guī)模；可以自我配置，不需要手工干預(yù)就可以自動把新加入節(jié)點合并到系統(tǒng)中；能提供簡單靈活的接口，可以為多個應(yīng)用同時使用。本文在第2章對DHT系統(tǒng)進行了綜述。但是目前DHT還面臨許多問題，最大的問題之一就是DHT在初始設(shè)計時忽略了參與節(jié)點在物理網(wǎng)絡(luò)上的鄰近性，導(dǎo)致重疊網(wǎng)絡(luò)和物理網(wǎng)絡(luò)脫節(jié)，即DHT未能充分利用底層物理網(wǎng)絡(luò)的拓撲信息，從而造成實際的尋路效率低下。因為路由算法是DHT的核心，所以提高DHT尋路效率是當(dāng)

4、前基于DHT的P2P研究的重點，具有很重要的意義。本文圍繞DHT尋路效率的改善，對如何提取節(jié)點在物理網(wǎng)絡(luò)上的位置信息和如何利用位置信息構(gòu)造拓撲敏感(topology-aware)的DHT系統(tǒng)進行了深入的研究，提出了具有層次化標識符的DHT、內(nèi)嵌式DHT和層次化DHT三種利用拓撲信息改進DHT路由性能的方案，本文通過把Chord改造成Chord6、eChord和hChord來分別闡述這幾種方案的思路，并通過仿真和分析闡明了這些方案能有效地改善現(xiàn)有DHT尋路效率。本文在第3章詳細介紹了我們的研究成果。DHT具有廣闊的應(yīng)用前景，國際上許多著名的研究機構(gòu)都在開展基于DHT的大規(guī)模P2P系統(tǒng)研制工作。圍

5、繞這個方向，在實驗室CNGI預(yù)研項目基于IPv6的P2P彈性重疊網(wǎng)絡(luò)智能節(jié)點的研制中，我們利用自己提出的Chord6，設(shè)計了一個IPv6環(huán)境下的文件共享系統(tǒng)FSS6。FSS6不僅可以在實踐中檢驗我們提出的DHT改進方案的有效性，而且還可以充分展示IPv6和P2P技術(shù)結(jié)合的優(yōu)越性，推動IPv6的普及發(fā)展，加速CNGI的順利演進；同時，F(xiàn)SS6還將給P2P應(yīng)用探索一個可運營、可管理和可控制的示范模式，進一步推動P2P應(yīng)用的良性發(fā)展，更好地滿足用戶需求。本文在第4章詳細介紹FSS6的設(shè)計。本文的主要工作和創(chuàng)新點如下：1. 提出了從IPv6地址前綴中提取節(jié)點位置信息的方法。我們注意到IPv6地址分配的

6、層次性，同一自治域內(nèi)的主機通常具有一定長度的相同的網(wǎng)絡(luò)前綴，因而DHT系統(tǒng)中的節(jié)點可以從自己的IPv6地址前綴中獲取位置信息。IPv6以及P2P系統(tǒng)都是下一代網(wǎng)絡(luò)中重要的發(fā)展方向，本文把兩者結(jié)合在一起是一個重要的嘗試。2. 提出了一種構(gòu)建層次化節(jié)點標識符的方案。我們創(chuàng)造性的提出節(jié)點標識符可以分段構(gòu)造，標識符的前綴可以通過哈希同一個域中節(jié)點共同的位置信息得到，從而使得物理網(wǎng)絡(luò)上臨近的節(jié)點在重疊網(wǎng)絡(luò)上也互為近鄰。作為示例，本文結(jié)合IPv6和Chord，構(gòu)造了一種改進型的DHT系統(tǒng)Chord6，僅僅對Chord協(xié)議做了很小的改動就取得了很好的尋路性能改善，并通過仿真驗證了這種方案的有效性。我們指出構(gòu)

7、建層次化節(jié)點標識符的思想完全可以應(yīng)用于其他的DHT系統(tǒng)中，如CAN和Pastry等。3. 提出了一種構(gòu)造內(nèi)嵌式DHT的方案，既改進了尋路效率又保持了原有DHT系統(tǒng)的負載平衡性質(zhì)。本文創(chuàng)新性的提出把節(jié)點的位置信息也存儲到DHT系統(tǒng)中，新加入的節(jié)點可以通過DHT查詢到具有相同位置信息的全部節(jié)點列表，從而在物理網(wǎng)絡(luò)上臨近的節(jié)點之間構(gòu)造內(nèi)嵌于全局DHT中的本地DHT。這樣，路由可以先在本地DHT中進行，必要時經(jīng)由全局DHT，從而避免多次跨域路由。該方案具有完全分布式的特點。作為示例，本文利用這種思想對Chord進行了改進，構(gòu)造了eChord。仿真的結(jié)果證明該方案的有效性。4. 提出了構(gòu)造層次化DHT的

8、方案，按物理網(wǎng)絡(luò)的遠近把節(jié)點劃分為多個組，使得節(jié)點動態(tài)加入和退出的影響局限在單個組中；同時也把關(guān)鍵字分層存儲以支持部分查詢。初步的分析結(jié)果證明這種方案具有良好的部分查詢性能。5. 利用我們自己提出的Chord6，設(shè)計了一個IPv6環(huán)境下的文件共享系統(tǒng)FSS6。關(guān)鍵字：P2P，DHT，Chord，查找，尋路，IPv6，拓撲，層次化，文件共享AbstractWith the great improvement of PC performance and the fast growth of Internet users, there emerges a vast quantity of compu

9、ting and storage resources on the Internet edge. P2P (peer-to-peer) technology can be an effective means to harness these resources, which accounts for the fact that P2P applications are becoming more and more popular these days. In a P2P system, all peers are identical regarding functionality. Unli

10、ke the traditional C/S (client/server) model, there are no dedicated servers and peers can directly communicate 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 large-scal

11、e 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 p

12、oint. Gnutella employs a messaging mechanism that is based on flooding, which can impose heavy burden on networks and thus compromise its scalability. To address the problem, several research groups independently proposed DHT (distributed hash table) systems, which include Chord, CAN, Pastry and Tap

13、estry.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

14、 overhead. They are self-configuring, 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 D

15、HTs 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 DHT-based P2P. While centering on the issue of routing enhancement, the auth

16、or has conducted an in-depth research on how to extract topology information and how to utilize that information to construct topology-aware DHT systems. In Chapter 3, we propose three solutions, which are called DHT with hierarchical identifiers, embedded DHT and hierarchical DHT. To illustrate our

17、 solutions, we build Chord6, eChord and hChord all upon the original Chord system. Analysis and simulation results prove that our solutions can greatly improve routing efficiency in Chord.Currently, a new generation of applications has been proposed on top of DHTs. In this paper, we also design a wi

18、de-area file-sharing system based on Chord6, validating the effectiveness of our research work on DHT routing enhancement. The major contributions of this paper are listed as follows:1. Propose a novel method to extract topology information from IPv6 address prefixes. We notice that IPv6 addresses a

19、re assigned in a hierarchical way so that nodes with the same prefix are in the same autonomous domain. Therefore peers in a DHT system can learn their location information from their own IPv6 addresses.2. Devise a smart scheme to exploit the IPv6 address hierarchical feature, so as to construct an

20、efficient version of Chord dubbed Chord6. We propose that node identifiers can be divided into several parts and thus be produced separately. For a node identifier divided into two parts, the higher bits can be obtained by hashing the shared address prefix among all nodes within the same AS, and the

21、 lower bits are the hash result of the rest of the IPv6 address. As a result, topologically close peers shall also be adjacent in the overlay. An important advantage of our scheme is that it is very simple and barely modifies the original Chord. Simulation results have shown that our method can sign

22、ificantly reduce inter-domain traffic that causes the long routing latency.3. Devise a novel scheme to construct embedded DHT, which can not only improve the routing efficiency, but also inherit the load-balancing feature of the original DHT. First, nodes independently insert their location informat

23、ion into DHT systems as they do with file indexes. Then, a newly joined node can utilize DHT to get a complete list of all nodes that are close to it in the underlying physical networks. Finally, nodes within the same domains are organized into many local DHTs which are then embedded into a global D

24、HT comprised of all nodes. Thus, routing can be conducted in local DHTs first, and pass through each other (if necessary) with the aid of the global DHT, which means that inter-domain traffic can be minimized to the extreme. To illustrate the feasibility and effectiveness of the scheme, we construct

25、 eChord upon the original Chord system. Analysis and simulation demonstrate that our scheme is very effective.4. Propose a new kind of hierarchical DHT dubbed hChord, in which topologically close nodes are grouped in the overlay and keys are stored in a hierarchical way. Analysis show that hChord ca

26、n isolate the effect of dynamic nodes within small groups for better scalability and stability, and show improved performance with partial queries. 5. Present a prototype design of an IPv6-based wide-area file sharing system based on Chord6.Keywords：P2P，DHT，Chord，look up, routing，IPv6，topology，hiera

27、rchical, file sharing目錄摘要IAbstractIII目錄V第1章 序論1.1 P2P研究背景1.2 什么是P2P1.3 為什么需要P2P1.4 P2P的應(yīng)用領(lǐng)域1.4.1 信息共享1.4.2 實時通信1.4.3 網(wǎng)絡(luò)游戲1.4.4 金融服務(wù)1.4.5 信息檢索1.4.6 協(xié)同工作1.4.7 普及計算1.4.8 網(wǎng)絡(luò)存儲1.5 如何實現(xiàn)P2P1.5.1 基于目錄服務(wù)器P2P1.5.2 非結(jié)構(gòu)化P2P1.5.3 結(jié)構(gòu)化P2P1.6 本章小結(jié)第2章 DHT基本原理2.1 引言2.2 Chord2.2.1 Chord的設(shè)計2.2.2 Chord的路由2.2.3節(jié)點加入和退出2.3

28、 Pastry2.3.1 Pastry的設(shè)計2.3.2 Pastry的路由2.3.3 節(jié)點加入和退出2.4 CAN2.4.1 CAN的設(shè)計2.4.2 CAN的路由2.4.3 節(jié)點加入和退出2.5 Tapestry2.5.1 Tapestry的設(shè)計2.5.2 Tapestry的路由2.5.3 節(jié)點加入和退出2.6 本章小結(jié)第3章 利用拓撲信息改進DHT3.1 引言3.2 獲取位置信息3.2.1 分布式網(wǎng)絡(luò)測量技術(shù)3.2.2 IP地址蘊涵拓撲信息3.3具有層次化標識符的DHT3.3.1 Chord6的設(shè)計3.3.2 分析與仿真3.3.3 小結(jié)和進一步討論3.4 內(nèi)嵌式DHT3.4.1 eChord

29、的設(shè)計3.4.2 eChord的路由3.4.3 節(jié)點的加入和退出3.4.4 分析與仿真3.4.5 小結(jié)和進一步討論3.5層次化DHT3.5.1 hChord的設(shè)計3.5.2性能評估和進一步的討論3.5.3 結(jié)語和未來工作3.6 本章小結(jié)第4章 基于DHT的P2P系統(tǒng)設(shè)計與實現(xiàn)4.1 FSS64.1.1 設(shè)計目標4.1.2 系統(tǒng)結(jié)構(gòu)4.1.3 Chord6實現(xiàn)4.1.4 智能節(jié)點設(shè)計4.1.5 消息處理4.2 相關(guān)的研究4.2.1 CFS4.2.2 PAST4.2.3 OceanStore4.3 本章小結(jié)第5章 結(jié)束語攻讀碩士期間發(fā)表的論文致謝縮略語索引參考文獻第1章 序論1.1 P2P研究背景

30、正如摩爾定律所指，“每十八個月處理器性能提高一倍，而價格降低一半”，在個人計算機的計算性能和存儲容量得到極大提高的同時，計算機的低廉價格也讓其使用越來越廣泛。同時，隨著近年來計算機通信技術(shù)的飛速發(fā)展，大量的個人計算機接入Internet，從而導(dǎo)致Internet規(guī)模不斷擴大，Internet入網(wǎng)的主機數(shù)、上網(wǎng)的人數(shù)都在飛速增長。圖1.1給出的是從1991年到2004年Internet入網(wǎng)主機數(shù)的增長曲線【1】。圖1.2給出了在線用戶數(shù)統(tǒng)計【2】。圖1.1 1991年到2004年Internet主機數(shù)增長曲線【1】(單位：百萬)圖 1.2Internet全球在線用戶數(shù)變化趨勢【2】另外，接入In

31、ternet的設(shè)備也變的多樣化，不僅有大型機、PC機，而且有越來越多的像手機和PDA這樣具有計算能力的手持終端設(shè)備。很明顯，網(wǎng)絡(luò)邊緣分布著大量的計算和存儲資源。但是，在傳統(tǒng)的C/S (Client/Server, 客戶/服務(wù)器)模式下，這些資源沒有能夠得到很好的開發(fā)和利用。因而，如何有效地利用這些計算和存儲資源也隨之成為研究的熱點。P2P（Peer to Peer，對等網(wǎng)絡(luò)）技術(shù)出現(xiàn)的目的就是希望充分利用互聯(lián)網(wǎng)中所蘊含的潛在計算和存儲資源。1.2 什么是P2PP2P中文稱為對等網(wǎng)絡(luò)，是指分布式系統(tǒng)中的各個節(jié)點是邏輯對等的，與目前互連網(wǎng)上比較流行的C/S計算模型不同的是：P2P計算模型中不再區(qū)別

32、服務(wù)器以及客戶端，系統(tǒng)中的各個節(jié)點之間可以直接進行數(shù)據(jù)通信而不需要通過中間的服務(wù)器。也就是說，對等網(wǎng)絡(luò)中每個節(jié)點的地位是對等的，既可充當(dāng)服務(wù)器為其它節(jié)點服務(wù)，也可充當(dāng)客戶機消費其它節(jié)點提供的服務(wù)。如圖1.3所示，P2P構(gòu)建了一種完全分散式的網(wǎng)絡(luò)結(jié)構(gòu)，不同于C/S的集中模式。 圖1.3(a) C/S模式網(wǎng)絡(luò) 圖1.3(b) P2P模式網(wǎng)絡(luò)P2P大體又可分為兩種類型。一種是配置了管理服務(wù)器的混和型P2P，如圖1.4(a)所示。這里的服務(wù)器并不提供傳統(tǒng)的數(shù)據(jù)服務(wù)，它主要是對節(jié)點間的通信進行控制和管理，節(jié)點在服務(wù)器的幫助下相互之間進行數(shù)據(jù)通信。目前流行的P2P軟件如Napster【3】和BitTorr

33、ent【4】等基本上都屬于混和型P2P?；旌闲蚉2P易于導(dǎo)入用戶認證、安全、和計費功能，但是由于管理服務(wù)器的存在，仍然面臨著單點故障和擴展性問題。另一種則是不引入任何服務(wù)器的完全對等的純P2P結(jié)構(gòu)，如圖1.4(b)所示。純P2P完全是自組織的，節(jié)點之間直接進行數(shù)據(jù)交換。 圖1.4 (a) 混和型P2P架構(gòu) 圖1.4 (b) 純P2P架構(gòu)1.3 為什么需要P2PP2P技術(shù)引起人們的熱切關(guān)注起源于Napster，Gnutella【5】等P2P文件共享軟件的迅速推廣。這些應(yīng)用在滿足人們快速交換大容量數(shù)據(jù)的需求的同時，也使得研究人員意識到P2P技術(shù)具有的獨特優(yōu)勢，可以利用它來解決傳統(tǒng)C/S模式存在的弊

34、端。在傳統(tǒng)的C/S方式下，由服務(wù)器向眾多的客戶機提供服務(wù)，這樣做的潛在前提是：假定服務(wù)器擁有強大的處理能力、高速網(wǎng)絡(luò)接口和大容量的存儲空間；與此對應(yīng)，客戶機的處理能力通常被認為比較弱小，基本上只是一個高性能的I/O設(shè)備。然而，今天計算機和網(wǎng)絡(luò)的飛速發(fā)展使得上面的假設(shè)出現(xiàn)了問題。第一，如1.1節(jié)指出，作為客戶機的聯(lián)網(wǎng)主機和用戶數(shù)目都在飛速增長；同時，網(wǎng)絡(luò)中要存儲和處理的數(shù)據(jù)也極為驚人，例如Internet上每年產(chǎn)生的網(wǎng)頁數(shù)據(jù)高達21018字節(jié)【6】。這兩者都服務(wù)器提出了巨大的挑戰(zhàn)。無論服務(wù)器性能多么優(yōu)越，它的存儲容量都是有限的，硬盤讀寫速度和網(wǎng)絡(luò)接口都有一定的限制，CPU處理能力也只能滿足一定的

35、要求。隨著客戶機的增多，服務(wù)能力和質(zhì)量必然會下降。因而面對今天數(shù)目巨大的用戶以及海量信息處理要求，簡單的C/S模式已經(jīng)不能滿足需要。也就是說，服務(wù)器負載過重，可能會成為瓶頸。第二，作為客戶機的個人計算機存儲和計算能力大為增加，例如今天的主流PC機配置，CPU主頻大都達到12GHZ，內(nèi)存512M左右，硬盤動輒就是40G或80G，而LAN或?qū)拵ЬW(wǎng)絡(luò)接口都有10M或100M。用戶主機已經(jīng)不再是一個簡單的I/O設(shè)備，再加上網(wǎng)絡(luò)帶寬的提高，用戶之間完全有能力進行共享和協(xié)作。另外，隨著社會和網(wǎng)絡(luò)的發(fā)展，人們對數(shù)據(jù)存儲和傳輸、高性能計算等也有著迫切的需求，用戶希望直接交換信息和數(shù)據(jù)而不必經(jīng)由特定的服務(wù)器中轉(zhuǎn)

36、。然而，C/S模式無法利用客戶端的閑置資源，同時也增加了中轉(zhuǎn)服務(wù)成本，給用戶節(jié)點直接通信帶來了不便。P2P技術(shù)避免了C/S結(jié)構(gòu)帶來的單點失效和性能瓶頸等問題，它不依賴或盡可能不依賴中央服務(wù)器，使得每個參與節(jié)點既能作為服務(wù)器，也可成為客戶機。P2P技術(shù)的核心思想就是將網(wǎng)絡(luò)應(yīng)用的重心從中央服務(wù)器向網(wǎng)絡(luò)邊緣的終端設(shè)備擴散；這些終端設(shè)備可以是高性能計算機，可以是PC機，可以是手機，也可以是PDA等等。與C/S模式相比，P2P模式有以下一些主要優(yōu)點：（1） 信息在用戶節(jié)點間直接流動，高速、及時、方便，降低了中轉(zhuǎn)服務(wù)成本。（2） 資源的高度利用率。在P2P網(wǎng)絡(luò)上，閑散資源有機會得到利用，所有節(jié)點的資源總和

37、構(gòu)成了整個網(wǎng)絡(luò)的資源，整個網(wǎng)絡(luò)可以被用作具有海量存儲能力和巨大計算處理能力的超級計算機。（3） 隨著節(jié)點的增加，C/S模式下服務(wù)器的負載會越來越重，將成為系統(tǒng)的瓶頸和單一故障點。也就是說，一旦服務(wù)器崩潰，整個網(wǎng)絡(luò)也隨之癱瘓。而在P2P網(wǎng)絡(luò)中，每個節(jié)點都向網(wǎng)絡(luò)貢獻些資源，如存儲空間、CPU周期等。所以，對等節(jié)點越多，網(wǎng)絡(luò)的可靠性也就越高。（4） 基于內(nèi)容的尋址方式處于一個更高的語義層次，因為用戶在搜索時只需指定具有實際意義的信息標識而不是物理地址。這將創(chuàng)造一個更加精煉的信息倉庫和一個更加統(tǒng)一的資源標識方法。（5） C/S 模式下的互聯(lián)網(wǎng)是完全依賴于中心點 服務(wù)器的。沒有服務(wù)器，網(wǎng)絡(luò)就沒有任何意義

38、。而P2P 網(wǎng)絡(luò)中，即使只有一個對等點存在，網(wǎng)絡(luò)也是活動的，節(jié)點可以隨意地將自己的信息發(fā)布到網(wǎng)絡(luò)上。P2P模式的出現(xiàn)也使得Internet恢復(fù)了初始設(shè)計的面貌：Internet本身是跨越全球的一個非集中式結(jié)構(gòu)的系統(tǒng)，但是上世紀九十年代在Internet上建立的許多應(yīng)用系統(tǒng)都是完全集中式的，從而改變了Internet設(shè)計的初衷。網(wǎng)絡(luò)技術(shù)的飛速發(fā)展與迅速普及使Internet成為數(shù)據(jù)通信的重要手段，網(wǎng)絡(luò)的發(fā)展大大超出了網(wǎng)絡(luò)的提出者以及早期的建立者的構(gòu)想。網(wǎng)絡(luò)規(guī)模越來越大，連入網(wǎng)絡(luò)中的設(shè)備以及計算單元的數(shù)量和種類也越來越多，然而這些設(shè)備以及計算單元并沒有得到充分的利用，如果能夠?qū)⑦@些設(shè)備以及計算單元

39、的處理器計算能力、磁盤存儲能力以及網(wǎng)絡(luò)帶寬資源等進行充分利用將會有效緩解目前互聯(lián)網(wǎng)所面臨的一些問題。1.4 P2P的應(yīng)用領(lǐng)域P2P計算技術(shù)具有廣闊的應(yīng)用前景，主要應(yīng)用的領(lǐng)域包括：信息共享、實時通信、網(wǎng)絡(luò)游戲、金融服務(wù)、信息檢索、協(xié)同工作、普及計算和網(wǎng)絡(luò)存儲等。【7】1.4.1 信息共享信息共享一直是網(wǎng)絡(luò)技術(shù)發(fā)展的重要推動力，也是P2P技術(shù)中最典型的應(yīng)用。目前人們主要采用Web技術(shù)來實現(xiàn)信息資源共享，在基于Web的方式進行信息資源共享時，Web 服務(wù)器被用來對大量用戶的訪問提供有效的服務(wù)，因而也經(jīng)常成為這類系統(tǒng)的性能瓶頸所在。采用P2P技術(shù)來共享信息資源可以更加充分的利用網(wǎng)絡(luò)中的帶寬資源，從而提

40、高了系統(tǒng)數(shù)據(jù)通信的效率。目前有很多研究項目和應(yīng)用軟件都是針對P2P的文件共享的，包括Freenet【8】、Gnutella、Free Haven【9】、Ohaha【10】、BitTorrent、Kazza【11】、eDonkey【12】等。1.4.2 實時通信實時通信技術(shù)是網(wǎng)絡(luò)中重要的通信技術(shù)，成功的實時通信技術(shù)吸引了數(shù)以萬計的在線用戶。目前的實時通信技術(shù)一般采用一個中心服務(wù)器控制用戶的認證等基本信息，節(jié)點之間直接進行數(shù)據(jù)通信。ICQ、OICQ、AIM，MSN等是典型的實時通信系統(tǒng)，這些系統(tǒng)也包含好友列表等基本功能。目前流行的Skype是完全采用P2P技術(shù)的即時通信工具。Jabber【13】是

41、一個開放源碼的實時通信平臺。1.4.3 網(wǎng)絡(luò)游戲?qū)拵ЬW(wǎng)絡(luò)游戲?qū)τ趲挼南氖潜容^多的，通過P2P技術(shù)，一方面是可以下載游戲場景，另一方面可以省卻一些昂貴的游戲服務(wù)器。游戲用戶之間，可以直接通信，而不需要通過游戲服務(wù)器進行轉(zhuǎn)發(fā)。1.4.4 金融服務(wù)由于P2P的溝通只單純涉及溝通的雙方，不會有第三者知道雙方溝通的信息，所以P2P非常適合發(fā)展在線金融服務(wù)。美國的Billpoint公司已將P2P技術(shù)應(yīng)用于電子商務(wù)的付費機制，通過eBay（一個有名的在線拍賣網(wǎng)站）向全球35個國家的使用者提供了這種技術(shù)，他們可直接用彼此的信用卡進行交易；1.4.5 信息檢索搜索引擎是目前人們在網(wǎng)絡(luò)中檢索信息資源的主要工具

42、，目前的搜索引擎如：Google【14】、天網(wǎng)【15】等都是集中式的搜索引擎，人們在需要搜索信息的時候要向服務(wù)器發(fā)出指令，由服務(wù)器把檢索出來的相關(guān)目錄通過一定的排序法則呈現(xiàn)在用戶面前，這就會不可避免的帶來一些問題，比如：如果服務(wù)器信息更新周期長，將有大量過時的信息產(chǎn)生；如何服務(wù)器不加鑒別、只是一味的搜集信息，將帶來許多無價值的垃圾信息；受設(shè)備條件影響，服務(wù)器收集的信息有限；受服務(wù)器制約，存在單點失效的問題等。而P2P將以用戶為中心，所有的用戶都是平等的伙伴。所有人都共享了他們認為最有價值的東西，這將使互聯(lián)網(wǎng)上信息的價值得到極大的提升。JXTA Search【16】采用P2P的搜索技術(shù)來有效的跟

43、蹤數(shù)據(jù)的更新速度、提高訪問的有效性以及檢索的效率。Pandango【17】搜索引擎也利用了P2P的技術(shù)。1.4.6 協(xié)同工作協(xié)同工作是指多個用戶之間利用網(wǎng)絡(luò)中的協(xié)同計算平臺互相協(xié)同來共同完成計算任務(wù)。通過采用P2P計算技術(shù)個人和組織可以隨時采用各種方式建立在線、非在線的協(xié)同應(yīng)用環(huán)境。同工作使得在不同地點的參與者可以在一起工作，因為采用文件直接共享的方式可以保證系統(tǒng)中的每個人所獲得的信息總是最新的，同時節(jié)省了采用單獨服務(wù)器時對該服務(wù)器存儲以及性能的要求。Groove【18】是基于Internet的P2P協(xié)同應(yīng)用軟件的典型代表，其用戶可以直接進行實時的協(xié)同工作。1.4.7 普及計算普及計算技術(shù)研究

44、的是如何充分利用網(wǎng)絡(luò)中各種各樣的計算單元來共同完成大規(guī)模的計算任務(wù)。由于單一計算單元的計算能力總是有限的，因此人們一般采用并行技術(shù)、分布式技術(shù)將多個計算單元節(jié)點聯(lián)合起來共同完成大規(guī)模的計算任務(wù)，同時目前網(wǎng)絡(luò)中的計算機的計算能力一直利用的不是很充分，人們期望能夠充分利用網(wǎng)絡(luò)中的閑散計算能力來完成大規(guī)模的計算任務(wù)，這樣將會使得網(wǎng)絡(luò)中所蘊含的海量計算能力得到更加充分的利用。P2P計算技術(shù)則為普及計算技術(shù)的發(fā)展提供了新的機遇。SETIhome【19】是UC Berkeley大學(xué)啟動的普及計算的研究項目，目前大約吸引了一百萬臺計算機參與研究。GRID【20】是研究普及計算的典型代表。1.4.8 網(wǎng)絡(luò)存儲

45、存儲技術(shù)一直是人們所關(guān)注的一項技術(shù)。由于網(wǎng)絡(luò)規(guī)模的擴大，人們對網(wǎng)絡(luò)的使用也變得十分靈活，人們開始將傳統(tǒng)的分布式操作系統(tǒng)、局域存儲技術(shù)向基于Internet的文件存儲系統(tǒng)發(fā)展。一些研究項目開始使用基于DHT的P2P技術(shù)來組織和存儲文件，典型的系統(tǒng)包括：Oceanstore【21】、Farsite【22】等。這些項目的目標都是提供面向全球規(guī)模的文件存儲服務(wù)。1.5 如何實現(xiàn)P2P讓對等節(jié)點之間進行數(shù)據(jù)通信，本身不是難點，完全可以通過現(xiàn)有的網(wǎng)絡(luò)編程技術(shù)實現(xiàn)，而如何穿越NAT（Network Address Translater）和防火墻也只是一些技術(shù)細節(jié)問題。P2P實現(xiàn)的難點在于提供一種對網(wǎng)絡(luò)中的海

46、量數(shù)據(jù)進行高效并且可擴展的管理和檢索機制。也就是說，如何在龐大的共享數(shù)據(jù)海洋中有效而快速的查找到感興趣的文件或服務(wù)。依據(jù)文件的檢索模型和機制，現(xiàn)有的P2P實現(xiàn)可以分為三種類型。它們分別是：基于目錄服務(wù)器P2P，非結(jié)構(gòu)化P2P，和結(jié)構(gòu)化P2P。1.5.1 基于目錄服務(wù)器P2P這一類系統(tǒng)中設(shè)置目錄服務(wù)器，用于保存用戶節(jié)點的地址信息和該節(jié)點上共享文件的描述信息，文件本身是分散存貯在各個節(jié)點上的，實際的文件傳輸也是在對等節(jié)點之間進行，目錄服務(wù)器僅僅起到中介作用，為節(jié)點提供發(fā)布和查詢文件索引服務(wù)，是文件索引的集散地，即在請求服務(wù)節(jié)點和提供服務(wù)節(jié)點之間進行匹配。圖1.5 Napster系統(tǒng)結(jié)構(gòu)Napste

47、r是該類系統(tǒng)的典型代表，它的工作過程很簡單，如圖1.5所示：用戶連接到Napster服務(wù)器，向服務(wù)器遞交欲查找的音樂信息（如歌曲名）和自己的IP地址；然后由服務(wù)器查找其維護的索引信息庫，找到后把存有該音樂文件的其他用戶節(jié)點的IP地址返回給這個用戶；用戶依據(jù)這些IP地址，選擇從其中某些用戶主機上下載文件。如用戶想要共享本機上的某個音樂文件，只需向服務(wù)器登記該文件名和自己的IP地址等信息即可?；谀夸浄?wù)器的P2P系統(tǒng)在查找目錄的時候，簡單高效，但由于依賴集中式的目錄服務(wù)器，隨著用戶節(jié)點數(shù)目的增加，服務(wù)器將遭遇瓶頸問題，而且會成為系統(tǒng)的單一故障點，系統(tǒng)的可擴展性差。Napster也因為存在目錄服務(wù)

48、器才卷入了法律糾紛，面臨被關(guān)閉的處境。1.5.2 非結(jié)構(gòu)化P2P鑒于集中式目錄服務(wù)器不僅可能成為系統(tǒng)的瓶頸，而且還可能引發(fā)法律糾紛。以Gnutella（見圖1.6）為代表的非結(jié)構(gòu)化P2P系統(tǒng)中，文件索引信息不再由集中式的目錄服務(wù)器存儲和管理，而是分散到網(wǎng)絡(luò)中，由節(jié)點自己保存。該類系統(tǒng)采用分布式的索引查找策略。為了查找網(wǎng)絡(luò)中的文件，節(jié)點要隨機地維護網(wǎng)絡(luò)中的其他一些節(jié)點作為鄰居，以便通過鄰居節(jié)點廣播查詢報文。由于P2P網(wǎng)絡(luò)中存在大量的數(shù)據(jù)冗余，因而可以通過限制查詢報文的TTL值來使得泛洪僅僅發(fā)生在P2P網(wǎng)絡(luò)的局部。圖1.6 Gnutella系統(tǒng)結(jié)構(gòu)非結(jié)構(gòu)化P2P系統(tǒng)中由于不存在目錄服務(wù)器，所以沒有

49、單點瓶頸問題，不存在單一故障點。然而其缺點也是明顯的：在網(wǎng)絡(luò)中廣播查詢報文加重了網(wǎng)絡(luò)通信負擔(dān)，其查詢機制在系統(tǒng)規(guī)模擴大時不具有可擴展性。另外，由于查詢報文被限制在特定的范圍內(nèi)，所以并不能保證一定可以找到網(wǎng)絡(luò)中存在的目的數(shù)據(jù)。1.5.3 結(jié)構(gòu)化P2P上面介紹的兩類P2P系統(tǒng)都缺乏有效的、可擴展的索引查找機制。為此，近年來許多研究小組在設(shè)計可擴展的查找機制方面做了大量的研究工作，提出了Chord【23】、Pastry【24】、CAN【25】和Tapestry【26】等用于構(gòu)建結(jié)構(gòu)化P2P的分布式哈希表系統(tǒng)（Distributed Hash Table，DHT）。DHT的主要思想是：首先，每條文件索

50、引被表示成一個(K, V)對，K稱為關(guān)鍵字，可以是文件名（或文件的其他描述信息）的哈希值，V是實際存儲文件的節(jié)點的IP地址（或節(jié)點的其他描述信息）。所有的文件索引條目(即所有的（K, V）對)組成一張大的文件索引哈希表，只要輸入目標文件的K值，就可以從這張表中查出所有存儲該文件的節(jié)點地址。然后，再將上面的大文件哈希表分割成很多局部小塊，按照特定的規(guī)則把這些小塊的局部哈希表分布到系統(tǒng)中的所有參與節(jié)點上，使得每個節(jié)點負責(zé)維護其中的一塊。這樣，節(jié)點查詢文件時，只要把查詢報文路由到相應(yīng)的節(jié)點即可（該節(jié)點維護的哈希表分塊中含有要查找的(K,V)對）。這里面有個很重要的問題，就是節(jié)點要按照一定的規(guī)則來分割

51、整體的哈希表，進而也就決定了節(jié)點要維護特定的鄰居節(jié)點，以便路由能順利進行。這個規(guī)則因具體系統(tǒng)的不同而不同，CAN，Chord，Pastry和Tapestry都有自己的規(guī)則，也就呈現(xiàn)出不同的特性。本文將在第二章中介紹這幾種DHT系統(tǒng)。圖1.7 分布式哈希表圖1.7給出了一個分布式哈希表的示意圖，可以看到每個節(jié)點都維護了哈希表的一部分。DHT實際上是把網(wǎng)絡(luò)中所有的參與節(jié)點按特定的規(guī)則在應(yīng)用層重新進行組織，形成了一個結(jié)構(gòu)化的邏輯的重疊網(wǎng)絡(luò)（Overlay）。這類系統(tǒng)不存在單點瓶頸問題，因為每個節(jié)點除了既是客戶又是數(shù)據(jù)服務(wù)器外，還提供目錄服務(wù)器的功能。又因為鄰居節(jié)點是有目的有規(guī)則建立的，所以DHT不需

52、要在網(wǎng)絡(luò)中泛洪查詢報文，而是按照相應(yīng)的路由規(guī)則在系統(tǒng)中轉(zhuǎn)發(fā)報文。DHT在節(jié)點失效、遭受攻擊和突發(fā)性高負載面前都能表現(xiàn)出很好的健壯性；它具有良好的可擴展性，能以較低系統(tǒng)開銷獲得較大的系統(tǒng)規(guī)模；可以自我配置，不需要手工干預(yù)就可以自動把新加入節(jié)點合并到系統(tǒng)中；能提供簡單靈活的接口，可以為多個應(yīng)用同時使用。但是目前DHT還面臨許多問題，Sylvia Ratnasamy 等人在總結(jié)現(xiàn)有的DHT路由算法的基礎(chǔ)之上【27】提出了結(jié)構(gòu)化對等網(wǎng)絡(luò)面臨著十五個主要問題。其中指出提高DHT路由效率是基于DHT的P2P研究的重點，而P2P路由性能直接影響P2P應(yīng)用的推廣。本文將在第三章中介紹作者圍繞這個方向所做的工作

53、。1.6 本章小結(jié)本章首先介紹了P2P研究的背景，即聯(lián)網(wǎng)的主機數(shù)和用戶增加使得網(wǎng)絡(luò)邊緣分布了大量的潛在計算和存儲資源，P2P研究正是為了開發(fā)利用這些資源。接著討論了P2P的含義以及P2P研究的必要性，然后本章對P2P的主要應(yīng)用領(lǐng)域做了概要的介紹。最后，本章指出P2P研究的難點在于設(shè)計一種高效可擴展的數(shù)據(jù)檢索機制，并據(jù)此將現(xiàn)有的P2P實現(xiàn)分為基于目錄服務(wù)器P2P、非結(jié)構(gòu)化P2P和結(jié)構(gòu)化P2P三種類型進行介紹，并指出前兩種類型的查找機制不具有可擴展性，結(jié)構(gòu)化P2P才是發(fā)展的方向和當(dāng)前研究的熱點。第2章 DHT基本原理2.1 引言P2P網(wǎng)絡(luò)的參與節(jié)點可以是來自家庭、學(xué)校和公司的計算機或其他計算終端設(shè)

54、備，同時在線的用戶節(jié)點數(shù)目常常是成千上萬。因而，如何把這些分散在各處的廉價且不可靠的用戶節(jié)點有效地組織起來，設(shè)計一個健壯的可擴展的大規(guī)模分布式系統(tǒng)就成為P2P研究中最大的挑戰(zhàn)之一。在這個大規(guī)模的分布式系統(tǒng)中，如何不引入目錄服務(wù)器就能高效快速地找到指定的數(shù)據(jù)則是研究中的核心問題。因此，P2P網(wǎng)絡(luò)數(shù)據(jù)檢索模型和路由算法的研究具有重要的意義，目前國內(nèi)外很多研究人員圍繞這個問題進行了大量的研究，提出的基于分布式哈希表（DHT）的分布式檢索和路由算法因為具有查找可確定性、簡單性和分布性等優(yōu)點，正成為國際上結(jié)構(gòu)化P2P網(wǎng)絡(luò)研究和應(yīng)用的熱點。例如，自2002年起，美國國家科學(xué)基金會（NSF）提供了1200萬

55、美元的資金啟動了一個為期5年的研究項目IRIS【28】，該項目集中了MIT和UC Berkeley等5所著名高等院校的強大科研力量，為下一代大規(guī)模分布式應(yīng)用研制基于DHT的新型基礎(chǔ)設(shè)施。哈希表作為一種數(shù)據(jù)結(jié)構(gòu)，可以在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系，使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)。因而在查找時，只要根據(jù)這個對應(yīng)關(guān)系就可以找到給定關(guān)鍵字K的存儲位置。分布式哈希表，顧名思義就是把哈希表分散到P2P網(wǎng)絡(luò)的各個節(jié)點上，目的是在記錄的存儲節(jié)點和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系。這里的一條記錄就是一個文件索引，抽象成一個(K, V)對。也就是說給定一個K，就可以按照對

56、應(yīng)關(guān)系找到存儲有相應(yīng)(K, V)對的節(jié)點。從這個節(jié)點上取得文件索引(K, V)對后，再從V中讀出真正存儲文件的節(jié)點IP地址。分布式哈希表在節(jié)點失效、遭受攻擊和突發(fā)性高負載面前都能表現(xiàn)出很好的健壯性；它具有良好的可擴展性，能以較低系統(tǒng)開銷獲得較大的系統(tǒng)規(guī)模；可以自我配置，不需要手工干預(yù)就可以自動把新加入節(jié)點合并到系統(tǒng)中；能提供簡單靈活的接口，可以為多個P2P應(yīng)用同時使用。本章將介紹Chord、CAN（Content Addressable Network）、Pastry和Tapestry這幾種最為典型的分布式哈希表系統(tǒng)的原理。2.2 ChordChord【23】是UC Berkeley和MIT共

57、同提出的一種分布式查找算法，目的是為了能在P2P網(wǎng)絡(luò)中查找數(shù)據(jù)。給定一個關(guān)鍵字，Chord可以有效地把該關(guān)鍵字映射到網(wǎng)絡(luò)中某個節(jié)點上。因而在P2P網(wǎng)絡(luò)中只要給每個數(shù)據(jù)V都賦予一個關(guān)鍵字K，就可以利用Chord在該關(guān)鍵字映射的節(jié)點上存儲或提取相應(yīng)的(K, V)對。Chord的突出特點是算法簡單，而且可擴展 查詢過程的通信開銷和節(jié)點維護的狀態(tài)隨著系統(tǒng)總節(jié)點數(shù)增加成指數(shù)關(guān)系。Chord的路由性能優(yōu)于CAN，而節(jié)點加入過程和維護開銷又優(yōu)于Tapestry和Pastry。本文在第三章以Chord作為示例，介紹作者在改善DHT路由性能方面所做的工作。2.2.1 Chord的設(shè)計 Chord中每個關(guān)鍵字和節(jié)點都分別擁有一個m比特的標識符。關(guān)鍵字標識符K通過哈希關(guān)鍵字本身得到，而節(jié)點標識符N則通過哈希節(jié)點的IP地址得到。哈希函數(shù)可以選用SHA-1【29】。所有節(jié)點按照其節(jié)點標識符從小到大（取模2m后）沿著順時針方向排列在一個邏輯的標識圓環(huán)上（稱為Chord環(huán)）。Chord的映射規(guī)則是：關(guān)鍵字標識為K的(K, V)對存儲在這樣的節(jié)點上，該節(jié)點的節(jié)點標識等于K或者在Chord環(huán)上緊跟在K之后，這