P2P原理与技术

1、2022-3-61P2P原理与技术简介暨南大学计算机科学系周继鹏2022-3-62P2P原理与技术的内容q P2P概念q P2P分类q 构件与算法q 关键技术特性q P2P分析与比较q 研究与未来2022-3-631、什么是P2P（Peer-to-Peer）nP2P：对等(网络，计算);端到端n以非集中方式使用分布式资源来完成关键任务的一类系统和应用n资源包括计算能力、数据（存储和内容）、网络带宽和场景（计算机、人和其它资源）n关键任务可能是分布式计算、数据/内容共享，通信和协同、或平台服务n节点是服务和数据的提供者又是需求者n共享资源可被网络上其他节点直接访问2022-3-64P2P系统特点

2、n可扩展性、自组织、容错性、高动态性可扩展性、自组织、容错性、高动态性n数据的位置往往是不固定的数据的位置往往是不固定的n没有统一的全局模式，查询基于关键字没有统一的全局模式，查询基于关键字n节点可能不包含完整的数据，因此对于节点可能不包含完整的数据，因此对于查询的回答往往不完整查询的回答往往不完整2022-3-65P2P系统的应用n共享文件n流媒体系统n对等计算文件共享系统-maze,北京大学n视频直播系统AnySee，华中科技大学n在线电视直播-PPLivenBT下载软件n(如视频直播的思想是直播系统中的节点既下在载数据也上传数据.)2022-3-66如何找到指定的信息如何找到指定的信息

3、? ?ABCDEFE?2022-3-67P2PP2P的网络基本构成的网络基本构成LinuxTCP/IPBluetoothHTTPTCP/IPTCP/IPXP2022-3-68P2P覆盖网络的概念（1）覆盖网络的结点2022-3-69P2P覆盖网络的概念（2）2022-3-610P2P覆盖网络的路由（1）结点结点的完全图2022-3-611P2P覆盖网络的路由（2）2022-3-612覆盖网络n在现有网络体系结构上新加一层overlay networksn建立一个使用已有的Internet传输的虚拟网络nInternet也曾经被部署为一个在电话网上的重叠网络n也被成为ALNnApplicatio

4、n-Level Network.nFile storage and searchn挑战n如何创新和部署 at scale2022-3-613覆盖网络模型 Overlay Network routing table peer 1 Internet: Supporting Netork A Generic Topological Model of P2P Systems routing and locating algorithm Data Storage Data Cache routing table peer 2 routing and locating algorithm Data Sto

5、rage Data Cache routing table peer n routing and locating algorithm Data Storage Data Cache 2022-3-614P2P系统分类n无结构P2P：文件位置与覆盖网拓扑无关n有中心的：Napstern无中心的：Gnutella、Freenetn层次结构：KaZaAn结构化P2P：文件或文件索引的位置与覆盖网的拓扑结构紧密相关n基于DHT：Chord、CAN、Pastry、Tapestry2022-3-615Napster原理(1)13245Server2022-3-616Napster原理(2)Where i

6、s file A?QueryReplysearch(A)Fetch目录服务器2022-3-617Napster优缺点n优点：只维护目录，结构简单，效率高n缺点：单点失效，存在瓶颈，法律问题2022-3-618洪泛请求模式n过程n每个Peer的请求直接广播到连接的Peersn各Peers又广播到各自的Peersn直到收到应答或 达到最大洪泛步数n特点n无广告性共享资源nGnutella 使用该算法,限于公司内通信有效n大量请求占用网络带宽,可扩展性并不一定最好n改进nKazaa 设立Super-Peer客户软件,以集中大量请求n文件分块nCache最近请求2022-3

7、-619Gnutella原理 (1)Flooding: Loop Prevention2022-3-620Gnutella原理(2)I have file A.I have file A.Where is file A?QueryReply2022-3-621Gnutella优缺点n容错性和健壮性好n覆盖网拓扑维护简单n查询代价高，可扩展性差，flooding2022-3-622KaZaA原理n介于Napster和Gnutella之间n无中心，但有中心簇集n层次结构，一个节点是超级节点或属于某超级节点的子节点n超级节点间采用flooding机制搜索2022-3-623KaZaA原理132Sup

8、er Nodes:1,2,32022-3-624KaZaA原理Where is file A?Querysearch(A)-8search(A)-0Replies802022-3-625有结构系统的文件路由模式n过程n每个网上Peer分配一个随机ID,并知道其他Peers的给定号码n当共享文件发布到系统上时,根据文件名字和内容Hash成为IDn每个Peer将根据该ID向该文件路由n该过程重复执行,直到最近的PeerID是现行Peer的IDn每个路由操作还保持文件副本在本地n当Peer请求某文件时,该请求将用该文件的ID

9、到达Peer,过程重复直到发现文件副本,最终文件下载到请求源端2022-3-626实现文件路由算法nChord/CAN/Tapestry/Pastryn目标相同n减少路由到指定文件的P2P跳数n减少每个Peer必须保持的路由状态n算法异同n都保证算法的跳数与Peer群组的大小相关n或都指出算法能以高概率完成n方法上的差别很小2022-3-627四个算法的比较nChordn每个Peer保持LogN其他Peer的踪迹(N是群组的全部Peer数)n当Peer加入或离开时,高优化算法版本仅需关注LogN个Peers的变化nCANn每个Peer保持少于LogN个其他Peers的踪迹n在插入和删除时仅这些

10、Peers受影响n其路由表较小,但到达的路径较长n可能更适合动态通信nTapestry与Pastry很相似n除减少跳数外,还积极削减每个P2P跳上的时延2022-3-628路由表n路由表内容nid文件标识符nnext_hop存储文件id的另一个节点nfile保存在本地的文件标识符为id的文件n搜索过程n如果文件id存储在本地，停止搜索，上传文件n如果不在本地，搜索路由表中最接近的id，将请求转到next_hopn如果所有节点都没有找到，返回失败，返回路由表中下一个最接近的idIDNext_hopfile2022-3-629文件路由原理 4 n1 f412 n2 f12 5 n3 9 n3 f9

11、 3 n1 f314 n4 f14 5 n314 n5 f1413 n2 f13 3 n6n1n2n3n4 4 n1 f410 n5 f10 8 n6n5query(10)1234452022-3-630Distributed Hash Table（DHT）分布式分布式Hash表表分布式应用分布式应用get (key)datanodenodenode.put(key, data)查找服务查找服务lookup(key)node IP address(文件共享文件共享)(DHash)(Chord)2022-3-631结构化覆盖网的路由q加入：开始时，联系一个“bootstrap”节点，加入分布式数

12、据结构，获得一个节点idq发布：向数据结构中最近的节点发布文件id的路由信息q搜索：向路由表中最近的节点查询文件id，数据结构保证查询会找到发布节点q获取：两个选项n查询到的节点保存有文件，则从查询结束的节点获取n查询到的节点返回结果：节点x有文件，则从节点x获取q DHT示例Chord:在一维空间（环）中给每个节点和文件一个唯一的idn例如从0.2m中选取n通常是文件和IP地址的hash2022-3-632ChordnChord系统提出了一个利用一致性的Hash函数将所有结点和文件对应到一个N个整数形成的逻辑环上的P2P系统。n每一个结点有一个代码（node ID）表示在逻辑环上的位置。结点

13、代码是利用结点IP通过一个Hash函数（node hash function）计算得到。n每一个文件用一个文件代码（File ID）表示，文件代码是文件名通过一个Hash函数（file hash function）计算得到。2022-3-633Chord环定义n在一个稳定状态下，在有N个结点（peer）的系统中，每一个结点维护一个O（logN）个结点的路由状态表。nVertex Set: 0N-1 : N is a power of 2nEdge Set: (u, v) | v-u is a power of 2nex: N=64, u=0, then the neighbors of u a

14、re 1, 2, 4, 8, 16, 322022-3-634Chord环定义qHash函数: node InodeID, data DdataIDqnodeID, dataID in 0, ., N -1 where N =2mqPut data D on node I, so that nodeID(I) is smallest nodeID larger than or equal to dataID(D)qGiven key=dataID(D), how to find successor(key) ? Lookup(key)=successor(key), find the firs

15、t live nodeID which is key.qFinger table: node k stores pointers to k+1, k+2, k+4 ., k +2m -1 (mod N) qFind node for every data in O(log(N) steps; O(log(N) storage per node0 1 2 3 4 . 7 8 9 . 14 15 16 . . . n-2 n-12022-3-635Chord环Chord环的 finger表121314171819202223302928272625211516240123456783191011A

16、ctual nodeNode identifier24345791217205767812121220201315141516202020281Node 1s finger tableNode 4s finger tableNode 12s finger tableStart = k + 2i (modulo 2m) IP addr of successor (start )A ring of 25 node Ids. m =5, i = 0m-1 .2022-3-637Chord环：路由算法When node k receives the lookup(key),If k key next(

17、k), return next(k) elseif key k at intermediate node k, return kelse forward to f such that f=MAXfingers|fingerskeyChord环：路由实例12131417181920222330292827262521151624012345678319101124345791217205767812121220201315141516202020281Node 1s finger tableNode 4s finger tableNode 12s finger tableStart = k +

18、2i (modulo 2m) IP addr of successor (start )Look up key=14,15,16,17 at node 1.2022-3-639CANn基于虚拟的d维笛卡尔坐标空间实现数据组织和查找功能。n利用类似网络路由的方式来寻找文件所在的位置。n在CAN系统中，每一个结点利用一个坐标路由表(coordinate routing table)记录在坐标空间中相邻结点的IP地址和空间位置。n当收到一个文档查询的请求时，起始结点先利用Hash函数计算出此文件所在的坐标，并附在查询请求中。n当一个结点收到此文件的查询请求时，先看查询文件是否存在，若存在，则返回此文

19、件；否则，利用查找路由表找出一个与查找文件位置最近的结点；以此继续下去。2022-3-640CAN2022-3-641P2P的关键技术特性（的关键技术特性（1）（1）非集中化）非集中化:置疑置疑 C/S 模式模式n集中化n在访问权限和安全上容易管理n但不可避免导致:低效/瓶颈/资源浪费n尽管硬件性能和成本有了改进,但建立和维护集中化知识库成本高昂,需要人员智能化地建立,保持信息的相关和更新n非集中化:更强有力的思想n强调用户端所有权,对数据和资源的控制n每个Peer都是平等的参与者n实现更困难(无全局服务器,看不到全局Peers及其文件)n这也是当前混合模式存在的原因2022-3-642（2）

20、可扩展性）可扩展性n可扩展性受限的主要原因n需要完成大量的集中化操作:如同步与一致n需要维护许多状态n固有的并行性应用展开n用来表示计算的编程模式nP2P解决可扩展性问题nNapster在其服务的高峰用户达到 600万n然SETIhone2002年止用户 仅接近350万.因为它集中在并行度有限的任务上,依靠因特网上的可用计算力来分析从天文望远镜收集来的数据,搜索外星生命nAvaki通过提供分布式对象模型来解决可扩展性问题2022-3-643（3）匿名n目的目的n重要目的是让人们使用系统时不用关心法律问题和其他节外重要目的是让人们使用系统时不用关心法律问题和其他节外生枝的问题生枝的问题n进一步目

21、的可能使数字内容的审查制度形同虚设进一步目的可能使数字内容的审查制度形同虚设n匿名形式匿名形式n作者作者:可以不标识文件的作者或创建者可以不标识文件的作者或创建者n发布者发布者:可以不标识对系统而言的文件发行者可以不标识对系统而言的文件发行者n读者读者:可以不标识文件的读者或其他消费数据者可以不标识文件的读者或其他消费数据者n服务器服务器:可以不标识含有未被标识文件的服务器可以不标识含有未被标识文件的服务器n文件文件:服务器并不知道它存储的是什么文件服务器并不知道它存储的是什么文件n查询查询:服务器并不告诉它正用何文件在响应用户的查询服务器并不告诉它正用何文件在响应用户的查询2022-3-6446种不同技术-适合不同匿名方式n多播使接收者匿名