第3讲P2P网络体系（1）ppt.ppt

《第3讲P2P网络体系（1）ppt.ppt》由会员分享，可在线阅读，更多相关《第3讲P2P网络体系（1）ppt.ppt（116页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1,P2P网络体系,2,大纲,第一代P2P网络：混合式P2P体系（）第二代P2P网络：无结构P2P体系（）第三代P2P网络：结构化P2P体系,3,本讲需要大家关注的是：,（1）P2P思想是如何应用到文件共享领域？（2）无结构的网络如何在节点随意加入和退出的情况下实现自组织？（3）多源下载技术的实现思想以及技术方法（4）Freenet的匿名技术,4,第一代P2P网络：混合式P2P体系,NapsterBitTorrent,5,Napster:P2P网络的先驱,世界上第一个应用性P2P网络，混合式P2P体系最杰出的代表1999年波士顿东北大学的Shawn Fanning开发Napster，用于MP3

2、文件交流，与传统的提供音乐下载的网站不同，Napster服务器里无歌曲，仅有其它用户硬盘上的文件的索引Napster使用的软件技术都是当时已有的，只是改变了软件的应用体系，打破了客户/服务器模式的瓶颈Napster半年吸引了5000万注册用户，最高时超过6100万用户,6,Napster网络的工作原理,服务器：维护所有Napster用户的共享文件索引监控系统中每个用户的状态(连接带宽、连接时间、在线状态),7,Napster性能分析,节点异构Bandwidth, online timeFree Riding20-40%用户几乎从来不提供文件共享而只是下载；大约1%的结点支撑Napster文件共

3、享,8,9,Napster的缺陷,C/S的残余：文件交换使用P2P，但文件查询、系统维护靠server，带来系统瓶颈、服务器单点失效、可扩展性低等问题组织管理过于松散，仅赋予用户平等的功能，无义务要求、能力区分版权问题：导致Napster发布后当年即被起诉，两年后关闭服务，是P2P文件共享系统迄今为止最大的困境,10,BitTorrent-分片优化的新一代混合式P2P网络,Napster进一步发展，BitTorrent：相同架构，但文件分片，使用散列函数映射用户有上传义务网络及用户信息更新、BT种子维护由server中的Tracker完成，下载同一文件的用户围绕Tracker形成独立子网，不同

4、文件的Tracker在不同server上，将server分散化，成为P2P在国内最成功的应用,11,BitTorrent体系原理,12,Overview system components,13,Overview system components,14,Overview system components,15,Overview system components,16,Overview system components,17,Overview system components,18,Overview system components,19,BitTorrent分片机制,BT将文件分为

5、固定大小的分片(典型大小256KB)，每个用户必须通知其他下载者自己拥有的分片，分片的完整性由散列函数保证分片流水作业：构架在TCP之上的应用层协议，同时发送多个请求，以避免在两个分片发送之间的延迟，进一步，分片可以划分为子分片(典型16KB)，BT一直保持几个请求（通常是5个）被流水式地同时发送。流水作业选择同时发送的请求数目的依据，是使大多数连接变得饱和以充分利用带宽,20,BitTorrent分片选择策略,严格的优先级（一个分片的下载）一旦请求了某个分片的子分片，那么该分片的所有子分片具有更高优先级，以尽可能快地获得一个完整的分片最少者优先（中间阶段/平稳期）尽量选择所知用户拥有数最少的

6、分片作为下一个下载分片，以使网络中最稀少的分片尽快拥有多个复制下载者从Tracker了解哪些分片较少随机的第一个片段（文件下载最初阶段）当最少的分片只有一个用户拥有时，为避免并发冲突，第一个分片先随机选择，完成下载后再切换到“最少者优先”策略最后阶段模式（文件下载最后阶段）为加速最后阶段下载，下载者向他所连接的所有用户都发送某分片的子分片请求，一旦某个子分片到了，下载者就会向其他用户发送cancel消息，以避免浪费带宽,21,BitTorrent阻塞算法,BT并不是由Tracker服务器集中分配资源，每个用户自己有责任尽可能地提高自己的下载速率下载者根据连接用户提供的下载速率给予同等的上传回报

7、(tit-for-tat)；对合作者提供上传服务，对不合作者进行临时阻塞一个好的阻塞算法应该利用所有可用的资源，为所有下载者提供一致、可靠的下载速率，并适当惩罚只下载而不上传的用户,22,阻塞算法的经济学背景帕累托有效当一个系统中资源配置已达到这样一种境地：任何重新改变资源配置的方式，都不可能使一部分人在没有其他人受损的情况下受益，这一资源配置的状态称为“帕累托最优”状态，或称为“帕累托有效”(Pareto efficient)在分布式系统领域，寻求帕累托有效是一种本地优化算法，BT的阻塞算法用一种奉献与回报相对应的方式来试图达到帕累托最优。BT用户对那些向它提供上传的用户给予同样的回报，以使

8、任何时候都有若干个连接正在进行着双向传输,23,BT的阻塞算法(choking algorithm)BT每个用户对固定数量的其他用户保持疏通(即不阻塞，通常为4个)每隔20秒进行一次轮询：前10秒计算出哪个用户要被阻塞，然后将阻塞状态保持10秒。Nave策略是仅疏通下载速率最高的前几个。10秒内足够TCP调整传输速率最优疏通(optimistic unchoking)为发现更好的空闲连接，不能只向为自己提供最高下载速率的用户提供上传，而是每隔30秒，重新计算一次哪个连接应该是“最优疏通”,24,反对冷落(anti-snubbing)某个下载者可能被所连接的所有用户阻塞，为缓解该问题，当从某个用

9、户那里一个分片也没有得到，下载者认为被对方“冷落”，不再为对方提供上传。“反对冷落”常常会导致多个并发的“最优疏通”，从而更快恢复下载速率仅仅上传用户完成下载后，优先选择可从自己得到更高上传速率的用户或刚好被所有人阻塞的用户,25,BitTorrent性能分析,Pouwelse et al., 2004,2005论文流行性：应用广泛，但BT网站、.torrent文件服务器及Tracker故障率较高，限制了网络规模可用性：同上，取决于服务器的可用性。实际较低，只有一半的BT网站镜像可正常工作超过2.1天，种子服务器更少下载性能：当时统计平均速度30KB/s,26,文件生命周期该文件的种子生命期，

10、由于服务器故障及用户行为不确定性，差别很大约17%的用户下载完成后做种时间超过1小时，仅3%用户做种时间超过10小时污染等级加入到BT网络中的共享文件的真实性审查系统(moderation system)，三种角色：需要审查的提交者；不需要审查的提交者；审查者。可逐级提升。,27,28,BitTorrent体系总结,BT是混合式结构的P2P网络，以BT网站、.torrent文件服务器和Tracker为核心，控制和帮助用户共享文件下载同一文件的用户围绕Tracker形成一个独立的子网BT限定用户在下载的同时必须提供上传，既提高了网络效率，又杜绝了P2P网络中的自私结点现象BT将文件分片，分片又被

11、划分成子分片，子分片流水作业，并在文件下载的不同阶段有不同的分片选择策略以优化性能。这是BT最大的特点，也是它高效的最本质原因BT基于经济学规律的阻塞算法，优化了网络资源配置，增强了用户间的协作BT通过对文件和分片生成散列值，保证文件的完整性BT提供了一定的安全机制，如文件审查、输入验证码BT服务器故障率高，导致可用性降低，且网络规模受限，文件无持久性保证,29,BT下载对硬盘的影响,硬盘的工作原理磁头读写盘片上的磁道，由于网络吞吐量低于磁盘吞吐量，持续低速下载（上传）带来频繁的读写操作，盘片可能会由于过热而损坏磁盘缓存技术使用内存缓存数据写数据时，仅当缓存满后再整体写入硬盘(下载)读数据时，

12、仅当缓存中没有时才从硬盘读数据，且整块读入，减少磁盘操作(上传)内存是有限资源，缓存在650MB即可结论：P2P下载不伤硬盘,30,第一代P2P网络的特点,拓扑结构混合式(C/S+P2P)星型拓扑结构，以服务器为核心查询与路由用户向服务器发出查询请求，服务器返回文件索引用户根据索引与其它用户进行数据传输路由跳数为O(1)，即常数跳容错性：取决于服务器的故障概率（实际网络中，由于成本原因，可用性较低）自适应：靠服务器监控实现自组织与自适应，只要服务器正常工作即可有效维护网络和结点信息匿名性：一般不提供，但支持增强机制：BT的文件分片、双向传输、防范攻击,31,第二代P2P网络：无结构P2P体系,

13、GnutellaKaZaAeDonkey/eMuleFreenet,32,Gnutella:纯分布式无结构P2P,Gnutella的历史Nullsoft公司，MP3播放软件WinAmp的发明人Justin Frankel、Tom Pepper开发2000年3月14日在网站上公开Gnutella软件一个半小时后，母公司AOL(American Online)担心步Napster后尘，关闭了网站数千名MP3迷下载了软件并公开与改造其纯分布式无结构P2P网络思想广泛流传Gnutella已不单纯对应具体软件，而是当作一种典型的无结构P2P网络协议,33,Gnutella体系的工作原理,Gnutella

14、协议0.4版(0.6版加入了超结点Ultrapeer，结构有变化),34,协议开发者称Peer为Servent(Server +Client)，网络中只有peer，没有serverGnutella覆盖网上每个结点对应一台实际的计算机每条连接对应一条点到点的链路覆盖网上的连接由每个peer保存的“邻居结点”信息确定，有一个邻居结点即对应有一条边,35,新结点加入时，必须首先连接到“众所周知”几乎总是在线的Gnutella结点(称为“自举”结点、“入口结点”)Gnutella网中的消息可以被广播或回播(back-propagate，沿广播的反向路径回传消息)，协议设计的支持机制：每条消息具有一个随

15、机产生的全局唯一标识符GUID(16字节)以互相区分每个结点缓存最近路由的消息以支持回播并阻止不必要的重广播每条消息都有TTL以避免过度消耗网络资源,36,Gnutella的典型消息,组成员消息：PING，PONG新结点加入时广播PING消息，或用来探测其它结点是否仍然存在(心跳)结点收到PING消息后，可以决定是否回播PONG消息，以及是否将PING转发给邻居，PONG消息包含结点IP,port,共享文件数量大小查询消息：QUERY，QUERY RESPONSEQUERY消息用来查询文件,包含查询内容与最小响应速度等附加信息,但不包含源结点信息RESPONSE消息包含文件下载的必须信息及该结

16、点的nodeID，沿QUERY消息路径回播,37,文件传输消息：GET，PUSH结点收到QUERY RESPONSE消息后用GET消息请求获得文件对处于防火墙后因而不能直接响应文件请求的结点，使用PUSH消息请求防火墙后的文件拥有者主动建立到自己的连接,38,Gnutella的文件检索过程,假定: m1s neighbors are m2 and m3; m3s neighbors are m4 and m5;,泛洪式搜索(flooding search)， 系统开销大有限深度TTL(Time to Live)， 不保证一定查询到已有文件,A,B,C,D,E,F,m1,m2,m3,m4,m5,

17、m6,39,Gnutella网络的维护各结点使用PING、PONG消息探测其他结点存在与否，在收到PING消息后，可以自主决定是否回播PONG，并根据TTL数值决定是否继续广播PING消息具有一定的自组织和自适应性,40,Gnutella网络的性能分析,Ripeanu,2001,2002、Saroiu et al., 2002,2003、Adar & Huberman, 2002Gnutella用户的连接带宽仅在Query response消息中作为辅助信息回播，因此，Gnutella网络中不共享文件的用户或其共享的文件与查询请求一直不匹配的用户，不会主动发布带宽Gnutella网络中结点功能

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

19、tella覆盖网的几种状态,左：正常的Gnutella覆盖网。中：随机移去30结点后的Gnutella覆盖网。右：移去连接数最多的4结点后的Gnutella覆盖网（它分裂了）（图片来自Saroiu et al.03）,44,早期Gnutella网络中，PING消息占所有消息的50%以上，显示其自适应机制低效。改进后的Gnutella网络，对用户真正有用的Query消息占总消息的90%以上Gnutella覆盖网络与物理网络的拓扑一致性较低，影响工作效率,45,采用Gnutella协议的P2P网络应解决：结点异构性：充分利用结点能力Free-Riding：鼓励上传，限制或剥夺Free-Rider的

20、权利保持高容错性：高效的机制检测和恢复网络分割继续优化查询机制，TTL的取值拓扑一致性,46,Napster与Gnutella的比较,共同点P2P的文件共享思想系统中的对等实体(peer)之间是对称的，既是客户又是服务器，既提供下载又提供上传可扩展性都不高：但Napster是因为C/S结构，Gnutella是因为泛洪搜索策略造成的系统开销都有结点异构性问题以及搭便车现象,47,不同点Napster有服务器，Gnutella没有，因此工作机制完全不同网络结构不同：混合式与纯分布式，Gnutella在Internet网上构建了覆盖网，这是后来的P2P网络都会做的一项基础性工作Napster中文件只

21、要存在一般都能查询到，Gnutella不一定Napster只在服务器故障时出错，Gnutella可能因为结点信息陈旧而出错，最大的问题是可能导致网络分割,48,Gnutella的双层结构,Gnutella协议0.6版层次化的无结构P2P网络,49,KaZaA：基于超结点的无结构P2P网络,2000年7月，基于FastTrack无结构P2P协议Niklas及Friis，P2P创业家，Joltid, Altnet, SkypeFastTrack协议首次引入超结点SuperNode，开发结点异构性(比Gnutella0.6早得多),50,KaZaA的工作原理,KaZaA是私有协议，并对消息加密，对其

22、理解基于测量与分析的结果,51,节点异构性带宽、处理能力、存储容量、NAT访问方式超结点高带宽、高处理能力、大存储容量、不受NAT限制功能上类似Napster中的服务器，但并非专门、永久的，经常由普通结点转变而来,52,普通结点加入网络时选择一个“父超结点”，并维持一条半永久的TCP连接，将其共享的文件元数据(也称“文件索引”)上传文件索引分布在KaZaA的超结点中，作用是将文件标识符映射到文件所在的结点IP文件索引包括：文件名、文件大小、文件内容Hash值、文件描述符(如艺术家、专辑名)文件内容Hash值的作用：当下载失败时，可自动搜索文件，不必再做关键词查询,53,用户查询文件向父超结点发

23、送带有文件关键词的查询消息超结点在自己的数据库中寻找匹配的文件索引返回给用户文件所在的IP地址、port、文件元数据超结点间局部保持着长期的TCP连接，构成超结点覆盖网文件查询局部性问题,54,KaZaA协议的应用,KaZaA用户应当具有4个软件构件KMD(KaZaA Media Desktop)存储在Windows注册表中的软件环境信息，其中包含一个有200个超结点信息(IP、port)的列表(超结点列表缓存)DBB文件：包含用户希望共享的文件的元数据DAT文件：每个DAT文件是一个部分下载的文件，下载完成后，将被重命名为下载的原始文件,55,KaZaA用户间的4种TCP通信方式信号通信，包

24、括：为建立连接的握手通信，将DBB文件从普通结点上传到超结点，超结点列表更新、查询和回复。所有的信号通信都加密文件传输通信：用户间直接的文件传输，以HTTP消息发送，不加密商业广告：通过HTTP发送实时消息通信：采用Base64编码,56,KaZaA的技术细节,自适应通过结点间交换超结点列表实现每次普通结点连接到超结点，后者立刻回送超结点更新列表，其中第一项为自己的IP,port以及工作负载值相邻的超结点间也交换超结点更新列表有效克服文件查询的局部性结点间的连接刚加入KaZaA网络时，选择父超结点。一对多UDP探测超节点，TCP选择父超结点得到sn refresh list，并最终选定一个父超

25、节点）超结点之间也需要交互sn refresh list,57,58,KaZaA的防火墙穿透：动态端口KaZaA的NAT穿透A无法与NAT后的B建立直接的TCP连接A发送请求到B的父超结点S，S发送消息到B，通知B应该由B发出到A的连接请求，主动建立一条到A的TCP连接，A通过此连接从B下载文件。称为“连接反转”(connection reversal),59,KaZaA的性能分析,基于文献Liang et al., 2004; 2005的测量结果KaZaA网络的超结点数在25000-40000之间，每个超结点平均与40-60个超结点连接，与60-150个普通结点连接KaZaA覆盖网动态性：连

26、接保持时间ON-SN平均34min，38%低于30minSN-SN平均11min，32%低于30min结点主动改变连接，超结点频繁交换列表,60,KaZaA网络局部性60%的SN-SN连接RTT (往返时间round trip time)小于50ms，40%的ON-SN连接RTT小于5ms超结点返回给普通结点的超结点列表中，很高比例的超结点与该普通结点的IP前缀相似结论：采用了提高局部性的方法KaZaA索引管理13%的ON上传了超过80%的元数据SN之间不交互索引信息,61,KaZaA网络总结,首次显式开发P2P网络节点异构性为缓解无结构P2P网络的查询局部性问题，并保持KaZaA网络的自适应

27、性，KaZaA用户间频繁地交换超结点更新列表，根据列表改变原有连接测量结果显示KaZaA网络考虑了局部性因素Free-Riding现象在KaZaA网络中依然存在KaZaA通过使用动态端口和连接反转的方法，有效地穿透防火墙和NAT，拓宽了网络适用范围,62,eDonkey/eMule：分块下载的双层无结构P2P网络,2000年eDonkey出现，特点：文件分块，可并行下载使用文件内容散列值验证数据完整性双层无结构，使用超结点作为“服务器”基于Overnet分布式搜索网络eMule出现于2002年5月，是对eDonkey客户端的出色改进,63,eDonkey工作原理,4661tcp:client-

28、server4662tcp:client-client4665upd:深层查询,64,eDonkey客户加入网络首先连接到“入口服务器”列表中离自己最近(时延最小)的一台服务器通过该入口服务器获得一个普通服务器列表，从中选择最合适的服务器建立连接并断开与入口服务器的连接客户将自己的共享文件信息发给服务器客户从存放自己信息的服务器查询文件，如无结果，则可以向其它服务器重新查询,65,eDonkey客户下载文件前，首先通过查询获得文件提供者列表，然后向列表中的每个文件提供者请求“上传槽”(upload slot)文件提供者将请求放进上传队列的“等待列表”，等到条件满足时才给该请求分配“上传槽”并将

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

30、y文件分块细节（Chunk、Segment、Block）,68,eDonkey性能分析,部分类似KaZaA，部分类似BT，定性分析可参照二者4662端口专用于客户间TCP连接下载连接传输总量占所有流传输总量的70.5%，不高(inbound，连接到测试网；outbound，从测试网向外）在所建立的TCP连接中，只有2.24%用作下载连接，不如BT高效的重要原因,69,eDonkey网络总结,双层：服务器层+客户层，类似于KaZaA， 服务器提供文件索引和交换服务器列表，开发了结点异构性将文件逐级分成分块、片段、小块，从而提供了类似BT的多源文件下载机制，并且对文件的完整性检查也有了更细的粒度为

31、适应动态的网络环境，eDonkey客户通过上传队列来管理客户间的连接，只有获得上传槽的连接才能真正传递数据，并且每个连接都有周期性检测以处理异常中断，提高了工作效率靠服务器间周期性地更新服务器列表维护自适应性，eDonkey的流行性验证了该机制是良好的,70,Freenet：自由、安全、匿名的无结构P2P网络,自由网的概念由Clarke于1999年提出，2000年3月推出第一版，更新很慢Freenet的理念：共享Internet计算机资源，组建一个自由、安全、匿名的信息发布和获取的平台(不同于其它P2P网络)Freenet结点划出一部分硬盘作为公用存储空间，但其中数据加密，仅对有权限者开放Fr

32、eenet匿名性的本质在于其隧道路由机制Freenet过于自由、界面不友好限制其发展,71,Freenet的密码学基础,Freenet中的文件以Hash值作为标识，使用SHA-1安全散列函数生成Freenet使用三种不同类型的文件标识，KSK，SSK，CHK，分别完成不同的功能，是Freenet的核心设施，三者相互独立，可以合并使用,72,KSKKeyword-signed key，关键词签名标识，用于构建Freenet的全局名空间用户在网络中存储文件时，必须给文件指定一个很短的描述性字符串作为输入产生一对非对称密钥，公钥被Hash以产生文件标识，私钥用来给文件做数字签名，附带提供了文件的完整

33、性检查字符串本身被作为密钥来加密原来的文件为让其他人获取文件，只需发布该文件的描述性字符串问题：用户选取的字符串容易相同从而文件标识相同,73,SSKSigned-subspace key，签名子空间标识，用以构建Freenet的个人名空间(解决了KSK相同字符串的问题)用户通过随机地产生一对非对称密钥来标识自己的名空间存储文件时，首先也是指定一个很短的描述性字符串，然后分别Hash该字符串和名空间公钥，再将两个Hash值异或，再次Hash异或值产生文件标识；随机私钥用来给文件签名，因而比KSK安全；字符串仍作为密钥加密原来的文件发布文件时，同样发布描述性字符串(包括了公钥及文件标识)；存储数

34、据需要私钥，因此只能是名空间拥有者存储它的文件。,74,CHKContent-hash key，内容散列标识，实现文件的更新与分割，将文件直接Hash得到的散列值就是它的CHK，并使用一个随机产生的密钥加密文件。发布文件时，只需发布解密密钥与文件标识(注意没有描述性字符串)可以单独用，但通常与SSK一起使用，实现文件更新用CHK存储文件，用SSK存储一个间接文件，此文件的内容就是CHK，相当于指向真实文件的指针更新文件时，先用新的CHK存储新文件，使用原来的SSK再存储一个新的间接文件，原间接文件所在的结点发现文件标识冲突，确认签名合法后更新间接文件SSK由于存在描述性字符串从而易为他人记住和

35、交流,75,显然，Freenet中的文件更新仅仅是间接文件的更新，新旧文件实际共存于网络之中，后者可通过旧CHK访问CHK用于文件分割用户将文件分成多个部分，每部分使用它自己的CHK来存储，最后存储一个间接文件（或者多层的间接文件）来指向文件的各个部分分割的好处：减少对单个结点存储容量和带宽的需求；对抗通信量分析,76,Freenet中数据的查询与获取,基于文件标识的“导向路由”为获取文件，用户首先获得或计算出文件标识，同时设置好请求消息的跳数限制，然后在自己的路由表里查找与该文件标识最接近的文件标识并把请求发送给与之相应的结点接收到请求的结点如果拥有该文件，则回送消息，否则按前述方法继续转发

36、，若最终查询文件被回送，该结点除了将文件回传给请求者，还会在自己的数据库里缓存该文件，并在自己的路由表里创建一个指向新项该文件的数据源,77,当某个结点尝试所有可路由结点仍无结果时，则返回失败消息给自己的前一跳，由后者尝试新的下一跳，即“深度优先”搜索策略，直至达到跳数限制（注：跳数可在途中任意减少）安全路由路由表自适应更新威胁到了网络的安全性和匿名性Freenet同意消息传送路径上的每一个结点都可以单方面修改消息，将消息原来的请求者或者文件源改成任意一个结点(匿名特性),78,简单示例,79,Query Example,Note: doesnt show file caching on th

37、e reverse path,4 n1 f412 n2 f12 5 n3,9 n3 f9,3 n1 f314 n4 f14 5 n3,14 n5 f1413 n2 f13 3 n6,n1,n2,n3,n4,4 n1 f410 n5 f10 8 n6,n5,query(10),80,这样的数据查询和获取机制，可以极大提高效率，即，若某个结点在其他结点的路由表中被列为是与某个文件相关的结点，则很可能会收到越来越多的对该文件的请求或与该文件相近的文件请求，产生“标识集群”效应。随着时间的推移，文件被复制得更多更优化，结点路由表表项也更多更“近”,81,Freenet中数据的存储与管理,存储数据用户使

38、用文件标识中的一种（KSK, SSK, CHK）给文件计算标识，并设置请求消息的跳数限制，然后发送文件插入消息到Freenet网收到文件插入消息的结点，首先检查自己的数据库中是否有该文件标识，有则回送此文件，请求方据此判断是该文件确实已经存在还是文件标识碰巧冲突(文件比对)，对前者用户不需要再插入，对后者重新计算文件标识再做插入,82,当已达到跳数限制且未检测到文件标识冲突时，回送“一切顺利”的消息，直至到达发出最初请求的用户，该用户沿此路径插入文件，路径上每个结点在其路由表中增加与此文件标识相关的项（对应结点为虚拟的文件源）,83,存储数据例子,定位: 如同查询，不过节点需要维护一个状态看是

39、否有冲突插入(等待回送的文件或一切顺利的消息)插入：Follow the forward path; insert the file at all nodes along the pathA node probabilistically replace the originator with itself; obscure(隐藏) the true originator,84,Insert Example,Assume query returned failure along “gray” path; insert f10 (定位),4 n1 f412 n2 f12 5 n3,9 n3 f9,

40、3 n1 f314 n4 f14 5 n3,14 n5 f1413 n2 f13 3 n6,n1,n2,n3,n4,4 n1 f411 n5 f11 8 n6,n5,insert(10, f10),85,Insert Example,10 n1 f10 4 n1 f412 n2,3 n1 f314 n4 f14 5 n3,14 n5 f1413 n2 f13 3 n6,n1,n3,n4,4 n1 f411 n5 f11 8 n6,n5,insert(10, f10),9 n3 f9,n2,orig=n1,86,Insert Example,n2 replaces the originator

41、(n1) with itself,10 n1 f10 4 n1 f412 n2,10 n1 f10 9 n3 f9,10 n2 10 3 n1 f314 n4,14 n5 f1413 n2 f13 3 n6,n1,n2,n3,n4,4 n1 f411 n5 f11 8 n6,n5,insert(10, f10),orig=n2,87,Insert Example,n2 replaces the originator (n1) with itself,10 n1 f10 4 n1 f412 n2,10 n1 f10 9 n3 f9,10 n2 10 3 n1 f314 n4,10 n2 f101

42、4 n5 f1413 n2,n1,n2,n3,n4,10 n4 f10 4 n1 f411 n5,n5,Insert(10, f10),88,存储机制与网络性能文件通常被存储到已经拥有相近标识文件的结点上，加强了“标识集群”效应新结点可以通过插入文件宣布自己的存在恶意结点不仅无法通过插入与已有文件标识相同的垃圾文件来“排挤”原文件，反而促使原文件的信息在网络中更广泛传播(文件回送),89,数据管理结点的存储区（大小由用户指定）按照最近使用优先（least recently used,LRU）方式管理被替换掉的旧文件在路由表中对应的项还会保留，直至路由表也发生超容量替换LRU对存储的利用高效，但

43、无法保证某个文件在网络中至少有一份拷贝存在,90,数据私密性文件经过加密后存放，存放结点用户无法获知文件内容，满足了数据的保密性需求，且Freenet用户可以否认对任何关于其数据库中文件内容的了解Freenet将网络中所有用户的存储区组织成了一个巨大的分布式系统，并且这个系统对于每个用户来说都是透明和不可知的,91,Freenet网络新结点加入,Freenet新结点的标识选取要求为了正确、高效地路由，该标识应该全局一致出于安全性考虑，不能让其他结点通过某些属性计算出结点标识（用于对网络的恶意攻击）Freenet采用加密协议选取标识新结点选择一个随机的“种子”并发送一条布告消息给某个现存的结点，

44、其中包含自己的IP、种子的Hash值及跳数限制,92,收到该消息的结点也产生一个随机的种子将该种子与消息中的Hash值异或对结果进行Hash产生一个“承诺”(commitment)从自己的路由表中随机选择一个结点发给它新的布告消息（其中包含“承诺”）这个过程一直继续下去形成一条链，直至布告消息中的跳数限制清零最后一个收到布告消息的结点只产生自己的种子，不再做其他的事,93,整个过程结束以后，这条链中所有的结点都公布它们各自的种子，所有种子的异或值就是新结点的标识链上的每个结点将新结点的标识加入路由表对“承诺”的检查使得链中的每个结点都确认其它结点所公布的种子是真实的，因此，Freenet所采用

45、的链式方法实际上产生了一个全局一致的随机的结点标识，并且这个标识不可能被某个恶意加入者影响,94,Freenet协议细节,Freenet协议面向数据包并且使用了相互独立的消息，每条消息包含一个随机产生的事务ID，因此结点可以追踪插入、查询消息的状态一个跳数限制，减少攻击者通过跳数限制所能获得的信息，在跳数限制减少到1以后消息仍有继续往前传的概率（跳数限制一直为1）一个深度计数器，消息每走一跳深度计数器+1回复结点以此为依据设置回复消息的跳数限制Hop=1的概率前传加大了猜测消息的难度,95,Freenet事务一般从结点发送的握手消息开始，其中包含发送者的IP（可能是虚拟的）接收结点回复后，建立

46、的连接可以持续几个小时，在此期间两结点之间随后的事务不需要再次握手为获取数据，用户发送“请求数据”消息，包含事务ID、跳数限制、深度计数器和查询关键码；同时开启一个定时器并根据跳数限制设定时间，若定时用完还未收到回复，就认为查询失败；当请求数据的消息被处理时，远处的结点可能会周期性地回发“重设定时器”消息，从而发送者可以继续等待(tolerant delay),96,如果数据请求成功，提供数据的结点会回送“发送数据”消息，包含请求者所要的数据和数据提供者的地址（可能虚拟，提供者可能是匿名者）如果数据请求失败，且跳数限制用完，回送“未发现”消息；如果失败但跳数未用完，通常是因为找不到可行的非循环

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

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