《宽带媒体服务技术之对等网络PowerPointPre》由会员分享，可在线阅读，更多相关《宽带媒体服务技术之对等网络PowerPointPre（72页珍藏版）》请在金锄头文库上搜索。
1、宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络科大10系 王雷第三章 第二代P2P网络无结构P2P体系Gnutella、KaZaA、eDonkey、Freenet1宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络章节内容o3.1 Gnutella：纯分布式无结构P2P网络o3.2 KaZaA：基于超节点的无结构P2P网络o3.3 eDonkey/eMule：分块下载的双层无结构P2P网络o3.4 Freenet：自由、安全、匿名的无结构P2P网络o3.5 无结构P2P网络的特点2宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络3.1 Gnutella：纯分布式无结构P2PoGnu
2、tella的历史nNullsoft公司，MP3播放软件WinAmp的发明人Justin Frankel、Tom Pepper开发n2000年3月14日在网站上公开Gnutella软件一个半小时后，母公司AOL(American Online)担心步Napster后尘，关闭了网站n数千名MP3迷下载了软件并公开与改造n其纯分布式无结构P2P网络思想广泛流传nGnutella已不单纯对应具体软件，而是当作一种典型的无结构P2P网络协议3宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络一、Gnutella体系的工作原理oGnutella协议0.4版(0.6版加入了超结点Ultrapeer，结构有
3、变化)4宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o协议开发者称Peer为Servent(Server +Client)，网络中只有peer，没有serveroGnutella覆盖网上每个结点对应一台实际的计算机o每条连接对应一条点到点的链路o覆盖网上的连接由每个peer保存的“邻居结点”信息确定，有一个邻居结点即对应有一条边5宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o新结点加入时，必须首先连接到“众所周知”几乎总是在线的Gnutella结点(称为“自举”结点、“入口结点”)oGnutella网中的消息可以被广播或回播(back-propagate，沿广播的反向路径回传消
4、息)，协议设计的支持机制：n每条消息具有一个随机产生的全局唯一标识符GUID(16字节)以互相区分n每个结点缓存最近路由的消息以支持回播并阻止不必要的重广播n每条消息都有TTL以避免过度消耗网络资源6宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络Gnutella的典型消息o组成员消息：PING，PONGn新结点加入时广播PING消息，或用来探测其它结点是否仍然存在(心跳)n结点收到PING消息后，可以决定是否回播PONG消息，以及是否将PING转发给邻居，PONG消息包含结点IP,port,共享文件数量大小o查询消息：QUERY，QUERY RESPONSEnQUERY消息用来查询文件,
5、包含查询内容与最小响应速度等附加信息,但不包含源结点信息nRESPONSE消息包含文件下载的必须信息及该结点的nodeID，沿QUERY消息路径回播7宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o文件传输消息：GET，PUSHn结点收到QUERY RESPONSE消息后用GET消息请求获得文件n对处于防火墙后因而不能直接响应文件请求的结点，使用PUSH消息请求防火墙后的文件拥有者主动建立到自己的连接8宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络Gnutella的文件检索过程o泛洪式搜索(flooding search)， 系统开销大o有限深度TTL(Time to Live)，
6、 不保证一定查询到已有文件9宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oGnutella网络的维护n各结点使用PING、PONG消息探测其他结点存在与否，在收到PING消息后，可以自主决定是否回播PONG，并根据TTL数值决定是否继续广播PING消息n具有一定的自组织和自适应性10宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络二、Gnutella网络的性能分析oRipeanu,2001,2002、Saroiu et al., 2002,2003、Adar & Huberman, 2002oGnutella用户的连接带宽仅在Query response消息中作为辅助信息回播，因此
7、，Gnutella网络中不共享文件的用户或其共享的文件与查询请求一直不匹配的用户，不会主动发布带宽oGnutella网络中结点功能平等，但能力有差异（异构性），如连接带宽o在无组织的Gnutella网络组织方式下，70%的结点承受较高时延(280ms)11宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o用户连接时间与Napster类似，超过50%的用户连接时间6ho25%的用户不共享任何文件，75%的用户共享文件数低于100，仅7%共享文件超过1000，即文献中的Free-Riding(搭便车)现象，对网络的高效工作不利oGnutella网络相当于社会网络，可用幂律(Power-law)
8、分布网络近似，拥有连接数L的结点占网络总结点的份额正比于L-a,a是取决于网络本身的常数因子，Gnutella网络a=2.3，容错性较高12宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o早期Gnutella网络中，PING消息占所有消息的50%以上，显示其自适应机制低效。改进后的Gnutella网络，对用户真正有用的Query消息占总消息的90%以上oGnutella覆盖网络与物理网络的拓扑一致性较低，影响工作效率13宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o采用Gnutella协议的P2P网络应解决：n结点异构性：充分利用结点能力nFree-Riding：鼓励上传，限制或
9、剥夺Free-Rider的权利n保持高容错性：高效的机制检测和恢复网络分割n继续优化查询机制，TTL的取值n拓扑一致性14宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络三、Napster与Gnutella的比较o共同点nP2P的文件共享思想n系统中的对等实体(peer)之间是对称的，既是客户又是服务器，既提供下载又提供上传n可扩展性都不高：但Napster是因为C/S结构，Gnutella是因为泛洪搜索策略造成的系统开销n都有结点异构性问题以及搭便车现象15宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o不同点nNapster有服务器，Gnutella没有，因此工作机制完全不同n网
10、络结构不同：混合式与纯分布式，Gnutella在Internet网上构建了覆盖网，这是后来的P2P网络都会做的一项基础性工作nNapster中文件只要存在一般都能查询到，Gnutella不一定nNapster只在服务器故障时出错，Gnutella可能因为结点信息陈旧而出错，最大的问题是可能导致网络分割16宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oGnutella协议0.6版n层次化的无结构P2P网络17宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络3.2 KaZaA：基于超结点的无结构P2P网络o2000年7月，基于FastTrack协议oNiklas及Friis，P2P创业
11、家，Joltid, Altnet, SkypeoFastTrack协议引入超结点SuperNode，开发结点异构性18宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络一、KaZaA的工作原理oKaZaA是私有协议，并对消息加密，对其理解基于测量与分析的结果19宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o节点异构性n带宽、处理能力、存储容量、NAT访问方式o超结点n高带宽、高处理能力、大存储容量、不受NAT限制n功能上类似Napster中的服务器，但并非专门、永久的，经常由普通结点转变而来20宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o普通结点加入网络时选择一个“父超结点
12、”，并维持一条半永久的TCP连接，将其共享的文件元数据(也称“文件索引”)上传o文件索引分布在KaZaA的超结点中，作用是将文件标识符映射到文件所在的结点IPo文件索引包括：文件名、文件大小、文件内容Hash值、文件描述符(如艺术家、专辑名)o文件内容Hash值的作用：当下载失败时，可自动搜索文件，不必再做关键词查询21宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o用户查询文件n向父超结点发送带有文件关键词的查询消息n超结点在自己的数据库中寻找匹配的文件索引n返回给用户文件所在的IP地址、port、文件元数据o超结点间局部保持着长期的TCP连接，构成超结点覆盖网o文件查询局部性问题22
13、宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络二、KaZaA协议的应用oKaZaA用户应当具有4个软件构件nKMD(KaZaA Media Desktop)n存储在Windows注册表中的软件环境信息，其中包含一个有200个超结点信息(IP、port)的列表(超结点列表缓存)nDBB文件：包含用户希望共享的文件的元数据nDAT文件：每个DAT文件是一个部分下载的文件，下载完成后，将被重命名为下载的原始文件23宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oKaZaA用户间的4种TCP通信方式n信号通信，包括：为建立连接的握手通信，将DBB文件从普通结点上传到超结点，超结点列表更新、
14、查询和回复。所有的信号通信都加密n文件传输通信：用户间直接的文件传输，以HTTP消息发送，不加密n商业广告：通过HTTP发送n实时消息通信：采用Base64编码24宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络三、KaZaA的技术细节o自适应n通过结点间交换超结点列表实现n每次普通结点连接到超结点，后者立刻回送超结点更新列表，其中第一项为自己的IP,port以及工作负载值n相邻的超结点间也交换超结点更新列表o结点间的连接n普通结点与超结点（一对多UDP，选择父超结点）n超结点之间25宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络26宽带媒体服务技术之对等网络宽带媒体服务技术之对等网
15、络oKaZaA的防火墙穿透：动态端口oKaZaA的NAT穿透nA无法与NAT后的B建立直接的TCP连接nA发送请求到B的父超结点S，S发送消息到B，通知B应该由B发出到A的连接请求，主动建立一条到A的TCP连接，A通过此连接从B下载文件。称为“连接反转”(connection reversal)27宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络四、KaZaA的性能分析o基于文献Liang et al., 2004; 2005的测量结果nKaZaA网络的超结点数在25000-40000之间，每个超结点平均与40-60个超结点连接，与60-150个普通结点连接oKaZaA覆盖网动态性：连接保
16、持时间nON-SN平均34min，38%低于30minnSN-SN平均11min，32%低于30minn结点主动改变连接，超结点频繁交换列表28宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oKaZaA网络局部性n60%的SN-SN连接RTT (往返时间round trip time)小于50ms，40%的ON-SN连接RTT小于5msn超结点返回给普通结点的超结点列表中，很高比例的超结点与该普通结点的IP前缀相似结论：采用了提高局部性的方法oKaZaA索引管理n13%的ON上传了超过80%的元数据nSN之间不交互索引信息29宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络五、KaZ
17、aA网络总结o首次显式开发P2P网络节点异构性o为缓解无结构P2P网络的查询局部性问题，并保持KaZaA网络的自适应性，KaZaA用户间频繁地交换超结点更新列表，根据列表改变原有连接o测量结果显示KaZaA网络考虑了局部性因素oFree-Riding现象在KaZaA网络中依然存在oKaZaA通过使用动态端口和连接反转的方法，有效地穿透防火墙和NAT，拓宽了网络适用范围30宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络3.3 eDonkey/eMule：分块下载的双层无结构P2P网络o2000年eDonkey出现，特点：n文件分块，可并行下载n使用文件内容散列值验证数据完整性n双层无结构，
18、使用超结点作为“服务器”n基于Overnet分布式搜索网络oeMule出现于2002年5月，是对eDonkey客户端的出色改进31宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络一、eDonkey工作原理32宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oeDonkey客户加入网络n首先连接到“入口服务器”列表中离自己最近(时延最小)的一台服务器n通过该入口服务器获得一个普通服务器列表，从中选择最合适的服务器建立连接并断开与入口服务器的连接n客户将自己的共享文件信息发给服务器o客户从存放自己信息的服务器查询文件，如无结果，则可以向其它服务器重新查询33宽带媒体服务技术之对等网络宽带媒
19、体服务技术之对等网络oeDonkey客户下载文件前，首先通过查询获得文件提供者列表，然后向列表中的每个文件提供者请求“上传槽”(upload slot)o文件提供者将请求放进上传队列的“等待列表”，等到条件满足时才给该请求分配“上传槽”并将它放进“上传列表”，此时提供者向请求者发起TCP连接，决定要发送哪些分块，然后发送数据o自适应性n每个下载者必须周期性地(40s)向上传者重发下载请求，否则原连接将被关闭neDonkey服务器间以较长周期交换服务器列表34宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络二、eDonkey文件分块o类似BT的文件分片，实现了“多源下载”机制o文件首先被分块
20、chunk，通常9500KBo每个chunk分成多个片段segment，其大小取决于“智能错误处理”(intelligent corruption handling,ICH)机制用来进行比分块更小的数据单元错误检查，从而不必在出错时丢弃整个分块o片段分成小块block，通常180KB35宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络三、eDonkey性能分析o部分类似KaZaA，部分类似BT，定性分析可参照二者o4662端口专用于客户间TCP连接o下载连接传输总量占所有流传输总量的70.5%，不高o在所建立的TCP连接中，只有2.24%用作下载连接，不如BT高效的重要原因36宽带媒体服务
21、技术之对等网络宽带媒体服务技术之对等网络四、eDonkey网络总结o双层：服务器层+客户层，类似于KaZaA， 服务器提供文件索引和交换服务器列表，开发了结点异构性o将文件逐级分成分块、片段、小块，从而提供了类似BT的多源文件下载机制，并且对文件的完整性检查也有了更细的粒度o为适应动态的网络环境，eDonkey客户通过上传队列来管理客户间的连接，只有获得上传槽的连接才能真正传递数据，并且每个连接都有周期性检测以处理异常中断，提高了工作效率o靠服务器间周期性地更新服务器列表维护自适应性，eDonkey的流行性验证了该机制是良好的37宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络3.4 Fr
22、eenet：自由、安全、匿名的无结构P2P网络o自由网的概念由Clarke于1999年提出，2000年3月推出第一版，更新很慢oFreenet的理念：共享Internet计算机资源，组建一个自由、安全、匿名的信息发布和获取的平台(不同于其它P2P网络)oFreenet结点划出一部分硬盘作为公用存储空间，但其中数据加密，仅对有权限者开放oFreenet匿名性的本质在于其隧道路由机制oFreenet过于自由、界面不友好限制其发展38宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络一、Freenet的密码学基础oFreenet中的文件以Hash值作为标识，使用SHA-1安全散列函数生成oFree
23、net使用三种不同类型的文件标识，KSK，SSK，CHK，分别完成不同的功能，是Freenet的核心设施，三者相互独立，可以合并使用39宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oKSKnKeyword-signed key，关键词签名标识，用于构建Freenet的全局名空间n用户在网络中存储文件时，必须给文件指定一个很短的描述性字符串o作为输入产生一对非对称密钥，公钥被Hash以产生文件标识，私钥用来给文件做数字签名，附带提供了文件的完整性检查o字符串本身被作为密钥来加密原来的文件n为让其他人获取文件，只需发布该文件的描述性字符串n问题：用户选取的字符串容易相同从而文件标识相同40
24、宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oSSKnSigned-subspace key，签名子空间标识，用以构建Freenet的个人名空间n用户通过随机地产生一对非对称密钥来标识自己的名空间n存储文件时，首先也是指定一个很短的描述性字符串，然后分别Hash该字符串和名空间公钥，再将两个Hash值异或，再次Hash异或值产生文件标识；私钥用来给文件签名，但比KSK安全；字符串仍作为密钥加密原来的文件n发布文件时，同样发布描述性字符串及文件标识即可41宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oCHKnContent-hash key，内容散列标识，实现文件的更新与分割，将
25、文件直接Hash得到的散列值就是它的CHKnCHK使用一个随机产生的密钥加密文件n发布文件时，只需发布解密密钥与文件标识n通常与SSK一起使用，实现文件更新o用CHK存储文件，用SSK存储一个间接文件，此文件的内容就是CHK，相当于指向真实文件的指针o更新文件时，先用新的CHK存储新文件，使用原来的SSK再存储一个新的间接文件，原间接文件所在的结点发现文件标识冲突，确认签名合法后更新间接文件42宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o显然，Freenet中的文件更新仅仅是间接文件的更新，新旧文件实际共存于网络之中，后者可通过旧CHK访问nCHK用于文件分割o用户将文件分成多个部分
26、，每部分使用它自己的CHK来存储，最后存储一个间接文件（或者多层的间接文件）来指向文件的各个部分o分割的好处：减少对单个结点存储容量和带宽的需求；对抗通信量分析43宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络二、Freenet中数据的查询与获取o基于文件标识的“导向路由”o为获取文件，用户首先获得或计算出文件标识，同时设置好请求消息的跳数限制，然后在自己的路由表里查找与该文件标识最接近的文件标识并把请求发送给与之相应的结点o接收到请求的结点如果拥有该文件，则回送消息，否则按前述方法继续转发，若最终查询文件被回送，该结点除了将文件回传给请求者，还会在自己的数据库里缓存该文件，并在自己的路
27、由表里创建一个指向新项该文件的数据源44宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n当某个结点尝试所有可路由结点仍无结果时，则返回失败消息给自己的前一跳，由后者尝试新的下一跳，即“深度优先”搜索策略，直至达到跳数限制（注：跳数可在途中任意减少）o安全路由n路由表自适应更新威胁到了网络的安全性和匿名性nFreenet同意消息传送路径上的每一个结点都可以单方面修改消息，将消息原来的请求者或者文件源改成任意一个结点45宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络简单示例46宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o这样的数据查询和获取机制，可以极大提高效率，即，若某个结
28、点在其他结点的路由表中被列为是与某个文件相关的结点，则很可能会收到越来越多的对该文件的请求或与该文件相近的文件请求，产生“标识集群”效应。随着时间的推移，文件被复制得更多更优化，结点路由表表项也更多更“近”47宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络三、Freenet中数据的存储与管理o存储数据n用户使用文件标识中的一种（KSK, SSK, CHK）给文件计算标识，并设置请求消息的跳数限制，然后发送文件插入消息到Freenet网n收到文件插入消息的结点，首先检查自己的数据库中是否有该文件标识，有则回送此文件，请求方据此判断是该文件确实已经存在还是文件标识碰巧冲突，对前者用户不需要再
29、插入，对后者重新计算文件标识再做插入48宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n当已达到跳数限制且未检测到文件标识冲突时，回送“一切顺利”的消息，直至到达发出最初请求的用户，该用户沿此路径插入文件，路径上每个结点在其路由表中增加与此文件标识相关的项（对应结点为虚拟的文件源）49宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o存储机制与网络性能n文件通常被存储到已经拥有相近标识文件的结点上，加强了“标识集群”效应n新结点可以通过插入文件宣布自己的存在n恶意结点不仅无法通过插入与已有文件标识相同的垃圾文件来“排挤”原文件，反而促使原文件的信息在网络中更广泛传播50宽带媒体服务技
30、术之对等网络宽带媒体服务技术之对等网络o数据管理n结点的存储区（大小由用户指定）按照最近使用优先（least recently used,LRU）方式管理n被替换掉的旧文件在路由表中对应的项还会保留，直至路由表也发生超容量替换nLRU对存储的利用高效，但无法保证某个文件在网络中至少有一份拷贝存在51宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o数据私密性n文件经过加密后存放，存放结点用户无法获知文件内容，满足了数据的保密性需求，且Freenet用户可以否认对任何关于其数据库中文件内容的了解oFreenet将网络中所有用户的存储区组织成了一个巨大的分布式系统，并且这个系统对于每个用户来说
31、都是透明和不可知的52宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络四、Freenet网络新结点加入oFreenet新结点的标识选取要求n为了正确、高效地路由，该标识应该全局一致n出于安全性考虑，不能让其他结点通过某些属性计算出结点标识（用于对网络的恶意攻击）oFreenet采用加密协议选取标识n新结点选择一个随机的“种子”并发送一条布告消息给某个现存的结点，其中包含自己的IP、种子的Hash值及跳数限制53宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n收到该消息的结点o也产生一个随机的种子o将该种子与消息中的Hash值异或o对结果进行Hash产生一个“承诺”(commitmen
32、t)o从自己的路由表中随机选择一个结点发给它新的布告消息（其中包含“承诺”）n这个过程一直继续下去形成一条链，直至布告消息中的跳数限制清零n最后一个收到布告消息的结点只产生自己的种子，不再做其他的事54宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n整个过程结束以后，这条链中所有的结点都公布它们各自的种子，所有种子的异或值就是新结点的标识n链上的每个结点将新结点的标识加入路由表o对“承诺”的检查使得链中的每个结点都确认其它结点所公布的种子是真实的，因此，Freenet所采用的链式方法实际上产生了一个全局一致的随机的结点标识，并且这个标识不可能被某个恶意加入者影响55宽带媒体服务技术之对等
33、网络宽带媒体服务技术之对等网络五、Freenet协议细节oFreenet协议面向数据包并且使用了相互独立的消息，每条消息包含n一个随机产生的事务ID，因此结点可以追踪插入、查询消息的状态n一个跳数限制，减少攻击者通过跳数限制所能获得的信息，在跳数限制减少到1以后消息仍有继续往前传的概率（跳数限制一直为1）n一个深度计数器，消息每走一跳深度计数器+1回复结点以此为依据设置回复消息的跳数限制56宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oFreenet事务一般从结点发送的握手消息开始，其中包含发送者的IP（可能是虚拟的）接收结点回复后，建立的连接可以持续几个小时，在此期间两结点之间随后的
34、事务不需要再次握手o为获取数据，用户发送“请求数据”消息，包含事务ID、跳数限制、深度计数器和查询关键码；同时开启一个定时器并根据跳数限制设定时间，若定时用完还未收到回复，就认为查询失败；当请求数据的消息被处理时，远处的结点可能会周期性地回发“重设定时器”消息，从而发送者可以继续等待57宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o如果数据请求成功，提供数据的结点会回送“发送数据”消息，包含请求者所要的数据和数据提供者的地址（可能虚拟）o如果数据请求失败，且跳数限制用完，回送“未发现”消息；如果失败但跳数未用完，通常是因为找不到可行的非循环的路径，回送“继续请求”消息，包含剩下的跳数，
35、请求信息的发送者收到此消息后将尝试新的下一跳58宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o为存储数据，用户发送“插入请求”消息，包含事务ID、跳数限制、深度计数器和“建议”关键码（用户建议采用的文件标识）o如果插入导致文件标识冲突，远处结点返回n“发送数据”消息，并返回现存的文件n“未找到”消息，表示现存文件未找到，但路由表有所指向o如果没有文件标识冲突，但消息在跳数限制用完之前就跑完了所有的结点，远处结点将回送“继续请求”消息，表示不能联系到足够多的结点导致失败o跳数限制用完且没有文件标识冲突时，返回“插入应答”消息，文件插入者发送“发送插入数据”消息，包含要插入的文件，沿途结点
36、缓存该文件59宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络六、Freenet性能分析o路由效率n结点的文件缓存、路由表都是逐步构造出来的n初期路由效率低，路由跳数大；后期“标识集群”路由效率提高，直至平稳o可扩展性nP2P网络中决定可扩展性的最重要因素是路由跳数h与网络结点总数N之间的关系，达到对数关系即认为是高可扩展的nFreenet服从对数关系，即hO(logN)60宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络七、Freenet的安全性和匿名性分析oFreenet设计的目标和初衷o系统的匿名性：发送者匿名、接收者匿名、文件标识匿名、关系匿名oFreenet提供了很好的发送者
37、匿名和接收者匿名，但无法进行文件标识匿名，因其依靠文件标识路由；研究者提出“预定路由”的辅助路由方法，对消息加密并以此指定路由61宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o防范DOS(denial of service,服务拒绝)攻击n攻击者可能通过插入大量的垃圾文件破坏Freenet或降低其工作效率n散列支付（hash cash），规定向Freenet网中插入文件的用户在插入之前必须做一次耗时的计算作为插入文件的支付代价，降低插入速度n将每个Freenet结点的存储区分成两部分，分别存放旧文件与新插入文件，这样攻击者无论插入多少垃圾文件，最多只能占用一般存储区62宽带媒体服务技术
38、之对等网络宽带媒体服务技术之对等网络八、Freenet体系总结o突出特点：自由、安全、匿名的P2P网络o利用每个参加者作为一个结点，划分一部分硬盘用作存储空间，存放经过加密的数据，存放者不知道内容，这是Freenet安全的核心oFreenet中文件查询通过一条“代理结点链”从一个结点传到另一个结点，路径上的每个结点只知道该请求的前一跳结点和由它决定的后一跳结点，对路径上的其他结点一无所知，这种“隧道路由”是Freenet匿名的核心oFreenet能够自适应地将使用到的文件缓存到更接近使用者的服务器上，即自动复制网上的内容63宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络oFreenet中
39、消息是通过结点路由表中保存的文件标识来导向路由的，文件标识有三种：KSK、SSK和CHK。消息路由采用改造过的图的深度优先算法oFreenet中插入文件之前先要检测是否存在文件标识冲突。结点存储区按照LRU方法更新，文件可以分割成多份保存在多个结点中。每个新结点加入Freenet网时，其结点标识是由网络中现存的多个结点共同决定的oFreenet具有文件标识集群效应，可扩展性好oFreenet总体上符合小世界模型和幂律模型oFreenet的安全和匿名仍不是完美的64宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络3.5 无结构P2P网络的特点o一、覆盖网拓扑结构无结构，指覆盖网没有固定、严格
40、的拓扑结构，而是一个随机生成、松散组织的普通图，但总是符合某种模型n小世界模型：20世纪60年代美国科学家的实验，任何一个美国人通过5-6层关系就能找到自己想找的人，小世界现象。1998年，Watts和Srogatz引入Small-world model，指任意两个网络结点间的距离一般很短，并且对每个结点而言，其邻居结点相识（互相连接）的概率很高，所以结点集群现象明显65宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n幂律模型：1999年，多位网络技术研究者指出很多实际网络如Internet的拓扑结构符合幂律模型（power-law model），即网络中拥有连接数L的结点占网络结点总数
41、的份额正比于L-a,a是取决于网络本身的常数因子，因此网络中大多数结点连接数很少，少数结点连接数很多nGnutella、Freenet等无结构P2P网络显然可以人认为符合小世界模型；虽然不符合严格的幂律模型，但可以看成是它们与其他模型的合成体，具有面对随机结点失效的高容错性等特征66宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络二、路由和定位方法oRouting、location含义接近，此处路由指消息走过的路径上的每一跳选择，定位看成是由多次路由组成的o无结构网络没有全局路由表，不可能预先知道要找的数据在哪里，只能随机路由，通常以洪泛法为基础，通过TTL限制搜索半径o四种典型的P2P随
42、机路由方法：洪泛法、扩展环、随机走、超结点路由67宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o洪泛法n绝大多数现存无结构P2P网络实际采用n路由覆盖范围是一个以TTL为半径的圆n不保证找到实际存在的文件68宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o扩展环（expanding ring）n试探性的洪泛法n逐步增加TTL，直至查询成功或者达到上限，从而形成一个个环n效率稍高69宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o随机走（random walks）n结点收到查询消息时只随机选择一个邻居结点发送该消息，直到数据被找到或TTL用完n因网络开销仅随跳数增加线性增加，故TTL可以较大n改进方法：带检测的随机走，行者IDn前途较为光明70宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络o超结点路由（supernode routing）n超结点自组织成一个网络，普通结点向其发起查询n可以在超结点网络中采用洪泛法neDonkey、KaZaA的流行，证明可行性71宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络三、优势和缺陷o优势n网络拓扑简单易实现n容错性、自适应性都好于结构化P2Pn可以具有很强的安全性和匿名性n数据复制方案很多o缺陷n路由效率低n可扩展性差n数据无法准确定位72
