P2P原理与技术课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,xx,HUST,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,xx,HUST,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,xx,HUST,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,xx,HUST,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,xx,HUST,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,xx,HUST,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,xx,HUST,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,xx,HUST,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,xx,HUST,*,P2P,原理与技术,Firewall,因特网洲际主干,洲际主干,ISP,消费者用户,第三方内容,Web,服务器,应用服务器,因特网主干,地区网络,企业网提供商,ISP,专业提供商,本地,ISP,T1,社团用户,社团网络,数据库,xx,消费者用户,Peer,Peer,Peer,Peer,xx,华中科技大学计算机学院,CERNET,华中地区网络中心,xx,HUST,1,P2P原理与技术Firewall因特网洲际主干洲际主干ISP,P2P,原理与技术,概述,分类,构件与算法,关键技术特性,P2P,分析与比较,研究与未来,xx,HUST,2,P2P原理与技术概述xx HUST 2,1.1,什么是,P2P,P2P,：,Peer-to-Peer,对等,(,网络，计算,),;,端到端,以非集中方式使用分布式,资源,来完成,关键任务,的一类系统和应用,资源,包括计算能力、数据（存储和内容）、网络带宽和场景（计算机、人和其它资源）,关键任务,可能是分布式计算、数据,/,内容共享，通信和协同、或平台服务,典型位置：因特网边界或,ad-hoc,网内,xx,HUST,3,1.1 什么是P2PP2P：Peer-to-Peerxx,网络服务,规模三法则,1,2,n-1,A:Sarnoff,law :,规模是,O(n),B: Metcalfe,law :,规模是,O(n,2,),C,n,3,C,n,n-1,C,n,2,C,n,2,C: Reed,law,：规模是,O(2,n,),Sarnoff,law,：效益规模是,O(n),：网络是广播媒介，任,1,发送者（设备）和多个,(n-1),接收者（设备）。,Metcalfe,law,：效益规模是,O(n,2,),网络是全互连媒介，任何,1,个设备可与其它,n-1,个交互，同时存在,n(n-1)=n,2,-n,个并发执行的事务,Reed,law,：效益规模是,O(2,n,),：网络是群组媒介。网络可建立,Cn,2,+Cn,3,+,Cn,n,-1+Cn,n,= 2,n,-n-1,个小组,xx,HUST,4,网络服务规模三法则12 n-1A:Sarnoff la,P2P,的效果,巨大的,扩展力,通过低成本交互来聚合资源，导致整体大于部分之和。,低成本的,所有权,和,共享,使用现存的基础设施、削减和分布成本,匿名和隐私,允许对等端在其数据和资源上很大的自治控制,xx,HUST,5,P2P的效果巨大的扩展力xx HUST 5,P2P Network,Linux,NAT,TCP/IP,Bluetooth,HTTP,Firewall,TCP/IP,TCP/IP,Application,XP,P2P,的网络基本构成,xx,HUST,6,P2P NetworkLinuxNATTCP/IPBluet,P2P,今天的影响,P2P,文件共享产生的流量可能是今天因特网,最大的单项流量,Source: www.internet2.edu, July 04,Source: Eurpoean Tier I ISP Feb 04,BT,HTTP,eDonkey,Internet2,traffic statistics,Eurpoean traffic,by Protocol,xx,HUST,7,P2P 今天的影响P2P文件共享产生的流量可能是今天因特网最,不同共享,P2P,的,下载率,和,使用率,xx,HUST,8,不同共享P2P的下载率和使用率 xx HUST 8,分布式,P2P,仿真,Deflection capabilities,Responsiveness,全系统仿真由许多子系统仿真构成,Lift Capabilities,Drag Capabilities,Responsiveness,Thrust performance,Reverse Thrust performance,Responsiveness,Fuel Consumption,Braking performance,Steering capabilities,Traction,Dampening capabilities,Crew Capabilities,- accuracy,- perception,- stamina,- re-action times,- SOPs,引擎模块,机身模块,翅膀模块,起落架装置模块,水平尾翼模块,乘员模块,xx,HUST,9,分布式 P2P 仿真Deflection capabilit,Foldinghome/,蛋白质折叠和药物设计,虚拟超级计算机,peer-to-peer technology,产生空前大量的计算能力,使医疗研究者能加速治疗方法的改进和药物的设计,加快癌研究的新发现,http:/www.stanford.edu/group/pandegroup/Cosm/, P2P,的定义,Intel,工作组：通过在系统之间,直接交换,来,共享计算机资源和服务,的一种应用模式,A.Weytsel:,在因特网,周边,以,非客户,地位使用的设备,R.l.Granham:,通过,3,个关键条件定义,具有,服务器质量,的可运行计算机,具有独立于,DNS,的,寻址,系统,具有与,可变连接合作,的能力,C.Shirky:,利用,因特网边界的,存储,/CPU/,内容,/,现场,等资源的一种应,访问这些非集中资源意味着运行在,不稳定连接和不可预知,IP,地址环境,下，,P2P,节点必须运行在,DNS,系统外边,具备有效或全部的,自治,xx,HUST,11,1.2 P2P的定义Intel 工作组：通过在系统之间直接交,Kindberg:,独立生存,的的系统,D.J.Milojicic:,给对等组提供或从对等组获得,共享,对等端向组,给出,某些资源，并从组,获得,某些资源,Napster:,把音乐供给组内其他人，并从其他人获得音乐,捐赠计算资源用于外星生命的搜索或战胜癌症，获得帮助其他人的满足,另一种应用模式选择：,相对集中式、和,C/S,模式,纯,P2P,：没有服务器的概念，所有成员都是对等端,并不是全新的概念,早期分布式系统：如,UUCP,和交换网络,电话通信,计算机网络中的通信、网络游戏中的诸玩家,自助餐，志愿组活动,xx,HUST,12,Kindberg:独立生存的的系统xx HUST 12,1.3 P2P,与,C/S,二者在结构和构成上有,很大区别,管理能力、构态能力、功能（查找或发现）、组织,(,分层与网孔,),、元素（,DNS,）和协议,(IP),但又,无明显边界,都能运行在不同的（,Internet / Intranet,）平台上,都能服务传统或新的应用：,eBusiness eServuices,Peer,Peer,Client,Server,xx,HUST,13,1.3 P2P 与 C/S二者在结构和构成上有很大区别Pee,有管理,自组织,预构,-,Ad-hoc,查找,发现,分层,Mesh,静态,移动,依赖服务器,独立生存,以,IP,为中心,不以,IP,为中心,基于,DNS,客户命名,RPC,异步,.NET,JXTA,C/S,模式,P2P,模式,CORBA,CORBA,Gnutella,Napster,eBusiness,Web apps,eServices,Distr.apps,Ad-hoc NW,Clusters,Internet Intranet,WANs,Grids,P2P,与,C/S,xx,HUST,14,有管理自组织预构-,1.4 P2P,相关背景,一般计算和因特网特殊计算的历史演进：因特网边界计算：,如,SETIhome,和其它分布式计算系统,内容共享的社会方面：如,Napster,音乐和其他文件,/,内容共享系统,计算机、网络通信技术的进步和改进,大型机,桌面,PC,便携机,手持设备（手机）,使通信和协同变得更方便,P2P,软件结构：如,JXTA,，,.NET,开发的,P2P,算法：如,Gnutella,，,FreeNet,xx,HUST,15,1.4 P2P 相关背景一般计算和因特网特殊计算的历史演进：,1.5 P2P,之目标：满足应用需要,共享,/,削减成本：,Napster,共享文件空间，,SETIhome,聚合未用资源,改进,可扩展性,/,可靠性,：对缺乏很强中心授权的自治对等端这点尤为重要,资源聚合,与,互操作,能力,增加自治,匿名,/,隐私：自治的理念和结果。用户不希望任何人或,ISP,知道其包含在系统中,动态性,;,资源,动态进入或离开,系统,实现,Ad-hoc,通信,和协同，动态的理念和结果,xx,HUST,16,1.5 P2P之目标：满足应用需要共享/削减成本：Napst,P2P,解决方案,JXTA , .NET,服务,分布式计算,协同与通信,内容共享,仿真,市场,计算,人口,分析,.,基因,系列,分析,蛋白,折叠,.,游戏,文件共享,.,进程,管理,在线,存储,.,即时,消息,白板,.,平台,市场,/,工业,应用实例,水平技术,金融,生物,通信,企业,娱乐,xx,HUST,17,P2P解决方案JXTA , .NET 服务分布式计算协同与通,2 P2P,分类,所有的计算机系统可分为集中式和分布式两类,分布式可进一步划分为,C/S,和,P2P,模式,C/S,模式可划分为,扁平：所有的客户端仅仅和单个服务器（含重复服务器）通信，如传统的中间件,分层：提高可扩展性，某层的服务器又作为更高层的客户端：如,DNS,服务器和文件系统,计算机系统,混合,纯,分层,扁平,P2P,C/S,分布式系统,集中式系统,（巨型机,/SMP/,工作站）,xx,HUST,18,2 P2P分类所有的计算机系统可分为集中式和分布式两类计算,纯,P2P,系统：如,Gnutella,和,Freenet,混合,P2P,系统：首先从服务器获得元数据或索引信息，如存储某些信息的对等端的标识符，或安全信誉的验证，以后,P2P,通信直接和对等端进行，典型系统有：,Napster,Groove , Aimster , Magi , Softwax ,iMesh,以及华中科技大学的,5Q,;Anysee,某些有,SuperPeers,的中间形式：如,Kazaa,，超级,Peers,拥有其他,Peers,没有的信息，它们常常在不能发现时查找这些超级,Peers,Peers,Server,2,3,Peers,Server,1,混合,P2P,的资源寻找过程,xx,HUST,19,纯P2P系统：如Gnutella 和 FreenetPeer,2.1 P2P,系统的分类,平台,协同,文件共享,分布式计算,P2P,系统,SETIhome,Avbaki,Entropia,Napster,Gnutella,Freenet,Publius,Free Haven,Magi,Groove,Jabber,JXTA,.NET,.NET,MyServices,xx,HUST,20,2.1 P2P系统的分类平台协同文件共享分布式计算P2P系统,P2P,多维视图,分布式计算,计算,文件共享,-,存储,Centerspan,Cybiko,平台,.NET,JXTA,Globus,Avaki,Porivo,Technology,Entropia, DataSynapse,SETIhome,United Device,通信与协同,-,带宽,Jabber,AiMster,Gnutella,Freenet,Mojo Nation,Pointera,OnSystems,Napster,Free Haven,Publius,Groove,Magi,xx,HUST,21,P2P 多维视图分布式计算文件共享-存储Centerspan,2.2 P2P,应用分类,P2P,应用,并行化,内容和文件管理,协同,计算密集,构件化,构件化,过滤挖掘,文件系统,即时消息,共享应用,游戏,xx,HUST,22,2.2 P2P 应用分类P2P 应用并行化内容和文件管理协同,可并行化,P2P,应用,计算密集型：把一个大的任务分解成许多可在大量独立对等端省并行执行的子任务。,基本思想是：利用连接在因特网上的诸多计算机的空闲周期来解那些需要大量计算的不同问题。,通常是那些使用不同参数的相同计算任务,:,如外星生命搜索,SETIhome,，密码破解，风险预测，市场和信誉评估，人口统计分析,构件化应用：还没有广泛认着为,P2P,应用,在许多对等端上运行,不同的构件,如,Workflow , JavaBean, Web Services,xx,HUST,23,可并行化P2P应用计算密集型：把一个大的任务分解成许多可在大,内容和文件管理,集中应用,信息存储,信息查询（来自网络上各种,Peers,）,大众模式：内容交换,2001,年：,Napster,和,Gnutella,让,Peers,搜速和下载文件,当前重点是提供可靠性：用户下载文件时的智能选择，重复,DB,协同过虑和挖掘开始出现,xx,HUST,24,内容和文件管理集中应用xx HUST 24,协同,什么是协同应用？,允许用户实时协同,不依赖中心服务器去搜集和转发消息,应用实例,实时消息：,Yahoo!,、,AOL,和,Jabber,已在各种计算机用户之间广泛使用,同行共享：,Buzzpad,分布式,Power Point,异地同时互动评审、编辑同一信息,P2P,游戏：,NetZ 1.0 ,Scour Exchange,Cybiko,游戏运行在所有,Peer,的计算机上，更新也分布在所有,Peer,端，不需要中心服务器,xx,HUST,25,协同什么是协同应用？xx HUST 25,P2P,平台环境,P2P,平台,由,Internet,、,Intranet,和,Ad-hoc,网构成,从拨号线到宽带都可支持,P2P,当前结构多是个人,家庭主机,、单位桌面机和个人移动计算机（便携和手持）,历史与现状,早期,P2P,系统多用家庭机进行内容共享，,Napster,Gnutella Aimster,分布式计算多基于桌面机，,SETIhome,Ad-hoc,手持网络最近可用，专于协同计算,，如,Endeavors, Technologies Magi,。,发展：更大的场景,单位桌面机支持内容共享、,IDC,与手持机资源聚合、,NGI/Inernet2,支持,P2P,系统和应用,xx,HUST,26,P2P 平台环境P2P平台xx HUST 26,2.3 P2P,市场分类,P2P,市场,消费类,企业,公用,内容交换,通信,生物技术,金融,B2B,内容交互,数字版权,娱乐,xx,HUST,27,2.3 P2P 市场分类P2P 市场消费类企业公用内容交换通,消费空间,个人：音乐和内容共享，及时消息，,email,和游戏,团体：,Napster Gnutella,方式：内容交换和通信,企业空间,单个应用：生物、金融、传统,IT,解决方案（,B2B,）,联合应用：,Data Synapse/Information Architects WorldStreet,公用空间,信息共享,数字版权管理,娱乐,CenterSpan,AIM,Scour,音乐和视频交付都在宽带上使用了,P2P,技术,xx,HUST,28,消费空间xx HUST 28,P2P,市场与,P2P,应用,行为类型,范围,消费,企业,公用,work,协同通信,分布计算,存储通信协同,通信,数字版权,play,游戏,HR-Sponsored event,数字媒体,数字体验,rest,音乐共享,内容消费,即时消息,xx,HUST,29,P2P 市场与 P2P应用范围消费企业公用work协同通信,3,构件与算法,P2P,结构抽象：由许多构件组成（非正式划分）,通信,可靠性,例程,工具,管理,消息,元数据,调度,服务,资源聚合,安全,发现,定位,/,路由,通信层,应用说明层,类说明层,健壮性层,组管理层,xx,HUST,30,3 构件与算法P2P结构抽象：由许多构件组成（非正式划分）通,3.1,基础设施构件,通信,P2P,模式覆盖广泛的通信方式,是通过高速稳定链路连接到因特网的,桌面机,可是小型无线设备,PDA,甚至通过无线媒质连接到,Ad-hoc,网的基于,传感,的装置,P2P,群体通信的根本挑战：,和对等端动态特点配合,的问题,有意（关机）或无意（拨号或网络断开）使,P2P,群体组发生,频繁变化,在这种环境下,维持应用层的连接,是,P2P,开发者面临的最大 的挑战,xx,HUST,31,3.1 基础设施构件通信xx HUST 31,组管理,组管理的内容,发现,本群组中,其他,Peers,：,Napster:,高度集中式发现,Peers,，,Gnutella:,高度分布式发现，有时在集中与分布之间,定位及,Peers,之间的路由,影响,发现算法设计的,原因,移动、无线设备的发现必须是其他,Peers,在通信范围内,桌面机运行的协议大多用于集中化目录,定位及路由算法：,从某,Peer,到另一个之间的消息传送路径的优化,已开发的,Napster Gnutella,主要优化现行网络的延时,xx,HUST,32,组管理组管理的内容xx HUST 32,健壮性,基本构成,安全、资源聚合、可靠性,安全是最大挑战,P2P,的好处是让节点同时具有客户和服务器的功能,但从客户端转变成,服务器角色就把大量风险带进到系统,：仅可信和授权的资源才可提供,然而：安全需求或要求来自用户潜在而烦琐的干预，或同可信,第三方交互,集中式的安全问题避开了分布的风险，可这却是,P2P,的潜在好处,xx,HUST,33,健壮性基本构成xx HUST 33,资源聚合,P2P,通过提供,Peers,间基本的交互来聚合其系统上可用的资源,资源范围广泛,文件和其他常驻在计算机内的内容，大量的文件共享系统解决了这类资源的聚合问题,但资源可定义为：在给定,Peer,设备上可用东西。如,CPU,处理能力,，,带宽,，,能量,和,磁盘空间,等等,xx,HUST,34,资源聚合P2P通过提供Peers间基本的交互来聚合其系统上可,可靠性,P2P,系统中,困难的问题,固有的分布式特点使保障可靠性很困难,通常解是：,冗余,计算密集模式中，当检测到某机失效，则该任务可,启动其它可用计算机,相同的任务可分配到,多个,Peers,上,在文件共享系统，可在许多,Peers,上,部署重复,DB,丢失的消息可,重发,或沿着,多个通路同时,发送,xx,HUST,35,可靠性P2P系统中困难的问题xx HUST 35,类说明,两类构件,前面所讨论的构件是,可应用,到,P2P,结构,应用类说明是构件每类,P2P,应用的,功能抽象,或概要,类说明,调度：应用于可并行化或计算密集类（任务分块调度给,Peers,）,元数据：应用于内容和文件管理，描述存储在各,Peers,上的内容，并可被查阅以决定所求信息的位置,消息：应用于协同，在各,Peers,间发送以完成通信,管理：支持先行,P2P,基础设施的管理,xx,HUST,36,类说明两类构件xx HUST 36,应用说明,构成与功能,工具、例程和服务,详细描述应用，以协调现行,P2P,设施上的某些应用,适应于,分布式调度（科学、金融、生物计算）,内容和文件共享（音乐,MP3,文件交换）,运行在协同和通信系统上面的特别应用，如日历、笔记、消息和聊天,xx,HUST,37,应用说明构成与功能xx HUST 37,3.2,模式与算法,集中目录模式,最流行，,Napster,使用,群组的,Peers,连接到发布其能提供共享内容的中心目录上，匹配请求与索引,文件直接交换在两个,Peers,间进行,需要一些可管理的设施（目录服务器：记载群组所有参加者的信息）,限制了规模的扩大：大量用户增加,大量请求,-,大服务器,-,存储器,然,Napster,经验表明,除开法律问题外,该模式还很有效和强大,Index,1,2,3,5,4,搜索,下载,xx,HUST,38,3.2 模式与算法集中目录模式Index12354搜索x,Napster,原理,I have X!,Publish,insert(X,1.2.3.4),.,1.2.3.4,xx,HUST,39,Napster原理I have X!Publishinser,Napster,原理,Where is file A?,Query,Reply,search(A),-,4.3.2.1,Fetch,4.3.2.1,xx,HUST,40,Napster原理Where is file A?Query,洪泛请求模式,过程,每个,Peer,的请求直接广播到连接的,Peers,各,Peers,又广播到各自的,Peers,直到收到应答或 达到最大洪泛步数,(,典型,5-9),特点,无广告性共享资源,Gnutella,使用该算法,限于公司内通信有效,大量请求占用网络带宽,可扩展性并不一定最好,改进,Kazaa,设立,Super-Peer,客户软件,以集中大量请求,BT,文件分块,Cache,最近请求,1,2,3,5,4,搜索,下载,6,xx,HUST,41,洪泛请求模式过程12354搜索6xx HUST 41,Gnutella,原理,I have file A.,I have file A.,Where is file A?,Query,Reply,xx,HUST,42,Gnutella原理I have file A.I have,KaZaA,原理,I have X!,Publish,insert(X,123.2.21.23),.,123.2.21.23,xx,HUST,43,KaZaA原理I have X!Publishinsert(,KaZaA,原理,Where is file A?,Query,search(A),-,123.2.0.18,search(A),-,123.2.22.50,Replies,123.2.0.18,123.2.22.50,xx,HUST,44,KaZaA原理Where is file A?Queryse,BitTorrent,原理,Tracker,A,D,C,B,xx,HUST,45,BitTorrent原理TrackerADCBxx HUST,BitTorrent,原理,A,C,B,D,xx,HUST,46,BitTorrent原理ACBDxx HUST 46,文件路由模式,过程,每个网上,Peer,分配一个随机,ID,并知道其他,Peers,的给定号码,当共享文件发布到系统上时,根据文件名字和内容,Hash,成为,ID,每个,Peer,将根据,该,ID,向该文件路由,该过程重复执行,直到最近的,PeerID,是现行,Peer,的,ID,每个路由操作还,保持文件副本在本地,当,Peer,请求某文件时,该请求将,用该文件的,ID,到达,Peer,过程重复直到发现文件副本,最终文件下载到请求源端,xx,HUST,47,文件路由模式过程xx HUST 47,4,个算法实现文件路由,Chord/CAN/Tapestry/Pastry,目标相同,减少,路由到指定文件的,P2P,跳数,减少,每个,Peer,必须保持的,路由状态,算法异同,都保证算法的跳数与,Peer,群组的大小相关,或都指出算法能以高概率完成,方法上的差别很小,xx,HUST,48,4个算法实现文件路由Chord/CAN/Tapestry/P,Chord,每个,Peer,保持,LogN,其他,Peer,的踪迹,(N,是群组的全部,Peer,数,),当,Peer,加入或离开时,高优化算法版本仅需关注,LogN,个,Peers,的变化,CAN,每个,Peer,保持,少于,LogN,个其他,Peers,的踪迹,在插入和删除时仅这些,Peers,受影响,其路由表较小,但到达的路径较长,可能,更适合动态通信,Tapestry,与,Pastry,很相似,除减少跳数外,还积极削减每个,P2P,跳上的时延,xx,HUST,49,Chordxx HUST 49,路由表,路由表内容,id,文件标识符,next_hop,存储文件,id,的另一个节点,file,保存在本地的,id,标识文件,搜索过程,如果文件,id,存储在本地，停止搜索，上传文件,如果不在本地，,搜索,路由表中,最接近的,id,，将请求,转到,next_hop,如果所有节点都没有找到，返回失败，返回路由表,中下一个最接近的,id,ID,Next_hop,file,xx,HUST,50,路由表路由表内容IDNext_hopfilexx HUST,文件路由原理,4 n1 f4,12 n2 f12,5 n3,9 n3 f9,3 n1 f3,14 n4 f14,5 n3,14 n5 f14,13 n2 f13,3 n6,n1,n2,n3,n4,4 n1 f4,10 n5 f10,8 n6,n5,query(10),1,2,3,4,4,5,网络趋向于一个小世界,small world,类似六度分隔（,Six,Degrees of Separation,）理论,因此，大部分查询只需经过少量跳数,xx,HUST,51,文件路由原理 4 n1 f4 9 n3 f9,Distributed Hash Table,分布式数据结构系统中，可以是环，树，超立方体，跳表，蝶形网络,.,CFS, OceanStore, PAST, ChordDNS,分布式,Hash,表,分布式应用,get (key),data,node,node,node,.,put(key, data),查找服务,lookup(key),node IP address,(,文件共享,),(DHash),(Chord),xx,HUST,52,Distributed Hash Table分布式数据结构系,结构化,重叠路由,加入,：开始时，联系一个,“,bootstrap,”,节点，加入分布式数据结构，,获得一个节点,id,发布,：向数据结构中最近的节点发布,文件,id,的路由信息,搜索,：向路由表中最近的节点查询文件,id,，数据结构保证查询会找到发布节点,获取,：两个选项,查询到的节点保存有文件，则从查询结束的节点获取,查询到的节点返回结果：节点,x,有文件，则从节点,x,获取,DHT,示例,Chord:,在一维空间（环）中给每个节点和文件一个唯一的,id,例如从,0.2,m,中选取,通常是文件和,IP,地址的,hash,xx,HUST,53,结构化重叠路由xx HUST 53,Chord,：插入,N32,N90,N105,K80,K20,K5,Circular ID space,Key 5,Node 105,xx,HUST,54,Chord：插入N32N90N105K80K20K5Circ,Chord,：查找,N32,N90,N105,N60,N10,N120,K80,“Where is key 80?”,“N90 has K80”,xx,HUST,55,Chord：查找N32N90N105N60N10N120K8,4 P2P,关键技术特性,4.1,非集中化,:,置疑,C/S,模式,集中化,在访问权限和安全上容易管理,但不可避免导致,:,低效,/,瓶颈,/,资源浪费,尽管硬件性能和成本有了改进,但建立和维护集中化知识库成本高昂,需要人员智能化地建立,保持信息的相关和更新,非集中化,:,更强有力的思想,强调用户端所有权,对数据和资源的控制,每个,Peer,都是平等的参与者,实现更困难,(,无全局服务器,看不到全局,Peers,及其文件,),这也是当前混合模式存在的原因,xx,HUST,56,4 P2P关键技术特性4.1 非集中化:置疑 C/S 模式,全非集中化文件系统,(Gnutella Freenet),发现网络是很困难的,新节点必须知道其他节点,或由主机列表知道其他,Peers,的,IP,地址,该节点通过和现行网络中至少一个,Peer,建立连接而加入网络,从而能发现其他,Peers,并,Cache,它们的,IP,地址在本地,专用单服务器,(,通过,Master),混合,SETIhome,Avaki,纯,所有节点相同,超级,Peers/Masters,多个专用服务器,Kazaa,Freenet,Gnutella,Napster,平台,分布计算,协同通信,文件共享,非集中化程度,JXTA,.NET,各种,P2P,系统按非集中化程度分类,xx,HUST,57,全非集中化文件系统(Gnutella Freenet)专用单,4.2,可扩展性,可扩展性受限的主要原因,需要完成大量的集中化操作,:,如同步与一致,需要维护许多状态,固有的并行性应用展开,用来表示计算的编程模式,P2P,解决可扩展性问题,Napster,在其服务的高峰用户达到,600,万,然,SETIhone2002,年止用户,仅接近,350,万,.,因为它集中在并行度有限的任务上,依靠因特网上的可用计算力来分析从天文望远镜收集来的数据,搜索外星生命,Avaki,通过提供分布式对象模型来解决可扩展性问题,xx,HUST,58,4.2 可扩展性可扩展性受限的主要原因xx HUST 58,Napster,是通过故意保留许多集中化文件操作来实现,-,达到好的扩展性并不是扩大其它所希望的特点,Gnutella,和,Freenet:,早期的,P2P,系统具有,Ad-hoc,的特点,Peer,必须把请求盲目发送到许多其他,Peers,促使它们搜索请求的文件,CAN,Chord,Oceanstore PST:,最近的,P2P,系统,专注在目标键和目标节点间找到一致的映射,每个节点仅维护较少的系统节点信息及其状态,故增加了可扩展性,这些系统设计规模是 数,10,亿用户,数百万服务器和,10,14,个文件,未来,:,带宽和计算能力继续增长,P2P,平台能利用这些能力去完成人们感兴趣的应用,结构将更自治可扩展,提供更多的资源,展开更多的应用,xx,HUST,59,Napster是通过故意保留许多集中化文件操作来实现-达到好,4.3,匿名,目的,重要目的是让人们使用系统时不用关心法律问题和其他节外生枝的问题,进一步目的可能使数字内容的审查制度形同虚设,匿名形式,作者,:,可以不标识文件的作者或创建者,发布者,:,可以不标识对系统而言的文件发行者,读者,:,可以不标识文件的读者或其他消费数据者,服务器,:,可以不标识含有未被标识文件的服务器,文件,:,服务器并不知道它存储的是什么文件,查询,:,服务器并不告诉它正用何文件在响应用户的查询,xx,HUST,60,4.3 匿名目的xx HUST 60,必须在,通信对之间强迫执行,3,种匿名,才能达到上述匿名,(,不管何种匿名形式,),发送者匿名,:,隐藏发送者的标识符,接收者匿名,:,隐藏接收者的标识符,相互匿名,:,隐藏发送者何接收者的标识符,且双方标识符对其他,Peers,也是隐藏的,匿名程度,绝对隐私,不可怀疑,:,即使攻击者能看到已发送消息的证据,但 发送者似乎并不比系统潜在的发送者更像真正的发送者,大概无罪,可能曝光,xx,HUST,61,必须在通信对之间强迫执行3种匿名,才能达到上述匿名(不管何种,6,种不同技术,-,适合不同匿名方式,多播使接收者匿名,发送者地址欺骗,- UDP,伪造其地址,标识符欺骗,-,改变通信参与者标识符,隐蔽通道,-,通过某些中间节点,难管的别名,-,代理服务器为客户生成稳固的别名,非志愿放置,-,文档非志愿放置在承载,(Hosting),主机上,xx,HUST,62,6种不同技术-适合不同匿名方式多播使接收者匿名xx HUST,项目,匿名技术与类型,发布者,读者,服务器,文档,Gnutella,组播,隐蔽通道,N/A,N/A,N/A,Freenet,隐蔽通道,标识符欺骗,隐蔽通道,非志愿放置,加密,APFS,隐蔽通道,隐蔽通道,N/A,N/A,FreeHaven,隐蔽通道,(remailer),隐蔽通道,广播,加密,/,把文件分成共享部分,Publius,隐蔽通道,(remailer),N/A,非志愿放置,加密,/,划分密钥,PAST,N/A,N/A,非志愿放置,加密,xx,HUST,63,匿名技术与类型发布者读者服务器文档Gnutella组播N/A,4.4,自组织,定义,自组织是一个过程,在此一个系统的组织,(,约束,/,冗余,),自然本能地增加,也就是不通过环境,也不包含其他外部系统来增加控制,P2P,需要自组织,可扩展性,:,系统数,/,用户数,/,负载数等每一个都不可预测,因为需要进行频繁的集中化重构,故障容错,(resilience,弹性,):,大规模导致故障率增加,这就需要对系统的自维护,/,自修复,资源的间歇连接,:,在很长期间内保持完整的预定义构态是很难的,故需要处理,Peers,连接和断开而引起的变化,所有权成本,:,管理这些专用设备和,/,或管理这样复杂波动环境的人需要成本,故管理应该在,Peers,间分布,xx,HUST,64,4.4 自组织定义xx HUST 64,有许多研究系统和产品都表明是自组织的,OceanStore,其自组织已应用到基础设施的定位和路由,由于,Peers,的间歇性及网络延迟带宽的变化,基础设施必须适应其路由和定位支持,Pastry,通过基于全网容错的节点进,/,出协议处理自组织,客户端请求保证在少于平均,log,16,N,步路由达到,负载平衡,;,文件副本分布,随机存储,FastTrack,对自组织分布式网络进行快速搜索和下载,系统中强大计算机可自动变成,超节点,作为搜索,Hubs,若有处理能力并满足联网标准,任客户端也可变成,超节点,这样分布式网络可取代任何集中化服务,xx,HUST,65,有许多研究系统和产品都表明是自组织的xx HUST 65,4.5,所有权成本,P2P,的前提,共享所有权,共享所有权减少了自有系统,/,内容,/,和维护它们的代价,SETIhome,比当今世界上最快的计算机还快,而且成本只是它的,1%,Napster,音乐共享的全部理念是基于每个成员把音乐文件贡献到文件池中去,其他文件系统也一样,.,P2P,协同,/,通信,/,平台,集中化计算机存储信息的削减也减少了所有权和维护成本,美国的无线通信采用了类似的方法,寄生网格,:,在用户之间共享家庭安装的,802.11,带宽,在成本上同安装有无线基础设施的公司竞争,xx,HUST,66,4.5 所有权成本P2P的前提xx HUST 66,4.6 Ad-hoc,连接,分布式并行计算,并不能在所有时间,/,所有系统上执行,某些系统在所有时间可用,/,部分时间可用,/,并不可用,Ad-hoc,系统,对,P2P,计算,可随进随出,是理想的,P2P,使用,对,P2P,内容共享系统,高服务保证通过冗余服务实现,削弱了,Ad-hoc,的特点,对,P2P,协同,用户希望用移动设备连接到因特网,Ad-hoc,可通过代理群接收消息,或发送中继来保持通信延迟和断开的透明,802.11b,蓝牙和红外支持,Ad-hoc,其半径有限,它接入,P2P,支持容许突然断开是很重要的,xx,HUST,67,4.6 Ad-hoc连接分布式并行计算xx HUST 67,4.7,性能,P2P,系统目标,:,聚合分散网络上的存储容量,(Napster/Gnutella),和计算周期,(,SETIhome,),来改进系统的性能,影响非集中化性能的三类资源,处理,/,存储,/,网络,网络资源中的带宽和时延是主要因素,中心协调系统,(Napster,SETIhome,),Peers,的协调和仲裁通过中心服务器进行,混合,P2P,以克服这些脆弱点,非集中协调系统,(Gnutella Freenet),用消息传递机制搜索信息和数据,查询搜索的带宽与发送消息数,命中前的,Perrs,数成正比,xx,HUST,68,4.7 性能P2P系统目标:xx HUST 68,优化性能的关键技术,复制,(Replication),把对象,/,文件的拷贝放在请求,Peers,附近,最小化连接距离,改变数据时必须保持数据拷贝的一致性,OceanStore,基于冲突解的更新传播模式支持一致性语义,高缓,(Cache),减少获取文件,/,对象路径的长度,进而,Peers,间交换消息数,这一减少很有意义,-Peers,间通信时延是严重的性能瓶颈,Freenet:,命中文件传播到请求者途中所有节点高缓它,目标是最小化时延,最大化请求吞吐率,很少高缓大数据,智能路由和网络组织,社交,“,小世界,”,现象,60,年美,明信片均,6,熟链找到生人,局部搜索策略,代价与网络规模成子,-,线性增加,OceanStore/Pastry,网络上积极移动数据提高性能,xx,HUST,69,优化性能的关键技术复制(Replication)xx HUS,4.8,安全,普通分布式系统的安全解也为,P2P,系统所用,Peers,和共享对象间的信任链,/,会话密钥交换模式,/,加密,/,数字摘要,/,签名,P2P,系统新的安全需求,多密钥加密,沙箱,数字版权管理,信誉与责任,防火墙,xx,HUST,70,4.8 安全普通分布式系统的安全解也为P2P系统所用xx,多密钥加密,Publius,通过公钥,/,多私钥,非对称加密机制,保护共享对象,/,及其作者,发布,Peers,和承载,Peers,的匿名,Byzantine attacks,是一个典型恶意授权攻击问题,新近改进减少了拜占庭协议固有的代价,并找到了通过大量用户加固系统的途径,xx,HUST,71,多密钥加密Publiusxx HUST 71,沙箱,沙箱,:,隔离特定计算机或网络资源,防止恶意访问,P2P,计算要把代码分载在,Peers,上执行,须防止潜在恶意代码侵袭,Peers,机,须防止恶意,Peers,机侵袭代码,保护,Peers,机的强制方法,外部代码不能闯入主机箱,或仅能以安全方式访问主机的数据,防止敏感数据泄露到恶意部件,相关技术有,:Sandbox,安全语言,(Java),虚拟机,(Internet C+, POSIX,虚拟机,实时,Linux),带验证的代码和保证编译器,程序验证技术验证机器代码的安全性,最近发展有,:,信息流校验和模式校验技术,xx,HUST,72,沙箱沙箱:隔离特定计算机或网络资源,防止恶意访问xx HUS,数字版权管理,P2P,文件共享系统,使文件拷贝更容易,必须保护作者的版权不被偷窃,处理方法,在文件中加入可识别签名,加在文件后面，但不影响文件内容,技术：数字水印 或 信息隐藏,RIAA,把密码信息以不可见、听的形式隐藏在文件中，保护,MP3,声音文件,xx,HUST,73,数字版权管理P2P文件共享系统xx HUST 73,信誉与责任,信任：精确保证公告的内容实际上就是其所宣称事实,P2P,系统的信誉,建立在信任之上，要有测量,Peer,的信誉是否,“,好的,”,或,“,有用的,”,的方法,给别人分享很多感兴趣的文件，则其信誉应很高。,Freeloader,是只下载不上载者，其信誉低,为防止非合作行为，须建立责任机制,先行系统常根据,Cross-ratings,但产生一个可靠的系统是很难的,xx,HUST,74,信誉与责任信任：精确保证公告的内容实际上就是其所宣称事实xx,防火墙,P2P,系统天生需要,Peers,间直连,内外网隔离减少了应用的访问权限,如,FW,阻止返回的,TCP,连接，导致,FW,内的计算机不可访问,更坏是：家庭用户频繁使用伪装,IP,或,NAT,保持同几个计算机之间因特网连接,但,FW,让,TCP80,端口常开，使隐藏机和因特网可保持连接,两个均在,FW,后,Peers,通信就更难了，需要中继服务器提供二者间的连接,xx,HUST,75,防火墙P2P系统天生需要Peers间直连xx HUST 75,4.9,透明性和可用性,P2P,透明性,主要形式是位置透明性,其它有：访问、并发、复制、失效、移动、扩展等等,P2P,透明性的量化,失效透明性量化让分布式应用觉察,Web,和因特网寻址透明性,P2P,继承因特网常规透明性,TCP,端端透明，两实体维持知识和状态，网络不负责,网上任一点知道其它通信端的名字和地址，,IPV4,地址缺乏导致其只在单次会晤中有效，如,SLIP/PPP/VPN/FW/ DHCP/NAT/,分裂,DNS/,因此,P2P,需要不同的命名及其发现模式,xx,HUST,76,4.9 透明性和可用性P2P透明性xx HUST 76,还需管理透明，因为其,Peers,端不是硬软件专家；,P2P,除开命名和寻址透明外,自更新软件,设备透明（独立），,PDA/,桌面机、手机，且工作在,Internet/intranet/ VPN,用宽带或拨号,安全与移动透明,自动透明授权给用户和基于代理的团体,支持移动用户特殊情况下的断开,P2P,应用的使用方式,作为用户服务，通过,Web,接口（内容共享、信息收集）,预包装非,P2P,应用，运行在,P2P,平台（,Groove .NET,）,作为本地安装的,P2P,软件（分布式计算、,Napster,）,xx,HUST,77,还需管理透明，因为其Peers端不是硬软件专家；P2P除开命,4.10,故障适应力,P2P,主要目标之一是避免中心点失效,尽管大多数纯,P2P,已经做到，不过是通过生成多主机和多网络来面对如下失效：断开、不可达、分离和节点失效（无线比有线企业网表现更厉害）,Genomehome,在连接的,Peers,上执行分割计算，当某些,Peers,因链路断连而消失，希望计算继续；消失,Peers,再现后，能合并原来结果继续计算吗？,P2P,系统应该提供比,Best effort,更好的服务,资源的非有效性断连导致的问题,断连，资源不可达,(,网络失效、资源机崩溃、离线,),，然先者仍在路由,Napster/Guntella,等都通过复制机制解决,管理责任完全分布并须寻址是,P2P,面临的挑战,xx,HUST,78,4.10 故障适应力P2P主要目标之一是避免中心点失效xx,4.11,交互能力,交互需求，系统,怎样知道它能交互,怎样通信，用何协议,:Sockets,Message or HTTP,怎样交换请求和数据，在高层执行任务，交换文件或搜索数据,怎样知道它在更高层协议是兼容的，如一个系统能依赖另一系统适当搜索一些信息吗？,怎样通告并维护同级安全、,QOS,和可靠性,P2P,工作组从,Ad-hoc,和,Grid,聚集开发者,JXTA,是交互操作方法的开放源代码,xx,HUST,79,4.11 交互能力交互需求，系统xx HUST 79,5 P2P,系统比较,Analysis and compare 8 P2P Systems,xx,HUST,80,5 P2P系统比较Analysis and compare,P2P,系统,实例研究摘要,-,系统特点,分类,可选解,平台,语言,/,工具,不同点,网络,Avaki,分布式计算,单装置,HPC,超级计算,Linux, Win,Solaris,OO,Paral,Fort.Ada,C,分布管理、异质、安全高并,因特,内网,SETIhome,分布式对象,所有通用,OS,Closed source,大规模,因特,Groove,协同,Web-Based,协同,Windows,JavaScript,VB,Perl,C+,XML,回放、自更新,因特,内网,Magi,分布文件,聊天,/,消息,Windows,Mac,Java,XML,HTTP,Web,DAV,基于,HTTP,平台独立,因特,Ad-hoc,Freenet,内容共享,匿名,可信单点,Any with,Java,Java,实现和,APIs,匿名保存,因特,Gnutella,中心服务,Windows,Linux,Java,C,协议,因特,JXTA,平台,C/S,Solaris Linux, Win,Java,C,Perl,开发源码,因特,.NET/My Service,Web-Based,Windows,C#,VC+,JScrip,VBScrip,VB,基于,MS,应用,因特,移动,xx,HUST,81,实例研究摘要-系统特点分类可选解平台语言/工具不同点,P2P,系统,实例特点比较研究,-,-,系统特点,非集中化,可扩展性,匿名,自组织,权成本,Ad-hoc,性能,安全,透明性,容错,交互,Avaki,无中心,1000,测,2-3,千,N/A,失效重构,低,进出计算资源,加速,加密