P2P网络的核心机制课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《P2P网络的核心机制课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- P2P 网络 核心 机制 课件
- 资源描述:
-
1、1P2P网络的核心机制 2章节内容l4.1 覆盖网拓扑结构l4.2 分布式散列表l4.3 路由和定位l4.4 查询和搜索l4.5 动态结点算法l4.6 容错性34.1 覆盖网拓扑结构l P2P网络是构建在底层物理网(如IP网)上的应用层覆盖网,拓扑结构对P2P网络的工作性能以及设计机制有决定性作用l 典型拓扑结构:带弦环、树、Plaxton Mesh、环面、超立方体、蝴蝶、异或l 问题:拓扑结构对P2P性能的影响情况?Geometries NaturelFNSlFRSPerformancelResiliencelLatency4Geometries consideredGeometryAlgo
2、rithmRingChord, SymphonyHypercubeCANTreePRRHybrid = Tree + RingTapestry, PastryXORd(id1, id2) = id1 XOR id2Kademlia5Geometry = Flexibility = PerformancelGeometry captures flexibility in selecting algorithmslFlexibility is important for routing performance Flexibility in selecting routes leads to sho
3、rter, reliable paths Flexibility in selecting neighbors leads to shorter paths6Metrics for flexibilityl FNS: Flexibility in Neighbor Selection= number of node choices for a neighborl FRS: Flexibility in Route Selection= avg. number of next-hop choices for all destinationsl Constraints for neighbors
4、and routesselect neighbors to have paths of O(logN) select routes so that each hop is closer to destination7Summary of flexibility analysisFlexibilityOrdering of GeometriesNeighbors(FNS)Hypercube Tree, XOR, Ring, Hybrid (1) (2i-1) Routes(FRS)Tree XOR, Hybrid Hypercube Ring (1) (logN/2) (logN/2) (log
5、N)How relevant is flexibility for DHT routing performance?8Static ResilienceTwo aspects of robust routingl Dynamic Recovery : how quickly routing state is recovered after failuresl Static Resilience : how well the network routes before recovery finishes captures how quickly recovery algorithms need
6、to work depends on FRSEvaluation:l Fail a fraction of nodes, without recovering any statel Metric: % Paths Failed9Does flexibility affect Static Resilience?Tree XOR Hybrid Hypercube Ring10Geometrys impact on ProximitylBoth FNS and FRS can reduce latencyTree has FNS, Hypercube has FRS, Ring & XOR hav
7、e both lMetric: Overlay Path Latency11Which is more useful: FNS or FRS?Plain FRS FNS FNS+FRSNeighbor Selection is much better than Route Selection12小结l拓扑结构影响性能,其中FRS对resilence显著,而FNS对latency显著。设计需要tradeoffl参考论文:lGummadi et al.03 K. P. Gummadi, R. Gummadi, S. D. Gribble, S. Ratnasamy, S. Shenker and
8、I. Stoica. The Impact of DHT Routing Geometry on Resilience and Proximity. In SIGCOMM 2003, pp. 381-394.134.2 分布式散列表l 分布式散列表(DHT,Distributed hash table)是P2P网络的核心设施,它基于一致性散列函数,提供对于结点、数据对象在覆盖网中的位置映射l 结点的映射可以保证准确的定位,还提供了匿名性l 数据对象映射的作用在于将其索引信息放到nodelD与objectID最近的结点上,对数据对象的定位需要首先在此结点上找到对象索引l DHT在实现物理网到覆盖
9、网映射的同时,损失了物理网上结点之间的邻近关系,带来了两者的不一致14P2P体系架构及其应用接口15lP2P体系架构上图反映了DHT在P2P网络中的地位:DHT位于结构化P2P应用和P2P覆盖网之间,它组织覆盖网中的结点,向上层提供三个最基本的接口Put(Key, Value):向网络中存储具有标识Key的数据ValueRemote(Key):在网络中删除具有标识Key的数据对象Value=Get(Key):从网络中获取具有标识Key的数据保存在Value中16l目前已在考虑结构化P2P网络公用API的规划,如Karp等在IPTPS04上提出的OpenHash体系以及Rhea等人在SIGCOM
10、M05发布的OpenDHT(www.opendht.org )服务lDHT的问题拓扑一致性问题,带来通信时延的增加数据对象的语义查询十分困难17OpenDHTlOpenDHT:公共DHT服务平台http:/opendht.org基于Bamboo DHT,改写自Pastry设计原则:易于部署,易于使用客户端不需要运行DHT软件,而是通过OpenDHT服务平台获取所需的服务,从而实现基于DHT的P2P应用l 客户端接口APIPut(K, V, t):将发布到OpenDHT网络,t为有效期Get(K):根据K从OpenDHT网络获取对18OpenDHT体系结构19Examples:l Here is
11、 an example usage scenario: l $ ./put.py colors red Success l $ ./get.py colors red l $ ./put.py -secret donttell colors blue Successl $ ./get.py colors red bluel $ ./rm.py colors blue donttell Success l $ ./get.py colors red 20散列函数l 散列函数:hash function,提供分布式数据存储功能l 安全散列函数:secure hash function,提供安全性、
12、匿名性l 一致性散列函数:consistent hash function,提供查询高效性与负载均衡l 常用的有:MD5,SHA-1,HMAC(用一个secret key和一个hash function产生一个MAC报文鉴别码)l 攻击:强行攻击(2n),生日攻击(相当于强行攻击的平方根,2(n/2)214.3 路由和定位l 概念接近,在应用中有区别l “定位”:确定结点或数据对象的位置,通过“路由”完成。结果与过程l 路由和定位的方式取决于两个因素:覆盖网拓扑结构、路由表结构l 结构化P2P网络通常维护一个较小的路由表,采用分布式、局部性的贪心路由算法,逐步缩小与目的结点之间的ID差异l 无
13、结构网络常使用“洪泛法”或变形来路由,效率低且无法保证定位成功22一、混合式P2P网络的路由和定位方法l 混合式P2P网络都采用服务器路由l 用户只要向服务器提交查询,后者即给出回复,回复中包含文件拥有者的信息,用户直接同文件拥有者建立连接,进行文件下载l 星型路由,常跳数O(1),路由性能只取决于服务器23二、无结构P2P网络的路由和定位方法l 以洪泛法为基础的随机路由,通过TTL限制半径,以减小网络负担,但低效l 无结构P2P网络的四种典型路由方法:洪泛法、扩展环、随机走和超结点路由,按结点本身引导路由l 导向路由(guided routing):路由消息时尽量选择可能包含相关内容的结点作
14、为下一跳,按数据对象内容引导路由l 要求路由表按照数据对象的内容构造,比如表项中保存文件标识,而文件标识指向可能包含它的结点24lFreenet是“导向路由”的代表,其路由表按照文件组织,每个表项记录一个文件标识以及文件标识所指向的结点,此结点很可能包含该文件,至少离文件更近l当文件被找到沿原路返回给请求者时,定位路径上的每一跳结点都会在路由表中添加关于此文件的项,将来的定位速度更快lFreenet的标识集群效应25Freenet中的“导向路由”过程示例无下一跳循环请求26三、结构化P2P网络的路由和定位方法l结构化P2P网络的路由和定位方法与其覆盖网拓扑结构、路由表机构密切相关,其本质是:采
展开阅读全文