专题3-P2P网络体系结构(2013简)

P2P网络体系结构

概述对等网络(P2P网络)是分布式系统和计算机网络相结合的产物，在应用领域和学术界获得了广泛的重视和成功，被称为“改变Internet的新一代网络技术”。课程信息教材对等网络：结构、应用与设计陈贵海、李振华著，清华大学出版社，2007.9

P2P网络的概念、发展、特点、应用P2P：PeertoPeer对等网络peer指网络结点在行为上是自由的——任意加入、退出，不受其它结点限制，匿名功能上是平等的——不管实际能力的差异连接上是互联的——直接/间接，任两结点可建立逻辑链接，对应物理网上的一条IP路径充分利用网络带宽、结点资源，提高工作效率从T/H,C/S到P2P-计算模式的轮回实线表示物理连接，虚线表示逻辑连接P2P的思想1956年提出（为什么今天成为现实？）1999年Internet上第一个应用Napster，半年发展了5000万用户其后涌现Gnutella,KaZaA,BitTorrent,eDonkey/eMule,Skype此后学术界重视占据Internet一半以上的带宽不同类型P2P网络几乎同时出现，无明确界定，大致分类混合式P2P网络：C/S、P2P模式的混合无结构P2P网络：分布/松散的结构结构化P2P网络：准确、严格的结构设计和实现P2P网络应解决的基本问题路由和定位、查询和搜索、动态结点算法、容错性P2P网络的增强机制数据复制、缓存、分片；负载均衡；拓扑一致性；匿名、声誉、信任、安全性P2P网络的优势一、充分利用网络带宽P2P不通过服务器进行信息交换，无服务器瓶颈，无单点失效，充分利用网络带宽，如BT下载多个文件，可接近实际最大带宽，HTTP及FTP很少有这样的效果二、提高网络工作效率结构化P2P有严格拓扑结构，基于DHT，将网络结点、数据对象高效均匀地映射到覆盖网中，路由效率高三、开发了每个网络结点的潜力结点资源：计算能力及存储容量个人计算机并非永久联网，是临时性的动态结点，称为“网络边缘结点”P2P使内容“位于中心”转变为“位于边缘”，计算模式由“服务器集中计算”“分布式协同计算”四、具有高可扩展性(scalability)可扩展性衡量，当网络结点总数增加时：结点负载如何改变为适应规模扩大而需要增加的额外设备的数量任意两个网络结点通信效率如何改变，尤其是路由效率P2P网络中，结点间分摊通信开销，无需增加设备，路由跳数增量小五、良好的容错性冗余方法周期性检测结点自适应状态维护P2P网络的各种应用文件共享：代替ftp，前述典型的P2P模型多媒体传输：Skype（语音），PPLive（视频）实时通信：QQ、MSNMessenger、Skype，都支持C/S、P2P模式协同工作：Groove虚拟办公室分布式数据存取：广域、海量，CFS、PAST、OceanStore、Granary分布式计算：GPU，Gnutella全球处理单元，计算任务由对等结点而非服务器分配，SETI@Home，U.C.Berkeley搜索外星文明P2P搜索引擎：第三代搜索引擎技术，离实用有差距其它第一代P2P网络——混合式P2P体系：Napster与BT内容Napster——P2P网络的先驱BitTorrent——分片优化的新一代混合式P2P网络第一代P2P网络的特点Napster：P2P网络的先驱世界上第一个应用性P2P网络，混合式P2P体系最杰出的代表1999年波士顿东北大学的ShawnFanning开发Napster，用于MP3文件交流，与传统的提供音乐下载的网站不同，Napster服务器里无歌曲，仅有其它用户硬盘上的文件的索引Napster使用的软件技术都是当时已有的，只是改变了软件的应用体系，打破了客户/服务器模式的瓶颈Napster半年吸引了5000万注册用户，最高时超过6100万用户一、Napster网络的工作原理Napster网络由两个部分组成：Napster用户(peer)Napster网站(N)是一个服务器机群提供统一的用户访问接口各自保存一部分用户的共享文件索引信息peer与固定的server相连加入时，将自身信息（连接带宽、存储空间等）以及共享文件信息发送给server，server记录信息内容及用户位置（文件索引）查询时，peer将查询消息发给server，server与其它server协作后回复表单（包括所有匹配的文件索引）下载时，peer直接从索引中选取peer并与之建立连接、下载文件Napster网站的功能维护所有用户的共享文件索引监控系统中每个用户的状态（用户报告的连接带宽、用户连入时间、是否掉线）删除掉线用户的索引，保证文件索引的时效性响应用户的查询请求，查询的返回消息中可包含带宽等信息，便于用户选择连接Napster的性能分析检测结果与结论Napster机群包括大约160台服务器每个用户只与一台服务器建立连接新用户加入网络时，可以选择是否报告连接带宽，但大多不报告，或者故意误报以减少其他用户从自己下载(自私性)结点异构性很强，表现在连接带宽、时延、连接时长、共享文件性等方面，如25%64Kbps，50%CableDSL，20%3M以上；超过50%的连接时间<1h，>6h的不到10%用户自私性：20%～40%用户几乎从不提供文件共享，仅1%结点为文件提供者因此，类似Napster的P2P网络在设计、优化时应考虑结点异构性：让不同能力的结点扮演不同的角色协同传输:增加并行传输连接数目,避免系统瓶颈.激励机制:鼓励上传，限制或禁止自私结点使用网络进一步的发展，BitTorrent：相同架构，但文件分片，使用散列函数映射用户有上传义务网络及用户信息更新、BT种子维护由server中的Tracker完成，下载同一文件的用户围绕Tracker形成独立子网，不同文件的Tracker在不同server上，将server分散化，成为P2P在国内最成功的应用BitTorrent：分片优化的新一代混合式P2P网络BT体系原理BT分片机制BT阻塞算法BT性能分析BT体系总结P2P下载对硬盘的影响BT体系原理BT网络的四个组成部分BT网站：提供BT种子文件(即.torrent文件)搜索的服务器，每个服务器包含部分种子文件的索引.torrent文件服务器：小型的种子数据库Tracker(跟踪服务器)：BT网络和用户信息的维护者，帮助用户交互，下载同一个文件的用户围绕Tracker形成一个独立的子网BT用户：可同时下载多个文件BT用户的下载步骤BT用户通过某个BT网站搜索文件，该网站将搜索请求重定向到网站镜像，后者检索并返回给用户该文件的.torrent文件列表用户选择列表中的.torrent文件，BT软件启动下载任务，并从Tracker获得当前也在下载该文件的用户信息BT软件与一定数量的用户建立连接，下载文件并同时提供上传下载过程中每隔一段时间更新一次连接以保持整网的工作效率BT分片机制BT将文件分为固定大小的分片(典型大小256KB)，每个用户必须通知其他下载者自己拥有的分片，分片的完整性由散列函数保证分片流水作业：构架在TCP之上的应用层协议，同时发送多个请求，以避免在两个分片发送之间的延迟，进一步，分片可以划分为子分片(典型16KB)，BT一直保持几个请求（通常是5个）被流水式地同时发送。流水作业选择同时发送的请求数目的依据，是使大多数连接变得饱和以充分利用带宽分片选择策略严格的优先级（一个分片的下载）一旦请求了某个分片的子分片，那么该分片的所有子分片具有更高优先级，以尽可能快地获得一个完整的分片最少者优先（中间阶段/平稳期）尽量选择所知用户拥有数最少的分片作为下一个下载分片，以使网络中最稀少的分片尽快拥有多个复制下载者从Tracker了解哪些分片较少分片选择策略随机的第一个片段（文件下载最初阶段）当最少的分片只有一个用户拥有时，为避免并发冲突，第一个分片先随机选择，完成下载后再切换到“最少者优先”策略最后阶段模式（文件下载最后阶段）为加速最后阶段下载，下载者向他所连接的所有用户都发送某分片的子分片请求，一旦某个子分片到了，下载者就会向其他用户发送cancel消息，以避免浪费带宽BT阻塞算法BT并不是由Tracker服务器集中分配资源，每个用户自己有责任尽可能地提高自己的下载速率下载者根据连接用户提供的下载速率给予同等的上传回报(tit-for-tat)；对合作者提供上传服务，对不合作者进行临时阻塞一个好的阻塞算法应该利用所有可用的资源，为所有下载者提供一致、可靠的下载速率，并适当惩罚只下载而不上传的用户BT的阻塞算法(chokingalgorithm)每隔20秒进行一次轮询：前10秒计算出哪个用户要被阻塞，然后将阻塞状态保持10秒10秒内足够TCP调整传输速率最优疏通(optimisticunchoking)为发现更好的空闲连接，不能只向为自己提供最高下载速率的用户提供上传，而是每隔30秒，重新计算一次哪个连接应该是“最优疏通”反对冷落(anti-snubbing)某个下载者可能被所连接的所有用户阻塞，为缓解该问题，当从某个用户那里一个分片也没有得到，下载者认为被对方“冷落”，不再为对方提供上传。“反对冷落”常常会导致多个并发的“最优疏通”，从而更快恢复下载速率仅仅上传用户完成下载后，优先选择可从自己得到更高上传速率的用户或刚好被所有人阻塞的用户BT性能分析

Pouwelseetal.,2004,2005论文流行性：应用广泛，但BT网站、.torrent文件服务器及Tracker故障率较高，限制了网络规模可用性：同上，取决于服务器的可用性。实际较低，只有一半的BT网站镜像可正常工作超过2.1天，种子服务器更少下载性能：当时统计平均速度30KB/s文件生命周期该文件的种子生命期，由于服务器故障及用户行为不确定性，差别很大约17%的用户下载完成后做种时间超过1小时，仅3%用户做种时间超过10小时污染等级加入到BT网络中的共享文件的真实性审查系统(moderationsystem)，三种角色：需要审查的提交者；不需要审查的提交者；审查者。可逐级提升。BT体系总结BT是混合式结构的P2P网络，以BT网站、.torrent文件服务器和Tracker为核心，控制和帮助用户共享文件下载同一文件的用户围绕Tracker形成一个独立的子网BT限定用户在下载的同时必须提供上传，既提高了网络效率，又杜绝了P2P网络中的自私结点现象BT将文件分片，分片又被划分成子分片，子分片流水作业，并在文件下载的不同阶段有不同的分片选择策略以优化性能。这是BT最大的特点，也是它高效的最本质原因BT基于经济学规律的阻塞算法，优化了网络资源配置，增强了用户间的协作BT通过对文件和分片生成散列值，保证文件的完整性BT提供了一定的安全机制，如文件审查、输入验证码BT服务器故障率高，导致可用性降低，且网络规模受限，文件无持久性保证第一代P2P网络的特点拓扑结构混合式(C/S+P2P)星型拓扑结构，以服务器为核心查询与路由用户向服务器发出查询请求，服务器返回文件索引用户根据索引与其它用户进行数据传输路由跳数为O(1)，即常数跳容错性：取决于服务器的故障概率（实际网络中，由于成本原因，可用性较低）自适应：靠服务器监控实现自组织与自适应，只要服务器正常工作即可有效维护网络和结点信息匿名性：一般不提供，但支持增强机制：BT的文件分片、双向传输、防范攻击第二代P2P网络——无结构P2P体系Gnutella、KaZaA、eDonkey、FreenetGnutella：纯分布式无结构P2PGnutella的历史Nullsoft公司，MP3播放软件WinAmp的发明人JustinFrankel、TomPepper开发2000年3月14日在网站上公开Gnutella软件一个半小时后，母公司AOL(AmericanOnline)担心步Napster后尘，关闭了网站数千名MP3迷下载了软件并公开与改造其纯分布式无结构P2P网络思想广泛流传Gnutella已不单纯对应具体软件，而是当作一种典型的无结构P2P网络协议一、Gnutella体系的工作原理Gnutella协议0.4版(0.6版加入了超结点Ultrapeer，结构有变化)协议开发者称Peer为Servent(Server+Client)，网络中只有peer，没有serverGnutella覆盖网上每个结点对应一台实际的计算机每条连接对应一条点到点的链路覆盖网上的连接由每个peer保存的“邻居结点”信息确定，有一个邻居结点即对应有一条边新结点加入时，必须首先连接到“众所周知”几乎总是在线的Gnutella结点(称为“自举”结点、“入口结点”)Gnutella网中的消息可以被广播或回播(back-propagate，沿广播的反向路径回传消息)，协议设计的支持机制：每条消息具有一个随机产生的全局唯一标识符GUID(16字节)以互相区分每个结点缓存最近路由的消息以支持回播并阻止不必要的重广播每条消息都有TTL以避免过度消耗网络资源Gnutella的典型消息组成员消息：PING，PONG新结点加入时广播PING消息，或用来探测其它结点是否仍然存在(心跳)结点收到PING消息后，可以决定是否回播PONG消息，以及是否将PING转发给邻居，PONG消息包含结点IP,port,共享文件数量大小查询消息：QUERY，QUERYRESPONSEQUERY消息用来查询文件,包含查询内容与最小响应速度等附加信息,但不包含源结点信息RESPONSE消息包含文件下载的必须信息及该结点的nodeID，沿QUERY消息路径回播文件传输消息：GET，PUSH结点收到QUERYRESPONSE消息后用GET消息请求获得文件对处于防火墙后因而不能直接响应文件请求的结点，使用PUSH消息请求防火墙后的文件拥有者主动建立到自己的连接Gnutella的文件检索过程泛洪式搜索(floodingsearch)，系统开销大有限深度TTL(TimetoLive)，不保证一定查询到已有文件Gnutella网络的维护各结点使用PING、PONG消息探测其他结点存在与否，在收到PING消息后，可以自主决定是否回播PONG，并根据TTL数值决定是否继续广播PING消息具有一定的自组织和自适应性Gnutella网络的性能分析Ripeanu,2001,2002、Saroiuetal.,2002,2003、Adar&Huberman,2002Gnutella用户的连接带宽仅在Queryresponse消息中作为辅助信息回播，因此，Gnutella网络中不共享文件的用户或其共享的文件与查询请求一直不匹配的用户，不会主动发布带宽Gnutella网络中结点功能平等，但能力有差异（异构性），如连接带宽在无组织的Gnutella网络组织方式下，70%的结点承受较高时延(>280ms)用户连接时间与Napster类似，超过50%的用户连接时间<1h，不到10%的>6h25%的用户不共享任何文件，75%的用户共享文件数低于100，仅7%共享文件超过1000，即文献中的Free-Riding(搭便车)现象，对网络的高效工作不利Gnutella网络相当于社会网络，可用幂律(Power-law)分布网络近似，拥有连接数L的结点占网络总结点的份额正比于L-a,a是取决于网络本身的常数因子，Gnutella网络a=2.3，容错性较高采用Gnutella协议的P2P网络应解决：结点异构性：充分利用结点能力Free-Riding：鼓励上传，限制或剥夺Free-Rider的权利保持高容错性：高效的机制检测和恢复网络分割继续优化查询机制，TTL的取值拓扑一致性Gnutella协议0.6版层次化的无结构P2P网络路由和定位方法Routing、location含义接近，此处路由指消息走过的路径上的每一跳选择，定位看成是由多次路由组成的无结构网络没有全局路由表，不可能预先知道要找的数据在哪里，只能随机路由，通常以洪泛法为基础，通过TTL限制搜索半径四种典型的P2P随机路由方法：洪泛法、扩展环、随机走、超结点路由洪泛法绝大多数现存无结构P2P网络实际采用路由覆盖范围是一个以TTL为半径的圆不保证找到实际存在的文件扩展环（expandingring）试探性的洪泛法逐步增加TTL，直至查询成功或者达到上限，从而形成一个个环效率稍高随机走（randomwalks）结点收到查询消息时只随机选择一个邻居结点发送该消息，直到数据被找到或TTL用完因网络开销仅随跳数增加线性增加，故TTL可以较大改进方法：带检测的随机走，行者ID前途较为光明超结点路由（supernoderouting）超结点自组织成一个网络，普通结点向其发起查询可以在超结点网络中采用洪泛法eDonkey、KaZaA的流行，证明可行性第三代P2P网络

——结构化P2P体系Chord、CAN、Tapestry、PastryChord与CFS：简单、精确的环形P2P网络MIT与Berkeley的研究者01年正式发表http:///chord/Chord作为一个P2P网络，是基于带弦环拓扑结构的分布式系统，提供对象的存储、查询、复制、缓存，在其上可以架构更高层的分布式数据存储系统如协同文件系统CFSChord作为一个分布式散列表，只支持结构化P2P最简单的功能：将结点和数据对象映射到覆盖网中，但具有几乎最优的路由效率、确定性的对象查询、负载均衡、高可靠性以及良好的容错性与自适应，最主要的是：简单、优美Chord的技术特点基于安全的一致性散列函数来分配结点ID和对象ID在一个有N个结点的网络中，每个Chord结点保存O(logN)个其他结点的信息查询数据对象需要的覆盖网路由跳数也为O(logN)当结点加入或者离开网络时，为了维持网络结构、保持自适应性所需要的消息数在O(log2N)Chord基础工作原理Chord使用安全散列函数（如SHA-1）为每个网络结点和数据对象分配唯一的IDnodeID=H(node属性)，属性可以是结点IP、port、公钥、随机数或它们的组合objectID=H(object属性)，属性可以是数据对象的名称、内容、大小、发布者或者它们的组合H是散列函数，SHA系列散列函数的Hash值长度≥160，保证ID的唯一性Chord按照如下方法将数据对象（只是其索引）分配到网络结点中所有的结点按照nodeID从小到大顺时针排列在一个环上数据对象k（ObjectID）被分配到环上顺时针方向紧随k（包括与k相等）的第一个结点，该结点称为对象k的后继，记做successor(k)Chord结点n的后继是环上紧随n（不等于n）的第一个结点，记做n.successor一个简单的Chord环（m=3）当Chord中有新结点n加入时，为保持正确、一致的对象放置，原本由n的后继结点负责的对象，其中一部分必须分配给n当Chord中有旧结点n离开时，原本由n负责的所有对象，必须分配给n的后继。除此以外，对象不需要再做移动，这正是一致性散列函数所追求的性质例：图中新加入结点7单纯的环可以工作，但效率太低为此，结点维护一个有m（ID位数）项的路由表，也称“指向表”（fingertable），其中第i项指向结点s，s=successor(n+2i-1)，1≤i≤m，即s是在顺时针方向到n的距离至少为2i-1的第一个结点，记做n.finger[i].nodeChord路由表的特点：每个结点只保存很少的其它结点信息，并且对离它越远的结点所知越少Chord结点不能从自己的路由表中看出对象k的后继为确定对象k的后继（k所在的结点）,结点n在自己的路由表中查找在k之前且离k最近的结点j，让j去找离k最近的结点，递归查找，最终可以找到对象k的前驱（在k之前离k最近的结点，记做predecessor(k)，类似，结点n的前驱记做n.predecessor）前驱中必然有后继的路由表项，定位成功Chord结点n的路由表各项属性及其定义属性定义finger[k].start(n+2k-1)mod2m,1≤k≤erval[finger[k].start,finger[k+1].start).node≥n.finger[k].start的第一个结点successor后继结点，即finger[1].nodepredecessor前驱结点Chord路由表的简单示例假设结点3要找到对象1的后继在结点3的路由表中，1属于3.finger[3].interval即[7,3)结点3让3.finger[3].node即结点0去找1结点0在路由表中发现自己的后继1恰好是对象1的后继，因此将1返回给结点3结点3由此知道对象1放在结点1中Chord结点加入算法Chord的自适应需要保持两个不变的属性每个结点的后继始终正确对每个对象k，结点successor(k)始终负责k的索引为此，新结点n的加入需要完成三个任务初始化n的前驱和路由表项更新网络其他结点的前驱和路由表项告诉其后继将应该由n负责的数据对象索引传递给nChord容错性和复制、缓存Chord中正确的后继关系是一切工作的基础无论机制如何完善，网络的动态性和不确定性都可以导致单后继失效因此，实际的Chord给每个结点维护一个后继列表，其中保存了该结点在Chord环上的r个后继，典型地取r=O(logN)，即使结点失效概率为1/2，仍能正确定位将结点保存的数据对象复制到所有后继中，可提高数据的可用性、持久性在Chord定位过程中，如每个中间结点缓存数据对象，可以提高获取数据的速度Chord实验分析负载均衡负载均衡是使用一致性散列函数的结构化P2P网络的共同属性对于Chord而言，由于数据对象被分配到其后继中，而数据对象、结点的ID都是随机、均匀产生的，因此每个结点所负担的数据对象也应该大致均衡此外，Chord还采用了“虚拟服务器”的方法，在一台计算机上运行多个Chord结点，可以使得结点各尽所能定位路径长度理论量级为O(logN)跳实验中网络结点数取N=2k，数据对象数取100×2k，k从3取到14测量结果：路径长度平均约logN/2，是logN的一半，原因是Chord路由表的指数构造，使其每次查找都能将目的ID与当前结点ID之间的差距减小至少一半，可推导出平均路径长度正好是logN的一半Chord总结Chord采用带弦环拓扑结构，通过一致性散列函数将结点、数据对象映射到覆盖网上，数据对象（索引）由其后继结点负责，简单、精确正是Chord最大的特点每个Chord结点维护一个很小的路由表，后继关系是Chord定位的基础，路由表可以将定位路径长度缩短为O(logN)跳Chord需要保持两个不变的属性才能正确工作：后继正确、后继对对象的索引正确Chord采用周期性的稳定算法和路由表更新算法检查和修正后继关系及路由表项为保持高容错性，Chord采用后继列表避免单后继失效，此时可以对数据对象进行复制和缓存，提高网络效率结构化P2P网络的特点与分析一、覆盖网拓扑结构带弦环：所有结点被组织在一个环上，环上只提供两种功能——取得当前结点的前驱和后继(单向环如Chord只提供后继)，只要后继关系正确，就能保证正确定位。为加速定位，加入“弦”，即维护一个路由表，指向环上离自己很远的结点。采用环形结构的P2P网络有Chord、Pastry、Kademlia、Cycloid多维空间所有结点被组织在一个多维笛卡尔空间里（严格说是“多维环面(Torus)”结构），每个结点有自己在空间中的邻居，典型P2P网络是CAN，超立方体（或PlaxtonMesh）所有结点被组织在一个超立方体中，典型的有Tapestry、Pastry，覆盖网每层维护匹配nodeID不同长度前缀（或后缀）的结点；Cycloid的基础CCC则是基于超立方体改造蝴蝶形蝴蝶网中，每个结点有“层”，每层的结点通常维护两个下边、一个上边以及两个同层边，典型的有Viceroy，基于蝴蝶网，不过每个结点还保存一个前驱和一个后继从而组织成一个全局的环结构deBruijn图每个节点有两条出边：一条指向结点2m(mod2b)，一条指向结点2m+1(mod2b)，b为ID位数。Koorde将deBruijn图嵌入到Chord环中，提高了路由效率CCC（cube-connected-cycles）一个d维带环立方体CCC是每个结点被一个包含d个结点的圆环所取代的d维超立方体，因此，每个结点度为3。Cycloid是基于CCC结构的常数度P2P模型其它形状（如跳表）基于跳表SkipList的典型网络是SkipNet分布式散列表所有的结构化P2P网络都使用分布式散列表（DHT）来将结点、数据对象映射到覆盖网中为使这种映射唯一、均匀、随机，分布式散列表都使用安全的一致性散列函数，其中最著名、也被大多数P2P系统采用的安全散列函数是SHA-1（安全散列算法），它能产生均匀、随