《第八章p2p原理与技术课件.ppt》由会员分享，可在线阅读，更多相关《第八章p2p原理与技术课件.ppt（39页珍藏版）》请在三一办公上搜索。
1、第八章 P2P原理与技术,概述分类构件与算法关键技术特性,1.1 什么是P2P,P2P：Peer-to-Peer对等(网络，计算);端到端以非集中方式使用分布式资源来完成关键任务的一类系统和应用资源包括计算能力、数据（存储和内容）、网络带宽和场景（计算机、人和其它资源）关键任务可能是分布式计算、数据/内容共享，通信和协同、或平台服务典型位置：因特网边界或ad-hoc网内,Sarnoff law：效益规模是O(n)：网络是广播媒介，任1发送者（设备）和多个(n-1)接收者（设备）。,Metcalfe law：效益规模是O(n2)网络是全互连媒介，任何1个设备可与其它n-1个交互，同时存在n(n-
2、1)=n2-n个并发执行的事务,Reed law：效益规模是O(2n)：网络是群组媒介。网络可建立Cn2+Cn3+Cnn-1+Cnn=2n-n-1 个小组,网络服务规模三法则,P2P的效果,巨大的扩展力通过低成本交互来聚合资源，导致整体大于部分之和。低成本的所有权和共享使用现存的基础设施、削减和分布成本匿名和隐私允许对等端在其数据和资源上很大的自治控制,P2P Network,Linux,NAT,TCP/IP,Bluetooth,HTTP,Firewall,TCP/IP,TCP/IP,Application,XP,P2P的网络基本构成,P2P 今天的影响,P2P文件共享产生的流量可能是今天因特
3、网最大的单项流量,Source:www.internet2.edu,July 04,Source:Eurpoean Tier I ISP Feb 04,BT,HTTP,eDonkey,Internet2 traffic statistics,Eurpoean traffic by Protocol,1.2 P2P的定义,Intel 工作组：通过在系统之间直接交换来共享计算机资源和服务的一种应用模式A.Weytsel:在因特网周边以非客户地位使用的设备R.l.Granham:通过3个关键条件定义具有服务器质量的可运行计算机具有独立于DNS的寻址系统具有与可变连接合作的能力C.Shirky:利用因
4、特网边界的存储/CPU/内容/现场等资源的一种应访问这些非集中资源意味着运行在不稳定连接和不可预知IP地址环境下，P2P节点必须运行在DNS系统外边具备有效或全部的自治,Kindberg:独立生存的的系统D.J.Milojicic:给对等组提供或从对等组获得共享对等端向组给出某些资源，并从组获得某些资源Napster:把音乐供给组内其他人，并从其他人获得音乐捐赠计算资源用于外星生命的搜索或战胜癌症，获得帮助其他人的满足另一种应用模式选择：相对集中式、和C/S模式纯P2P：没有服务器的概念，所有成员都是对等端并不是全新的概念早期分布式系统：如UUCP和交换网络电话通信计算机网络中的通信、网络游戏
5、中的诸玩家自助餐，志愿组活动,1.3 P2P 与 C/S,二者在结构和构成上有很大区别管理能力、构态能力、功能（查找或发现）、组织(分层与网孔)、元素（DNS）和协议(IP)但又无明显边界都能运行在不同的（Internet/Intranet）平台上都能服务传统或新的应用：eBusiness eServuices,有管理自组织,预构-Ad-hoc,查找发现,分层Mesh,静态移动,依赖服务器独立生存,以IP为中心不以IP为中心,基于DNS客户命名,RPC异步,.NET,JXTA,C/S模式,P2P模式,CORBA,CORBA,Gnutella,Napster,eBusiness,Web apps
6、,eServices,Distr.apps,Ad-hoc NW,Clusters,Internet Intranet,WANs,Grids,P2P与C/S,1.4 P2P 相关背景,一般计算和因特网特殊计算的历史演进：因特网边界计算：如SETIhome和其它分布式计算系统内容共享的社会方面：如Napster音乐和其他文件/内容共享系统计算机、网络通信技术的进步和改进大型机桌面PC 便携机手持设备（手机）使通信和协同变得更方便P2P软件结构：如JXTA，.NET开发的P2P算法：如Gnutella，FreeNet,1.5 P2P之目标：满足应用需要,共享/削减成本：Napster 共享文件空间，
7、SETIhome聚合未用资源改进可扩展性/可靠性：对缺乏很强中心授权的自治对等端这点尤为重要资源聚合与互操作能力增加自治匿名/隐私：自治的理念和结果。用户不希望任何人或ISP知道其包含在系统中动态性;资源动态进入或离开系统实现Ad-hoc通信和协同，动态的理念和结果,2 P2P分类,所有的计算机系统可分为集中式和分布式两类分布式可进一步划分为C/S和P2P模式C/S模式可划分为扁平：所有的客户端仅仅和单个服务器（含重复服务器）通信，如传统的中间件分层：提高可扩展性，某层的服务器又作为更高层的客户端：如DNS服务器和文件系统,纯P2P系统：如Gnutella 和 Freenet混合P2P系统：首
8、先从服务器获得元数据或索引信息，如存储某些信息的对等端的标识符，或安全信誉的验证，以后P2P通信直接和对等端进行，典型系统有：Napster,Groove,Aimster,Magi,Softwax,iMesh 以及华中科技大学的5Q;Anysee某些有SuperPeers的中间形式：如Kazaa，超级Peers拥有其他Peers没有的信息，它们常常在不能发现时查找这些超级Peers,混合P2P的资源寻找过程,2.1 P2P系统的分类,SETIhomeAvbaki,Entropia,NapsterGnutellaFreenetPubliusFree Haven,MagiGrooveJabber,
9、JXTA.NET.NETMyServices,P2P 多维视图,2.2 P2P 应用分类,3 构件与算法,P2P结构抽象：由许多构件组成（非正式划分）,3.1 基础设施构件,通信P2P模式覆盖广泛的通信方式是通过高速稳定链路连接到因特网的桌面机可是小型无线设备PDA甚至通过无线媒质连接到Ad-hoc网的基于传感的装置P2P群体通信的根本挑战：和对等端动态特点配合的问题有意（关机）或无意（拨号或网络断开）使P2P群体组发生频繁变化在这种环境下维持应用层的连接是P2P开发者面临的最大 的挑战,组管理,组管理的内容发现本群组中其他Peers：Napster:高度集中式发现Peers，Gnutella
10、:高度分布式发现，有时在集中与分布之间定位及Peers之间的路由影响发现算法设计的原因移动、无线设备的发现必须是其他Peers在通信范围内桌面机运行的协议大多用于集中化目录定位及路由算法：从某Peer到另一个之间的消息传送路径的优化已开发的Napster Gnutella主要优化现行网络的延时,应用说明,构成与功能工具、例程和服务详细描述应用，以协调现行P2P设施上的某些应用适应于分布式调度（科学、金融、生物计算）内容和文件共享（音乐MP3文件交换）运行在协同和通信系统上面的特别应用，如日历、笔记、消息和聊天,3.2 模式与算法,集中目录模式最流行，Napster使用群组的Peers连接到发布
11、其能提供共享内容的中心目录上，匹配请求与索引文件直接交换在两个Peers间进行需要一些可管理的设施（目录服务器：记载群组所有参加者的信息）限制了规模的扩大：大量用户增加大量请求-大服务器-存储器然Napster经验表明,除开法律问题外,该模式还很有效和强大,Napster原理,I have X!,insert(X,1.2.3.4).,1.2.3.4,Napster原理,Where is file A?,search(A)-4.3.2.1,4.3.2.1,洪泛请求模式,过程每个Peer的请求直接广播到连接的Peers各Peers又广播到各自的Peers直到收到应答或 达到最大洪泛步数(典型5-9
12、)特点无广告性共享资源Gnutella 使用该算法,限于公司内通信有效大量请求占用网络带宽,可扩展性并不一定最好改进Kazaa 设立Super-Peer客户软件,以集中大量请求BT 文件分块Cache最近请求,Gnutella原理,Where is file A?,KaZaA原理,I have X!,insert(X,123.2.21.23).,123.2.21.23,KaZaA原理,Where is file A?,BitTorrent原理,Tracker,A,D,C,B,BitTorrent原理,A,C,B,D,文件路由模式,过程每个网上Peer分配一个随机ID,并知道其他Peers的给定
13、号码当共享文件发布到系统上时,根据文件名字和内容Hash成为ID每个Peer将根据该ID向该文件路由该过程重复执行,直到最近的PeerID是现行Peer的ID每个路由操作还保持文件副本在本地当Peer请求某文件时,该请求将用该文件的ID到达Peer,过程重复直到发现文件副本,最终文件下载到请求源端,4个算法实现文件路由,Chord/CAN/Tapestry/Pastry目标相同减少路由到指定文件的P2P跳数减少每个Peer必须保持的路由状态算法异同都保证算法的跳数与Peer群组的大小相关或都指出算法能以高概率完成方法上的差别很小,Chord每个Peer保持LogN其他Peer的踪迹(N是群组的
14、全部Peer数)当Peer加入或离开时,高优化算法版本仅需关注LogN个Peers的变化CAN每个Peer保持少于LogN个其他Peers的踪迹在插入和删除时仅这些Peers受影响其路由表较小,但到达的路径较长可能更适合动态通信Tapestry与Pastry很相似除减少跳数外,还积极削减每个P2P跳上的时延,路由表,路由表内容id文件标识符next_hop存储文件id的另一个节点file保存在本地的id标识文件搜索过程如果文件id存储在本地，停止搜索，上传文件如果不在本地，搜索路由表中最接近的id，将请求转到next_hop如果所有节点都没有找到，返回失败，返回路由表中下一个最接近的id,文件
15、路由原理,4 n1 f412 n2 f12 5 n3,9 n3 f9,3 n1 f314 n4 f14 5 n3,14 n5 f1413 n2 f13 3 n6,n1,n2,n3,n4,4 n1 f410 n5 f10 8 n6,n5,query(10),网络趋向于一个小世界small world,类似六度分隔（Six Degrees of Separation）理论因此，大部分查询只需经过少量跳数,Distributed Hash Table,分布式数据结构系统中，可以是环，树，超立方体，跳表，蝶形网络.CFS,OceanStore,PAST,ChordDNS,结构化重叠路由加入：开始时，联
16、系一个“bootstrap”节点，加入分布式数据结构，获得一个节点id发布：向数据结构中最近的节点发布文件id的路由信息搜索：向路由表中最近的节点查询文件id，数据结构保证查询会找到发布节点获取：两个选项查询到的节点保存有文件，则从查询结束的节点获取查询到的节点返回结果：节点x有文件，则从节点x获取DHT示例Chord:在一维空间（环）中给每个节点和文件一个唯一的id例如从0.2m中选取通常是文件和IP地址的hash,Chord：插入,N32,N90,N105,K80,K20,K5,Circular ID space,Key 5,Node 105,Chord：查找,N32,N90,N105,N60,N10,N120,K80,“Where is key 80?”,“N90 has K80”,
