《网络的核心机制》PPT课件.ppt

1,P2P网络的核心机制,2,章节内容,4.1 覆盖网拓扑结构 4.2 分布式散列表 4.3 路由和定位 4.4 查询和搜索 4.5 动态结点算法 4.6 容错性,3,4.1 覆盖网拓扑结构,P2P网络是构建在底层物理网（如IP网）上的应用层覆盖网，拓扑结构对P2P网络的工作性能以及设计机制有决定性作用 典型拓扑结构：带弦环、树、Plaxton Mesh、环面、超立方体、蝴蝶、异或 问题：拓扑结构对P2P性能的影响情况？ Geometries Nature FNS FRS Performance Resilience Latency,4,Geometries considered,5,Geometry = Flexibility = Performance,Geometry captures flexibility in selecting algorithms Flexibility is important for routing performance Flexibility in selecting routes leads to shorter, reliable paths Flexibility in selecting neighbors leads to shorter paths,6,Metrics for flexibility,FNS: Flexibility in Neighbor Selection = number of node choices for a neighbor FRS: Flexibility in Route Selection = avg. number of next-hop choices for all destinations Constraints for neighbors and routes select neighbors to have paths of O(logN) select routes so that each hop is closer to destination,7,Summary of flexibility analysis,How relevant is flexibility for DHT routing performance?,8,Static Resilience,Two aspects of robust routing Dynamic Recovery : how quickly routing state is recovered after failures Static Resilience : how well the network routes before recovery finishes captures how quickly recovery algorithms need to work depends on FRS Evaluation: Fail a fraction of nodes, without recovering any state Metric: % Paths Failed,9,Does flexibility affect Static Resilience?,Tree XOR Hybrid Hypercube Ring,10,Geometrys impact on Proximity,Both FNS and FRS can reduce latency Tree has FNS, Hypercube has FRS, Ring & XOR have both Metric: Overlay Path Latency,11,Which is more useful: FNS or FRS?,Plain FRS FNS FNS+FRS Neighbor Selection is much better than Route Selection,12,小结,拓扑结构影响性能，其中FRS对resilence显著，而FNS对latency显著。设计需要tradeoff 参考论文： Gummadi et al.03 K. P. Gummadi, R. Gummadi, S. D. Gribble, S. Ratnasamy, S. Shenker and I. Stoica. The Impact of DHT Routing Geometry on Resilience and Proximity. In SIGCOMM 2003, pp. 381-394.,13,4.2 分布式散列表,分布式散列表(DHT，Distributed hash table)是P2P网络的核心设施，它基于一致性散列函数，提供对于结点、数据对象在覆盖网中的位置映射 结点的映射可以保证准确的定位，还提供了匿名性 数据对象映射的作用在于将其索引信息放到nodelD与objectID最近的结点上，对数据对象的定位需要首先在此结点上找到对象索引 DHT在实现物理网到覆盖网映射的同时，损失了物理网上结点之间的邻近关系，带来了两者的不一致,14,P2P体系架构及其应用接口,15,P2P体系架构 上图反映了DHT在P2P网络中的地位：DHT位于结构化P2P应用和P2P覆盖网之间，它组织覆盖网中的结点，向上层提供三个最基本的接口 Put(Key, Value)：向网络中存储具有标识Key的数据Value Remote(Key)：在网络中删除具有标识Key的数据对象 Value=Get(Key)：从网络中获取具有标识Key的数据保存在Value中,16,目前已在考虑结构化P2P网络公用API的规划，如Karp等在IPTPS04上提出的OpenHash体系以及Rhea等人在SIGCOMM05发布的OpenDHT( )服务 DHT的问题 拓扑一致性问题，带来通信时延的增加 数据对象的语义查询十分困难,17,OpenDHT,OpenDHT：公共DHT服务平台 基于Bamboo DHT，改写自Pastry 设计原则：易于部署，易于使用 客户端不需要运行DHT软件，而是通过OpenDHT服务平台获取所需的服务，从而实现基于DHT的P2P应用 客户端接口API Put(K, V, t)：将发布到OpenDHT网络，t为有效期 Get(K)：根据K从OpenDHT网络获取对,18,OpenDHT体系结构,19,Examples:,Here is an example usage scenario: $ ./put.py colors red Success $ ./get.py colors red $ ./put.py -secret donttell colors blue Success $ ./get.py colors red blue $ ./rm.py colors blue donttell Success $ ./get.py colors red,20,散列函数,散列函数：hash function，提供分布式数据存储功能 安全散列函数：secure hash function，提供安全性、匿名性 一致性散列函数：consistent hash function，提供查询高效性与负载均衡 常用的有： MD5,SHA-1,HMAC(用一个secret key和一个hash function产生一个MAC报文鉴别码) 攻击：强行攻击(2n)，生日攻击（相当于强行攻击的平方根，2(n/2),21,4.3 路由和定位,概念接近，在应用中有区别 “定位”：确定结点或数据对象的位置，通过“路由”完成。结果与过程 路由和定位的方式取决于两个因素：覆盖网拓扑结构、路由表结构 结构化P2P网络通常维护一个较小的路由表，采用分布式、局部性的贪心路由算法，逐步缩小与目的结点之间的ID差异 无结构网络常使用“洪泛法”或变形来路由，效率低且无法保证定位成功,22,一、混合式P2P网络的路由和定位方法,混合式P2P网络都采用服务器路由 用户只要向服务器提交查询，后者即给出回复，回复中包含文件拥有者的信息，用户直接同文件拥有者建立连接，进行文件下载 星型路由，常跳数O(1)，路由性能只取决于服务器,23,二、无结构P2P网络的路由和定位方法,以洪泛法为基础的随机路由，通过TTL限制半径，以减小网络负担，但低效 无结构P2P网络的四种典型路由方法：洪泛法、扩展环、随机走和超结点路由，按结点本身引导路由 导向路由(guided routing)：路由消息时尽量选择可能包含相关内容的结点作为下一跳，按数据对象内容引导路由 要求路由表按照数据对象的内容构造，比如表项中保存文件标识，而文件标识指向可能包含它的结点,24,Freenet是“导向路由”的代表，其路由表按照文件组织，每个表项记录一个文件标识以及文件标识所指向的结点，此结点很可能包含该文件，至少离文件更近 当文件被找到沿原路返回给请求者时，定位路径上的每一跳结点都会在路由表中添加关于此文件的项，将来的定位速度更快 Freenet的标识集群效应,25,Freenet中的“导向路由”过程示例,无下一跳,循环请求,26,三、结构化P2P网络的路由和定位方法,结构化P2P网络的路由和定位方法与其覆盖网拓扑结构、路由表机构密切相关，其本质是：采用分布式、局部性的贪心路由算法，逐步缩小当前结点与目的结点之间的ID差异 路由效率都是O(logN) 典型路由方法：数值邻近路由、逐位匹配路由、位置邻近路由、层次路由、混合式路由 结点度和网络直径对路由算法的影响具有折中关系,27,P2P网络定位至少需要多少跳？,Kaashoek & Karger在IPTPS03关于P2P网络路由的数学结论（数学归纳法可证）： 假设某个分布式系统中共有N个结点，并且结点最大度为d，则在最坏情况下定位至少需要(logdN-1)跳，而平均路由跳数为(logdN-O(1) (logdN-1)称为“Moore Bound”(摩尔界限) 证明： 从任一结点A出发，与其距离在h跳范围内的结点最多有1+d1+d2+dh=d(h+1)/(d-1)个。令d(h+1)/(d-1)=Nh约为O(logN),28,结点度和网络直径的折中关系对路由算法的影响,29,4.4 查询和搜索,查询：精确查询或模糊查询，精确查询等同于定位过程，模糊查询对应搜索过程，结构化P2P网络目前无法提供模糊查询，无结构网络可以模糊查询，但不保证命中 无结构查询方法： 随机走 导向搜索 基于相似内容组的搜索（将结点组织到包含相似内容的多个组中，提高查询效率）,30,结构化P2P网络中的模糊查询方法 关键码搜索 语义搜索 VSM vector space mode LSI latent semantic index Refer to Tang et.al.2003&Zhu et.al.,2003,31,三种P2P模糊查询的方法,路由索引（routing indices）：其本质是一种基于结点内容的无结构P2P查询方法，但也可在结构化P2P网络中使用 论文Crespo & Garcia-Molina, 2002设计了三种路由索引方案：复合索引CRI、跳数索引HRI、指数索引ERI 基于DHT的P2P网络模糊查询Harren, 02 前缀散列树Ramabhadran, 2004,32,路由索引,结点A收到一条关于”Database”和”Languages”的查询请求，那么可以期待的经由B可以访问到的文件数是100*(20/100)*(30/100)=6，经由C能访问到的文件数是1000*(0/1000)*(50/1000)=0，经由D能访问到文件数是200*(100/200)*(150/200)=75，所以B、C、D的Goodness值分别是6,0,75。基于这个衡量准则，很明显A将会把查询请求发给D。Goodness计算如下式：CRI（Si)表示复合路由索引中第i个话题Si的文件数,33,34,基于DHT的P2P网络模糊查询,文本检索和散列索引 N-grams Beethovens 9th12个3元子串:Bee eet eth tho hov ove ven ens ns_ s_9 _9t 9th 通常拆分为2或者3长子串 可以有效直接关键码匹配的模糊查询(对于每个查询如thoven，可分解为tho,hov,oev,ven4个3元搜索子串，返回结果再做concatenation，如定位的文档至少在每个子串中出现一次。,35,前缀散列树,36,前缀散列树的“线性查询”算法,37,前缀散列树的“二分查询”算法,38,39,4.5 动态结点算法,在新结点加入时通知其他结点新成员的到来 在旧结点离开时通知其他结点老成员的离去 高效合理地检测到结点失效并修复P2P网络,40,混合式P2P网络的动态结点算法,所有处理都由中心服务器完成 加入：用户连接到服务器，告诉服务器自己的信息，服务器将其保存下来，按照需要或者周期性地把新用户信息发给其他用户 离开：用户告诉服务器自己即将离开，服务器从数据库中删除该用户的信息，并通知其他用户以更新缓存 失效：服务器周期性检测,41,无结构P2P网络的动态结点算法,Gnutella动态结点算法 加入： 新结点N连接到众所周知的Gnutella结点，通过后者连入网络并获得最初的邻居表 N广播PING消息，收到该消息的结点决定是否回播PONG消息，并将PING广播给它的邻居 Peer通过周期性地发送PING消息、回复PONG消息来维护路由表,42,KaZaA动态结点算法,KaZaA是双层无结构P2P网络，普通结点不论加入还是离开，都通过连接超结点完成 KaZaA网络通过结点间频繁交换结点列表来保持自适应性 每当普通结点连接到超结点时，后者都会回送一个超结点更新列表 超结点之间也频繁交换超结点更新列表，重新组织和优化自己以保持较高的自适应性,43,eDonkey的动态结点算法 与KaZaA工作原理类似，算法本质相同 Freenet的动态结点算法 由于要始终通过加密方法保证安全、匿名，新结点的加入需要一个复杂的多方协商过程，采用链式“承诺”的方法防止恶意结点的加入,44,结构化P2P网络的动态结点算法,结点加入 Join Step1：新结点N以某种方式找到一个网络众所周知结点G，称为“自举结点” Join Step2：N通过G发送以N为目的地的消息，该消息最终到达ID与N最接近的结点Z，N从Z或者从消息路径的每个结点中获取路由表信息以及应由自己负责的数据，之后再做修正和优化，这一步开销最大 Join Step3：通知邻居结点更新路由表,45,结点离开和失效 主动离开：通知邻居结点更新路由表并接管数据，可看作加入Join Step3的逆过程 结点失效：周期性检测路由表中的邻居；发现失效结点后进行路由表修复；Tapestry还采用“软状态重发布”的方法让结点定期重新发布自己的对象信息；CAN则多了一个“背景区域重分配”过程 对结点失效的处理是结构化P2P网络最大的开销所在,46,4.6 容错性,P2P网络工作在一个极具动态性和成员不可靠的环境下，错误来源包括结点失效、结点负担过重、恶意攻击等 典型的容错机制 冗余方法：通过保存适当的冗余信息，提供有效的替代，以空间换取容错 周期性检查：通过每个结点周期性地检测，及时纠正错误，以时间换取容错,47,为了保证容错，结点度至少需要多少？,定理：对于一个网络而言，假设其中每个结点失效概率为1/2，那么为了使网络以常数概率保持连通，其中某些结点度必须为 (logN) 证明见IPTPS03Kaashoek&Karger,2003,48,容错的传统方法冗余,混合式P2P网络是以服务器为核心的网络，其容错性只在于服务器的故障概率，可以采用“硬件冗余”，但成本太高，所以实际系统可靠性不高 无结构P2P网络和结构化P2P网络没有硬件服务器的概念，可以采用“软件冗余”，包括路由表项冗余或者数据对象复制,49,容错性的分类（仅针对结点失效）,静态容错性(static resilience)：在保持路由表不变、不做修复的情况下，仅仅删除网络中那些失效结点的相关项，所看到的P2P网络的查询成功率 路由恢复下的容错性(routing recovery resilience)：对路由表进行修复,50,静态容错性 影响静态容错性最关键的因素是“灵活性” (flexibility)，即在确定了源结点和目的结点的情况下，网络中有多少个可选的邻居结点和多少条可选的路由路径 路由恢复下的容错性 按需恢复：直到发现的时候才进行恢复 稳定化恢复：周期性检测并恢复 捎带恢复：使用每条接收到的消息捎带更新,51,网络动态性的分类,P2P网络的动态性称为“搅动”(churn)：即结点频繁加入、离开或者失效的现象 普通搅动：结点一个接一个地串行加入P2P网络，或者离开前通知其邻居更新路由表。这些搅动事件发生的频率不高，并且网络有足够的时间来做修复，以保持P2P网络应有的结构和连通性 高搅动：大量的结点频繁并且并发地加入、离开或者失效P2P网络的“试金石”,52,P2P覆盖网分割问题,覆盖网分割(overlay partitioning)也称为“网络分割”，一直是P2P领域的一大难题 两种导致覆盖网分割的情况 粗糙的覆盖网设计，没有考虑到维护连通性 不规则的、意料之外的结点行为 只要离开的结点构成一个“点割集”或者相关边构成一个“边割集”，覆盖网就会被分割,53,崩溃点Crash Point,50%查询失败作为崩溃点(如果查询成功率低于50%，有理由认为网络被分割),54,五种P2P网络崩溃点实验测量结果,55,缓解覆盖网分割问题的四种方法,主动避免和事件驱动：要求所有结点的加入和离开都必须预先通知服务器，不现实 主动避免和周期检测：周期性地检测覆盖网割点，并通过割点主动加边以将自己调整成普通结点，以尽量避免割点的存在 被动修复和事件驱动：其设计方法只适用于可以提供数据语义、消息路由双重局部性的特殊网络，不具有通用性 被动修复和周期检测：结点与邻居间交叉验证，缺点是随机、不确定性,56,思考题,1、PHT本质展现了本地数据结构如何利用DHT实现分布数据结构的策略，它实现了DHT的范围搜索。试考虑支持模糊搜索。 2、设计一种可以有效处理overlay partition的算法。,57,学期论文IDEA之三,Searching Similarity Documents unstructured overlay Structured overlay Interest-Cluster PAIS: A Proximity-Aware Interest-Clustered P2P File