P2P网络

nullP2P 结构P2P 结构邓玉辉P2P是什么？P2P是什么？计算机网络  因特网 Internet 网络的基础结构： 1、集中式：C/S = Client/Server -- 好：管理简单，控制有效 -- 坏：Server瓶颈 2、分布式：Distributed -- 好：无瓶颈，资源充分利用 -- 坏：管理松散，难于控制  P2P = 分布式的极端 （since 1956年）自由 平等 互联null网络服务规模三法则网络服务规模三法则Sarnoff ’law：效益规模是O(n)：网络是广播媒介，任1发送者（设备）和多个(n-1)接收者（设备）。 Metcalfe ’law：效益规模是O(n2)网络是全互连媒介，任何1个设备可与其它n-1个交互，同时存在n(n-1)=n2-n个并发执行的事务Reed ’law：效益规模是O(2n)：网络是群组媒介。网络可建立Cn2+Cn3+…Cnn-1+Cnn = 2n-n-1 个小组P2P网络技术的概念和定义P2P网络技术的概念和定义1、Peer-to-peer is a type of Internet network allowing a group of computer users with the same networking program to connect with each other for the purposes of directly accessing files from one another's hard drives. 2、Peer-to-peer networking (P2P) is an application that runs on a personal computer and shares files with other users across the Internet. P2P networks work by connecting individual computers together to share files instead of having to go through a central server.null3、P2P是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源（处理能力、存储能力、网络连接能力、打印机等），这些共享资源需要由网络提供服务和内容，能被其它对等节点(Peer)直接访问而无需经过中间实体。在此网络中的参与者既是资源（服务和内容）提供者（Server），又是资源（服务和内容）获取者（Client）。nullP2P is a special distributed system on the application layer, where each pair of peers can communicate each other through the routing protocol in P2P layers. Overlay网络（为实现某一应用目标，若干peer互联形成一个overlay network） Overlay网络是在应用层之上的网络。由对等点连结而成的网络。 对等联网模式的理念—在资源共享中，现为“ 人人为我，我为人人”的思想。 Overlay网络Overlay网络在现有网络体系结构上新加一层——overlay networks 建立一个使用已有的Internet传输的虚拟网络 Internet也曾经被部署为一个在电话网上的重叠网络 也被成为ALN Multicast (Application-Level). File storage and search 挑战 如何创新和部署 at scaleOverlay网络模型Overlay网络模型nullnullP2P的历史（工业界）P2P的历史（工业界）溯源：（1）Napster -- 1999年，18岁的美国学生Shawn Fanning -- 宿舍开发，朋友共享mp3 -- 半年5000万用户！ -- 2001年，版权纠纷，被迫关闭 nullNapster运行原理Napster是众所周知的音乐交换系统。每个节点登录到服务器上并发送它们的文件清单，发布查询到服务器上查找哪些节点是它们拥有的想要的文件，并直接与目标节点连接下载文件。支持模糊匹配How does Naspter Work (very simple!)How does Naspter Work (very simple!)Application-level: (1) client/server protocol over point-to-point TCP/IP; (2) central directory server. User operation steps: connect to Napster server (http://www.napster.com) upload a request list and the IP address in the server. Index server searches the list and returns results to the IP. User pings the music hosts, looking for best transfer rate. User chooses a music provider for data transfer. The index server does not scale its P2P system. Napster原理Napster原理I have X!insert(X, 1.2.3.4) ...1.2.3.4Napster原理Napster原理Where is file A?search(A) --> 4.3.2.14.3.2.1洪泛请求模式洪泛请求模式过程 每个Peer的请求直接广播到连接的Peers 各Peers又广播到各自的Peers 直到收到应答或 达到最大洪泛步数(典型5-9) 特点 无广告性共享资源 Gnutella 使用该算法,限于公司内通信有效 大量请求占用网络带宽,可扩展性并不一定最好 改进 Kazaa 设立Super-Peer客户软件,以集中大量请求 BT 文件分块 Cache最近请求（2）Gnutella（2）Gnutella2000年3月，Nullsoft公司 Justin Frankel & Tom Pepper: Winamp发明人 版权问上线一个半小时关闭 无结构P2P系统代表 其思想和代码被复制、改写、继承 nullGnutella运行原理、洪泛问题Gnutella原理Gnutella原理Where is file A?（3）KaZaa/Skype,eDonkey/eMule（3）KaZaa/Skype,eDonkey/eMule2009年7月，KaZaa Niklas & Friis 300万在线用户！ Niklas继续创办Skype2000年，eDonkey 2002年，Merkur改良eDonkey  eMule 国内VeryCD层次化无结构P2P系统nullflooding queryUnstructured P2P: GnutellaSuper Node based P2P: KaZaA Super Node based P2P: KaZaA ..................super peerflooding queryKaZaA原理KaZaA原理I have X!insert(X, 123.2.21.23) ...123.2.21.23KaZaA原理KaZaA原理Where is file A?（4）BT（4）BT2002年10月 Bram Cohen穷困潦倒……  企业家Gilmore资助生活费  2003年BitTorrent流行  Bram Cohen依然穷困潦倒   2003年末找到工作！BitTorrent原理BitTorrent原理TrackerADCBBitTorrent原理BitTorrent原理ACBD（5）PPLive, PPS, UUSee（5）PPLive, PPS, UUSeePPLive：姚欣（华中科大本科） PPStream：张洪禹（哈尔滨师大本科）+ 雷量（成都一程序员） UUSee：李竹（清华本科）+ 刘怀宇（清华硕士）（6）迅雷，QQ旋风（6）迅雷，QQ旋风迅雷 2003年，深圳 邹胜龙（硅谷海归）+ 程浩（硅谷海归） 中国最大的互联网资源聚合平台QQ旋风 2007年，上海 腾讯研究院 No.2互联网资源聚合平台 P2P的典型应用P2P的典型应用文件共享 媒体播放 数据存储 分布计算等 根据具体应用不同，可把P2P分为以下这些类型：根据具体应用不同，可把P2P分为以下这些类型：提供文件和其它内容共享的P2P网络，例如Napster、Gnutella、eDonkey、emule、BitTorrent等； 挖掘P2P对等计算能力和存储共享能力，例如http://setiathome.ssl.berkeley.edu/、Avaki、Popular Power等； 基于P2P方式的协同处理与服务共享平台，例如JXTA、Magi、Groove、.NET My Service等； 即时通讯交流，包括ICQ、OICQ、Yahoo Messenger等； 安全的P2P通讯与信息共享，例如Skype、Crowds、Onion Routing等。set@homeset@home计算机系统的架构划分计算机系统的架构划分所有的计算机系统可分为集中式和分布式两类 分布式可进一步划分为C/S和P2P模式 C/S模式可划分为 扁平：所有的客户端仅仅和单个服务器（含重复服务器）通信，如传统的中间件 分层：提高可扩展性，某层的服务器又作为更高层的客户端：如DNS服务器和文件系统P2P体系结构（分为三类）P2P体系结构（分为三类）1、完全集中式 研究目标及重点是应用模式从C/S模式向对等模式的转变 优点：应用模式消除了应用服务器的瓶颈问题并缓解了应用流量的不均衡性，在目录服务器获取资源索引信息之后的所有数据的交换都是在节点间完成的。简单易部署。可以模糊查询。 缺点：单点失效。尽管可以用并行服务器解决。 拓扑结构：非结构化、集中式。 典型代表：Napster null2、非集中式、非结构化 研究目标和重点是去除体系结构上的单点失效问题。对象查询是分布式的。查询是逐跳的，泛洪式直到成功或失败或超时。 优点：自组织的管理模式使得整个系统的鲁棒性得以大幅度增强。可以模糊查询。 缺点：消息传递（泛洪、回溯等）的资源定位模式制约了网络规模的可缩放性。查询效率低。 典型代表：Gnutella、Freenet、KaZaA 拓扑结构：非结构化、非集中式、无规则分布式 拓扑结构示例拓扑结构示例null3、非集中式且结构化 需要解决的问题则是如何增强网络规模的可缩放特性。对象查询也是分布式的。使用DHT技术构造结构化拓扑。对象的查询也是逐跳的执行，经过确定的步跳可以确信是成功的。 拓扑结构：非集中式、结构化。 如：mesh、ring、d-dimension torus and butterfly。 典型P2P网络如：CAN、Chord、Oceanstore等。 优点：在资源管理过程中同时拥有自组织特性、规模的强可缩放特性以及部署的廉价性等等。为规模庞大的资源整合及共享提供了可能性。 缺点：节点仅存在局部视图。缺少权威第三方的控制。不支持模糊查询。文档路由模型(Document Routing Model) 文档路由模型(Document Routing Model) 这种文件路由模型需要用分布式哈希表(Distributed Hash Tables, DHT) ,这是有结构对等网络采用的搜索方法, 也是有结构和无结构对等网络的根本区别。是确定性的算法。 在这种模型下,每个对等体都有一个ID,每个文件有一个关键字Key,当宣告一个关键字为K1的文件时,先通过哈希映射得到对应的K1 → ID1 ,然后将该文件存到ID号为ID1 的节点,文件的存放过程需要将文件路由到该节点ID1。反过来,当查找一个关键字为K1 的文件时,先进行哈希映射得到K1 → ID1 ,然后将该文件从ID号为ID1 的节点上取到该文件,从该网络中取文件需要将请求消息路由到ID1 节点,然后文件从ID1 节点原路返回。 文件路由模式文件路由模式过程 每个网上Peer分配一个随机ID,并知道其他Peers的给定号码 当共享文件发布到系统上时,根据文件名字和内容Hash成为ID 每个Peer将根据该ID向该文件路由 该过程重复执行,直到最近的PeerID是现行Peer的ID 每个路由操作还保持文件副本在本地 当Peer请求某文件时,该请求将用该文件的ID到达Peer,过程重复直到发现文件副本,最终文件下载到请求源端四大结构化模型四大结构化模型2001年，SIGCOMM（网络通信顶尖会议） -- Chord: Ion Stoica等（Berkeley、MIT） -- CAN: Ratnasamy等（Berkeley、AT&T） 2001年，其它两个模型 -- Pastry: Rowstron等（微软、Rice） -- Tapestry: 赵燕斌等（Berkeley） 4个算法实现文件路由4个算法实现文件路由Chord/CAN/Tapestry/Pastry 目标相同 减少路由到指定文件的P2P跳数 减少每个Peer必须保持的路由状态 算法异同 都保证算法的跳数与Peer群组的大小相关 或都指出算法能以高概率完成 方法上的差别很小nullChord 每个Peer保持LogN其他Peer的踪迹(N是群组的全部Peer数) 当Peer加入或离开时,高优化算法版本仅需关注LogN个Peers的变化 CAN 每个Peer保持少于LogN个其他Peers的踪迹 在插入和删除时仅这些Peers受影响 其路由表较小,但到达的路径较长 可能更适合动态通信 Tapestry与Pastry很相似 除减少跳数外,还积极削减每个P2P跳上的时延路由表路由表路由表内容 id－文件标识符 next_hop－存储文件id的另一个节点 file－保存在本地的id标识文件 搜索过程 如果文件id存储在本地，停止搜索，上传文件 如果不在本地，搜索路由表中最接近的id，将请求转到next_hop 如果所有节点都没有找到，返回失败，返回路由表中下一个最接近的id…文件路由原理文件路由原理 4 n1 f4 12 n2 f12 5 n3 9 n3 f9 3 n1 f3 14 n4 f14 5 n314 n5 f14 13 n2 f13 3 n6n1n2n3n4 4 n1 f4 10 n5 f10 8 n6n5query(10)网络趋向于一个小世界－small world,类似六度分隔（Six Degrees of Separation）理论 因此，大部分查询只需经过少量跳数Distributed Hash TableDistributed Hash Table分布式数据结构系统中，可以是环，树，超立方体，跳表，蝶形网络 ... CFS, OceanStore, PAST, ChordDNSnull结构化重叠路由 加入：开始时，联系一个“bootstrap”节点，加入分布式数据结构，获得一个节点id 发布：向数据结构中最近的节点发布文件id的路由信息 搜索：向路由表中最近的节点查询文件id，数据结构保证查询会找到发布节点 获取：两个选项 查询到的节点保存有文件，则从查询结束的节点获取 查询到的节点返回结果：节点x有文件，则从节点x获取 DHT示例－Chord:在一维空间（环）中给每个节点和文件一个唯一的id 例如从[0...2m]中选取 通常是文件和IP地址的hashChord拓扑结构：带弦环Chord拓扑结构：带弦环指网络中任意两节点间距离的最大值，一般用链路数来度量。 Chord介绍 Chord介绍 Chord：最简单、最精确 功能： -- 节点/数据对象 映射到 拓扑网络中 映射方法： -- 节点ID = Hash(IP, port) -- 数据ID = Hash(Value) -- 节点按ID顺时针排列 -- 节点后继 vs 对象后继匿名、 虚节点Chord：插入Chord：插入N32N90N105K80K20K5Circular ID spaceKey 5Node 105Chord：查找Chord：查找N32N90N105N60N10N120K80“Where is key 80?”“N90 has K80” 第二代P2P 第二代P2P没有集中的目录服务器，但是拓扑结构有意义。这个结构意味着P2P网络拓扑被紧紧的控制。比如： Mesh, Ring , d-dimension Torus, K-ary tree。 使用DHT技术，有较好的可伸缩性和查询效率。提供负载均衡和确定性的搜索保证。但是容错性或弹性不好，尤其是在恶意攻击下。文件不是被 随机地而是以特定的位置放置，这样使得连续的查询更加容易满足。 它使用精确的定位算法和特殊的路由使得搜索效率提高。支持精确查询不能支持模糊查询。 But it is not clear how well such designs work with an extremely transient population of nodes and adversarial node failures (except Butterfly). DHTDHTDHT（分布式散列表）第二代的代表第二代的代表Tapestry :用于覆盖网络的定位和路由。Tapestry具有自我管理、容错和灵活平衡负载等特点。 Pastry：是一个路由定位协议，与Tapestry有许多相似性。 CAN：可以在Internet规模的大型对等网络上提供类似哈希表的功能，提供查询服务。CAN具有可扩展、容错和完全自组织等特点。。 CHORD：是一个分布式的非集中式的P2P查询服务，存储关键字/值对。给定一个关键字（key），将key映射到某个结点。如果给对等网络应用的每个数据都分配一个key，那么对等网络中的数据查找问题就可以用Chord很容易地解决了。 OceanStore的目标是提供全球的持久存储系统。 PAST是基于Internet的，P2P的全球存储应用，它可以提供持久存储、高可用性、可扩展性和安全性。 CFS（Cooperative File System）是一个用于对等网络的只读的存储系统，它可以提供高效率的、鲁棒的和负载平衡的文件存取功能。P2P查询算法P2P查询算法目标查询的算法研究是P2P网络的关键部分。算法的优劣决定了P2P网络性能的优劣。 随机地和确定性地，非泛洪和泛洪式的，集中式的和非集中式的。 除了Napster集中式的查询外，所有其他的P2P网络使用分布式的和逐跳的转发请求查询方式。 null随机查询被转发到一个随机选择的邻居节点。通常有一个较长的路径长度。应用于非结构化P2P网络中。如Gnutella。 泛洪式查询方法是在纯粹分布式结构中采用的方法,不需要向目录服务器报告共享的信息,而是将请求泛洪到直接相连的邻居,直到收到响应,或者达到了最大的泛洪步数。由于这种模型需要很多的网络带宽来进行资源的搜索工作,因而这种模型的扩展性并不是很好,但是在像公司这样的小型团体里还是很有效的。 为了解决扩展问题,引入了混合式结构,把查询请求集中到超级节点,这样就减少了网络带宽的消耗。 TTL/Hops ExampleTTL/Hops ExampleTTL = 7 Hops = 0TTL = 6 Hops = 1TTL = 5 Hops = 2TTL = 4 Hops = 3TTL = 3 Hops = 4Horizon exampleHorizon exampleTTL = 1TTL = 2TTL = 4TTL = 3TTL = 5TTL = 6TTL = 7More about TTL and HopsMore about TTL and HopsIn general, you greatly increase the nodes you can connect to as you broaden your horizon Where nhosts is the number of hosts reachable, nhops is the number of hops, and d is the average number of hosts reachable from each host (degree of connectivity) (assumes acyclic graph) Ping and PongPing and PongAfter knowing where to go to join a network, a servent uses Ping and Pong to locate other nodes to connect to Originally, Ping message sent to the node connected to, which forwarded to all neighbors All those servents willing to connect to the sender respond with Pong Pongs convey IP, Port, Files shared, and distance (hops)泛洪式算法的改进泛洪式算法的改进有各种方法可以控制和减少在分布式无结构P2P网络中基于泛洪搜索方法带来大量不必要流量,这大致可归为三类 基于改进转发机制的方法； 基于缓存的方法； 拓扑结构的优化。 “dynamic TTL setting or expanding ring” and “k-walker random walk”. But “k-walker random walk” may have large lookup length (latency). So object replication mechanisms (such as uniform replication, proportional replication, square-root proportional replication, and log-form replication) are proposed at the same time to reduce the lookup length. Lookup message and length can be simultaneously decreased using cache mechanisms such as: cache some objects in the reverse path of queries 这些改进方法会使得无结构P2P网络在将来会有更广阔的应用。Ping/Pong ExamplePing/Pong ExamplenullnullnullnullnullnullnullnullnullnullP2P 的影响P2P 的影响P2P文件共享产生的流量可能是今天因特网最大的单项流量Source: www.internet2.edu, July ‘04 Internet traffic statistics nullSource: Eurpoean Tier I ISP Feb ‘04 BTHTTPeDonkeyEurpoean traffic by Protocol 不同共享P2P的下载率和使用率不同共享P2P的下载率和使用率 P2P网络中的安全问题P2P网络中的安全问题P2P作为分布式的网络模型,在系统安全中面临着巨大的挑战,它需要在没有中心节点的情况下,提供身份验证、授权、数据信息的安全传输、数字签名、加密等机制。还要避免大量信息传输拥塞、病毒的入侵和恶意代码攻击等问题。 P2P网络的安全问题,归结为以下三类: 1)数据安全问题,包括数据的完整、真实和保密; 2)网络对等节点安全问题,对等机相互信息和个人环境安全; 3)信息安全问题,网络信息内容和版权的管理。 研究内容：上述三类问题即可以作为研究对象。P2P网络中的信任问题P2P网络中的信任问题在纯分布式对等网络中,没有中心控制,具有高度的动态性、自治性和异构性,即:每个用户参与网络是随机的、自愿的,并且不同的用户有不同的能力和可靠性,由此导致不可靠的服务质量及大量欺诈行为的存在,网络的可用性差。目前解决这一问题的有效方法是在P2P网络中建立信誉体制。 所谓信誉体制是指用户通过自己的过去经历或他人的推荐来选择符合自己要求的交互端的一种体制。此体制能激励用户提供可靠高质量的服务,节省时间和通信开销,减少交互风险和损失,促进网络的良性发展。 许多学者对此进行了研究，主要是提出合理的信誉评价方案和信誉计算方法。而信誉体制的安全和有效性是影响网络可用性的关键因素。 P2P网络中的激励机制P2P网络中的激励机制在P2P 系统中所有节点往往更多地表现出自兴趣和理性,单个节点的目标往往是使自身的网络效用 最大化,这样导致了以下问题: (1) 搭便车( free riding)问题, 70%的Gnutella用户不共享任何文件,接近50%的 文件查询命中仅来自1%的Gnutella用户; (2) 公共的悲剧 ( tragedy of common)问题,即网络资源作为非排他性占有的公共资源,被大多数 P2P节点无节制地使用. 如何使节点根据自身的期望,主观上愿意参与共享其资源不仅是困扰P2P系统的问题,同样也严重 困扰着大规模计算资源共享系统.有指出了使用微支付(micro payment)和虚拟流通( virtual currency)的方法来解决P2P文件共享网络中的共享激励问题.null资源放置 　　　在P2P系统中，并非个人资源（比如数据）都放置在各自的机器上，很可能是所有机器共同管理资源，比如在P2P存储系统中经常采用分布式哈希表放置数据，各人数据可能放置在他人的机器上，于是如何进行资源放置就成了必须回答的第一个问题。null资源定位 　　　数据的查找与资源放置方法是直接相关的。对于以DHT方式放置的数据，可以直接定位，但在多数文件共享系统中，用户的文件都是放在各自的机器上，如何知道哪些机器放有用户需要的数据就成为一个关键问题，常常需要较大规模的搜索才可以完成。资源定位就是研究如何更有效率地找到需要的资源所处的位置，尤其是一些在网络中稀有（rare）的数据。null资源获取 　　　资源定位后就需要获得资源，有些资源并不能直接获得，比如计算资源、大文件、流媒体资源。这里的问题主要在于如何才能更高效的获取资源，或者说如何使一些热点资源服务更多的需要该资源的用户，通常这需要尽量发挥P2P系统中所有参与者的能力。而使用P2P模式充分地利用了所有结点的带宽资源，使得并行下载能力得到了极大的扩展。 性能性能P2P系统目标: 聚合分散网络上的存储容量(Napster/Gnutella)和计算周期(SETI@home) 来改进系统的性能 影响非集中化性能的三类资源 处理/存储/网络 网络资源中的带宽和时延是主要因素 中心协调系统(Napster SETI@home) Peers的协调和仲裁通过中心服务器进行 混合P2P以克服这些脆弱点 非集中协调系统(Gnutella Freenet) 用消息传递机制搜索信息和数据 查询搜索的带宽与发送消息数,命中前的Perrs数成正比,优化性能的关键技术优化性能的关键技术复制(Replication) 把对象/文件的拷贝放在请求Peers附近,最小化连接距离 改变数据时必须保持数据拷贝的一致性 OceanStore基于冲突解的更新传播模式支持一致性语义 高缓(Cache) 减少获取文件/对象路径的长度,进而Peers间交换消息数 这一减少很有意义-Peers间通信时延是严重的性能瓶颈 Freenet:命中文件传播到请求者途中所有节点高缓它 目标是最小化时延,最大化请求吞吐率,很少高缓大数据 智能路由和网络组织 社交“小世界”现象,60年美, 明信片均6熟链找到生人 局部搜索策略,代价与网络规模成子-线性增加 OceanStore/Pastry网络上积极移动数据提高性能null