中国计算机学会学术著作丛书：《对等网络——结构、应用与设计 Peer-to-Peer Network Structure, Application and Design》PDF电子书（正文，共九章）

第 章 P2P网络简介 1.1什么是P2P网络？ 计算机是20世纪人类最伟大的发明之一，它的出现改变 了人类几千年来对信息存储、表示、处理的方式，也极大地影 响了人类生活与思考的方式。 计算机网络(computer network)是相互连接的多台计算 机的集合体，人们使用计算机并通过网络互相交流信息，同时 扩展计算机的功能。计算机网络的影响深人到人类生活的各 个方面，它作为一种新的媒体改变了人类的交流方式，同时也 改变了人们对计算机能力的评价一计算机的能力不仅仅在 于它的处理速度和存储容量，更重要的是它们之间的连接 方式。 因特网(Internet)是计算机网络中最耀眼的明星，它是世 界上最大的广域网，连接了地球上几乎每个角落的计算机，是 人类最广泛、最有效的信息交流平台。任何一台计算机只要 接人因特网，它就潜在地拥有了世界上最大容量的信息仓库 和最高速度的计算能力，从这种意义上说；因特网将单台计 算机的能力扩展到了极致。 计算机网络自产生以来，其管理与控制就有两种不同的 方式：集中式与分布式。集中式系统(centralized system)中 的结点在功能上是不平等的，总会有一些通常是少数的管理

! !"! !"##$#$%! !"#$!"%&’()*+,-./0"1,2345 6’(789:;<=>?#@A#BC,DE"FG+HI J6’(KLMNO,DE$ !"#PQ%#$%&’()*+)(,$*-&$RSTU,VW!" #,XYZ"’[\]!"#^_‘PQSRab<="cd ef!"#,gh$!"#PQ,IJijk’(KL,l mDn"1op0qr,sZ456’(,abDE"cdF 456’[;!"#ht,uv’’’!"#,htwxxy z1,BC{|}>?~"€‚ , $ 1 [ / ƒ , T U DE$ „…P%.+()*+)(&$!"#PQ†)‡ˆ,.‰"1$% Š‹)+,ŒP"TU6HŽ‹7m‘’,!"#"$ ’()Œ#)•,<=abW$0W!"#™‚ Uj„…P"1š›yHœ6%Š‹)+~,<=ž })Ÿ{|,!"ht" ¡q¢£‹¤(„…P¥¦W! "#,htefk6G§$ !"#PQ¨©Kª:"«¬CM­®š¯qwc, DE)X†EM°±E$X†E²³%#)+(*/012)3454()%&† ,´µygh‹$w¶,"·¸0¹_º$»¼,¬C

对3网终：往钓、应闲5设计 结点(server,服务器)在系统中占据中心、主导的地位，管理其他从属结点(client, 客户)可执行的操作，控制其他结点之间的信息交换。分布式系统(distributed system)将管理和控制分散到它的各个成员结点中去，结点之间在功能上是平等 的，没有谁拥有比其他人更多的特权。集中式系统的优势在于管理的集中化，能够 对整个系统进行有效的控制，但它的优势也正是它的缺陷。由于所有结点之间的 信息交换都要经过服务器，服务器本身成为限制系统工作效率和规模扩展的瓶颈； 分布式系统刚好相反，由于管理的分散化，对整个系统的控制不像集中式那样强， 但是由于信息交换的自由、平等，分布式系统常常拥有远远高于集中式系统的工作 效率和规模可扩展性。在实际情况中，很多网络系统并不是采用纯集中式或纯分 布式的极端方式，而是兼有两方面的特性，称为混合式系统(hybrid system)。 因特网是最大的计算机网络，同样，它自诞生以来也一直存在着集中式与分布 式两种不同的工作方式。客户/服务器模式(client/server mode,简称C/S)是因特 网最传统、最成熟的集中式工作模式，许多重要的因特网应用协议（如HTTP FTP、SMTP等)采用了这一模式。在这种集中式的模式下，服务器将一直运行， 被动地等待客户的主动接入，客户将请求发给服务器，服务器返回给客户所要的信 息。客户/服务器模式在因特网的最初阶段工作得非常好，然而，随着因特网在规模 上不断膨胀、在功能上不断扩展，服务器的负担越来越重，客户/服务器模式的低效率 与难以扩展的缺陷暴露出来，它不再能适应需要极高效率与巨大规模的现代因特网。 “是人类的需求，真正推动了技术的革命。”每当人类所发明的技术不再能适应 人类本身需求的时候，一定会有人提出新的思想、发明新的技术来解决现实与需求 之间的矛盾。当传统的客户/服务器模式不再能适应现代因特网需求的时候，人们 将目光重新放回到长久被忽视的分布式系统上，对等模式(Peer-to-Peer mode,简 称P2P)正是在这种情况下受到重视并很快成为研究热点。“Peer”一词在英文中 的意思是“同等、对等的人”，故而“Peer-to-Peer”译为“对等（计算）”：国内很多人 将P2P称作“点对点”，这是不恰当的，因为“点对点”是“point-to-Point'”,和P2P不 是一回事。对等模式的本质思想在于打破传统的客户/服务器模式，让一切网络成 员享有自由、平等、互联的功能，不再有客户、服务器之分，任何两个网络结点之间 都能共享文件、传递消息。图1.1.1反映出从C/S到P2P的转变，Peers之间的逻 辑连接构建在物理连接的基础上。 对等网络(peer-to-peer network,简称P2P网络)是分布式系统与计算机网络 相结合的产物，是采用对等模式工作的计算机网络。图1.1.2描绘了随着分布式 系统规模的扩展，分布式计算的模式相应发生的改变。在对等网络中，每个网络结 点在行为上是自由的，在功能上是平等的，在连接上是互联的，所有结点分布式地 自组织成一个整体网络，因此，它能够极大程度地提高网络效率，充分利用网络带 宽，开发每个网络结点的潜力

! !"#$)%&#’()*+ ´µ%4)*6)*"½¾¿&y²³†ÀÁ†Â#ÃÄ,HÅ"¬C«Æ Ç´µ%#01)+(" ÈÉ&ÊËÌ,Ío"­®«Æ´µ/ƒ,<=aÎ$°± E ² ³%314(*17’()3 454()%&¥¬C}­®°Ïk1,lmÐÑ´µ†Ò"´µ/ƒygh‹$¶ ,"ÓԜիƒ€V,…Ö$X†E²³,×Øyz¬C,X†Ù"hÚ ;Ûm²³Ü̕,­®"Ý1,×ØFÞ$1,ßà$ázâ´µ/ƒ, <=aÎã‚䑽¾¿"½¾¿åæÐp箲³èo•é}êëef,ìí( °±E²³îïRð"áz¬C,°ÏÙ";Ûm²³,­®wñX†Eòóô" Ý$áz<=aÎ,¨á#¶"°±E²³ººœõõŸzX†E²³,èo •é}êëÊefö$y÷øùú†"ûVPQ²³^w$ü]ýX†Eþý° ±E,GÿDE"!$"¯Dn,…ö"#p$YE²³%857*13454()%&$ „…P$)+,!"#PQ"có"1¨%Kª:F0&>y’X†EM°± E¯qwc,èoDE$ÈÉ*½¾¿ëE%#01)+(*4)*6)*%$3)"(# 9*:&$„… P))³#)Ð*,X†EèoëE"+V‚,„…P,]-.%/ ;<<=# ><=#:?<=¶&ü]6¡0ëE$y¡qX†E,ëE0"½¾¿¥0&1Ì" 23H¶4ÈÉ,Ã3Uj"ÈÉ¥56-7½¾¿"½¾¿897ÈÉâ‚,< =$ÈÉ*½¾¿ëEy„…P,):;<èo=>ºï"?!"@’„…Pyêë ‹wABC#ygh‹wAef"½¾¿,DEF:F"ÈÉ*½¾¿ëE,G•é MHªef,ßàIJ2:"1wKhL,M‚GŸ•éMN+êë,3O„…P$ +$’(,M6"PÞQ36RS,TU$,V’(â-.,RSwKhL, ’(åæM6,dW"0X¸’Y2r,NZ#-.r,RS:[\3÷MM6 /ƒ,]^$V)³,ÈÉ*½¾¿ëEwKhL,3O„…PM6,dW"’[ ¥_‘ra9kbc2de,°±E²³‹";¶ëE%=))*@($@=))*%$3)"( #=!=&Þ$y¡qùú0fke^ûgÐphijµ$+=))*,0kylm† ,¢N$+c¶#;¶,’,"n!+=))*@($@=))*,op+;¶%!"&,(pqûV’ ¥=!=#o+µ;µ,"¡$wrV,"„p+µ;µ,$+&$1+(@($@=$1+(,"} =!=w $09s$;¶ëE,åtNZyzuv)³,ÈÉ*½¾¿ëE"w0xPQÐ Ñy¨á#¶#Sz,gh"wKÈÉ#½¾¿/°"¯mPQ´µ/ƒ ãh{ym|#)}~=$ABABAð€2  9*:k =!=,5"=))*4/ƒ,‚ ƒTU„…y†CTU,‡ˆ‹$ ;¶PQ%&))*@($@&))*+)(,$*-"(# =!=PQ&$°±E²³M!"#PQ R´Y,©†"$ü];¶ëEèo,!"#PQ$ABAB!‰Š6@’°±E ²³êë,ef"°±E!",ëER,-K,45$y;¶PQ†"mPQ´ µyÌp‹$¨á,"ygh‹$¶,"yTU‹$Sz,"â´µ°±EH ¨‹ŒÐ0mÛZPQ"„"1hÚG+Ž|HYŸPQ•é"°]PQ‘ ’"-mPQ´µ,›t$

3 第1章P2p网终简尔 Clients 图1.1.1从C/S到P2P (实线表示物理连接，虚线表示逻辑连接) 106 分布式计算 P2P 1000 Grid 100 Cluster 10 Mainframe 单机 LAN WAN/专网 Internet 地域分布 图1.1.2分布式计算模式与系统规模的关系 横轴：计算机网络在地域分布上的扩展：纵轴：分布式系统在规模上的膨胀， 斜箭头：适应于不同需求的分布式计算模式，Mainframe:主机计算，Cluster:机群计算；Grid:网格计 算，P2P:对等计算 P2P的思想起源很早，我们用“Google学术搜索”(http:/scholar.google. com)找到最早提及P2P的文献发表于1956年，从那以后几乎每年都有与P2P相 关的文章，但一直未成为热点。任何一种思想、理论的流行通常都需要一个杀手锏 (killer application),以一种征服性的力量冲击人类的传统思维。P2P的杀手锏正 是出现于1999年的世界上第一个应用性对等网络Napster,它创造了在半年时间里 拥有5000万用户的网络奇迹，向整个世界展示了P2P优异的性能和巨大的潜力。 学术的脚步常常先于应用踏入某个领域，又往往在应用之后成为热点，P2P和 Napster的关系正是如此。在Napster之后，是一系列人们耳熟能详的P2P网络 软件：Gnutella,KaZaA,Bit Torrent,eDonkey/eMule,Skype,等等。虽然从l999 年到现在只有短短几年，但是由于在工作模式上具有的优势和对于现代因特网的 适应性，P2P得以迅速从一个民间小软件发展为计算机网络的一项重要技术，在应 用领域和学术界获得了广泛的重视和成功，并占据了当前Internet超过一半的带

, ! - " # " #$./ " !!"!"! ! !!""#$# %÷@A†CTU"•@A‚ƒTU& !!"!"$ #$%&’(%)*+,(-.* )!"#PQyH°±‹,ef()°±E²³yêë‹,BC" ™š›)L,zwcM6,°±E!"ëE(%&’()*&+,)Ã#!"(!-./0,*)#œ!"(1*’2)P! ""#$#);¶!" =!=, N Z ž Ÿ û "¡ [ ] +C$$D0)¢ S £ ¤,%8((&)**4#8$0/*BD$$D0)B #$%&¥k) Y¦ =!=,m§-@zAEFG9" òª¨79ãM =!=R ©,mª"Ý0&«Ðpjµ$0qNZ#C¬,bÌ_ºãM‚0m­®¯ %-100)*/&&01#/(1$+&"ª0q°½ö,t±²’(,)³N³$=!=,­®¯Þ $23zAEEE9,%Š‹´0m,]ö;¶PQ H/&4()*"1µ¶6y·9dƒ¸ œF"""¹]É,PQº»"¼Ûm%ŠfA6=!=×½,öh}N+,›t$ ¢S,¾¿ººÀz,]ÁjÂmÍ"ÄÅÅy,]/¨Ðpjµ"=!=} H/&4()*,©²Þ$/$y H/&4()*/¨"$0²Æ’[Ç*hÈ, =!= PQ É|)C+’()00/"I/J/K"L1(<$**)+(")M$+-)5*)?’0)":-5&)"¶¶$Ê?  AEEE 9k3y™ËË79"Ý$ázyèoëE‹Ì,×Ø};z3O„…P, L,ö"=!==ªÍ{ 0m΃ÏÉ|-fp!"#PQ,0Ё‚RS"y, ]Í}¢SŠÑ=6Œ,e}Ðg"^ÀÁ6VÒ.+()*+)(Ó‘0·,‘

对3网终：镇钓、应闭5设计 宽资源，被认为是“改变Internet的新一代网络技术”。 对于已经应用或正处于理论研究阶段的各种P2P网络，国内外的研究者从多 个不同的角度对它们进行了分类，包括从体系结构、出现时间角度和应用领域角度 进行的分类，到目前为止尚未出现公认的、明确的分类方法。本书从P2P网络设 计思想出发，兼顾体系结构和出现时间两个方面的考虑，将P2P网络分成三代： 第一代，混合式P2P网络，它是C/S和P2P两种模式的混合； 第二代，无结构P2P网络，它以分布、松散的结构来组织网络，故称“无结构”： 第三代，结构化P2P网络，它以准确、严格的结构来组织网络，并能高效地定 位结点和数据。 对这三代P2P网络的讲解，是本书的一大重点，分别对应第2、3、4章的内容。 读者需要注意的是：我们的分类仅出于本书行文、讲解的考虑，并非P2P领域明确 的界定。 现代计算机网络均采用层次化的结构，以提供一个便于分析的模型和利于开 发的技术接口，它具体地表现为一个网络通信从高层到低层的协议栈。这里面最 为著名的是ISO/OSI(国际标准化组织/开放系统互联)模型和TCP/IP(传输控制 协议/因特网协议)模型，前者细致、正式，后者更为实用。在本书中对于层次化的 网络结构描述均采用TCP/IP模型，如图1.1.3所示。 图1.1.3中TCP/IP模型共分四层： 应用层 (C/S:P2P) 网络接入层、网络层(IP协议)、传输层 传输坛 (TCP/UDP协议) (TCP/UDP协议)和应用层。在此之前 树铬尽 TP协议) 所说的集中式系统、分布式系统、客户/服 网路接入层（链接协议与粉班协议） 务器工作模式以及对等计算模式，都是指 四层中的最高层一应用层的工作方式， 图1.1.3TCPP协议栈 而下面的三层通常采用标准、单一的工作方式，本身并没有集中式与分布式之分， 只是为应用层不同的工作方式提供底层的服务支持。 P2P网络的核心机制，是在应用层建立逻辑上的覆盖网络(overlay network), 封装下面的三层，让P2P网络的研究者和开发者不必关心下面三层是如何工作 的，而仅仅去考虑应用层覆盖网络的工作情况，将精力集中于覆盖网络的设计、优 化上。虽然如此，在对P2P网络做基础的研究和设计时，有时还是要考虑到下面 层的工作情况，因为应用层建立的覆盖网与底层实际的物理网的工作情况不可能 完全相同，在图1.1.4中，覆盖网上的一条逻辑连接AE对应物理网上三条物理连 接：AC,CD和DE。所以从覆盖网看到的行为与底层物理网实际的行为并不一 致。P2P领域的研究者已经对这种不一致性做了大量的工作以尽可能减少两者之 间的差异，提高整个网络的效率。简言之：P2P网络工作于应用层，但兼顾网络底 层。读者在阅读本书时应该注意到这一点，这一问题在以后的章节中会有详述

# !"#$)%&#’()*+ ’ÔŸ"2Õp$+45.+()*+)(,r0OPQRS,$ ;zÖä,]þÞBzC¬hi;<,lq =!=PQ"pq×,hiØ V mwc,‘|;1[ÜÌ6°("ÙÚ Z²´„#23dƒ‘|},]͑| ÜÌ,°("k_ÒpÛÜ«23ÝÕ,#.Þ,°(Dß$åà  =!=PQá !NZ2-""âZ²´„}23dƒ¯mDn,Oã"¥=!=PQ°ÐäO) ´0O"$YE =!=PQ"1$ 9*:}=!=¯qëE,$Y( ´åO"洄 =!=PQ"1ª°±#çÏ,´„:‹ŒPQ"n#+洄,( ´äO"´„Ù =!=PQ"1ªèÞ#é,´„:‹ŒPQ"^hŸ•HX Å´µ}¼Á$ ;¡äO =!=PQ,ê["$åà,0+µ"°ë;,´!#N#Oª,q~$ ìØM‚í¢,$)¡[,°(x2zåàÌm#ê[,Oã"^>=!=Í.Þ ,ŠX$ 3O!"#PQîü]ïðÙ,´„"ªYñ0mòz°ó,ëô}z -,RSUõ"1ÌZH@3p0mPQ_< ŸïkGï,-.ö$¡¸n) p÷ø,$.:P*P:.%pøùèًŒ*a²³Sz&ëô} <9=*.=%)ú­® -.*„…P-.&ëô"ÒØû§#ÞE"¨Ø€p÷]$yåà†;zïðÙ, PQ´„‰üîü] <9=*.=ëô"/ABABNâA$ !!"!"% 3!#!4#/01 ABABN† <9=*.=ëô{°ýï) PQ U j ï#P Q ï %.= - .&#) ú ï %<9=*QM=-.&} ,]ï$y /Ò â¤,X†E²³#°±E²³#ÈÉ*½ ¾¿èoëEª¦;¶!"ëE"ã$þ ýï†,)Ÿï’’’,]ï,èoDE" !0n,äï_ºü]ùè#¦0,èoDE"åæ^ÓX†EM°±E/°" ™$p,]ïwc,èoDEYñÿï,½¾!"$ =!=PQ,#Â#®"$y,]ï…$‚ƒ‹,%&PQ%$6)*0/5+)(,$*-&" ’(0n,äï"w =!= PQ,hiØ}-Øw)©Â0näï$/èo ,"!xxÒOã,]ï%&PQ,èoùú"¥*tX†z%&PQ,á!#× Ù‹$Ê?/"y; =!=PQ+‡ˆ,hi}á!d"d,$‚Oãk0n ï,èoùú"„p,]ï…$,%&PMÿï÷ø,†CP,èoùúwÊh -.Rc"yABABO†"%&P‹,0/‚ƒTU!" ;,†CP‹ä/†CT U)!#"#$ }$"$⪠%&P0k,ÌpMÿï†CP÷ø,Ìp^w0 §$=!=Í,hiØÖä;¡qw0§ö+6+,èoª1Êh2»¯Ø/ ƒ,3½"YŸÛmPQ,•é$(4/)=!=PQèoz,]ï"Ý"âPQÿ ï$ìØy5ìåàd,6í¢k¡0µ"¡078yª¨,ª9†¸Èü$

6 第1章P2p网终简尔 P2P卷溢树 底层物理树 图1.1.4P2P覆盖网和底层物理网的不一致性 (虚线表示逻辑连接，实线表示物理连接》 在P2P覆盖网上依靠DHT(distributed hash table,分布式散列表)通常能准 确、快速地路由消息和定位数据对象，这正是P2P查询的优势所在。“祸兮，福之 所倚；福兮，祸之所伏。”正如计算机领域那条著名的“没有白吃的午餐定理”(No Free Lunch Theorem)[Wolpert and Macready,l997]所述任何方法对一类问题做 得好，必然对另外某类问题做得不好，这就是代价。使用覆盖网和DHT的P2P网 络，为追求性能和效率所付出的代价，是语义模糊查询的困难以及对动态网络环境 中错误行为的容忍性下降。针对前者，语义模糊查询至今仍然是P2P领域的一个 开放型问题，尤其对结构化P2P网络更为困难；针对后者，P2P领域的研究者提出 的方案各具特色，总体上分两类：①网络周期性主动更新：②在检测到错误后被动 更新。前者机制简单而开销很大，后者开销较小而机制复杂，这就带来了两难问题。 前面描述了P2P的核心机制，有了它们，一个P2P网络能正常工作，但不见得 “好用”，因此人们又提出了很多P2P的“增强机制”，以改善网络状况，让它更好地 工作。这些增强机制不少是从分布式系统或者计算机网络领域借鉴过来的，如数 据复制、缓存、分片等；当然，更多的增强机制来自P2P本身，如负载的均衡、异构 性的开发、少数结点负担过重导致的“热点”问题、物理网与覆盖网不一致造成的 “拓扑意识”问题、保护用户隐私的“匿名”问题、P2P用户的“声誉”和“信任”问题以 及最令人不放心的P2P“安全”问题。 “纸上得来终觉浅，绝知此事要躬行。”理论是灰色的，生活之树常青。理论并 不都现实可行，即使真的实现了，也未必好用，所以做研究注重理论结合实践，强调 实践的作用。对P2P来说，由于其网络规模巨大，开发实际系统的软硬件开销巨 大，因此P2P实验更侧重于“模拟”和“仿真”。 “图难于其易，为大于其细。”本章的后续部分，将从“大”而“易”的方面讲述 P2P的历史、现状、缘由、特点、应用和著名模型：而本书后面的各章，则从“细”而

, ! - " # " #$./ $ !!"!"& #$#234567894-:;<= %•@A‚ƒTU"÷@A†CTU& y=!=%&P‹:; M;<%314(*17’()38/48(/70)"°±EÏÆ@&_ºhè Þ#g{H<á~=}XżÁ;="¡Þ$ =!=>?,×Øây$+@A"B/ âC(BA"@/âD$,Þ/!"#Íò/÷ø,+ÓEF,GHXC,%H$ >*))R’+#8<8)$*)%&-S$0&)*(/+3?/#*)/35"AEET.âüDß;0(78+ =ï")?;I×Â(78+=wï"¡š$Ov$\]%&P} M;< ,=!=P Q"pJ6öh}•éâK2,Ov"$L£ëM>?,NHª¦;3OPQPQ †RSÌp,~Tö0U$V;ÒØ"L£ëM>?WXY?$ =!=Í,0m aô78"Z«;´„Ù=!=PQ€pNH(V;¨Ø"=!=Í,hiØY2 ,D[l̅\"·Z‹°¯()!PQ]^öÃ3€r("y_‘kRS¨23 €r$ÒØ#®(¦!aû+"¨ØabÏ!#®cd"¡š‘:6¯H78$ Òn‰ü6=!=,#Â#®"61["0m =!=PQhÞºèo"Ýwe= +ï],"„’[ÄY26ûV =!=,+fô#®,"ª4gPQhú"w1€ïH èo$¡¹fô#®w»$ °±E²³þØ!"#PQÍij‘:,"/¼ Ác®#k>#°l¶(V?"€V,fô#®:¨ =!=åæ"/Dm,în#½„ ö,-#»¼´µDE‘Ä§,+jµ,78#†CPM%&Pw0§¶Ð, +op¢q,78#rs]Étu,+vø,78#=!=]É,+wx,}+<,78ª ¦)y’waÂ, =!=+z.,78$ +{‹=:|}~"€s‚Ì$,C¬$‚\,"KL/ƒº„$C¬^ wã3÷ÊÌ"…\P,÷36"F«)ï]"âª+hiíC¬´Y÷†"ô‡ ÷†,o]$; =!=:¤"áz«PQêëN+"-÷ø²³,Ɉ|aN +"„=!=÷‰€Šz+ë‹,}+ŒP,$ +Hz«"p+z«û$,åª,¨Ž°"¥ ++,!+,,Dnêü =!=,‘#3h#’á#…µ#,]}÷øëô(!åà¨n,lª" +û,!