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

P2P网络的核心机制 1章节内容l4.1 覆盖网拓扑结构l4.2 分布式散列表l4.3 路由和定位l4.4 查询和搜索l4.5 动态结点算法l4.6 容错性24.1 覆盖网拓扑结构lP2P网络是构建在底层物理网（如IP网）上的应用层覆盖网，拓扑结构对P2P网络的工作性能以及设计机制有决定性作用l典型拓扑结构：带弦环、树、Plaxton Mesh、环面、超立方体、蝴蝶、异或l问题：拓扑结构对P2P性能的影响情况？Geometries NaturelFNSlFRSPerformancelResiliencelLatency3Geometries consideredGeometryAlgorithmRingChord, SymphonyHypercubeCANTreePRRHybrid = Tree + RingTapestry, PastryXORd(id1, id2) = id1 XOR id2Kademlia4Geometry = Flexibility = PerformancelGeometry captures flexibility in selecting algorithmslFlexibility is important for routing performance Flexibility in selecting routes leads to shorter, reliable paths Flexibility in selecting neighbors leads to shorter paths5Metrics for flexibilitylFNS: Flexibility in Neighbor Selection= number of node choices for a neighborlFRS: Flexibility in Route Selection= avg. number of next-hop choices for all destinationslConstraints for neighbors and routesselect neighbors to have paths of O(logN) select routes so that each hop is closer to destination6Summary 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) (logN)How relevant is flexibility for DHT routing performance?7Static ResilienceTwo aspects of robust routinglDynamic Recovery : how quickly routing state is recovered after failureslStatic Resilience : how well the network routes before recovery finishescaptures how quickly recovery algorithms need to workdepends on FRSEvaluation:lFail a fraction of nodes, without recovering any statelMetric: % Paths Failed8Does flexibility affect Static Resilience?Tree XOR Hybrid Hypercube Ring9Geometrys impact on ProximitylBoth FNS and FRS can reduce latencyTree has FNS, Hypercube has FRS, Ring & XOR have both lMetric: Overlay Path Latency10Which is more useful: FNS or FRS?Plain FRS FNS FNS+FRSNeighbor Selection is much better than Route Selection11小结l拓扑结构影响性能，其中FRS对resilence显著，而FNS对latency显著。

设计需要tradeoffl参考论文：lGummadi 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.124.2 分布式散列表l分布式散列表(DHT，Distributed hash table)是P2P网络的核心设施，它基于一致性散列函数，提供对于结点、数据对象在覆盖网中的位置映射l结点的映射可以保证准确的定位，还提供了匿名性l数据对象映射的作用在于将其索引信息放到nodelD与objectID最近的结点上，对数据对象的定位需要首先在此结点上找到对象索引lDHT在实现物理网到覆盖网映射的同时，损失了物理网上结点之间的邻近关系，带来了两者的不一致13P2P体系架构及其应用接口14lP2P体系架构上图反映了DHT在P2P网络中的地位：DHT位于结构化P2P应用和P2P覆盖网之间，它组织覆盖网中的结点，向上层提供三个最基本的接口Put(Key, Value)：向网络中存储具有标识Key的数据ValueRemote(Key)：在网络中删除具有标识Key的数据对象Value=Get(Key)：从网络中获取具有标识Key的数据保存在Value中15l目前已在考虑结构化P2P网络公用API的规划，如Karp等在IPTPS04上提出的OpenHash体系以及Rhea等人在SIGCOMM05发布的OpenDHT(www.opendht.org )服务lDHT的问题拓扑一致性问题，带来通信时延的增加数据对象的语义查询十分困难16OpenDHTlOpenDHT：公共DHT服务平台http:/基于Bamboo DHT，改写自Pastry设计原则：易于部署，易于使用客户端不需要运行DHT软件，而是通过OpenDHT服务平台获取所需的服务，从而实现基于DHT的P2P应用l客户端接口APIPut(K, V, t)：将发布到OpenDHT网络，t为有效期Get(K)：根据K从OpenDHT网络获取对17OpenDHT体系结构18Examples:lHere is an example usage scenario: l$ ./ colors red Success l$ ./ colors red l$ ./ -secret donttell colors blue Successl $ ./ colors red bluel $ ./ colors blue donttell Success l $ ./ colors red 19散列函数l散列函数：hash function，提供分布式数据存储功能l安全散列函数：secure hash function，提供安全性、匿名性l一致性散列函数：consistent hash function，提供查询高效性与负载均衡l常用的有：MD5,SHA-1,HMAC(用一个secret key和一个hash function产生一个MAC报文鉴别码)l攻击：强行攻击(2n)，生日攻击（相当于强行攻击的平方根，2(n/2)204.3 路由和定位l概念接近，在应用中有区别l“定位”：确定结点或数据对象的位置，通过“路由”完成。

结果与过程l路由和定位的方式取决于两个因素：覆盖网拓扑结构、路由表结构l结构化P2P网络通常维护一个较小的路由表，采用分布式、局部性的贪心路由算法，逐步缩小与目的结点之间的ID差异l无结构网络常使用“洪泛法”或变形来路由，效率低且无法保证定位成功21一、混合式P2P网络的路由和定位方法l混合式P2P网络都采用服务器路由l用户只要向服务器提交查询，后者即给出回复，回复中包含文件拥有者的信息，用户直接同文件拥有者建立连接，进行文件下载l星型路由，常跳数O(1)，路由性能只取决于服务器22二、无结构P2P网络的路由和定位方法l以洪泛法为基础的随机路由，通过TTL限制半径，以减小网络负担，但低效l无结构P2P网络的四种典型路由方法：洪泛法、扩展环、随机走和超结点路由，按结点本身引导路由l导向路由(guided routing)：路由消息时尽量选择可能包含相关内容的结点作为下一跳，按数据对象内容引导路由l要求路由表按照数据对象的内容构造，比如表项中保存文件标识，而文件标识指向可能包含它的结点23lFreenet是“导向路由”的代表，其路由表按照文件组织，每个表项记录一个文件标识以及文件标识所指向的结点，此结点很可能包含该文件，至少离文件更近l当文件被找到沿原路返回给请求者时，定位路径上的每一跳结点都会在路由表中添加关于此文件的项，将来的定位速度更快lFreenet的标识集群效应24Freenet中的“导向路由”过程示例无下一跳循环请求25三、结构化P2P网络的路由和定位方法l结构化P2P网络的路由和定位方法与其覆盖网拓扑结构、路由表机构密切相关，其本质是：采用分布式、局部性的贪心路由算法，逐步缩小当前结点与目的结点之间的ID差异l路由效率都是O(logN)l典型路由方法：数值邻近路由、逐位匹配路由、位置邻近路由、层次路由、混合式路由l结点度和网络直径对路由算法的影响具有折中关系26P2P网络定位至少需要多少跳？lKaashoek & Karger在IPTPS03关于P2P网络路由的数学结论（数学归纳法可证）： 假设某个分布式系统中共有N个结点，并且结点最大度为d，则在最坏情况下定位至少需要(logdN-1)跳，而平均路由跳数为(logdN-O(1)l(logdN-1)称为“Moore Bound”(摩尔界限)l证明：从任一结点A出发，与其距离在h跳范围内的结点最多有1+d1+d2+dh=d(h+1)/(d-1)个。

令d(h+1)/(d-1)=Nh约为O(logN)27结点度和网络直径的折中关系对路由算法的影响284.4 查询和搜索l查询：精确查询或模糊查询，精确查询等同于定位过程，模糊查询对应搜索过程，结构化P2P网络目前无法提供模糊查询，无结构网络可以模糊查询，但不保证命中l无结构查询方法：随机走导向搜索基于相似内容组的搜索（将结点组织到包含相似内容的多个组中，提高查询效率）29l结构化P2P网络中的模糊查询方法关键码搜索语义搜索lVSMvector space modelLSI latent semantic indexlRefer to Tang et.al.2003&Zhu et.al.,200330三种P2P模糊查询的方法l路由索引（routing indices）：其本质是一种基于结点内容的无结构P2P查询方法，但也可在结构化P2P网络中使用 论文Crespo & Garcia-Molina, 2002设计了三种路由索引方案：复合索引CRI、跳数索引HRI、指数索引ERIl基于DHT的P2P网络模糊查询Harren, 02l前缀散列树Ramabhadran, 200431路由索引l结点A收到一条关于”Database”和”Languages”的查询请求，那么可以期待的经由B可以访问到。