P2P基礎(chǔ)知識簡介

P2P基礎(chǔ)知識簡介李振華在讀博士北京大學計算機系網(wǎng)絡(luò)所P2P組Homepage:/~p2p提綱1P2P是什么？2P2P歷史（工業(yè)界）3P2P歷史（學術(shù)界）4國內(nèi)科研情況5AmazingStore系統(tǒng)簡介6基礎(chǔ)實驗平臺簡介7上機作業(yè)1P2P是什么？網(wǎng)上眾說紛紜……我們的看法：1、一種思想2、一種工具3、一類應用1.1一種思想計算機網(wǎng)絡(luò)

因特網(wǎng)Internet網(wǎng)絡(luò)的基礎(chǔ)結(jié)構(gòu)：1、集中式：C/S=Client/Server

--好：管理簡單，控制有效 --壞：Server瓶頸2、分布式：Distributed

--好：無瓶頸，資源充分利用 --壞：管理松散，難于控制

P2P=分布式的極端（since1956年）自由平等互聯(lián)1.2一種工具Peer-to-Peer一切網(wǎng)絡(luò)皆可P2P化！But……1.3一類應用文件共享媒體播放數(shù)據(jù)存儲分布計算等2P2P的歷史（工業(yè)界）2.1溯源：Napster --1999年，18歲的美國學生ShawnFanning --宿舍開發(fā)，朋友共享mp3

--半年5000萬用戶！

--2001年，版權(quán)糾紛，被迫關(guān)閉1999-2009，P2P十年……Napster運行原理2.2Gnutella2000年3月，Nullsoft公司JustinFrankel

&TomPepper:Winamp發(fā)明人版權(quán)問題

上線一個半小時關(guān)閉無結(jié)構(gòu)P2P系統(tǒng)代表其思想和代碼被多出復制、改寫、繼承Gnutella運行原理、洪泛問題2.3KaZaa/Skype,eDonkey/eMule2009年7月，KaZaaNiklas&Friis300萬在線用戶！Niklas繼續(xù)創(chuàng)辦Skype2000年，eDonkey2002年，Merkur改良eDonkey

eMule國內(nèi)VeryCD層次化無結(jié)構(gòu)P2P系統(tǒng)2.4BT2002年10月BramCohen窮困潦倒……

企業(yè)家Gilmore資助生活費2003年BitTorrent流行

BramCohen依然窮困潦倒

2003年末找到工作！2.5PPLive,PPS,UUSee2003年，中國PPLive：姚欣（華中科大本科）PPStream：張洪禹（哈爾濱師大本科）+雷量（成都一程序員）UUSee：李竹（清華本科）+劉懷宇（清華碩士）2.6迅雷，QQ旋風迅雷2003年，深圳鄒勝龍（硅谷海歸）+程浩（硅谷海歸）中國最大的互聯(lián)網(wǎng)資源聚合平臺QQ旋風2007年，上海騰訊研究院No.2互聯(lián)網(wǎng)資源聚合平臺Relaxation1“出名要趁早啊，來得太晚的話，快樂也不那么痛快?！?——張愛玲房子、車子、妻子、孩子、……互聯(lián)網(wǎng)是造就青年英雄的園地！3P2P歷史（學術(shù)界）3.1O’reilly的P2P峰會 --2000年8月，O’reilly組織P2P峰會 --澄清P2P的理念，消除P2P恐懼 --2001年，O’reilly出版最早的P2P專著3.2四大結(jié)構(gòu)化模型2001年，SIGCOMM（網(wǎng)絡(luò)通信頂尖會議） --Chord:IonStoica等（Berkeley、MIT） --CAN:Ratnasamy等（Berkeley、AT&T）2001年，其它兩個模型 --Pastry:Rowstron等（微軟、Rice） --Tapestry:趙燕斌等（Berkeley）結(jié)構(gòu)化P2P系統(tǒng) =DHT(DistributedHashTable)

Chord前傳：環(huán)形數(shù)組/鏈表環(huán)形數(shù)組路由？

--二分查找 --O(logN)跳環(huán)形鏈表路由？

--二分查找NO！如何O(logN)？

--帶弦環(huán)

=路由表（網(wǎng)絡(luò)）Chord介紹1Chord：最簡單、最精確拓撲結(jié)構(gòu)：帶弦環(huán)功能：

--節(jié)點/數(shù)據(jù)對象映射到拓撲網(wǎng)絡(luò)中映射方法：

--節(jié)點ID=Hash(IP,port) --數(shù)據(jù)ID=Hash(Value) --節(jié)點按ID順時針排列 --節(jié)點后繼vs對象后繼匿名、虛節(jié)點路由表（fingertable） --指數(shù)距離：1、2、4、8、…、2^m --m項，m為節(jié)點ID比特數(shù)Chord介紹2Chord介紹3路由： --二分查找，由遠及近 --定位節(jié)點/數(shù)據(jù)對象平均路由跳數(shù)O(logN) --思考題1：為什么是O(logN)而不是O(m)？ --思考題2：平均跳數(shù)是(logN)/2，為什么？DHTDHT（分布式散列表）3.3常數(shù)度結(jié)構(gòu)化模型

常數(shù)度：每個節(jié)點有常數(shù)條邊Viceroy：蝴蝶結(jié)構(gòu)Koorde：Chord+德布羅意圖Cycloid：3維CCC3.4結(jié)構(gòu)化P2P的特點1、節(jié)點度為常數(shù)或O(logN)2、數(shù)據(jù)對象存放位置確定（hash）3、定位對象的路由跳數(shù)為O(logN)4、結(jié)構(gòu)嚴格，維護開銷大迄今為止，除Kademlia模型在BT、eMule中輔助使用外，沒有實用的結(jié)構(gòu)化P2P模型

但是，結(jié)構(gòu)化P2P的思想被用在服務器集群、云計算等領(lǐng)域，取得了不錯的效果

3.5專著

4國內(nèi)科研情況

北京大學網(wǎng)絡(luò)所--Maze共享、AmazingStore存儲華中科大網(wǎng)格實驗室--AnySee視頻直播清華大學高性能所、多媒體所--Granary存儲、GridMedia視頻直播Relaxation2P2P科研領(lǐng)域目前的境況：--美國學者——引領(lǐng)、挖坑--中國學者——跟蹤、灌水為什么？——找祖宗、2000年怎么辦？——沒辦法“牢騷太盛防腸斷，欲望太強睡不著?！?AmazingStore系統(tǒng)簡介P2P共享+P2P存儲教育網(wǎng)網(wǎng)址：amazingstore.兼容Maze資源開發(fā)小組：代亞非教授，蘇冰/周模/丁嵩/董嵬/肖鋒/陳馳/曲直在線用戶突破800優(yōu)良的P2P科研試驗平臺

5.1AmazingStore6大功能1、熱門資源推薦 2、所有資源搜索 3、對等節(jié)點瀏覽4、經(jīng)典資源收藏 5、P2P網(wǎng)絡(luò)硬盤 6、開發(fā)中……基礎(chǔ)實驗平臺簡介1、最好的平臺：自己搭建系統(tǒng)

--自由修改，數(shù)據(jù)齊全，適合研究2、較好的平臺：利用現(xiàn)有系統(tǒng)

--如QQ旋風、AmazingStore等3、公認的平臺：PlanetLabP2P研究者居家必備之良藥！（北大已加入）基礎(chǔ)實驗平臺簡介24、湊合的平臺：自己寫代碼模擬

--靈活方便，簡單易行，但不具有說服力5、最不好的平臺：用他人寫的模擬器

--手到擒來，但自由度太小，極易受他人置疑 --MIT:p2psim,Trento:PeerSim,GaTech:GnutellaSim,3LS基礎(chǔ)實驗平臺簡介3推薦實驗方式：4、自己寫代碼模擬

--Java或C#，面向?qū)ο髮崿F(xiàn)，單線程 --1個Monitor對象+N個Node對象 --Monitor對象記錄所有運行數(shù)據(jù) --Node對象屬性：物理地址，ID，路由表，鄰居表等 --Node對象方法：定位對象、傳遞路由消息等 --網(wǎng)絡(luò)拓撲結(jié)構(gòu)：GT-ITM、BRITE拓撲發(fā)生器、真實數(shù)據(jù)

--權(quán)宜之計，發(fā)不了一流論文！上機作業(yè)使用任意實驗方式模擬Chord網(wǎng)絡(luò)（單機）

--算法偽代碼均在Chord原始論文中 --節(jié)點IP、port及數(shù)據(jù)對象Value隨機生成 --節(jié)點/數(shù)據(jù)對象ID產(chǎn)生可使用任意Hash函數(shù)（SHA、MD5在Java、C#類庫中有） --節(jié)點順序加入，不考慮并行 --路由表構(gòu)造（Table1）、路由算法實現(xiàn)（Figure4）參照原始論文 --僅處理節(jié)點加入（Figure6），不處理節(jié)點退出、意外 --需要處理節(jié)點加入時數(shù)據(jù)對象的移交（Figure6）

上機作業(yè)（