【文章內(nèi)容簡介】 攻讀碩士期間發(fā)表的論文 ４７致謝 ４８縮略語索引 ４９參考文獻(xiàn) ５０中國科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 第1章 序論第1章 序論 P2P研究背景正如摩爾定律所指，“每十八個(gè)月處理器性能提高一倍，而價(jià)格降低一半”，在個(gè)人計(jì)算機(jī)的計(jì)算性能和存儲容量得到極大提高的同時(shí)，計(jì)算機(jī)的低廉價(jià)格也讓其使用越來越廣泛。同時(shí)，隨著近年來計(jì)算機(jī)通信技術(shù)的飛速發(fā)展，大量的個(gè)人計(jì)算機(jī)接入Internet，從而導(dǎo)致Internet規(guī)模不斷擴(kuò)大，Internet入網(wǎng)的主機(jī)數(shù)、上網(wǎng)的人數(shù)都在飛速增長。【1】?！?】。 1991年到2004年Internet主機(jī)數(shù)增長曲線【1】(單位：百萬)圖 Internet全球在線用戶數(shù)變化趨勢【2】另外，接入Internet的設(shè)備也變的多樣化，不僅有大型機(jī)、PC機(jī)，而且有越來越多的像手機(jī)和PDA這樣具有計(jì)算能力的手持終端設(shè)備。很明顯，網(wǎng)絡(luò)邊緣分布著大量的計(jì)算和存儲資源。但是，在傳統(tǒng)的C/S (Client/Server, 客戶/服務(wù)器)模式下，這些資源沒有能夠得到很好的開發(fā)和利用。因而，如何有效地利用這些計(jì)算和存儲資源也隨之成為研究的熱點(diǎn)。P2P（Peer to Peer，對等網(wǎng)絡(luò)）技術(shù)出現(xiàn)的目的就是希望充分利用互聯(lián)網(wǎng)中所蘊(yùn)含的潛在計(jì)算和存儲資源。 什么是P2PP2P中文稱為對等網(wǎng)絡(luò)，是指分布式系統(tǒng)中的各個(gè)節(jié)點(diǎn)是邏輯對等的，與目前互連網(wǎng)上比較流行的C/S計(jì)算模型不同的是：P2P計(jì)算模型中不再區(qū)別服務(wù)器以及客戶端，系統(tǒng)中的各個(gè)節(jié)點(diǎn)之間可以直接進(jìn)行數(shù)據(jù)通信而不需要通過中間的服務(wù)器。也就是說，對等網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的地位是對等的，既可充當(dāng)服務(wù)器為其它節(jié)點(diǎn)服務(wù)，也可充當(dāng)客戶機(jī)消費(fèi)其它節(jié)點(diǎn)提供的服務(wù)。，P2P構(gòu)建了一種完全分散式的網(wǎng)絡(luò)結(jié)構(gòu)，不同于C/S的集中模式。 (a) C/S模式網(wǎng)絡(luò) (b) P2P模式網(wǎng)絡(luò)P2P大體又可分為兩種類型。一種是配置了管理服務(wù)器的混和型P2P，(a)所示。這里的服務(wù)器并不提供傳統(tǒng)的數(shù)據(jù)服務(wù)，它主要是對節(jié)點(diǎn)間的通信進(jìn)行控制和管理，節(jié)點(diǎn)在服務(wù)器的幫助下相互之間進(jìn)行數(shù)據(jù)通信。目前流行的P2P軟件如Napster【3】和BitTorrent【4】等基本上都屬于混和型P2P。混合型P2P易于導(dǎo)入用戶認(rèn)證、安全、和計(jì)費(fèi)功能，但是由于管理服務(wù)器的存在，仍然面臨著單點(diǎn)故障和擴(kuò)展性問題。另一種則是不引入任何服務(wù)器的完全對等的純P2P結(jié)構(gòu)，(b)所示。純P2P完全是自組織的，節(jié)點(diǎn)之間直接進(jìn)行數(shù)據(jù)交換。 (a) 混和型P2P架構(gòu) (b) 純P2P架構(gòu) 為什么需要P2PP2P技術(shù)引起人們的熱切關(guān)注起源于Napster，Gnutella【5】等P2P文件共享軟件的迅速推廣。這些應(yīng)用在滿足人們快速交換大容量數(shù)據(jù)的需求的同時(shí)，也使得研究人員意識到P2P技術(shù)具有的獨(dú)特優(yōu)勢，可以利用它來解決傳統(tǒng)C/S模式存在的弊端。在傳統(tǒng)的C/S方式下，由服務(wù)器向眾多的客戶機(jī)提供服務(wù)，這樣做的潛在前提是：假定服務(wù)器擁有強(qiáng)大的處理能力、高速網(wǎng)絡(luò)接口和大容量的存儲空間；與此對應(yīng)，客戶機(jī)的處理能力通常被認(rèn)為比較弱小，基本上只是一個(gè)高性能的I/O設(shè)備。然而，今天計(jì)算機(jī)和網(wǎng)絡(luò)的飛速發(fā)展使得上面的假設(shè)出現(xiàn)了問題。第一，作為客戶機(jī)的聯(lián)網(wǎng)主機(jī)和用戶數(shù)目都在飛速增長；同時(shí)，網(wǎng)絡(luò)中要存儲和處理的數(shù)據(jù)也極為驚人，例如Internet上每年產(chǎn)生的網(wǎng)頁數(shù)據(jù)高達(dá)21018字節(jié)【6】。這兩者都服務(wù)器提出了巨大的挑戰(zhàn)。無論服務(wù)器性能多么優(yōu)越，它的存儲容量都是有限的，硬盤讀寫速度和網(wǎng)絡(luò)接口都有一定的限制，CPU處理能力也只能滿足一定的要求。隨著客戶機(jī)的增多，服務(wù)能力和質(zhì)量必然會下降。因而面對今天數(shù)目巨大的用戶以及海量信息處理要求，簡單的C/S模式已經(jīng)不能滿足需要。也就是說，服務(wù)器負(fù)載過重，可能會成為瓶頸。第二，作為客戶機(jī)的個(gè)人計(jì)算機(jī)存儲和計(jì)算能力大為增加，例如今天的主流PC機(jī)配置，CPU主頻大都達(dá)到1－2GHZ，內(nèi)存512M左右，硬盤動(dòng)輒就是40G或80G，而LAN或?qū)拵ЬW(wǎng)絡(luò)接口都有10M或100M。用戶主機(jī)已經(jīng)不再是一個(gè)簡單的I/O設(shè)備，再加上網(wǎng)絡(luò)帶寬的提高，用戶之間完全有能力進(jìn)行共享和協(xié)作。另外，隨著社會和網(wǎng)絡(luò)的發(fā)展，人們對數(shù)據(jù)存儲和傳輸、高性能計(jì)算等也有著迫切的需求，用戶希望直接交換信息和數(shù)據(jù)而不必經(jīng)由特定的服務(wù)器中轉(zhuǎn)。然而，C/S模式無法利用客戶端的閑置資源，同時(shí)也增加了中轉(zhuǎn)服務(wù)成本，給用戶節(jié)點(diǎn)直接通信帶來了不便。P2P技術(shù)避免了C/S結(jié)構(gòu)帶來的單點(diǎn)失效和性能瓶頸等問題，它不依賴或盡可能不依賴中央服務(wù)器，使得每個(gè)參與節(jié)點(diǎn)既能作為服務(wù)器，也可成為客戶機(jī)。P2P技術(shù)的核心思想就是將網(wǎng)絡(luò)應(yīng)用的重心從中央服務(wù)器向網(wǎng)絡(luò)邊緣的終端設(shè)備擴(kuò)散；這些終端設(shè)備可以是高性能計(jì)算機(jī)，可以是PC機(jī)，可以是手機(jī)，也可以是PDA等等。與C/S模式相比，P2P模式有以下一些主要優(yōu)點(diǎn)：（1） 信息在用戶節(jié)點(diǎn)間直接流動(dòng)，高速、及時(shí)、方便，降低了中轉(zhuǎn)服務(wù)成本。（2） 資源的高度利用率。在P2P網(wǎng)絡(luò)上，閑散資源有機(jī)會得到利用，所有節(jié)點(diǎn)的資源總和構(gòu)成了整個(gè)網(wǎng)絡(luò)的資源，整個(gè)網(wǎng)絡(luò)可以被用作具有海量存儲能力和巨大計(jì)算處理能力的超級計(jì)算機(jī)。（3） 隨著節(jié)點(diǎn)的增加，C/S模式下服務(wù)器的負(fù)載會越來越重，將成為系統(tǒng)的瓶頸和單一故障點(diǎn)。也就是說，一旦服務(wù)器崩潰，整個(gè)網(wǎng)絡(luò)也隨之癱瘓。而在P2P網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都向網(wǎng)絡(luò)貢獻(xiàn)些資源，如存儲空間、CPU周期等。所以，對等節(jié)點(diǎn)越多，網(wǎng)絡(luò)的可靠性也就越高。（4） 基于內(nèi)容的尋址方式處于一個(gè)更高的語義層次，因?yàn)橛脩粼谒阉鲿r(shí)只需指定具有實(shí)際意義的信息標(biāo)識而不是物理地址。這將創(chuàng)造一個(gè)更加精煉的信息倉庫和一個(gè)更加統(tǒng)一的資源標(biāo)識方法。（5） C/S 模式下的互聯(lián)網(wǎng)是完全依賴于中心點(diǎn) — 服務(wù)器的。沒有服務(wù)器，網(wǎng)絡(luò)就沒有任何意義。而P2P 網(wǎng)絡(luò)中，即使只有一個(gè)對等點(diǎn)存在，網(wǎng)絡(luò)也是活動(dòng)的，節(jié)點(diǎn)可以隨意地將自己的信息發(fā)布到網(wǎng)絡(luò)上。P2P模式的出現(xiàn)也使得Internet恢復(fù)了初始設(shè)計(jì)的面貌：Internet本身是跨越全球的一個(gè)非集中式結(jié)構(gòu)的系統(tǒng)，但是上世紀(jì)九十年代在Internet上建立的許多應(yīng)用系統(tǒng)都是完全集中式的，從而改變了Internet設(shè)計(jì)的初衷。網(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è)備以及計(jì)算單元的數(shù)量和種類也越來越多，然而這些設(shè)備以及計(jì)算單元并沒有得到充分的利用，如果能夠?qū)⑦@些設(shè)備以及計(jì)算單元的處理器計(jì)算能力、磁盤存儲能力以及網(wǎng)絡(luò)帶寬資源等進(jìn)行充分利用將會有效緩解目前互聯(lián)網(wǎng)所面臨的一些問題。 P2P的應(yīng)用領(lǐng)域P2P計(jì)算技術(shù)具有廣闊的應(yīng)用前景，主要應(yīng)用的領(lǐng)域包括：信息共享、實(shí)時(shí)通信、網(wǎng)絡(luò)游戲、金融服務(wù)、信息檢索、協(xié)同工作、普及計(jì)算和網(wǎng)絡(luò)存儲等?！?】 信息共享信息共享一直是網(wǎng)絡(luò)技術(shù)發(fā)展的重要推動(dòng)力，也是P2P技術(shù)中最典型的應(yīng)用。目前人們主要采用Web技術(shù)來實(shí)現(xiàn)信息資源共享，在基于Web的方式進(jìn)行信息資源共享時(shí)，Web 服務(wù)器被用來對大量用戶的訪問提供有效的服務(wù)，因而也經(jīng)常成為這類系統(tǒng)的性能瓶頸所在。采用P2P技術(shù)來共享信息資源可以更加充分的利用網(wǎng)絡(luò)中的帶寬資源，從而提高了系統(tǒng)數(shù)據(jù)通信的效率。目前有很多研究項(xiàng)目和應(yīng)用軟件都是針對P2P的文件共享的，包括Freenet【8】、Gnutella、Free Haven【9】、Ohaha【10】、BitTorrent、Kazza【11】、eDonkey【12】等。 實(shí)時(shí)通信實(shí)時(shí)通信技術(shù)是網(wǎng)絡(luò)中重要的通信技術(shù)，成功的實(shí)時(shí)通信技術(shù)吸引了數(shù)以萬計(jì)的在線用戶。目前的實(shí)時(shí)通信技術(shù)一般采用一個(gè)中心服務(wù)器控制用戶的認(rèn)證等基本信息，節(jié)點(diǎn)之間直接進(jìn)行數(shù)據(jù)通信。ICQ、OICQ、AIM，MSN等是典型的實(shí)時(shí)通信系統(tǒng)，這些系統(tǒng)也包含好友列表等基本功能。目前流行的Skype是完全采用P2P技術(shù)的即時(shí)通信工具。Jabber【13】是一個(gè)開放源碼的實(shí)時(shí)通信平臺。 網(wǎng)絡(luò)游戲?qū)拵ЬW(wǎng)絡(luò)游戲?qū)τ趲挼南氖潜容^多的，通過P2P技術(shù)，一方面是可以下載游戲場景，另一方面可以省卻一些昂貴的游戲服務(wù)器。游戲用戶之間，可以直接通信，而不需要通過游戲服務(wù)器進(jìn)行轉(zhuǎn)發(fā)。 金融服務(wù)由于P2P的溝通只單純涉及溝通的雙方，不會有第三者知道雙方溝通的信息，所以P2P非常適合發(fā)展在線金融服務(wù)。美國的Billpoint公司已將P2P技術(shù)應(yīng)用于電子商務(wù)的付費(fèi)機(jī)制，通過eBay（一個(gè)有名的在線拍賣網(wǎng)站）向全球35個(gè)國家的使用者提供了這種技術(shù)，他們可直接用彼此的信用卡進(jìn)行交易； 信息檢索搜索引擎是目前人們在網(wǎng)絡(luò)中檢索信息資源的主要工具，目前的搜索引擎如：Google【14】、天網(wǎng)【15】等都是集中式的搜索引擎，人們在需要搜索信息的時(shí)候要向服務(wù)器發(fā)出指令，由服務(wù)器把檢索出來的相關(guān)目錄通過一定的排序法則呈現(xiàn)在用戶面前，這就會不可避免的帶來一些問題，比如：如果服務(wù)器信息更新周期長，將有大量過時(shí)的信息產(chǎn)生；如何服務(wù)器不加鑒別、只是一味的搜集信息，將帶來許多無價(jià)值的垃圾信息；受設(shè)備條件影響，服務(wù)器收集的信息有限；受服務(wù)器制約，存在單點(diǎn)失效的問題等。而P2P將以用戶為中心，所有的用戶都是平等的伙伴。所有人都共享了他們認(rèn)為最有價(jià)值的東西，這將使互聯(lián)網(wǎng)上信息的價(jià)值得到極大的提升。JXTA Search【16】采用P2P的搜索技術(shù)來有效的跟蹤數(shù)據(jù)的更新速度、提高訪問的有效性以及檢索的效率。Pandango【17】搜索引擎也利用了P2P的技術(shù)。 協(xié)同工作協(xié)同工作是指多個(gè)用戶之間利用網(wǎng)絡(luò)中的協(xié)同計(jì)算平臺互相協(xié)同來共同完成計(jì)算任務(wù)。通過采用P2P計(jì)算技術(shù)個(gè)人和組織可以隨時(shí)采用各種方式建立在線、非在線的協(xié)同應(yīng)用環(huán)境。同工作使得在不同地點(diǎn)的參與者可以在一起工作，因?yàn)椴捎梦募苯庸蚕淼姆绞娇梢员ＷC系統(tǒng)中的每個(gè)人所獲得的信息總是最新的，同時(shí)節(jié)省了采用單獨(dú)服務(wù)器時(shí)對該服務(wù)器存儲以及性能的要求。Groove【18】是基于Internet的P2P協(xié)同應(yīng)用軟件的典型代表，其用戶可以直接進(jìn)行實(shí)時(shí)的協(xié)同工作。 普及計(jì)算普及計(jì)算技術(shù)研究的是如何充分利用網(wǎng)絡(luò)中各種各樣的計(jì)算單元來共同完成大規(guī)模的計(jì)算任務(wù)。由于單一計(jì)算單元的計(jì)算能力總是有限的，因此人們一般采用并行技術(shù)、分布式技術(shù)將多個(gè)計(jì)算單元節(jié)點(diǎn)聯(lián)合起來共同完成大規(guī)模的計(jì)算任務(wù)，同時(shí)目前網(wǎng)絡(luò)中的計(jì)算機(jī)的計(jì)算能力一直利用的不是很充分，人們期望能夠充分利用網(wǎng)絡(luò)中的閑散計(jì)算能力來完成大規(guī)模的計(jì)算任務(wù)，這樣將會使得網(wǎng)絡(luò)中所蘊(yùn)含的海量計(jì)算能力得到更加充分的利用。P2P計(jì)算技術(shù)則為普及計(jì)算技術(shù)的發(fā)展提供了新的機(jī)遇。SETI@home【19】是UC Berkeley大學(xué)啟動(dòng)的普及計(jì)算的研究項(xiàng)目，目前大約吸引了一百萬臺計(jì)算機(jī)參與研究。GRID【20】是研究普及計(jì)算的典型代表。 網(wǎng)絡(luò)存儲存儲技術(shù)一直是人們所關(guān)注的一項(xiàng)技術(shù)。由于網(wǎng)絡(luò)規(guī)模的擴(kuò)大，人們對網(wǎng)絡(luò)的使用也變得十分靈活，人們開始將傳統(tǒng)的分布式操作系統(tǒng)、局域存儲技術(shù)向基于Internet的文件存儲系統(tǒng)發(fā)展。一些研究項(xiàng)目開始使用基于DHT的P2P技術(shù)來組織和存儲文件，典型的系統(tǒng)包括：Oceanstore【21】、Farsite【22】等。這些項(xiàng)目的目標(biāo)都是提供面向全球規(guī)模的文件存儲服務(wù)。 如何實(shí)現(xiàn)P2P讓對等節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)通信，本身不是難點(diǎn)，完全可以通過現(xiàn)有的網(wǎng)絡(luò)編程技術(shù)實(shí)現(xiàn)，而如何穿越NAT（Network Address Translater）和防火墻也只是一些技術(shù)細(xì)節(jié)問題。P2P實(shí)現(xiàn)的難點(diǎn)在于提供一種對網(wǎng)絡(luò)中的海量數(shù)據(jù)進(jìn)行高效并且可擴(kuò)展的管理和檢索機(jī)制。也就是說，如何在龐大的共享數(shù)據(jù)海洋中有效而快速的查找到感興趣的文件或服務(wù)。依據(jù)文件的檢索模型和機(jī)制，現(xiàn)有的P2P實(shí)現(xiàn)可以分為三種類型。它們分別是：基于目錄服務(wù)器P2P，非結(jié)構(gòu)化P2P，和結(jié)構(gòu)化P2P。 基于目錄服務(wù)器P2P這一類系統(tǒng)中設(shè)置目錄服務(wù)器，用于保存用戶節(jié)點(diǎn)的地址信息和該節(jié)點(diǎn)上共享文件的描述信息，文件本身是分散存貯在各個(gè)節(jié)點(diǎn)上的，實(shí)際的文件傳輸也是在對等節(jié)點(diǎn)之間進(jìn)行，目錄服務(wù)器僅僅起到中介作用，為節(jié)點(diǎn)提供發(fā)布和查詢文件索引服務(wù)，是文件索引的集散地，即在請求服務(wù)節(jié)點(diǎn)和提供服務(wù)節(jié)點(diǎn)之間進(jìn)行匹配。 Napster系統(tǒng)結(jié)構(gòu)Napster是該類系統(tǒng)的典型代表，它的工作過程很簡單，：用戶連接到Napster服務(wù)器，向服務(wù)器遞交欲查找的音樂信息（如歌曲名）和自己的IP地址；然后由服務(wù)器查找其維護(hù)的索引信息庫，找到后把存有該音樂文件的其他用戶節(jié)點(diǎn)的IP地址返回給這個(gè)用戶；用戶依據(jù)這些IP地址，選擇從其中某些用戶主機(jī)上下載文件。如用戶想要共享本機(jī)上的某個(gè)音樂文件，只需向服務(wù)器登記該文件名和自己的IP地址等信息即可。基于目錄服務(wù)器的P2P系統(tǒng)在查找目錄的時(shí)候，簡單高效，但由于依賴集中式的目錄服務(wù)器，隨著用戶節(jié)點(diǎn)數(shù)目的增加，服務(wù)器將遭遇瓶頸問題，而且會成為系統(tǒng)的單一故障點(diǎn)，系統(tǒng)的可擴(kuò)展性差。Napster也因?yàn)榇嬖谀夸浄?wù)器才卷入了法律糾紛，面臨被關(guān)閉的處境。 非結(jié)構(gòu)化P2P鑒于集中式目錄服務(wù)器不僅可能成為系統(tǒng)的瓶頸，而且還可能引發(fā)法律糾紛。以Gnutella（）為代表的非結(jié)構(gòu)化P2P系統(tǒng)中，文件索引信息不再由集中式的目錄服務(wù)器存儲和管理，而是分散到網(wǎng)絡(luò)中，由節(jié)點(diǎn)自己保存。該類系統(tǒng)采用分布式的索引查找策略。為了查找網(wǎng)絡(luò)中的文件，節(jié)點(diǎn)要隨機(jī)地維護(hù)網(wǎng)絡(luò)中的其他一些節(jié)點(diǎn)作為鄰居，以便通過鄰居節(jié)點(diǎn)廣播查詢報(bào)文。由于P2P網(wǎng)絡(luò)中存在大量的數(shù)據(jù)冗余，因而可以通過限制查詢報(bào)文的TTL值來使得泛洪僅僅發(fā)生在P2P網(wǎng)絡(luò)的局部。 Gnutella系統(tǒng)結(jié)構(gòu)非結(jié)構(gòu)化P2P系統(tǒng)中由于不存在目錄服務(wù)器，所以沒有單點(diǎn)瓶頸問題，不存在單一故障點(diǎn)。然而其缺點(diǎn)也是明顯的：在網(wǎng)絡(luò)中廣播查詢報(bào)文加重了網(wǎng)絡(luò)通信負(fù)擔(dān)，其查詢機(jī)制在系統(tǒng)規(guī)模擴(kuò)大時(shí)不具有可擴(kuò)展性。另外，由于查詢報(bào)文被限制在特定的范圍內(nèi)，所以并不能保證一定可以找到網(wǎng)絡(luò)中存在的目的數(shù)據(jù)。 結(jié)構(gòu)化P2P上面介紹的兩類P2P系統(tǒng)都缺乏有效的、可擴(kuò)展的索引查找機(jī)制。為此，近年來許多研究小組