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网络的路由和定位方法与其覆盖网拓扑结构、路由表机构密切相关，其本质是：采
15、用分布式、局部性的贪心路由算法，逐步缩小当前结点与目的结点之间的ID差异l路由效率都是O(logN)l典型路由方法：数值邻近路由、逐位匹配路由、位置邻近路由、层次路由、混合式路由l结点度和网络直径对路由算法的影响具有折中关系27P2P网络定位至少需要多少跳？l Kaashoek & Karger在IPTPS03关于P2P网络路由的数学结论（数学归纳法可证）： 假设某个分布式系统中共有N个结点，并且结点最大度为d，则在最坏情况下定位至少需要(logdN-1)跳，而平均路由跳数为(logdN-O(1)l (logdN-1)称为“Moore Bound”(摩尔界限)l 证明：从任一结点A出发，与其距
16、离在h跳范围内的结点最多有1+d1+d2+dh=d(h+1)/(d-1)个。令d(h+1)/(d-1)=Nh约为O(logN)28结点度和网络直径的折中关系对路由算法的影响294.4 查询和搜索l查询：精确查询或模糊查询，精确查询等同于定位过程，模糊查询对应搜索过程，结构化P2P网络目前无法提供模糊查询，无结构网络可以模糊查询，但不保证命中l无结构查询方法：随机走导向搜索基于相似内容组的搜索（将结点组织到包含相似内容的多个组中，提高查询效率）30l结构化P2P网络中的模糊查询方法关键码搜索语义搜索lVSMvector space modelLSI latent semantic indexlR
17、efer to Tang et.al.2003&Zhu et.al.,200331三种P2P模糊查询的方法l路由索引（routing indices）：其本质是一种基于结点内容的无结构P2P查询方法，但也可在结构化P2P网络中使用 论文Crespo & Garcia-Molina, 2002设计了三种路由索引方案：复合索引CRI、跳数索引HRI、指数索引ERIl基于DHT的P2P网络模糊查询Harren, 02l前缀散列树Ramabhadran, 200432路由索引l 结点A收到一条关于”Database”和”Languages”的查询请求，那么可以期待的经由B可以访问到的文件数是100*(
18、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的文件数3334基于DHT的P2P网络模糊查询l 文本检索和散列索引N-gramsl Beethovens 9th12个3元子串:Bee eet eth tho hov ove ven ens ns_ s_9 _9t 9thl 通常拆
19、分为2或者3长子串可以有效直接关键码匹配的模糊查询(对于每个查询如thoven，可分解为tho,hov,oev,ven4个3元搜索子串，返回结果再做concatenation，如定位的文档至少在每个子串中出现一次。35前缀散列树36前缀散列树的“线性查询”算法37前缀散列树的“二分查询”算法38394.5 动态结点算法l在新结点加入时通知其他结点新成员的到来l在旧结点离开时通知其他结点老成员的离去l高效合理地检测到结点失效并修复P2P网络40混合式P2P网络的动态结点算法所有处理都由中心服务器完成l加入：用户连接到服务器，告诉服务器自己的信息，服务器将其保存下来，按照需要或者周期性地把新用户信
20、息发给其他用户l离开：用户告诉服务器自己即将离开，服务器从数据库中删除该用户的信息，并通知其他用户以更新缓存l失效：服务器周期性检测41无结构P2P网络的动态结点算法lGnutella动态结点算法l加入：新结点N连接到众所周知的Gnutella结点，通过后者连入网络并获得最初的邻居表N广播PING消息，收到该消息的结点决定是否回播PONG消息，并将PING广播给它的邻居lPeer通过周期性地发送PING消息、回复PONG消息来维护路由表42KaZaA动态结点算法lKaZaA是双层无结构P2P网络，普通结点不论加入还是离开，都通过连接超结点完成lKaZaA网络通过结点间频繁交换结点列表来保持自适
21、应性l每当普通结点连接到超结点时，后者都会回送一个超结点更新列表l超结点之间也频繁交换超结点更新列表，重新组织和优化自己以保持较高的自适应性43leDonkey的动态结点算法与KaZaA工作原理类似，算法本质相同lFreenet的动态结点算法由于要始终通过加密方法保证安全、匿名，新结点的加入需要一个复杂的多方协商过程，采用链式“承诺”的方法防止恶意结点的加入44结构化P2P网络的动态结点算法l结点加入Join Step1：新结点N以某种方式找到一个网络众所周知结点G，称为“自举结点”Join Step2：N通过G发送以N为目的地的消息，该消息最终到达ID与N最接近的结点Z，N从Z或者从消息路径
22、的每个结点中获取路由表信息以及应由自己负责的数据，之后再做修正和优化，这一步开销最大Join Step3：通知邻居结点更新路由表45l结点离开和失效主动离开：通知邻居结点更新路由表并接管数据，可看作加入Join Step3的逆过程结点失效：周期性检测路由表中的邻居；发现失效结点后进行路由表修复；Tapestry还采用“软状态重发布”的方法让结点定期重新发布自己的对象信息；CAN则多了一个“背景区域重分配”过程l对结点失效的处理是结构化P2P网络最大的开销所在464.6 容错性lP2P网络工作在一个极具动态性和成员不可靠的环境下，错误来源包括结点失效、结点负担过重、恶意攻击等l典型的容错机制冗余
23、方法：通过保存适当的冗余信息，提供有效的替代，以空间换取容错周期性检查：通过每个结点周期性地检测，及时纠正错误，以时间换取容错47为了保证容错，结点度至少需要多少？l定理：对于一个网络而言，假设其中每个结点失效概率为1/2，那么为了使网络以常数概率保持连通，其中某些结点度必须为(logN)l证明见IPTPS03Kaashoek&Karger,200348容错的传统方法冗余l混合式P2P网络是以服务器为核心的网络，其容错性只在于服务器的故障概率，可以采用“硬件冗余”，但成本太高，所以实际系统可靠性不高l无结构P2P网络和结构化P2P网络没有硬件服务器的概念，可以采用“软件冗余”，包括路由表项冗余
24、或者数据对象复制49容错性的分类（仅针对结点失效）l静态容错性(static resilience)：在保持路由表不变、不做修复的情况下，仅仅删除网络中那些失效结点的相关项，所看到的P2P网络的查询成功率l路由恢复下的容错性(routing recovery resilience)：对路由表进行修复50l静态容错性影响静态容错性最关键的因素是“灵活性” (flexibility)，即在确定了源结点和目的结点的情况下，网络中有多少个可选的邻居结点和多少条可选的路由路径l路由恢复下的容错性按需恢复：直到发现的时候才进行恢复稳定化恢复：周期性检测并恢复捎带恢复：使用每条接收到的消息捎带更新51网络动
25、态性的分类lP2P网络的动态性称为“搅动”(churn)：即结点频繁加入、离开或者失效的现象l普通搅动：结点一个接一个地串行加入P2P网络，或者离开前通知其邻居更新路由表。这些搅动事件发生的频率不高，并且网络有足够的时间来做修复，以保持P2P网络应有的结构和连通性l高搅动：大量的结点频繁并且并发地加入、离开或者失效P2P网络的“试金石”52P2P覆盖网分割问题l覆盖网分割(overlay partitioning)也称为“网络分割”，一直是P2P领域的一大难题l两种导致覆盖网分割的情况粗糙的覆盖网设计，没有考虑到维护连通性不规则的、意料之外的结点行为l只要离开的结点构成一个“点割集”或者相关边
26、构成一个“边割集”，覆盖网就会被分割53崩溃点Crash Pointl 50%查询失败作为崩溃点(如果查询成功率低于50%，有理由认为网络被分割)54五种P2P网络崩溃点实验测量结果55缓解覆盖网分割问题的四种方法l 主动避免和事件驱动：要求所有结点的加入和离开都必须预先通知服务器，不现实l 主动避免和周期检测：周期性地检测覆盖网割点，并通过割点主动加边以将自己调整成普通结点，以尽量避免割点的存在l 被动修复和事件驱动：其设计方法只适用于可以提供数据语义、消息路由双重局部性的特殊网络，不具有通用性l 被动修复和周期检测：结点与邻居间交叉验证，缺点是随机、不确定性56思考题l1、PHT本质展现了
27、本地数据结构如何利用DHT实现分布数据结构的策略，它实现了DHT的范围搜索。试考虑支持模糊搜索。l2、设计一种可以有效处理overlay partition的算法。57学期论文IDEA之三l Searching Similarity Documents unstructured overlay Structured overlayl Interest-Cluster PAIS: A Proximity-Aware Interest-Clustered P2P File Sharing System,CCGrid 2009,Haiying Shenl Routing Indices Adapti
28、ve Resource Indexing Technique for Unstructured Peer-to-Peer Networks,CCGrid2009,Sumeth Lerthirunwong, Naoya Maruyama, and Satoshi Matsuokal Range Query Range Query Using Learning-Aware RPS in DHT-Based Peer-to-Peer Networks,CCGrid2009,Ze Deng, Dan Feng, Ke Zhou, Zhan Shi, and Chao Luo58实践练习l试用OpenD
29、HT实现一个分布式应用(如anycast、文件分发等)59下次课前阅读：l Cohen and Shenker.02 Edith Cohen and Scott Shenker. Replication Strategies in Unstructured Peer-to-Peer Networks. In SIGCOMM 2002, pp. 84-95. l Rao et al.03 Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, Ion Stoica. Load Balancing in Structured P2P Systems. In IPTPS 2003, pp. 68-79. l Balancing Locality and Randomness in DHTsShuheng Zhou, Gregory R. Ganger, Peter Steenkiste. Carnegie Mellon University Technical Report CMU-CS-03-203, November 2003.
