对等网络课件.ppt

《对等网络课件.ppt》由会员分享，可在线阅读，更多相关《对等网络课件.ppt（106页珍藏版）》请在三一文库上搜索。

1、对等网络 Peer-to-Peer Networks （P2P） 1. 概述 o传统的因特网应用采用客户-服务器模式： n所有内容与服务在服务器上，客户向服务器请求 内容或服务，客户自己的资源不共享。 n这种集中式结构面临服务器负载过重、拒绝服务 攻击、网络带宽限制等难以解决的问题。 对等计算模型 o在对等网络中： n每个节点都有一些资源（处理能力、存储空间 、网络带宽、内容等）可以提供给其它节点。 n节点之间直接共享资源，不需要服务器参与。 n所有节点地位相等（称对等方），具备客户和 服务器双重特性。 n可缓解集中式结构的问题，充分利用终端的丰 富资源。 P2P技术的发展 oP2P技术的第一

2、个应用是Napster文件共享系统（ 1999-2000），用户通过该系统交换音乐文件。 o自1999年以来，P2P研究得到学术界和商业组织的 广泛关注，同时该技术也一直饱受争议。 oP2P技术被广泛应用于计算机网络的各个应用领域 ，如文件共享、流媒体直播与点播、分布式科学计 算、语音通信、在线游戏支撑平台等。 o目前以文件共享为代表的P2P应用已成为因特网上 增长最迅速的应用。 P2P技术的应用（1） o提供文件或其它内容共享，如Napster、 Gnutella、eDonkey、emule、BitTorrent等。 oBitTorrent是最流行的P2P文件共享系统之一： n种子节点（保存

3、完整的文件拷贝）把一个文件分成N 个分片（默认为256KB）。 n节点X从种子节点随机下载第L个分片，Y 随机下载 第M个分片，然后节点X与Y 交换彼此拥有的分片。 n减轻了种子节点的负担，提高了节点下载的速度与效 率。 P2P技术的应用（2） oP2P媒体网： nP2P也非常适合流媒体直播与点播，因此P2P研 究热点迅速转移到P2P的流媒体上。 n目前P2P非常广泛的一个应用是网上实时电视， 提供节目的成本很低，用户却可以得到较好的收 视质量。 n流行的软件包括Coolstreaming、AnySee、 Gridmedia、PPLive和PPStream等。 P2P技术的应用（3） o基于P

4、2P方式的协同处理与服务共享平台： nP2P技术将众多终端空闲的CPU资源联合起来，服 务于一个共同的计算。 n计算任务（包括逻辑与数据等）划分成多个片，分 配到参与计算的P2P节点上；计算结果返回给一个 或多个服务器；众多结果整合得到最终结果。 n最著名的P2P分布式科学计算系统为搜索外星文明 的SETIhome科学实验。 P2P技术的应用（4） o即时通信交流： nVoIP是一种全新的网络电话通信业务，Skype 就是一款典型的P2P VoIP软件。 nSkype的出现给传统电信业带来强烈的冲击， 截至2011年年底，Skype占有全球长途通话时 长的33%。 nSkype仍在迅速向各个国

5、家渗透。 P2P系统的定义 oP2P系统是一个由直接相连的节点所构成的 分布式系统，这些节点能够为了共享内容、 CPU时间、存储或者带宽等资源而自组织形 成一定的网络拓扑结构，能够在适应节点数 目的变化和失效的同时维持可以接受的连接 能力和性能，并且不需要一个全局服务器或 者权威的中介支持。 2. P2P网络的拓扑结构 oP2P系统的主要概念之一是分散，包括分布式存储 、处理、信息共享和控制信息。 o根据P2P系统的分散程度，可以将P2P架构分成纯分 散式和混合式。 o根据结构关系可以将P2P系统细分为四种拓扑形式 ： n中心化拓扑 n全分布式非结构化拓扑 n全分布式结构化拓扑 n半分布式拓扑

6、 2.1 中心化拓扑 o最早出现的P2P网络结构，也称集中目录式 结构，或非纯粹的P2P结构。 o优点： n维护简单，资源发现效率高。 o缺点： n单点故障；扩放性差；版权问题。 o对小型网络而言在管理和控制方面有一定 优势，不适合大型网络应用。 Napster文件共享系统 o中央索引服务器保存所有用户 上传的音乐文件索引和存放位 置。 o用户需要某个音乐文件时，先 查询中央索引服务器，得到存 有该文件的节点信息。 o用户选择合适的节点建立直接 连接。 oNapster首先实现了文件查询 与文件传输的分离。Napster的拓扑结构 2.2 全分布式非结构化拓扑 o也称纯P2P结构，取消了中央服

7、务器，每台机器是 真正的对等关系（称为对等机）。 o每个用户随机接入网络，并与自己相邻的一组节点 通过端-端连接构成一个逻辑覆盖网络。 o对等节点之间的内容查询和内容共享均直接通过相 邻节点广播接力传递。 o每个节点记录搜索轨迹，防止产生搜索环路。 oGnutella是应用最广泛的全分布式非结构化拓扑 。 Gnutella早期的拓扑结构 o要下载文件的计算机以文 件名或关键字生成一个查 询，发送给与它相连的所 有计算机。 o存在该文件的计算机与查 询机器建立连接；否则继 续向自己的邻居节点洪泛 。 o重复该过程，直至找到文 件为止。 o一般通过TTL值控制查询的 深度。 全分布式非结构化拓扑的

8、特点 o将覆盖网络看成完全随机图，节点之间的链路没有遵 循某些预先定义的拓扑来构建。 o优点： n解决了网络结构中心化的问题，扩展性和容错性较好； n支持复杂的查询（如多关键词查询、模糊查询等）。 o缺点： n查询结果可能不完全，查询速度较慢； n网络规模较大时，消耗网络带宽多，易造成部分低带宽节 点因过载而失效，影响网络的可用性； n容易受到垃圾信息甚至是病毒的恶意攻击。 2.3 全分布式结构化拓扑 o采用分布式散列表（DHT）组织网络中的节点： nDHT是由广域范围内大量节点共同维护的巨大散列表。 n散列表被分割成不连续的块，每个节点被分配一个散列 块，并成为这个散列块的管理者。 n每个节

9、点按照一定的方式被赋予一个惟一的Node ID。 n资源对象的名字或关键词通过一个散列函数映射为128 位或160位的散列值，资源对象存储在Node ID与其散 列值相等或相近的节点上。 n需要查找资源时，采用同样的方法定位到存储该资源的 节点。 基于DHT的节点组织 o每个节点通过散列其IP地 址，得到一个128位的节 点标识符。 o所有节点标识符形成一个 环形的node ID空间，其 中只有一部分对应了实节 点。 oKey的散列值为d46a1c的 内容存放在节点d467c4 上。 全分布式结构化拓扑的特点 o优点： n采用确定性拓扑结构，DHT可以提供精确发现 。 o缺点： n维护机制较复

10、杂，尤其是节点频繁加入/退出造 成的网络波动会极大地增加维护DHT的代价。 n仅支持精确关键词匹配查询，无法支持内容/语 义等复杂查询。 o这种结构目前还没有大规模成功应用的实例。 2.4 半分布式结构 o亦称混合结构，吸取了中心化结构和全分布式非结 构化的优点。 o选择性能（处理、存储、带宽）较高的节点作为超 级节点，各个超级节点上存储其它部分节点的信息 。 o发现算法仅在超级节点之间转发，超级节点再将查 询请求转发给适当的叶子节点。 o半分布式结构是一种层次式结构： n超级节点之间构成一个高速转发层 n超级节点和所负责的普通节点构成若干层次 Kazaa的拓扑结构 o节点按能力不同区分为普通

11、节点和搜索节点。 o搜索节点与其临近的若干普通节点构成一个自治的簇 ： n簇内采用中心化P2P结构 n簇之间通过纯P2P结构将搜索节点连接起来 Kazaa的特点 o自动将性能好的机器当成超级节点，采用Gnutella 的全分布式结构，不需要中央索引服务器。 o超级节点存储离它最近的叶子节点的文件信息，其 索引功能使得搜索效率大大提高。 o文件搜索先在本地簇内进行，必要时再通过搜索节 点进行有限的泛洪，消除了纯P2P结构中泛洪算法 带来的网络拥塞、搜索迟缓等不利影响。 o搜索节点监控着簇内所有普通节点的行为，一些攻 击行为能在网络局部得到控制。 o超级节点的存在一定程度上提高了网络的负载平衡 。

12、 Gnutella后期的结构 o计算能力较强的节点加入网络时，立即成为一个超 级对等节点（SuperPeer），并与其它SuperPeer 建立连接，同时设置一个使其保持SuperPeer所需 的最小客户节点数目。 o当该节点在一个规定的时间内收到不少于该数目的 客户连接请求时，它继续成为SuperPeer，否则变 为一个普通的客户节点。 o如果没有可用的SuperPeer，它又会在一个给定的 时间内担当SuperPeer。 Skype网络结构 oSkype是P2P技术演进到混合模式后的典型 应用： n登录服务器：惟一的集中服务器，存储用户名和 密码信息，保证登录名全球惟一，进行用户身份认证

13、等。 n用户节点：分为普通节点和超级节点。 o普通节点：下载了skype应用的普通终端。 o超级节点：具有公网IP地址和足够资源（CPU 、存储空间、网络带宽）的普通节点均可为超 级节点的候选。 Skype网络结构示意图 o普通节点必须连接到一 个超级节点上，通过超 级节点： n向登录服务器认证自 己 n向好友发送在线信息 n查找用户 n检测NAT和防火墙类 型 Skype的通信过程 o初始化：询问skype的最新版本 o登录：连接到超级节点，进行身份认证等 o用户搜索：查找用户 o呼叫与终止：与通信方建立与终止连接 o媒体传输：传输音频信息 登录 o客户端启动后连接到超级节点，向登录服 务器

14、发送身份认证信息。 o登录服务器验证用户名和密码的合法性。 o客户端向好友及其它对等节点发送在线信 息。 o客户端与超级节点交换消息，检测NAT和 防火墙类型。 o客户端发现拥有公网IP地址的在线Skype 节点。 连接到超级节点 o客户端在主机缓存中维护一个超级节点列表，包含 一系列超级节点的。 o初次安装客户端软件后，超级节点列表中至少包含 7个，这些便是初始的超级节点 。 o登录时，客户端试图同列表中的每一个表项（超级 节点）建立连接。 oSkype没有默认的服务端口号，在安装客户端软件 时随机选择（或设置）一个端口号监听，同时监听 80和443端口。 向好友发送在线信息 oSkype采

15、用路由缓存机制： n超级节点缓存查找到的用户信息（缓存72小时 ）。 n用户登录后，其状态信息可以通过超级节点通 知到好友终端，也可以得到好友的状态。 o一旦缓存超时，需通过其它超级节点查找用户 。 查找用户 o具有公网地址的客户端，查找用户的过程： n向超级节点（SN）发送要查找的用户信息； n若不成功，从SN获取四个节点地址，发送用户信息； n若不成功，报告SN，获取八个节点地址，发送用户信 息； n n成功或失败返回 o位于私网内的受限客户端，查找用户的过程： n客户端将需要查找的用户信息发送给其超级节点； n超级节点完成查找后，返回给私网内的客户端。 呼叫建立和释放 主、被叫都在公网内

16、 呼叫建立和释放（续） 主、被叫至少有一方在私网内 Skype的技术优势 o较强的NAT和防火墙穿越能力：首先识别NAT和 防火墙类型，然后动态选择信令和媒体代理。 o快速路由机制：采用全球索引技术，用户路由信息 分布式存储于网络节点中。 o结合互联网特点的语音编解码算法：引入专门针对 互联网特点的语音质量增强软件。 o很低的运行成本：很多工作下放给网络节点完成， 大大降低了中心服务器的负担，减少了维护和管理 成本。 2.5 四种拓扑结构的对比 中心化全分布式非结构化全分布式结构化半分布式 可扩展性 差差好中 可靠性 差好好中 可维护 性 最好最好好中 发现 算法 效率 最高中高中 复杂查询

17、支持支持不支持支持 3 P2P网络的资源发现机制 o中心化结构：集中式索引和存储 o分布式非结构化：查询请求的洪泛广播 o分布式结构化：内容可寻址网络 3.1 集中式索引和存储 o一个集中的目录服务器保存所有资源的位置和使用信息 ： n网络中所有文件的元数据（文件名、创建时间等）索引； n登录用户的连接信息表（IP地址、连接速度等）； n每个用户拥有并愿意共享的文件列表。 o起始时，客户与目录服务器建立连接，报告其保存的文 件列表。 o当目录服务器收到来自用户的查询时，查找索引表，返 回存有所需文件的用户列表。 o用户选择其中一个对等方建立直接连接，下载文件。 Napster中的资源发现 3.

18、2 查询请求的洪泛广播 o洪泛查询的过程： n在覆盖网络上，查询节点将一个资源发现请求发 送给与其直接相连的所有节点； n这些节点再向其直接相连的邻居洪泛该请求； n n直到请求被响应或达到最大洪泛次数。 o早期的Gnutella使用洪泛机制发现网络中的 文件。 Gnutella使用的消息 oPing：节点使用该消息宣告自己。 oPong：对Ping的响应，包含响应主机的IP地址、能接 受响应的端口、本机共享文件数量及所占空间大小。 oQuery：搜索请求，包含一个搜索字符串和对响应主 机的最小速度要求。 oQueryHit：对Query的响应，包含响应主机的IP地址 、能接受连接的端口、连线

19、速度、查询结果集（包含 匹配的文件数量以及每个匹配文件的索引、文件大小 及文件名）。 Gnutella查询与响应过程 o一个节点与自己所知道的每一个节点建立TCP/IP连接 。 o节点向每一个连接的节点发送Ping消息；收到Ping消 息的节点发送一个Pong消息，同时将Ping消息继续向 其邻居传播。 o节点使用Query查询文件，Query使用相同的洪泛方 式传输。 oTTL被用来限制Ping和Query的传播范围。每个消息 携带全局唯一的标识符，用于检测和丢弃重复的消息 。 o当收到QueryHit时，表明在响应主机上找到了文件。 3.3 内容可寻址网络 o分布式P2P系统的核心是一个将

20、文件名映射到 文件存放位置的索引系统。 o查找服务通过将对等节点组织到一个有结构的 覆盖网络中，并将消息通过覆盖网络路由到相 关对等节点来实现。 o到目前为止，已经有多个研究项目实现了分布 式P2P查找服务。 Content-Addressable Network（CAN） oCAN类似于一张大哈希表，基本操作包括插入、查 找和删除对： n关键字可能是部分或完整的文件名 n值可能为获取该文件所需的信息（如大小、位置等） o网络中每个节点保存哈希表的一块（区）。 o对一个特定关键字的请求（插入、查找或删除）由 中间CAN节点路由到包含该关键字的目标CAN节点 。 CAN的坐标空间 oCAN基于一

21、个虚拟的d维笛卡尔坐标空间来 组织数据和实现查找功能： n整个坐标空间被动态分配给系统中的所有节点； n每个节点都拥有独立和不相交的一块区域； n如果两个区域在（d-1）维上跨度相同，而在另 一个维度上相邻，就称这两个区域相邻； n若两个节点拥有的区域相邻，就称这两个节点在 坐标空间中相邻。 一个二维的CAN坐标空间示例 名字到位置的映射 o存储对的方法： n使用一个均匀哈希函数将key映射成坐标空间中的一 个点P，被保存在P所在区域对应的CAN 节点中。 o查询关键字Key： n使用相同的哈希函数得到点P，从P所在区域对应的 CAN节点中得到Value。 o如果P不在查询节点所拥有的区域中，

22、查询请求通过 CAN网络路由到包含P的CAN节点。 CAN路由 oCAN中的节点自动形成一个表示虚拟坐标空间 的覆盖网络： n每个节点学习并维护坐标空间中相邻节点的IP地 址和虚拟坐标区域，这组邻居节点就形成了坐标 路由表。 o每条CAN消息都包含目的点P的坐标。 o节点利用坐标路由表，使用贪婪转发机制将消 息转发给距离P最近的邻居节点。 一个CAN查找的例子 节点加入CAN o找到一个已有节点： n在DNS中查找CAN的域名，得到一个引导节点的IP地址。 n引导节点随机选择当前系统中几个节点的IP地址，提供给新节点 。 o找到一个要分裂的区域： n在坐标空间中随机选择一个点P，向P发送一个加

23、入请求。 n该消息通过已有节点送入CAN，路由到P所在区域的CAN节点。 n该节点将它的区域分裂成两半，将一半分配给新节点。 o加入路由： n新节点向区域的原节点了解其邻居节点的IP地址，形成自己的邻 居集合；原节点也要更新自己的邻居集合。 n新老节点将自己当前分配的区域告知其邻居。 新节点加入的例子 节点7加入前 节点7加入后 节点离开CAN o正常的做法： n节点显式地将其区域和相关的数据库转 交给一个邻居节点。 n如果某个邻居节点的区域可以和该节点的区域合并成一个 合法的区域，转交完成。否则， n该区域转交给当前区域最小的节点，这个节点要临时接管 两个区域。 o节点通过周期性更新消息，告

24、知邻居自己的区域坐标和 其邻居节点的区域坐标。 o当节点失效时，其邻居之一要立即接管失效节点的区域 ，但失效节点中保存的丢失。 CAN的缺点 o经过哈希之后，节点的位置信息被破坏了，来自同 一个子网的站点很可能节点号相距很远，这不利于 查询性能的优化。 o基于哈希表的系统不能利用应用本身的信息，许多 应用（如文件系统）的数据本身是按照层次结构组 织的，而使用哈希函数后这些层次信息就丢失了。 4 P4P技术 oP2P带宽吞噬问题： nP2P流量已经占到整个互联网流量的50%左右 ，且仍在持续增长。 nP2P流量大量占用宝贵的骨干网带宽资源，尤 其是互联互通出口及国际出口的带宽，极大地 增加了投资

25、成本压力，并造成运营成本上升。 n用户正常的上网业务的服务质量难以得到有效 保障。 带宽吞噬问题的根源P2P的交换机制 oP2P过于强调对等，它对资源在网络中的位置 不作区分，一律平等地返回给用户，而用户随 机选择一个节点交换。 o节点之间的交换完全是无序的，无序的交换导 致无谓的跨地区甚至是跨国的“流量旅行”，耗 费了宝贵的国内和国际带宽资源。 依靠P2P应用的解决方案 o基于局部性原则选择节点： n如优先选择相同子网、相同ISP内的节点交换文件片段 。 n若不考虑链路流量、不同链路的通信开销，可能会给骨 干网带来拥塞或造成不必要的费用开销。 o基于逆向流量工程的流量走向调整： n应用发送探

26、测消息收集和推测底层网络状态，确定流量 走向。 n依赖网络测量技术，而测量会消耗带宽，且不能完全反 映网络的真实状态。 n一些新技术（如MPLS）对探测消息不响应。 n无法推测ISP运营商的策略信息。 基于ISP的流量控制 o目前因特网上的流量控制主要是ISP的责任： n应用给出网络流的目的地址及流量需求模式，ISP根 据当前网络状态确定最有效的路由。 oP2P模式改变了传统的流量控制问题： n应用需要的数据可以从很多节点、以很多种方式得到 ，每一种方式都会产生一种不同的流量需求模式并导 致不同的网络使用效率。 nP2P的动态流量模式能够自动适应网络变化，但也使 得ISP估计网络状态并确定最佳

27、路由的努力无效。 基于ISP和P2P应用合作的P4P技术 o网络运营商和P2P应用应合作解决流量吞噬问题 ： n网络运营商将底层网络状态及策略信息提供给 P2P应用 nP2P应用根据这些信息智能地选择数据交换对象 oP4P（Proactive network Provider Participation for p2p）： n一个旨在同时优化ISP和P2P系统性能的网络架构 n已集成到一些具有代表性的P2P软件中，在商业 测试中表现出色。 4.1 P4P架构 oP4P是一个允许网络运营者向新型应用显式提供 网络信息、策略及能力的通用框架，除P2P之外 可支持各种高带宽应用。 oP4P由控制面、

28、管理面和数据面组成： n数据面（可选）：区分应用流和设定应用流的 优先级 n控制面：通过iTracker向应用提供网络信息 n管理面：监视控制面的行为 P2P控制面中的实体 oiTracker：代表一个网络运营商 oappTracker：代表一个P2P应用 oPeer：代表P2P客户 o对等客户从appTracker或iTracker（若无appTracker ）获得必要的信息，并帮助分发信息。 iTracker提供的接口 o策略接口：用于向对等客户或appTracker提供网络使用策 略和指导意见。 oP4P距离接口：用于查询对等客户之间的开销和网络距离 。 o能力接口：用于对等客户或内容接

29、供商向运营商请求能力 （资源）。 appTracker使用接口的例子 4.2 P4P距离（p-distance） oP4P架构中最核心的接口是P4P距离： n运营商通过该接口告诉应用当前网络中域内和 域间的网络开销。 n应用使用P4P距离来优化连接，提高网络通信效 率。 oP4P接口有两个视图： niTracker看到的内部视图 n应用看到的外部视图 内部视图 o内部视图是一个网络拓扑G =（V, E），其中V是节点 集合，E是链路集合。 oV中的节点称为PID（opaque ID），有以下几种类型 ： n汇聚节点：代表一组客户（如一个网点或网络状态相同的 一组节点），对外部是可见的。 n核心

30、路由器：对应用和客户不可见。 n外部域节点：对应用和客户不可见。 oiTracker在内部视图中连接两个PID（如果这样连接是 有意义的），并给每条PID层次的链路指定一个p-距离 。 外部视图 oiTracker提供的外部视图是一个全连接的 网状网络： n给定一对外部可见的PID i和j，iTracker给出 从PID-i到PID-j的p-距离（pij）。 npij是iTracker根据网络内部距离和路由计算出 来的，iTracker可以给这个距离一个干扰来增 强隐秘性。 p4p距离的指定 oISP可以有很多种方法来指定p-距离，比如 ： n从OSPF权值和BGP偏好来得到p-距离 n给具有

31、较高成本或接近拥塞的链路指定较大的p -距离 n按照某种优化目标计算p-距离 P-距离信息的分发 oISP可从以下几个方面控制p-距离信息的分发： nPID的聚合粒度：控制粒度 vs 扩放性和用户隐私。 n网络信息的粒度和语义：简单、健壮 vs 控制粒度 和信息语义。 n信息的接收者：安全、隐私保护 vs 信息的中立性 。 o使用p-距离接口的权衡涉及扩放性、语义和隐私。 o接口本身是简单、灵活和标准化的（易于互操作） ，复杂性体现在如何使用，而如何使用是由ISP决 定的。 使用P-距离接口选择对等客户（1） o按p-距离选择对等客户： nPID-i客户选择PID-j客户的概率为pij的递减函

32、数。 n当来自PID-i的一个客户加入一个P2P会话时， appTracker查询iTracker，得到从PID-i到其它 PID的p-距离。 n如果iTracker指定PID-i内的p-距离最小，到其它 PID的p-距离次之，到外部网络的p-距离最高，则 应用可减少穿过PID和自治系统的流量。 使用P-距离接口选择对等客户（2） o有上/下载流量匹配要求的应用： n假设P2P会话k计算出PID-i到其它PID的上载容量为uik， 下载容量为dik，从PID-i到PID-j的流量为tijk。不考虑网络 效率，会话k选择P2P对等客户的问题描述为以下优化问题 ： 有上/下载流量匹配要求的应用（续

33、） o若考虑ISP的优化目标，会话k可选择在满足一定流量 的前提下最大化网络效率，则以上优化问题变为： 使用P-距离接口选择对等客户（3） o有鲁棒性要求的应用： nPID-i中的客户应与其它 PID中一定数量的客户连 接。 n引入变量ijk：PID-i客 户到PID-j客户的流量应 占PID-i客户到所有其它 PID客户流量的最小比例 。 P4P设计的理论基础 oiTracker收集网络状态信息： nbe：边e上的背景流量（非P2P流量） nce：边e的容量 nIe(i,j)：指示边e是否在从PID-i到PID-j的路由上。 oTk为会话k可以接受的流量模式集合。 o对于其中一个tkTk，若

34、会话k选择tk，则它将产生从 PID-i到PID-j的P2P流量tijk，相应地边e上的流量总 和为tek。 问题描述 o若采用传统的ISP流量工程目标，需要求解以下优 化问题（最小化最大链路利用率）： o改写以上优化问题为： 问题分解 o对于公式（9）中的每一个约束条件，引入一个对偶变量 pe0，定义拉格朗日对偶方程： o为使方程有界，的系数必须为0，即： o对偶方程简化如下： iTracker与应用的交互 o会话 k 从 iTracker 获得 o本地计算 ，使满足 oiTracker获得应用反馈的 ，调整pe： o更新pij，返回给查询的应用； o应用更新tk。 4.3 基于P4P架构的

35、P2P流媒体系统 oP2P流媒体是结合流媒体技术与P2P技术的流媒 体解决方案。 o基于组播树的P2P流媒体技术： n构建以视频源为根的数据分发树；当节点收到数 据包后，将数据包的拷贝转发给它的每一个子节 点。（典型的数据推送方法） n优点：拓扑结构简单。 n缺点：拓扑维护开销大，可靠性差，不利于在大 规模的实际环境中使用。 基于P4P架构的P2P流媒体系统（续 ） o基于数据驱动的P2P流媒体技术： n每一个频道看作是一个子覆盖网络，频道的媒体数 据分割成chunk，节点间采用gossip协议分发数据 。 n优点：不需要维护分发结构，系统健壮性好。 n缺点：随机推送导致大量冗余；没有明确的拓

36、扑结 构支持，最小化启动和传输时延成为主要问题。 n改进：通过数据拉取技术解决传输冗余问题。节点 维护一组伙伴，周期性地同伙伴交换数据可用性信 息和数据。 一个融合P4P架构的P2P流媒体系统 如何发现iTracker地址 oappTracker通过DNS解析P4P服务的域名，获取 iTracker的IP地址。 o在appTracker上直接配置iTracker地址。 4.4 基于P4P技术的Gnutella路由算法 oGnutella 0.6引入了超级节点的概念： n超级节点：叶子节点的代理，只在认为叶子节点能 够响应查询请求时才向叶子节点转发查询请求； n叶子节点：从不向超级节点转发查询请

37、求。 Gnutella 0.6的工作原理 o节点加入： n节点连接到网络后，使用Ping消息找到最近的超级节点； n通过该超级节点了解并连接更多的超级节点； n选择一个超级节点，成为它的叶子节点。 o查询转发： n节点向自己的超级节点发送Query消息； n若超级节点有符合查询要求的文件，发送QueryHit消息 ； n超级节点递减Query的TTL值，若不为0，向相邻的超级 节点及可能包含该文件的叶子节点转发Query消息。 使用P4P技术优化超级节点的选择 o在Gnutella网络中，满足以下条件的对等节点成为 超级节点： n主机没有处在防火墙内且运行合适的操作系统 n具有足够的带宽、机器

38、性能和正常运行时间 n连接了不少于一定数量的客户节点 o可以利用P4P技术优化超级节点的选择： n基于P4P技术获得的信息，选择那些连通度较高的 节点作为超级节点。 使用P4P技术优化节点加入 o在Gnutella协议中： n节点从获得的超级节点中随机选择一个加入。 o利用P4P技术优化节点加入： n基于P4P技术获得的网络信息，优先选择位于 同一个ISP、（在同一个ISP时）同一个城市的 超级节点加入。 n可减小超级节点和叶子节点的通信延迟，降低 骨干网络间的通信流量。 使用P4P技术优化查询请求的转发 o超级节点的路由表中维护了到其它超级节点的路 由。 o基于P4P技术获得的网络信息，超级

39、节点可以计 算到其它超级节点的通信代价，记录在路由表中 。 o在向其它超级节点转发查询请求时，选择通信代 价较小的超级节点转发查询请求。 5 搭便车现象及抑制机制 oP2P通信模式倡导的理念是协作和共享，但P2P网络 的理性用户更多地表现出自主性和自私性，只想索取 资源而不愿贡献资源。 o节点只享受服务而不为系统做贡献的行为称为搭便车 （free riding），大量搭便车现象将导致P2P网络效 用大幅降低。 oP2P网络中还存在大量不可靠的服务以及欺诈行为。 o必须考虑P2P网络中节点的自主行为，激励节点之间 有效合作并合理使用网络资源。 搭便车行为的研究进展 o第一阶段：试图测量不同对等网

40、络中的搭便车现 象，分析其数学特征。 o第二阶段：一些搭便车行为的抑制机制被提出， 其中少数已应用到真实系统中。 o第三阶段：意识到还没有哪一种方法可以彻底解 决对等网络中的搭便车行为，应更深入地研究抑 制机制，并在真实系统中验证有效性。 搭便车现象的测量结果 o极少数热心节点维持了大量的连接。 o测量结果表明，搭便车现象在对等网络中广泛存在 。 拱便车行为的数学建模 o有文献采用排队论对对等网络的服务能力进 行了数学建模，研究表明： n提供服务的节点数越多、单一文件的拷贝数 量（网络中包含该文件的节点数）越多，则 对等网络的服务能力越强。 n不同结构的P2P应用系统，容忍搭便车行为 的能力有

41、所不同。 搭便车节点比例与对等网络吞吐率的关系 oCIA：具有集中 索引服务器的对 等网络 oDIFA：分布式 洪泛机制的对等 网络 oDIHA：分布式 哈希表索引的对 等网络 BT的激励机制 oBT采用激励机制来抑制搭便车行为：节点以较大优先级 选择向其提供了较大下载带宽的节点提供数据上传服务 。 o在该机制下，单个搭便车节点能获取的最大带宽如下， 是节点上传带宽，nu是单个节点最大并发下载连接数 ： o直接提高nu即可降低搭便车者享受的服务，但节点需支 持较多的并发TCP连接数，易出现超时重传或拥塞现象 ，网络有效吞吐率下降。在BT中，nu设为4。 搭便车行为对对等网络的影响 o大量搭便车

42、节点可能使热心节点因长期过载而宕 机，导致整个对等网络的连通性发生巨大变化。 o大量搭便车行为会降低对等网络的生命周期：热 心节点因得不到资源而离开网络，并带走大量的 资源，导致更多的节点离开。 o如果搭便车现象过于严重，对等网络将趋近客户 机/服务器通信模式，其可用性甚至比传统的客 户机/服务器通信模式更差。 为什么容忍搭便车现象的存在？ o多数对等网络软件开发者容忍搭便车现象存在。 以下三个因素值得考虑： n搭便车现象使对等网络抵御随机选择节点攻击的 能力较强。 n搭便车现象使得对等网络中节点的重要性不再均 衡，管理者可以重点管理数量不多的热心节点。 n允许一定程度的搭便车现象，有利于吸引

43、自私的 节点用户加入到对等网络，提高对等网络的用户 数量。 搭便车行为抑制机制 o抑制搭便车行为的共同指导原则是：根据节点 已做出的贡献，确定它能够享受服务的能力。 o已提出的抑制机制分为三类： n基于节点行为的激励机制 n基于博弈论的方法 n采用社会网络或经济模型的控制策略 基于节点行为的激励机制 o激励机制的算法流程： o不同激励机制之间的差异主要体现在效用函数定义 、测量点选择等方面。 效用函数设计 o效用函数：节点享受服务的能力与节点为系统已做贡献 的关系。 o效用函数可能涉及以下自变量： n节点共享文件的数量 n节点已下载文件的数量 n节点已上传文件数量 n节点已下载数据的大小 n节

44、点已上传数据的大小等。 o定义计算复杂度小、又能客观反映搭便车控制关键问题 的效用函数是激励机制设计的核心。 测量点位置选择 o自我测量： n节点把自已每次提供服务或享受服务的行为记录下 来，评价自己在网络中的贡献大小。 n工程上容易实现，开销小，但很难对付恶意欺骗的 节点。 o相邻节点测量： n每个节点对相邻节点进行测量和监督，各个节点的 贡献大小由邻接节点评价。 n节点互相测量能有效防止少数节点的恶意欺骗，但 分布式测量的系统开销比较大。 自我测量的激励机制（1） o效用函数一： n|UList(Pi , T)|表示在 T 时刻节点 i 所提供的共 享文件数量，是一个规范化系数（常量）。

45、n节点能享受的服务质量正比于节点共享的文件 数量。 自我测量的激励机制（2） o效用函数二： n节点能享受的服务质量正比于节点共享的文件 大小总量。 o以上两个效用函数没有反映节点所提供的文件 被其它节点下载次数的动态信息。 自我测量的激励机制（3） o效用函数三： n第一项是节点i在时刻T的奖励值，第二项是惩罚 值，上传（下载）越多，奖励（惩罚）越多。 nK可以用作在线时间的度量，实现免费赠品。 自我测量的激励机制（4） o考虑节点异构性的效用函数值比较： nCi(t)是节点所做绝对贡献值，di是节点最大可 支持物理带宽。 邻居节点测量 o测量方法： n节点观察其邻居节点发送、转发信令包和数

46、 据包的行为（节点可以仅对通过自己转发的 报文做日志记录）； n根据日志记录定期计算邻居节点的效用函数 ，发现搭便车者。 三类搭便车者 o发出响应报文次数极低的节点，表明该节点一般 没有提供共享信息资源，或仅共享了不被其它用 户访问的资源。 o从邻接节点获得的资源数量远大于它为其它节点 提供服务的报文数量。 o转发信令报文非常少的节点，该节点不为整个对 等网络承担路由维护义务。 三个层次的惩罚方案 o第一个层次： n快速降低搭便车者发出的查询请求消息的TTL值 ，降低报文在网络中的传播范围。 o第二个层次： n忽略自私节点的查询请求。 o第三个层次： n直接取消与搭便车者的连接，将其清除出对等

47、 网络。 基于激励的抑制机制面临的困难 o自我测量的激励机制： n效用函数严格程度的选择，在如何抑制搭便车行为 与鼓励用户加入对等网络之间存在两难。 n位于防火墙或NAT之后的节点会被认定搭便车者。 o分布式测量与监视机制： n节点之间互相监视开销大。 n对连接数很高的节点，监视邻接节点会增加节点负 担。 博弈论方法 o博弈论是分析社会群体和经济活动中，个体和群 体选择最优行为策略的有效数学工具。 o利用博弈论方法建模，一个节点的行为选择与同 时在线的其它节点的行为选择紧密相关。 o节点在对等网络中的行为可以建模为长期博弈过 程，节点可在包括热心为系统做贡献、贪婪下载 、贡献收益平衡等多种行为

48、策略集合中找到有利 于最大化自身收益的策略选择。 博弈论方法的困难 o采用博弈论作为数学工具，定量化分析程度高 ，但在实际系统开发过程中面临以下问题： n一般需要整个对等网络系统的全局知识，难以 满足。 n一些假设太严格，与真实环境差异很大，结果 未必具有指导意义。 社会网络和经济模型 o对等网络中的节点存在的自私行为，是节点用户 个人心理因素的一种延伸。 o一些来自经济学、公共策略管理领域的学者讨论 利用社会网络模型、经济模型、价格机制等方法 来抑制搭便车现象。 o已提出的一些方案包括利用市场管理技术促进节 点之间的协作、利用市场机制模型抑制搭便车现 象、采用社会经济生活中审计、竞价等机制抑

49、制 搭便车行为等。 社会网络方法面临的困难 o大多假设对等网络软件具有对节点的行为审计 和微支付功能，在大规模对等网络中基本难以 满足。 o尽管提出了一些模型，但定量化分析和工程实 现方面研究较少。 参考文献 1 B. Pourebrahimi, et, al. A Survey of Peer-to-Peer Networks. 2 An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol. 3 S. Ratnasamy, et, al. A Scalable Content-Addressable Network. SIGCOMM 2001. 4 Haiyong Xie, et, al. P4P: Provider Portal for Applications. SIGCOMM 2008. 5 基于P4P架构的P2P流媒体系统。 6 P4P-Gnutella：基于P4P技术的Gnutella路由算法。 7 对等网络中的搭便车行为分析与抑制机制综述。