宽带媒体服务技术之对等网络-PowerPointPre

1、第三章 第二代P2P网络无结构P2P体系Gnutella、KaZaA、eDonkey、Freenet1章节内容3.1 Gnutella：纯分布式无结构P2P网络3.2 KaZaA：基于超节点的无结构P2P网络3.3 eDonkey/eMule：分块下载的双层无结构P2P网络3.4 Freenet：自由、安全、匿名的无结构P2P网络3.5 无结构P2P网络的特点23.1 Gnutella：纯分布式无结构P2PGnutella的历史Nullsoft公司，MP3播放软件WinAmp的发明人Justin Frankel、Tom Pepper开发2000年3月14日在网站上公开Gnutella软件一个半

2、小时后，母公司AOL(American Online)担心步Napster后尘，关闭了网站数千名MP3迷下载了软件并公开与改造其纯分布式无结构P2P网络思想广泛流传Gnutella已不单纯对应具体软件，而是当作一种典型的无结构P2P网络协议3一、Gnutella体系的工作原理Gnutella协议0.4版(0.6版加入了超结点Ultrapeer，结构有变化)4协议开发者称Peer为Servent(Server +Client)，网络中只有peer，没有serverGnutella覆盖网上每个结点对应一台实际的计算机每条连接对应一条点到点的链路覆盖网上的连接由每个peer保存的“邻居结点”信息确定

3、，有一个邻居结点即对应有一条边5新结点加入时，必须首先连接到“众所周知”几乎总是在线的Gnutella结点(称为“自举”结点、“入口结点”)Gnutella网中的消息可以被广播或回播(back-propagate，沿广播的反向路径回传消息)，协议设计的支持机制：每条消息具有一个随机产生的全局唯一标识符GUID(16字节)以互相区分每个结点缓存最近路由的消息以支持回播并阻止不必要的重广播每条消息都有TTL以避免过度消耗网络资源6Gnutella的典型消息组成员消息：PING，PONG新结点加入时广播PING消息，或用来探测其它结点是否仍然存在(心跳)结点收到PING消息后，可以决定是否回播PON

4、G消息，以及是否将PING转发给邻居，PONG消息包含结点IP,port,共享文件数量大小查询消息：QUERY，QUERY RESPONSEQUERY消息用来查询文件,包含查询内容与最小响应速度等附加信息,但不包含源结点信息RESPONSE消息包含文件下载的必须信息及该结点的nodeID，沿QUERY消息路径回播7文件传输消息：GET，PUSH结点收到QUERY RESPONSE消息后用GET消息请求获得文件对处于防火墙后因而不能直接响应文件请求的结点，使用PUSH消息请求防火墙后的文件拥有者主动建立到自己的连接8Gnutella的文件检索过程泛洪式搜索(flooding search)， 系

5、统开销大有限深度TTL(Time to Live)， 不保证一定查询到已有文件9Gnutella网络的维护各结点使用PING、PONG消息探测其他结点存在与否，在收到PING消息后，可以自主决定是否回播PONG，并根据TTL数值决定是否继续广播PING消息具有一定的自组织和自适应性10二、Gnutella网络的性能分析Ripeanu,2001,2002、Saroiu et al., 2002,2003、Adar & Huberman, 2002Gnutella用户的连接带宽仅在Query response消息中作为辅助信息回播，因此，Gnutella网络中不共享文件的用户或其共享的文件与查询请

6、求一直不匹配的用户，不会主动发布带宽Gnutella网络中结点功能平等，但能力有差异（异构性），如连接带宽在无组织的Gnutella网络组织方式下，70%的结点承受较高时延(280ms)11用户连接时间与Napster类似，超过50%的用户连接时间6h25%的用户不共享任何文件，75%的用户共享文件数低于100，仅7%共享文件超过1000，即文献中的Free-Riding(搭便车)现象，对网络的高效工作不利Gnutella网络相当于社会网络，可用幂律(Power-law)分布网络近似，拥有连接数L的结点占网络总结点的份额正比于L-a,a是取决于网络本身的常数因子，Gnutella网络a=2.3

7、，容错性较高12早期Gnutella网络中，PING消息占所有消息的50%以上，显示其自适应机制低效。改进后的Gnutella网络，对用户真正有用的Query消息占总消息的90%以上Gnutella覆盖网络与物理网络的拓扑一致性较低，影响工作效率13采用Gnutella协议的P2P网络应解决：结点异构性：充分利用结点能力Free-Riding：鼓励上传，限制或剥夺Free-Rider的权利保持高容错性：高效的机制检测和恢复网络分割继续优化查询机制，TTL的取值拓扑一致性14三、Napster与Gnutella的比较共同点P2P的文件共享思想系统中的对等实体(peer)之间是对称的，既是客户又是

8、服务器，既提供下载又提供上传可扩展性都不高：但Napster是因为C/S结构，Gnutella是因为泛洪搜索策略造成的系统开销都有结点异构性问题以及搭便车现象15不同点Napster有服务器，Gnutella没有，因此工作机制完全不同网络结构不同：混合式与纯分布式，Gnutella在Internet网上构建了覆盖网，这是后来的P2P网络都会做的一项基础性工作Napster中文件只要存在一般都能查询到，Gnutella不一定Napster只在服务器故障时出错，Gnutella可能因为结点信息陈旧而出错，最大的问题是可能导致网络分割16Gnutella协议0.6版层次化的无结构P2P网络173.2

9、 KaZaA：基于超结点的无结构P2P网络2000年7月，基于FastTrack协议Niklas及Friis，P2P创业家，Joltid, Altnet, SkypeFastTrack协议引入超结点SuperNode，开发结点异构性18一、KaZaA的工作原理KaZaA是私有协议，并对消息加密，对其理解基于测量与分析的结果19节点异构性带宽、处理能力、存储容量、NAT访问方式超结点高带宽、高处理能力、大存储容量、不受NAT限制功能上类似Napster中的服务器，但并非专门、永久的，经常由普通结点转变而来20普通结点加入网络时选择一个“父超结点”，并维持一条半永久的TCP连接，将其共享的文件元数

10、据(也称“文件索引”)上传文件索引分布在KaZaA的超结点中，作用是将文件标识符映射到文件所在的结点IP文件索引包括：文件名、文件大小、文件内容Hash值、文件描述符(如艺术家、专辑名)文件内容Hash值的作用：当下载失败时，可自动搜索文件，不必再做关键词查询21用户查询文件向父超结点发送带有文件关键词的查询消息超结点在自己的数据库中寻找匹配的文件索引返回给用户文件所在的IP地址、port、文件元数据超结点间局部保持着长期的TCP连接，构成超结点覆盖网文件查询局部性问题22二、KaZaA协议的应用KaZaA用户应当具有4个软件构件KMD(KaZaA Media Desktop)存储在Windo

11、ws注册表中的软件环境信息，其中包含一个有200个超结点信息(IP、port)的列表(超结点列表缓存)DBB文件：包含用户希望共享的文件的元数据DAT文件：每个DAT文件是一个部分下载的文件，下载完成后，将被重命名为下载的原始文件23KaZaA用户间的4种TCP通信方式信号通信，包括：为建立连接的握手通信，将DBB文件从普通结点上传到超结点，超结点列表更新、查询和回复。所有的信号通信都加密文件传输通信：用户间直接的文件传输，以HTTP消息发送，不加密商业广告：通过HTTP发送实时消息通信：采用Base64编码24三、KaZaA的技术细节自适应通过结点间交换超结点列表实现每次普通结点连接到超结点

12、，后者立刻回送超结点更新列表，其中第一项为自己的IP,port以及工作负载值相邻的超结点间也交换超结点更新列表结点间的连接普通结点与超结点（一对多UDP，选择父超结点）超结点之间2526KaZaA的防火墙穿透：动态端口KaZaA的NAT穿透A无法与NAT后的B建立直接的TCP连接A发送请求到B的父超结点S，S发送消息到B，通知B应该由B发出到A的连接请求，主动建立一条到A的TCP连接，A通过此连接从B下载文件。称为“连接反转”(connection reversal)27四、KaZaA的性能分析基于文献Liang et al., 2004; 2005的测量结果KaZaA网络的超结点数在2500

13、0-40000之间，每个超结点平均与40-60个超结点连接，与60-150个普通结点连接KaZaA覆盖网动态性：连接保持时间ON-SN平均34min，38%低于30minSN-SN平均11min，32%低于30min结点主动改变连接，超结点频繁交换列表28KaZaA网络局部性60%的SN-SN连接RTT (往返时间round trip time)小于50ms，40%的ON-SN连接RTT小于5ms超结点返回给普通结点的超结点列表中，很高比例的超结点与该普通结点的IP前缀相似结论：采用了提高局部性的方法KaZaA索引管理13%的ON上传了超过80%的元数据SN之间不交互索引信息29五、KaZaA

14、网络总结首次显式开发P2P网络节点异构性为缓解无结构P2P网络的查询局部性问题，并保持KaZaA网络的自适应性，KaZaA用户间频繁地交换超结点更新列表，根据列表改变原有连接测量结果显示KaZaA网络考虑了局部性因素Free-Riding现象在KaZaA网络中依然存在KaZaA通过使用动态端口和连接反转的方法，有效地穿透防火墙和NAT，拓宽了网络适用范围303.3 eDonkey/eMule：分块下载的双层无结构P2P网络2000年eDonkey出现，特点：文件分块，可并行下载使用文件内容散列值验证数据完整性双层无结构，使用超结点作为“服务器”基于Overnet分布式搜索网络eMule出现于2

15、002年5月，是对eDonkey客户端的出色改进31一、eDonkey工作原理32eDonkey客户加入网络首先连接到“入口服务器”列表中离自己最近(时延最小)的一台服务器通过该入口服务器获得一个普通服务器列表，从中选择最合适的服务器建立连接并断开与入口服务器的连接客户将自己的共享文件信息发给服务器客户从存放自己信息的服务器查询文件，如无结果，则可以向其它服务器重新查询33eDonkey客户下载文件前，首先通过查询获得文件提供者列表，然后向列表中的每个文件提供者请求“上传槽”(upload slot)文件提供者将请求放进上传队列的“等待列表”，等到条件满足时才给该请求分配“上传槽”并将它放进“

16、上传列表”，此时提供者向请求者发起TCP连接，决定要发送哪些分块，然后发送数据自适应性每个下载者必须周期性地(40s)向上传者重发下载请求，否则原连接将被关闭eDonkey服务器间以较长周期交换服务器列表34二、eDonkey文件分块类似BT的文件分片，实现了“多源下载”机制文件首先被分块chunk，通常9500KB每个chunk分成多个片段segment，其大小取决于“智能错误处理”(intelligent corruption handling,ICH)机制用来进行比分块更小的数据单元错误检查，从而不必在出错时丢弃整个分块片段分成小块block，通常180KB35三、eDonkey性能分析

17、部分类似KaZaA，部分类似BT，定性分析可参照二者4662端口专用于客户间TCP连接下载连接传输总量占所有流传输总量的70.5%，不高在所建立的TCP连接中，只有2.24%用作下载连接，不如BT高效的重要原因36四、eDonkey网络总结双层：服务器层+客户层，类似于KaZaA， 服务器提供文件索引和交换服务器列表，开发了结点异构性将文件逐级分成分块、片段、小块，从而提供了类似BT的多源文件下载机制，并且对文件的完整性检查也有了更细的粒度为适应动态的网络环境，eDonkey客户通过上传队列来管理客户间的连接，只有获得上传槽的连接才能真正传递数据，并且每个连接都有周期性检测以处理异常中断，提高

18、了工作效率靠服务器间周期性地更新服务器列表维护自适应性，eDonkey的流行性验证了该机制是良好的373.4 Freenet：自由、安全、匿名的无结构P2P网络自由网的概念由Clarke于1999年提出，2000年3月推出第一版，更新很慢Freenet的理念：共享Internet计算机资源，组建一个自由、安全、匿名的信息发布和获取的平台(不同于其它P2P网络)Freenet结点划出一部分硬盘作为公用存储空间，但其中数据加密，仅对有权限者开放Freenet匿名性的本质在于其隧道路由机制Freenet过于自由、界面不友好限制其发展38一、Freenet的密码学基础Freenet中的文件以Hash值

19、作为标识，使用SHA-1安全散列函数生成Freenet使用三种不同类型的文件标识，KSK，SSK，CHK，分别完成不同的功能，是Freenet的核心设施，三者相互独立，可以合并使用39KSKKeyword-signed key，关键词签名标识，用于构建Freenet的全局名空间用户在网络中存储文件时，必须给文件指定一个很短的描述性字符串作为输入产生一对非对称密钥，公钥被Hash以产生文件标识，私钥用来给文件做数字签名，附带提供了文件的完整性检查字符串本身被作为密钥来加密原来的文件为让其他人获取文件，只需发布该文件的描述性字符串问题：用户选取的字符串容易相同从而文件标识相同40SSKSigned

20、-subspace key，签名子空间标识，用以构建Freenet的个人名空间用户通过随机地产生一对非对称密钥来标识自己的名空间存储文件时，首先也是指定一个很短的描述性字符串，然后分别Hash该字符串和名空间公钥，再将两个Hash值异或，再次Hash异或值产生文件标识；私钥用来给文件签名，但比KSK安全；字符串仍作为密钥加密原来的文件发布文件时，同样发布描述性字符串及文件标识即可41CHKContent-hash key，内容散列标识，实现文件的更新与分割，将文件直接Hash得到的散列值就是它的CHKCHK使用一个随机产生的密钥加密文件发布文件时，只需发布解密密钥与文件标识通常与SSK一起使用

21、，实现文件更新用CHK存储文件，用SSK存储一个间接文件，此文件的内容就是CHK，相当于指向真实文件的指针更新文件时，先用新的CHK存储新文件，使用原来的SSK再存储一个新的间接文件，原间接文件所在的结点发现文件标识冲突，确认签名合法后更新间接文件42显然，Freenet中的文件更新仅仅是间接文件的更新，新旧文件实际共存于网络之中，后者可通过旧CHK访问CHK用于文件分割用户将文件分成多个部分，每部分使用它自己的CHK来存储，最后存储一个间接文件（或者多层的间接文件）来指向文件的各个部分分割的好处：减少对单个结点存储容量和带宽的需求；对抗通信量分析43二、Freenet中数据的查询与获取基于文

22、件标识的“导向路由”为获取文件，用户首先获得或计算出文件标识，同时设置好请求消息的跳数限制，然后在自己的路由表里查找与该文件标识最接近的文件标识并把请求发送给与之相应的结点接收到请求的结点如果拥有该文件，则回送消息，否则按前述方法继续转发，若最终查询文件被回送，该结点除了将文件回传给请求者，还会在自己的数据库里缓存该文件，并在自己的路由表里创建一个指向新项该文件的数据源44当某个结点尝试所有可路由结点仍无结果时，则返回失败消息给自己的前一跳，由后者尝试新的下一跳，即“深度优先”搜索策略，直至达到跳数限制（注：跳数可在途中任意减少）安全路由路由表自适应更新威胁到了网络的安全性和匿名性Freene

23、t同意消息传送路径上的每一个结点都可以单方面修改消息，将消息原来的请求者或者文件源改成任意一个结点45简单示例46这样的数据查询和获取机制，可以极大提高效率，即，若某个结点在其他结点的路由表中被列为是与某个文件相关的结点，则很可能会收到越来越多的对该文件的请求或与该文件相近的文件请求，产生“标识集群”效应。随着时间的推移，文件被复制得更多更优化，结点路由表表项也更多更“近”47三、Freenet中数据的存储与管理存储数据用户使用文件标识中的一种（KSK, SSK, CHK）给文件计算标识，并设置请求消息的跳数限制，然后发送文件插入消息到Freenet网收到文件插入消息的结点，首先检查自己的数据

24、库中是否有该文件标识，有则回送此文件，请求方据此判断是该文件确实已经存在还是文件标识碰巧冲突，对前者用户不需要再插入，对后者重新计算文件标识再做插入48当已达到跳数限制且未检测到文件标识冲突时，回送“一切顺利”的消息，直至到达发出最初请求的用户，该用户沿此路径插入文件，路径上每个结点在其路由表中增加与此文件标识相关的项（对应结点为虚拟的文件源）49存储机制与网络性能文件通常被存储到已经拥有相近标识文件的结点上，加强了“标识集群”效应新结点可以通过插入文件宣布自己的存在恶意结点不仅无法通过插入与已有文件标识相同的垃圾文件来“排挤”原文件，反而促使原文件的信息在网络中更广泛传播50数据管理结点的存

25、储区（大小由用户指定）按照最近使用优先（least recently used,LRU）方式管理被替换掉的旧文件在路由表中对应的项还会保留，直至路由表也发生超容量替换LRU对存储的利用高效，但无法保证某个文件在网络中至少有一份拷贝存在51数据私密性文件经过加密后存放，存放结点用户无法获知文件内容，满足了数据的保密性需求，且Freenet用户可以否认对任何关于其数据库中文件内容的了解Freenet将网络中所有用户的存储区组织成了一个巨大的分布式系统，并且这个系统对于每个用户来说都是透明和不可知的52四、Freenet网络新结点加入Freenet新结点的标识选取要求为了正确、高效地路由，该标识应该

26、全局一致出于安全性考虑，不能让其他结点通过某些属性计算出结点标识（用于对网络的恶意攻击）Freenet采用加密协议选取标识新结点选择一个随机的“种子”并发送一条布告消息给某个现存的结点，其中包含自己的IP、种子的Hash值及跳数限制53收到该消息的结点也产生一个随机的种子将该种子与消息中的Hash值异或对结果进行Hash产生一个“承诺”(commitment)从自己的路由表中随机选择一个结点发给它新的布告消息（其中包含“承诺”）这个过程一直继续下去形成一条链，直至布告消息中的跳数限制清零最后一个收到布告消息的结点只产生自己的种子，不再做其他的事54整个过程结束以后，这条链中所有的结点都公布它们

27、各自的种子，所有种子的异或值就是新结点的标识链上的每个结点将新结点的标识加入路由表对“承诺”的检查使得链中的每个结点都确认其它结点所公布的种子是真实的，因此，Freenet所采用的链式方法实际上产生了一个全局一致的随机的结点标识，并且这个标识不可能被某个恶意加入者影响55五、Freenet协议细节Freenet协议面向数据包并且使用了相互独立的消息，每条消息包含一个随机产生的事务ID，因此结点可以追踪插入、查询消息的状态一个跳数限制，减少攻击者通过跳数限制所能获得的信息，在跳数限制减少到1以后消息仍有继续往前传的概率（跳数限制一直为1）一个深度计数器，消息每走一跳深度计数器+1回复结点以此为依

28、据设置回复消息的跳数限制56Freenet事务一般从结点发送的握手消息开始，其中包含发送者的IP（可能是虚拟的）接收结点回复后，建立的连接可以持续几个小时，在此期间两结点之间随后的事务不需要再次握手为获取数据，用户发送“请求数据”消息，包含事务ID、跳数限制、深度计数器和查询关键码；同时开启一个定时器并根据跳数限制设定时间，若定时用完还未收到回复，就认为查询失败；当请求数据的消息被处理时，远处的结点可能会周期性地回发“重设定时器”消息，从而发送者可以继续等待57如果数据请求成功，提供数据的结点会回送“发送数据”消息，包含请求者所要的数据和数据提供者的地址（可能虚拟）如果数据请求失败，且跳数限制

29、用完，回送“未发现”消息；如果失败但跳数未用完，通常是因为找不到可行的非循环的路径，回送“继续请求”消息，包含剩下的跳数，请求信息的发送者收到此消息后将尝试新的下一跳58为存储数据，用户发送“插入请求”消息，包含事务ID、跳数限制、深度计数器和“建议”关键码（用户建议采用的文件标识）如果插入导致文件标识冲突，远处结点返回“发送数据”消息，并返回现存的文件“未找到”消息，表示现存文件未找到，但路由表有所指向如果没有文件标识冲突，但消息在跳数限制用完之前就跑完了所有的结点，远处结点将回送“继续请求”消息，表示不能联系到足够多的结点导致失败跳数限制用完且没有文件标识冲突时，返回“插入应答”消息，文件

30、插入者发送“发送插入数据”消息，包含要插入的文件，沿途结点缓存该文件59六、Freenet性能分析路由效率结点的文件缓存、路由表都是逐步构造出来的初期路由效率低，路由跳数大；后期“标识集群”路由效率提高，直至平稳可扩展性P2P网络中决定可扩展性的最重要因素是路由跳数h与网络结点总数N之间的关系，达到对数关系即认为是高可扩展的Freenet服从对数关系，即hO(logN)60七、Freenet的安全性和匿名性分析Freenet设计的目标和初衷系统的匿名性：发送者匿名、接收者匿名、文件标识匿名、关系匿名Freenet提供了很好的发送者匿名和接收者匿名，但无法进行文件标识匿名，因其依靠文件标识路由；

31、研究者提出“预定路由”的辅助路由方法，对消息加密并以此指定路由61防范DOS(denial of service,服务拒绝)攻击攻击者可能通过插入大量的垃圾文件破坏Freenet或降低其工作效率散列支付（hash cash），规定向Freenet网中插入文件的用户在插入之前必须做一次耗时的计算作为插入文件的支付代价，降低插入速度将每个Freenet结点的存储区分成两部分，分别存放旧文件与新插入文件，这样攻击者无论插入多少垃圾文件，最多只能占用一般存储区62八、Freenet体系总结突出特点：自由、安全、匿名的P2P网络利用每个参加者作为一个结点，划分一部分硬盘用作存储空间，存放经过加密的数据，

32、存放者不知道内容，这是Freenet安全的核心Freenet中文件查询通过一条“代理结点链”从一个结点传到另一个结点，路径上的每个结点只知道该请求的前一跳结点和由它决定的后一跳结点，对路径上的其他结点一无所知，这种“隧道路由”是Freenet匿名的核心Freenet能够自适应地将使用到的文件缓存到更接近使用者的服务器上，即自动复制网上的内容63Freenet中消息是通过结点路由表中保存的文件标识来导向路由的，文件标识有三种：KSK、SSK和CHK。消息路由采用改造过的图的深度优先算法Freenet中插入文件之前先要检测是否存在文件标识冲突。结点存储区按照LRU方法更新，文件可以分割成多份保存在多个结点中。每个新结点加入Freenet网时，其结点标识是由