分布式与云计算系统PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,Chapter 8:Peer-to-Peer Computing and Overlay Networks,对等计算和覆盖网络,2,8.1,对等计算系统,P2P,覆盖网络是构建于互联网上的虚拟网络，由大量的边缘客户端计算机组成。,P2P,计算系统已被广泛应用于分布式文件共享、消息传递、在线聊天、流媒体和社会网络中。与传统的分布式系统不同，,P2P,网络是由分布在互联网边缘的节点（,peer,）或客户端自由组成的自治和自组织系统。在,P2P,网络中，节点之间共享计算和数据资源，所有节点按照自愿的方式共同提供丰富的在线服务。,3,图,8-1,基于应用趋势的互联网流量分布,4,P2P,计算系统的基本概念,对于端到端通信来说，如果两个端用户在功能上是对等、相同的，那么就可以认为该通信是,P2P,通信。按照这个定义，早期的分布式系统都可以认为是对等模式的。,P2P,技术利用互联网边缘节点空闲的计算资源（如存储、,CPU,和带宽）和内容资源（如内容文件）来完成大规模任务，比如大规模内容分发、分布式搜索引擎和,CPU,受限的计算任务等。,因为网络边缘节点上的资源在任意时刻都可能增加和移除，所以,P2P,网络中的资源是间断性可用的。,P2P,计算无需中央服务器的协调，没有一个节点拥有全局的视图，每个节点都只有系统的部分视图。节点既作为服务器向其他节点直接提供服务，又作为客户端从其他节点获得服务。,5,P2P,网络具有下列共同的特征：,去中心化：在纯,P2P,计算系统中，节点在功能上是对等的，并不存在中央服务器来协调整个系统。每个节点仅有系统的部分视图来构建覆盖网络，控制其数据和资源。,自组织：自组织意味着系统无需中央管理器来组织分散在所有节点上的计算和数据资源。,P2P,计算系统中的资源是动态或波动的，即资源可以随时随意地增加和移除。,临时连接和动态性：节点可能随时加入或者离开，其可用性是不可预见的。这就导致覆盖网络拓扑和系统规模以较大的幅度变化。,6,匿名性：在去中心化的,P2P,网络中，节点通过迂回路径来发送和接收请求（即两个节点借助一些中间节点通信），这个特点保证了发送者的匿名性。匿名性也可以借助哈希运算来实现。,可扩展性：,P2P,模型消除了传统集中式客户端,/,服务器模型中固有的单点失效问题，每个节点仅仅维护有限的系统状态并和其他节点直接共享资源。这些特征使得,P2P,计算系统具有很高的可扩展性。,容错：在,P2P,网络中，所有节点在功能上是对等的，没有节点支配整个系统。因此，单个节点不会造成系统的单点失效问题，资源可以存储在多个节点来提高容错能力。,7,客户端,/,服务器体系结构和,P2P,体系结构的区别,传统的客户端,/,服务器体系结构由一台服务器和与其连接的大量客户端主机组成。,P2P,计算系统并不需要一台中央服务器，而是由对等主机按照完全分布式的结构组成的。也就是说，客户端,/,服务器体系结构是面向服务器的：服务器把任务分成多个子任务，并把子任务分配给客户端，客户端则独立地完成分配的子任务；或者客户端向服务器请求资源，而服务器把所请求的资源分发到客户端。,与此相反，在,P2P,网络中，客户端（节点）在功能上是对等的，是自治的、自组织的，它们之间直接交换资源。与客户端,/,服务器系统相比，,P2P,系统相对松散而没有结构，安全性和可控性较低。,(a)Client-server architecture (b)P2P computing model,图,8-2,客户端,/,服务器体系结构和,P2P,网络模型的比较,8,9,三种,P2P,网络模型,P2P,分布式计算系统通常维护一定数量的中央服务器用于任务管理或与客户端对等节点的通信，但是客户端对等节点之间却不需要通信。因此在这种系统中，节点是贡献资源的计算系统。,P2P,平台作为中间件基础方便,P2P,系统的开发和部署。该平台提供安全服务、通信服务和标准服务,10,P2P,应用,AAAAAA,最流行的,P2P,应用当属文件共享应用，数据对象在,P2P,内容网络上分发给所有用户。,11,图,8-4 Skype,体系结构及其主要组件,12,图,8-5,对于志愿者计算，,SETIHome,工作负载的分发过程,13,P2P,计算面临的基础挑战,节点资源异构：对等节点在硬件、软件和网络方面都是异构的,系统规模可扩展性：系统的扩展性直接与性能和带宽相关。,所需节点的高效定位：高效的数据或者节点定位算法的设计。,数据局部性和网络邻近性：数据局部性和网络邻近性是现代,P2P,应用的两个主要设计目标。数据局部性是指具有相似属性值的数据保存在覆盖网络拓扑中邻近的节点上，是实现复杂查询操作和快速数据定位的有效方法。网络邻近性是由底层物理,IP,网络中两个节点的距离来度量的。,14,图,8-6,构建网络邻近性感知的,P2P,覆盖网络,15,路由效率：路由算法直接影响着系统的性能。纯,P2P,系统虽然不存在单点失效问题，但仍然面临连接中断、目的不可达、网络图分割和节点失效等问题。,避免,“,搭便车,”,：,P2P,系统依赖于互联网边缘的资源聚集来提高性能，但是参与节点可能是自私的，不愿意贡献任何资源，这就造成了,“,搭便车,”,问题。解决该问题的方法是激励机制。,匿名和隐私：,P2P,系统中的节点希望隐藏自己的信息。匿名是节点的一个选择，特别是对于,P2P,通信系统中的节点。,16,图,8-7,基于,“,洋葱式,”,路由的匿名通信举例,17,信任和信誉管理：要求系统提供一种可信的环境。节点的信任是可以度量的，而且恶意节点会受到处罚。然而,P2P,系统是完全分布式的，节点之间的交互是直接进行的，并不需要经过中央服务器。,网络威胁和攻击防御：,P2P,系统分散和自组织的特点使得实施针对系统的攻击非常容易。拒绝服务和分布式拒绝服务攻击可以通过对其他节点宣称目标节点拥有请求的所有文件并向目标节点泛洪消息来实现，而服务质量攻击则可以通过以较慢的速度发送文件或者发送异于请求的文件来实现。此外，,P2P,系统匿名特性有利于恶意节点对外隐藏信息，更不容易被发现。,18,图,8-8 P2P,网络中通过消息泛洪实现的,DDoS,攻击举例,19,抗扰动（,Churn Resilience,）：,P2P,计算系统中的节点来自互联网边缘的客户端，它们可能随时加入、离开，甚至失效。节点失效使得容错成为,P2P,网络面临的巨大挑战。,抵御共谋盗版：网上盗版阻碍了,P2P,文件共享系统合法化和商业化。不合法文件内容从拥有合法内容的节点处散播给盗版者，这种行为称为共谋。共谋盗版是,P2P,网络中知识产权侵犯的主要来源。,20,P2P,网络系统分类,图,8-9,按照功能和设计模式对,P2P,系统进行分类,21,无结构,P2P,覆盖网络,无结构,P2P,覆盖网络的邻居关系以一种没有约束的随机方式建立。当用户匿名性和低管理开销是系统设计目标时，无结构覆盖网络是较好的选择。无结构,P2P,覆盖网络的特征：,数据随机分布在节点上。,覆盖网络由集中式控制开始，逐渐转移到完全去中心化控制。,没有广播机制（即使有，也是非常受限的）。,在整个网络上的泛洪查询产生大量网络流量。,没有确定性搜索结果的保障。,TTL(time to live,，存活时间,),受限的查询消息可能到达整个网络。,22,结构化,P2P,覆盖网络,在结构化,P2P,覆盖网络中，对等节点按照预先定义好的结构组织，结构化,P2P,覆盖网络的一些有用特征：,覆盖网络上的结构化路由机制。,在节点之上增加应用层覆盖网络。,和基于随机图的覆盖网络相比，路由跳数低。,消除了泛洪和热点区域问题。,保证搜索结果。,提供对等节点之间的负载均衡。,提供良好的可扩展性和容错能力。,如果需要，可以保持数据的局部性。,在拓扑受限的情况下提供自组织能力。,提供增强的安全保护。,支持节点异构。,23,8,2 P2P,覆盖网络及其性质,覆盖网络是建立在物理,IP,网络上的，其中的节点是来自物理网络的主机，而链路则是节点之间的,TCP,连接或者是简单地指向,IP,地址的指针。这个虚拟链路不一定具有相同的权重，可根据链路的类型来为链路赋予不同的权重。,由于终端主机是动态的，需要拓扑维护协议来维护覆盖网络。,新节点借助已经在覆盖网络中的节点来加入覆盖网络，而节点之间使用周期性心跳消息来探测邻居是否存活。如果邻居失效，节点需要按照维护协议选择其他节点连接。,24,物理,IP,网络中的主机可以映射到由虚拟链路建立的覆盖网络。在图,1-17,中，垂直虚线表示了从物理主机到虚拟节点（也称为对等节点）的映射关系。,覆盖网络不需要额外的物理设施，因此易于部署和使用，而且其拓扑也可以根据应用来改变。节点失效处理较为容易，因为节点可以选择其他仍然存活的节点连接。,通信协议没有任何限制，应用设计者可以根据需要设计任意协议。底层物理网络对于覆盖网络设计者来说是透明的，但是为了更好地利用网络资源（如网络邻近性），设计者则需要考虑物理网络。,25,图,1-17,通过映射物理,IP,网络到一个覆盖网络络建立虚拟链接的,P2P,系统结构,26,P2P,网络是一种覆盖网络。根据覆盖图的性质，,P2P,网络可以分为两类：无结构覆盖网络和结构化覆盖网络。,无结构覆盖网络通常基于随机图来建立，节点随机从覆盖网络中选择节点作为邻居。与其相反，结构化覆盖网络图则具有事先定义好的结构（比如环、超立方体等），每个节点具有唯一的标识而且只能和那些标识满足预先定义条件的节点连接。,有些,P2P,覆盖网络则是无结构和结构化覆盖网络的混合，具有无结构和结构化覆盖网络的优点。,27,无结构,P2P,覆盖网络,为了构建一个好的无结构,P2P,覆盖网络，节点的度（即邻居的数目）以及从一个节点到另一个节点所经过的节点数目应该尽量小。此外，加入或离开操作不能对覆盖网络拓扑图造成大的变动。最后，在节点失效或者意想不到地离开时，覆盖网络仍然可以确定消息转发路径。,基于随机图的覆盖网络构建：,ER,（,ErdosRenyi,）随机图可以看做是无结构,P2P,覆盖网络构建的基础模型。,任意两个顶点（节点）有一条边的概率,p,是相同和独立的。对于无结构,P2P,系统来说，,ER,随机图过于随机化，设计分布式路由算法非常困难。,28,小世界（,Small-World,）模型：有两个显著的特性：平均最短路径小和聚类系数高。前者可以减少节点之间的跳数，而后者有利于处理大量用户或者任务同时到来的问题。在小世界模型的,P2P,网络中，每个节点有两类邻居，即近邻居和远邻居。,无标度图：节点的度服从幂律分布，即一个节点的度为,k,的概率与,k-,成正比，其中,是一个介于,(2,3),的常数。当图的规模增大时，直径变化并不大。,P2P,分布式文件共享系统：无结构,P2P,网络最流行的应用当属,P2P,文件共享系统。数据随机分布在节点上，使用泛洪算法来查找所需的文件。为了减少泛洪产生的大量流量，查找消息带有,TTL,以限制泛洪的范围。而且系统并不对搜索结果进行保证。,29,30,图,8-10 Gnutella,系统中的泛洪搜索机制，用于搜索能提供数字内容文件的节点,图,8-11 Gnutella,数据包描述符格式,31,分布式哈希表（,DHT,）,分布式哈希表作为中间件为分布式系统（特别是,P2P,系统）提供信息搜索或者表查询服务。哈希表由（键，值）对组成，,DHT,把这种哈希对存储在标识空间。,图,8-12,分布式哈希表的键值映射,32,图,8-13 DHT,在快速、安全搜索和其他互联网应用中的运用,DHT,部署：,DHT,作为基础提供两种原语，其核心思想是把节点和键映射到标识空间并把键分配给近距离的节点。,DHT,能够实现快速搜索，而且这种搜索具有可证明的搜索时间上限。此外，,DHT,覆盖网络避免了泛洪造成的大量搜索成本，具有更好的可扩展性。,33,结构化,P2P,覆盖网络,结构化覆盖网络是基于,DHT,的,.,使用全局统一的协议来保证任何节点都能够高效路由搜到拥有所需文件的节点，无论文件是稀缺的还是拥有大量副本，这就要求覆盖网络链接具有更多结构化模式。最常见的结构化,P2P,网络是,DHT,覆盖网络。,分布式哈希表：使用分布式哈希实现键查询，失去了数据的局部性，但避免了泛洪查询。,树状结构系统：树状结构的层次化数据访问维持了数据的局部性。,基于跳跃表的系统：通过键排序而不是键查找来加快查询处理。,34,AAAAAA,35,图,8-14,使用,16,个键搜索空间组成的,Chord,网络的例子。指针表建立了位于不同区域节点之间的链接,36,图,8-15,通过重复分割二维坐标空间而构成的,CAN,网络及其路由过程,37,混合式覆盖网络,混合式,P2P,覆盖网络同时具有无结构和结构化覆盖网络的特征。通常有两种方法来建立混合覆盖网络。,第一种是在无结构覆盖网络上增加结构化覆盖网络。混合,P2P,覆盖网络通常保留每种覆盖网络的主要组件，而次要组件则以无开销方法获得。,Pastry,节点的路由表由基于兴趣的覆盖网络的集群来提供，而基于兴趣的覆盖网络中的全局随机节点信息由,Pastry,的叶子节点集提供。,38,图,8-16,构建混合,P2P,覆盖网络：保持主要组件而借助无开销的方法构建次要组件,39,图,8-18 Gnutella,和,Chord,的混合,P2P,体系结构,40,图,8-17,由超级节点构成骨干覆盖网络的,KaZaA,体系结构,第二种是使用超级节点构造骨干覆盖网络,41,42,8,3,路由、邻近性和容错,P2P,系统的两个基本技术，即路由和局部性感知。,路由算法计算如何从一个节点到达另一个节点，应该是分布式的且仅依赖于整个系统本地视图中的节点。局部性感知又称为网络邻近性感知，它使得对等节点与其物理上邻近的节点相连，以便减小平均覆盖网络链路延迟和骨干网带宽消耗。,P2P,覆盖网络是非正式的。因此，系统需要相应的机制来容忍和恢复节点的失效和断开。,43,P2P,覆盖网络的路由,在无结构,P2P,覆盖网络中，因为节点的邻居是不受任何限制而随机选择的，所以无法定位一个特定的节点，而其中的路由算法通常是基于泛洪的。当一个节点,A,从邻居节点,B,收到消息后，它简单地把消息转给发除,B,以外的所有邻居。,在一个由,n,个平均度（邻居的数目）为,k,的节点组成的覆盖网络中，定位一个节点平均需要使用,n(k-1),个消息。因为消息是按照最短路径从源到达目的节点的，所以路由复杂度（即从任意节点到达某个特定节点所需的覆盖网络跳数）直接由覆盖网络图的直径决定。,基于小世界图的覆盖网络直径小，路由复杂度低。,Freenet,就是这样一种覆盖网络。,44,图,8-19 Freenet,中节点的数据存储栈举例,45,图,8-20 Chord,覆盖网络中的表查询路由举例,基于,DHT,的结构化覆盖网络有严格的、事先定义好的结构，这有利于消息的路由。路由的过程就是逐渐减少消息处理节点到目的节点在标识空间上的距离。尽管不同结构的覆盖网络有不同的路由协议，但路由复杂度通常在,O(log n),跳，其中,n,是节点的数目。基于,DHT,的,Chord,网络的表查询路由,:,46,P2P,覆盖网络中的网络邻近性,P2P,覆盖网络是构建于,IP,网络上的逻辑结构，尽管基于随机图的覆盖网络具有良好的容错能力和较低的直径，但这样的覆盖网络忽略了,IP,网络上的网络邻近信息，从而导致物理上邻近的节点在覆盖网络上彼此相距很远，而覆盖网络上邻近的节点在物理网络上彼此也相距很远。这种现象称为拓扑不匹配，结构化,P2P,覆盖网络同样存在该问题,对于结构化,P2P,覆盖网络来说，节点的邻居选择是严格受其结构限制的，,507,根据网络邻近性感知原则优化它们是比较难的。在结构化,P2P,覆盖网络中，有三种方法来实现网络邻近性：地理布局、邻近路由和邻近邻居选择。,47,容错和失效恢复,错误和节点失效,:,节点失效将导致该节点的覆盖网络连接中断，严重影响,P2P,覆盖网络连接性。节点失效对覆盖网络连通性影响的程度依赖于覆盖网络图的性质和失效节点的度。例如，在基于幂律图的,P2P,覆盖网络中，部分节点的随机失效并不会将覆盖网络分割为不连接的几个部分。然而一些度高的节点失效很容易损害覆盖网络，从而导致覆盖网络分割为若干个不连接部分。,48,失效恢复分析：由于失效是经常发生的，,P2P,系统需要有效的从节点失效恢复，如,Chord,借助周期性稳定操作来解决节点失效。另一种方法是让节点周期性地从指针表中随机选择邻居来检测是否活跃。,容错技术：和传统的基于客户端,/,服务器模型的分布式系统不同，在,P2P,系统中没有一个节点拥有全局视图，节点依赖局部视图来发现错误并以完全分散的方式从失效中恢复。,P2P,覆盖网络通过冗余来保证稳定的吞吐量。,错误分析：容错方面的工作需要考虑邻近信息感知的覆盖网络中的容错。,49,抗扰动与失效,P2P,网络经常面临由节点扰动带来的问题，节点扰动来源于非预期节点加入、离开或者失效。,节点失效或者突然离开对网络性能有非常不利的影响，因为失效节点上存储的数据将变得不再可用，而正在从失效节点请求服务的节点需要重新定位服务。,P2P,覆盖网络应该具有容错能力和抗扰动能力。,50,图,8-21,基于,CRP,的覆盖网络设计举例,51,图,8-22 P2P,网络中的,5,种数据分发机制的平均分发时间比较,52,8,4,信任、信誉和安全管理,对等节点的匿名性和动态性导致,P2P,网络容易受到自私和恶意节点的攻击。大多数,P2P,文件共享网络由利己自治节点组成，目前并没有有效的办法来阻止恶意节点加入,P2P,这种开放的网络。为了鼓励节点贡献资源并抵御恶意节点的行为，信任和信誉管理对,P2P,网络变得异常重要。,如果没有信任，节点向其他节点贡献资源的动机会很小。因为担心接收到被毁坏或污染的文件或者被恶意软件利用，节点可能不愿意和不熟悉的节点交互。为了识别出可信任的节点，商用,P2P,应用（如在线商店、拍卖、内容分发和每次交易付费的应用等）需要信誉系统的支持。,53,节点信任和信誉系统,节点信任特征,有两种方法来模型化节点之间的信任或者不信任，即信任和信誉。信任指的是一个节点根据自己对某个节点的直接经验而产生的对该节点的信赖程度，而信誉则是根据其他节点推荐而产生的对某个节点的信赖。为了更好地应对,P2P,开放网络实际情况，必须假设,P2P,系统的参与节点互相并不信任，除非信任得到了证明。,为了建立节点之间的信任或者不信任关系，需要构建一个根据节点过去行为记录而形成的信誉系统。系统的目的是通过一个科学的筛选过程把,“,好,”,节点和,“,坏,”,节点区分开来。信誉系统的性能主要由其周期性更新中的准确性和效率来衡量。,54,0 0 0 0.2 0.8,0.6 0 0 0 0.4,Trust Matrix,M,(,t,)=0 0.7 0 0 0.3,0 0 0 0 0,0.9 0 0 0.1 0,计算信誉所使用的信任矩阵,55,图,8-23 P2P,网络中,5,个节点的信任关系有向图,56,信誉系统,可以构建一个评估系统来测量节点的信誉。在每次交易后，参与交易的节点互评对方，给出诚实的分数，这和我们目前在,eBay,等在线拍卖系统所做的一样。,但是并不是每个节点都是可信的，恶意节点给出的分数是没有意义的，而越可信的节点给出的分数越有意义。这说明需要根据节点的信誉来为反馈分数给予不同的权重。,节点的信誉可能和别的节点不同，信誉可以用一个信誉矩阵来表示。,57,全局信誉聚集,Reputation Vector,V,(,t,),=v1(t),v2(t),v3(t),v4(t),v5(t)=0.32,0.001,0.009,0.04,0.63,v5(,t,+1)=,m,15(t)v1(,t,)+,m,25(t)v2(,t,)+,m,35(t)v3(,t,)=0.8 0.32+0.4 0.001+0.3 0.009=0.2573,Global Reputation Score of Node 5,V,(t,+1,),=v1(t+1),v2(t+1),v3(t+1),v4(t+1),v5(t+1,=0.5673,0.0063,0,0.1370,0.2573,Global Reputation Vector,Normalized Global Reputation Vector,V,(t,+1,),=v1(t+1),v2(t+1),v3(t+1),v4(t+1),v5(t+1),=0.5862,0.0065,0,0.1416,0.2657 ,58,信誉系统的设计目标,高准确性：系统计算所得的信誉分数需要尽量和节点真实的可信度一致。,快速收敛：节点的信誉是随时间变化的，信誉集群化应该快速收敛以反映节点行为的真实变化。,低开销：为了监测和评估节点的信誉，系统只应该消耗有限的计算和带宽资源。,自适应节点动态性：信誉系统都应该能够适应节点的动态性，而不是依赖于预先确定的节点。,针对恶意节点的鲁棒性：系统应该具有良好的鲁棒性。,可扩展性：就准确性、收敛速度和节点额外开销等指标评价来说，信誉系统应该能够扩展到包含大量节点的,P2P,系统。,59,60,信任覆盖网络和,DHT,实现,信任覆盖网络（,TON,）,建立在,P2P,系统之上的虚拟网络。该网络用有向图表示的，其中,TON,图中的节点对应,P2P,系统中的节点。有向边或者连接的权重是两个交互节点的反馈分数。该分数是由连接的源节点生成的，用来评估与其交互的节点（连接的目的）所提供的服务。,例如，节点,N5,在从,N2,和,N7,下载完音乐文件后对两个文件提供节点分别生成值为,0.7,和,0.3,的反馈分数。如果一个节点从同一提供商处获得多个服务，那么该节点在每次交易后产生更新后的分数。,61,图,8-24,用于,P2P,信任管理的信任覆盖网络，其中边的权重是节点对所提供服务的反馈分数。一个节点的全局信誉值是所有入边代表的本地（局部）信任值的加权和,62,DHT,实现,分布式信誉排名需要两个不同的哈希覆盖网络，一个把节点分配给它们的信誉分数管理者，另一个根据节点的全局信誉分数对节点排序。,图,8-25,分布式信誉排名，使用了建立在基于,DHT,的,P2P,系统之上的局部性保持哈希函数,63,图,8-26 PowerTrust,系统功能模块，系统用来聚集信任分数并计算全局信誉值,PowerTrust,：可扩展的信誉系统,64,图,8-27 P2P,网络中两个信誉系统的收敛开销比较,信誉系统的收敛开销,65,图,8-28,两种信誉系统比较：分布式文件系统中的查询成功率,查询成功率,66,加强覆盖网络安全，抵御,DDoS,攻击,当对等节点恶意攻击其他无辜节点时，,P2P,网络的安全性将存在问题。经常发生的有,4,种网络攻击：,如果大量的节点快速或者随机地加入和离开，那么,P2P,系统将进入扰动模式。,针对目标节点的泛洪攻击导致的分布式拒绝服务攻击（,DDoS,）。,路由攻击试图重新路由消息以窃取内容或者实施,DDoS,攻击。,攻击者阻止请求数据的传输将导致存储,/,检索攻击。,为了抵御网络扰动带来的问题，可以强制节点签名所有消息。为了处理,DDoS,攻击，可以复制内容并把内容散播在网络上。,67,8.5 P2P,文件共享和版权保护,P2P,技术使得节点之间以一种分布式的方式自由共享文件。客户端首先进行搜索操作以定位拥有所需文件的节点。客户端直接从文件提供节点下载文件。,P2P,文件共享的最终目标是向所有请求者尽快分发内容。,P2P,内容缓存是提高内容下载速度和流量本地化的有效手段。,快速搜索、副本和一致性,对,P2P,文件共享应用来说，搜索算法扮演着最重要的角色。评价搜索算法的指标有两个：查询路径长度和消息开销。前者用到达目标节点前查询消息经过的节点平均数目衡量，而后者则用搜索操作产生的查询消息平均数目来衡量。,68,在结构化,P2P,覆盖网络中，数据对象的键和节点映射到同一标识空间，节点保存那些键映射到自己所负责标识区域的数据对象。搜索算法和覆盖网络上的路由算法类似。然而在无结构,P2P,覆盖网络应用中，每个节点通常仅保存自己共享的数据对象信息，查询消息在到达目的之前需要访问大量节点。,结构化,P2P,覆盖网络中，每个节点负责一部分标识空间。无结构,P2P,覆盖网络所使用的搜索算法基本上可以归为两类：盲目搜索和有知识的搜索。盲目搜索适合于节点仅保存自己共享的文件信息的应用，而有知识的搜索适用于节点保存其他节点共享的文件信息的应用。盲目搜索通常又被称为泛洪（,flooding,）算法。,泛洪算法节点第一次收到消息后将转发消息给,k,个随机选择的邻居，直到消息的,TTL,减为,0,。查询消息在覆盖网络中从请求节点出发以类似水波传播的方式一轮接一轮地转发。泛洪算法不可避免地带来大量的消息开销。,69,图,8-29 BitTorrent,系统体系结构,70,图,8-30,多个,swarm,组成的,BitTorrent,系统流程示意，每个,swarm,是不同的跟踪器来协调跟踪的,71,图,8-31,一个副本组的辅助结构,副本和一致性,副本技术是提升,P2P,文件共享应用搜索性能的重要手段之一。覆盖网络上的数据副本越多，数据越容易搜索。与副本技术相关的一个重要问题是副本一致性的维护。,72,P2P,内容分发网络,73,图,8-32,全球,CDN,概念，,CDN,使用了位于主要区域或国家的代理服务器,全球内容分发网络,74,三种方法分发数据内容：基于泛洪的方法、基于树的方法和基于,swarm,的方法。,75,版权保护问题和解决方案,P2P,网络能够高效地把大文件分发给大量节点。但目前的,P2P,网络由于音乐、游戏、视频和流行软件的非法下载而被滥用。这不仅导致媒体和内容产业蒙受了巨大的经济损失，也阻碍了,P2P,技术的商用。,系统的目标是阻止,P2P CDN,内的共谋盗版行为，传统,CDN,需要使用大量分布在,WAN,上的代理内容服务器。内容分发者需要在大量服务器上复制或者缓存内容，维护这样的,CDN,所需带宽和资源是非常昂贵的。,P2P,内容网络大幅降低了内容分发的成本，因为它不需要大量的内容服务器，而是利用了开放网络。由于每个节点都可以作为内容提供商，因此，,P2P,网络提高了内容可用性。,76,图,8-33,针对版权保护内容分发的安全,P2P,平台,77,78,图,8-34,可信,P2P,网络中的预先污染，合法客户接收到干净的文件分块（白色），盗版者接收到污染后的文件分块（阴影）,P2P,网络中的共谋盗版预防,随机共谋者识别,79,图,8-35,分布式代理随机招募一些客户（端）来探测可疑节点，当节点向非法请求提供版权保护文件时，汇报共谋行为,80,图,8-36,版权保护,P2P,内容分发系统中节点加入过程，使用了,7,个消息，包含,4,个实体,81,图,8-37,针对三种系统的预防成功率对比,82,Conclusions:,P2P technology enables cost-effective content delivery,but copyright violation is serious.,Napster started P2P/CDN,followed by KaZaA.The BitTorrent has gained growing acceptance,P2P video streaming demands jitter-free operations,if the QoS must be guaranteed.,IPTV becomes the hottest Internet applications just look at the success of youtube.,P2P technology can lower the cost of VoD,IPVoice,and IPTV services,significantly.,83,Major References:,G.Pallis and A.Vakali,2006.,“Insight and Perspectives for Content Delivery Networks,”,Comm.of The ACM,Vol.,49,No.1(Jan.2006),pp.101-106,M.Hofmann and L.Beaumont,Content Networking,Chapters 6 and 9,Morgan Kaufmann,2005,Y.Huang,et al,“Challenges,Design,and Analysis of a Large-Scale P2P VoD System”,ACM SIGCOMM 08,Seattle,2008.,X.Lou and K.Hwang,“Collusive Piracy Prevention in P2P Content Delivery Networks”,IEEE Trans.on Computers,July,2009,pp.970-983.,X.Lou and K.Hwang,“Jitter-Free Video Streaming in P2P Networks”,ACM Trans.on Multimedia Computing,Communication,and Applications,accepted to appear 2011,