对等网络课件

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

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

3、、BitTorrent等。BitTorrent是最流行的P2P文件共享系统之一：种子节点（保存完整的文件拷贝）把一个文件分成N个分片（默认为256KB）。节点X从种子节点随机下载第L个分片，Y 随机下载第M个分片，然后节点X与Y 交换彼此拥有的分片。减轻了种子节点的负担，提高了节点下载的速度与效率。 P2P技术的应用（1）提供文件或其它内容共享，如NapsteP2P技术的应用（2）P2P媒体网：P2P也非常适合流媒体直播与点播，因此P2P研究热点迅速转移到P2P的流媒体上。目前P2P非常广泛的一个应用是网上实时电视，提供节目的成本很低，用户却可以得到较好的收视质量。流行的软件包括Coolstr

4、eaming、AnySee、Gridmedia、PPLive和PPStream等。 P2P技术的应用（2）P2P媒体网：P2P技术的应用（3）基于P2P方式的协同处理与服务共享平台：P2P技术将众多终端空闲的CPU资源联合起来，服务于一个共同的计算。计算任务（包括逻辑与数据等）划分成多个片，分配到参与计算的P2P节点上；计算结果返回给一个或多个服务器；众多结果整合得到最终结果。最著名的P2P分布式科学计算系统为搜索外星文明的SETIhome科学实验。P2P技术的应用（3）基于P2P方式的协同处理与服务共享平台P2P技术的应用（4）即时通信交流：VoIP是一种全新的网络电话通信业务，Skype就

5、是一款典型的P2P VoIP软件。Skype的出现给传统电信业带来强烈的冲击，截至2011年年底，Skype占有全球长途通话时长的33%。 Skype仍在迅速向各个国家渗透。 P2P技术的应用（4）即时通信交流：P2P系统的定义P2P系统是一个由直接相连的节点所构成的分布式系统，这些节点能够为了共享内容、CPU时间、存储或者带宽等资源而自组织形成一定的网络拓扑结构，能够在适应节点数目的变化和失效的同时维持可以接受的连接能力和性能，并且不需要一个全局服务器或者权威的中介支持。 P2P系统的定义P2P系统是一个由直接相连的节点所构成的分布2. P2P网络的拓扑结构P2P系统的主要概念之一是分散，包

6、括分布式存储、处理、信息共享和控制信息。 根据P2P系统的分散程度，可以将P2P架构分成纯分散式和混合式。根据结构关系可以将P2P系统细分为四种拓扑形式：中心化拓扑全分布式非结构化拓扑全分布式结构化拓扑半分布式拓扑2. P2P网络的拓扑结构P2P系统的主要概念之一是分散，包2.1 中心化拓扑最早出现的P2P网络结构，也称集中目录式结构，或非纯粹的P2P结构。优点：维护简单，资源发现效率高。缺点：单点故障；扩放性差；版权问题。对小型网络而言在管理和控制方面有一定优势，不适合大型网络应用。2.1 中心化拓扑最早出现的P2P网络结构，也称集中目录式结Napster文件共享系统中央索引服务器保存所有用

7、户上传的音乐文件索引和存放位置。用户需要某个音乐文件时，先查询中央索引服务器，得到存有该文件的节点信息。用户选择合适的节点建立直接连接。Napster首先实现了文件查询与文件传输的分离。Napster的拓扑结构Napster文件共享系统中央索引服务器保存所有用户上传的音2.2 全分布式非结构化拓扑 也称纯P2P结构，取消了中央服务器，每台机器是真正的对等关系（称为对等机）。每个用户随机接入网络，并与自己相邻的一组节点通过端-端连接构成一个逻辑覆盖网络。对等节点之间的内容查询和内容共享均直接通过相邻节点广播接力传递。每个节点记录搜索轨迹，防止产生搜索环路。 Gnutella是应用最广泛的全分布式

8、非结构化拓扑。 2.2 全分布式非结构化拓扑 也称纯P2P结构，取消了中央服Gnutella早期的拓扑结构要下载文件的计算机以文件名或关键字生成一个查询，发送给与它相连的所有计算机。存在该文件的计算机与查询机器建立连接；否则继续向自己的邻居节点洪泛。重复该过程，直至找到文件为止。一般通过TTL值控制查询的深度。Gnutella早期的拓扑结构要下载文件的计算机以文件名或关全分布式非结构化拓扑的特点将覆盖网络看成完全随机图，节点之间的链路没有遵循某些预先定义的拓扑来构建。优点：解决了网络结构中心化的问题，扩展性和容错性较好；支持复杂的查询（如多关键词查询、模糊查询等）。缺点：查询结果可能不完全，查

9、询速度较慢；网络规模较大时，消耗网络带宽多，易造成部分低带宽节点因过载而失效，影响网络的可用性；容易受到垃圾信息甚至是病毒的恶意攻击。 全分布式非结构化拓扑的特点将覆盖网络看成完全随机图，节点之间2.3 全分布式结构化拓扑 采用分布式散列表（DHT）组织网络中的节点：DHT是由广域范围内大量节点共同维护的巨大散列表。散列表被分割成不连续的块，每个节点被分配一个散列块，并成为这个散列块的管理者。每个节点按照一定的方式被赋予一个惟一的Node ID。资源对象的名字或关键词通过一个散列函数映射为128位或160位的散列值，资源对象存储在Node ID与其散列值相等或相近的节点上。需要查找资源时，采用

10、同样的方法定位到存储该资源的节点。 2.3 全分布式结构化拓扑 采用分布式散列表（DHT）组织网基于DHT的节点组织每个节点通过散列其IP地址，得到一个128位的节点标识符。所有节点标识符形成一个环形的node ID空间，其中只有一部分对应了实节点。Key的散列值为d46a1c的内容存放在节点d467c4上。基于DHT的节点组织每个节点通过散列其IP地址，得到一个12全分布式结构化拓扑的特点优点：采用确定性拓扑结构，DHT可以提供精确发现。缺点：维护机制较复杂，尤其是节点频繁加入/退出造成的网络波动会极大地增加维护DHT的代价。仅支持精确关键词匹配查询，无法支持内容/语义等复杂查询。 这种结构

11、目前还没有大规模成功应用的实例。全分布式结构化拓扑的特点优点：2.4 半分布式结构亦称混合结构，吸取了中心化结构和全分布式非结构化的优点。选择性能（处理、存储、带宽）较高的节点作为超级节点，各个超级节点上存储其它部分节点的信息。发现算法仅在超级节点之间转发，超级节点再将查询请求转发给适当的叶子节点。半分布式结构是一种层次式结构：超级节点之间构成一个高速转发层超级节点和所负责的普通节点构成若干层次2.4 半分布式结构亦称混合结构，吸取了中心化结构和全分布式Kazaa的拓扑结构节点按能力不同区分为普通节点和搜索节点。搜索节点与其临近的若干普通节点构成一个自治的簇：簇内采用中心化P2P结构簇之间通过

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

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

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

15、ype的通信过程初始化：询问skype的最新版本登录客户端启动后连接到超级节点，向登录服务器发送身份认证信息。登录服务器验证用户名和密码的合法性。客户端向好友及其它对等节点发送在线信息。客户端与超级节点交换消息，检测NAT和防火墙类型。客户端发现拥有公网IP地址的在线Skype节点。登录客户端启动后连接到超级节点，向登录服务器发送身份认证信息连接到超级节点客户端在主机缓存中维护一个超级节点列表，包含一系列超级节点的。初次安装客户端软件后，超级节点列表中至少包含7个，这些便是初始的超级节点。登录时，客户端试图同列表中的每一个表项（超级节点）建立连接。Skype没有默认的服务端口号，在安装客户端软

16、件时随机选择（或设置）一个端口号监听，同时监听80和443端口。连接到超级节点客户端在主机缓存中维护一个超级节点列表，包含一向好友发送在线信息Skype采用路由缓存机制：超级节点缓存查找到的用户信息（缓存72小时）。用户登录后，其状态信息可以通过超级节点通知到好友终端，也可以得到好友的状态。一旦缓存超时，需通过其它超级节点查找用户。 向好友发送在线信息Skype采用路由缓存机制：查找用户具有公网地址的客户端，查找用户的过程：向超级节点（SN）发送要查找的用户信息；若不成功，从SN获取四个节点地址，发送用户信息；若不成功，报告SN，获取八个节点地址，发送用户信息；成功或失败返回位于私网内的受限客

17、户端，查找用户的过程：客户端将需要查找的用户信息发送给其超级节点；超级节点完成查找后，返回给私网内的客户端。查找用户具有公网地址的客户端，查找用户的过程：呼叫建立和释放 主、被叫都在公网内呼叫建立和释放 主、被叫都在公网内呼叫建立和释放（续） 主、被叫至少有一方在私网内呼叫建立和释放（续） 主、被叫至少有一方在私网内Skype的技术优势较强的NAT和防火墙穿越能力：首先识别NAT和防火墙类型，然后动态选择信令和媒体代理。 快速路由机制：采用全球索引技术，用户路由信息分布式存储于网络节点中。结合互联网特点的语音编解码算法：引入专门针对互联网特点的语音质量增强软件。很低的运行成本：很多工作下放给网

18、络节点完成，大大降低了中心服务器的负担，减少了维护和管理成本。Skype的技术优势较强的NAT和防火墙穿越能力：首先识别N2.5 四种拓扑结构的对比中心化全分布式非结构化全分布式结构化半分布式可扩展性差差好中可靠性差好好中可维护性最好最好好中发现算法效率最高中高中复杂查询支持支持不支持支持2.5 四种拓扑结构的对比中心化全分布式非结构化全分布式结构3 P2P网络的资源发现机制中心化结构：集中式索引和存储分布式非结构化：查询请求的洪泛广播分布式结构化：内容可寻址网络3 P2P网络的资源发现机制中心化结构：集中式索引和存储3.1 集中式索引和存储一个集中的目录服务器保存所有资源的位置和使用信息：网

19、络中所有文件的元数据（文件名、创建时间等）索引；登录用户的连接信息表（IP地址、连接速度等）；每个用户拥有并愿意共享的文件列表。 起始时，客户与目录服务器建立连接，报告其保存的文件列表。当目录服务器收到来自用户的查询时，查找索引表，返回存有所需文件的用户列表。用户选择其中一个对等方建立直接连接，下载文件。 3.1 集中式索引和存储一个集中的目录服务器保存所有资源的位Napster中的资源发现Napster中的资源发现3.2 查询请求的洪泛广播洪泛查询的过程：在覆盖网络上，查询节点将一个资源发现请求发送给与其直接相连的所有节点；这些节点再向其直接相连的邻居洪泛该请求；直到请求被响应或达到最大洪泛

20、次数。早期的Gnutella使用洪泛机制发现网络中的文件。 3.2 查询请求的洪泛广播洪泛查询的过程：Gnutella使用的消息Ping：节点使用该消息宣告自己。Pong：对Ping的响应，包含响应主机的IP地址、能接受响应的端口、本机共享文件数量及所占空间大小。Query：搜索请求，包含一个搜索字符串和对响应主机的最小速度要求。QueryHit：对Query的响应，包含响应主机的IP地址、能接受连接的端口、连线速度、查询结果集（包含匹配的文件数量以及每个匹配文件的索引、文件大小及文件名）。Gnutella使用的消息Ping：节点使用该消息宣告自己。Gnutella查询与响应过程一个节点与自己

21、所知道的每一个节点建立TCP/IP连接。节点向每一个连接的节点发送Ping消息；收到Ping消息的节点发送一个Pong消息，同时将Ping消息继续向其邻居传播。节点使用Query查询文件，Query使用相同的洪泛方式传输。TTL被用来限制Ping和Query的传播范围。每个消息携带全局唯一的标识符，用于检测和丢弃重复的消息。 当收到QueryHit时，表明在响应主机上找到了文件。 Gnutella查询与响应过程一个节点与自己所知道的每一个节3.3 内容可寻址网络分布式P2P系统的核心是一个将文件名映射到文件存放位置的索引系统。查找服务通过将对等节点组织到一个有结构的覆盖网络中，并将消息通过覆盖

22、网络路由到相关对等节点来实现。到目前为止，已经有多个研究项目实现了分布式P2P查找服务。 3.3 内容可寻址网络分布式P2P系统的核心是一个将文件名映Content-Addressable Network（CAN）CAN类似于一张大哈希表，基本操作包括插入、查找和删除对：关键字可能是部分或完整的文件名值可能为获取该文件所需的信息（如大小、位置等） 网络中每个节点保存哈希表的一块（区）。对一个特定关键字的请求（插入、查找或删除）由中间CAN节点路由到包含该关键字的目标CAN节点。 Content-Addressable Network（CACAN的坐标空间CAN基于一个虚拟的d维笛卡尔坐标空间来

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

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

25、。找到一个要分裂的区域：在坐标空间中随机选择一个点P，向P发送一个加入请求。 该消息通过已有节点送入CAN，路由到P所在区域的CAN节点。该节点将它的区域分裂成两半，将一半分配给新节点。 加入路由：新节点向区域的原节点了解其邻居节点的IP地址，形成自己的邻居集合；原节点也要更新自己的邻居集合。 新老节点将自己当前分配的区域告知其邻居。 节点加入CAN找到一个已有节点：新节点加入的例子 节点7加入前 节点7加入后新节点加入的例子 节点7加入前 节点7加入后节点离开CAN正常的做法：节点显式地将其区域和相关的数据库转交给一个邻居节点。如果某个邻居节点的区域可以和该节点的区域合并成一个合法的区域，转

26、交完成。否则，该区域转交给当前区域最小的节点，这个节点要临时接管两个区域。节点通过周期性更新消息，告知邻居自己的区域坐标和其邻居节点的区域坐标。当节点失效时，其邻居之一要立即接管失效节点的区域，但失效节点中保存的丢失。节点离开CAN正常的做法：CAN的缺点经过哈希之后，节点的位置信息被破坏了，来自同一个子网的站点很可能节点号相距很远，这不利于查询性能的优化。基于哈希表的系统不能利用应用本身的信息，许多应用（如文件系统）的数据本身是按照层次结构组织的，而使用哈希函数后这些层次信息就丢失了。 CAN的缺点经过哈希之后，节点的位置信息被破坏了，来自同一个4 P4P技术P2P带宽吞噬问题：P2P流量已

27、经占到整个互联网流量的50%左右，且仍在持续增长。 P2P流量大量占用宝贵的骨干网带宽资源，尤其是互联互通出口及国际出口的带宽，极大地增加了投资成本压力，并造成运营成本上升。用户正常的上网业务的服务质量难以得到有效保障。 4 P4P技术P2P带宽吞噬问题：带宽吞噬问题的根源P2P的交换机制P2P过于强调对等，它对资源在网络中的位置不作区分，一律平等地返回给用户，而用户随机选择一个节点交换。节点之间的交换完全是无序的，无序的交换导致无谓的跨地区甚至是跨国的“流量旅行”，耗费了宝贵的国内和国际带宽资源。 带宽吞噬问题的根源P2P的交换机制P2P过于强调对等，它对依靠P2P应用的解决方案基于局部性原

28、则选择节点：如优先选择相同子网、相同ISP内的节点交换文件片段。若不考虑链路流量、不同链路的通信开销，可能会给骨干网带来拥塞或造成不必要的费用开销。基于逆向流量工程的流量走向调整：应用发送探测消息收集和推测底层网络状态，确定流量走向。 依赖网络测量技术，而测量会消耗带宽，且不能完全反映网络的真实状态。一些新技术（如MPLS）对探测消息不响应。无法推测ISP运营商的策略信息。 依靠P2P应用的解决方案基于局部性原则选择节点：基于ISP的流量控制目前因特网上的流量控制主要是ISP的责任：应用给出网络流的目的地址及流量需求模式，ISP根据当前网络状态确定最有效的路由。P2P模式改变了传统的流量控制问

29、题：应用需要的数据可以从很多节点、以很多种方式得到，每一种方式都会产生一种不同的流量需求模式并导致不同的网络使用效率。P2P的动态流量模式能够自动适应网络变化，但也使得ISP估计网络状态并确定最佳路由的努力无效。基于ISP的流量控制目前因特网上的流量控制主要是ISP的责任基于ISP和P2P应用合作的P4P技术网络运营商和P2P应用应合作解决流量吞噬问题：网络运营商将底层网络状态及策略信息提供给P2P应用P2P应用根据这些信息智能地选择数据交换对象P4P（Proactive network Provider Participation for p2p）：一个旨在同时优化ISP和P2P系统性能的网

30、络架构已集成到一些具有代表性的P2P软件中，在商业测试中表现出色。 基于ISP和P2P应用合作的P4P技术网络运营商和P2P应用4.1 P4P架构P4P是一个允许网络运营者向新型应用显式提供网络信息、策略及能力的通用框架，除P2P之外可支持各种高带宽应用。P4P由控制面、管理面和数据面组成：数据面（可选）：区分应用流和设定应用流的优先级控制面：通过iTracker向应用提供网络信息管理面：监视控制面的行为 4.1 P4P架构P4P是一个允许网络运营者向新型应用显式提P2P控制面中的实体iTracker：代表一个网络运营商appTracker：代表一个P2P应用Peer：代表P2P客户对等客户从

31、appTracker或iTracker（若无appTracker）获得必要的信息，并帮助分发信息。P2P控制面中的实体iTracker：代表一个网络运营商iTracker提供的接口策略接口：用于向对等客户或appTracker提供网络使用策略和指导意见。P4P距离接口：用于查询对等客户之间的开销和网络距离。能力接口：用于对等客户或内容接供商向运营商请求能力（资源）。iTracker提供的接口策略接口：用于向对等客户或appTappTracker使用接口的例子appTracker使用接口的例子4.2 P4P距离（p-distance）P4P架构中最核心的接口是P4P距离：运营商通过该接口告诉应用

32、当前网络中域内和域间的网络开销。应用使用P4P距离来优化连接，提高网络通信效率。P4P接口有两个视图：iTracker看到的内部视图应用看到的外部视图4.2 P4P距离（p-distance）P4P架构中最核心内部视图内部视图是一个网络拓扑G =（V, E），其中V是节点集合，E是链路集合。 V中的节点称为PID（opaque ID），有以下几种类型：汇聚节点：代表一组客户（如一个网点或网络状态相同的一组节点），对外部是可见的。核心路由器：对应用和客户不可见。外部域节点：对应用和客户不可见。 iTracker在内部视图中连接两个PID（如果这样连接是有意义的），并给每条PID层次的链路指定一个

33、p-距离。 内部视图内部视图是一个网络拓扑G =（V, E），其中V是节外部视图iTracker提供的外部视图是一个全连接的网状网络：给定一对外部可见的PID i和j，iTracker给出从PID-i到PID-j的p-距离（pij）。pij是iTracker根据网络内部距离和路由计算出来的，iTracker可以给这个距离一个干扰来增强隐秘性。外部视图iTracker提供的外部视图是一个全连接的网状网络p4p距离的指定ISP可以有很多种方法来指定p-距离，比如：从OSPF权值和BGP偏好来得到p-距离给具有较高成本或接近拥塞的链路指定较大的p-距离按照某种优化目标计算p-距离p4p距离的指定IS

34、P可以有很多种方法来指定p-距离，比如：P-距离信息的分发ISP可从以下几个方面控制p-距离信息的分发：PID的聚合粒度：控制粒度 vs 扩放性和用户隐私。网络信息的粒度和语义：简单、健壮 vs 控制粒度和信息语义。信息的接收者：安全、隐私保护 vs 信息的中立性。使用p-距离接口的权衡涉及扩放性、语义和隐私。接口本身是简单、灵活和标准化的（易于互操作），复杂性体现在如何使用，而如何使用是由ISP决定的。P-距离信息的分发ISP可从以下几个方面控制p-距离信息的分使用P-距离接口选择对等客户（1）按p-距离选择对等客户：PID-i客户选择PID-j客户的概率为pij的递减函数。当来自PID-i

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

36、（2）有上/下载流量匹配要求的应有上/下载流量匹配要求的应用（续）若考虑ISP的优化目标，会话k可选择在满足一定流量的前提下最大化网络效率，则以上优化问题变为：有上/下载流量匹配要求的应用（续）若考虑ISP的优化目标，会使用P-距离接口选择对等客户（3）有鲁棒性要求的应用：PID-i中的客户应与其它PID中一定数量的客户连接。引入变量ijk：PID-i客户到PID-j客户的流量应占PID-i客户到所有其它PID客户流量的最小比例。使用P-距离接口选择对等客户（3）有鲁棒性要求的应用：P4P设计的理论基础iTracker收集网络状态信息：be：边e上的背景流量（非P2P流量）ce：边e的容量Ie

37、(i,j)：指示边e是否在从PID-i到PID-j的路由上。Tk为会话k可以接受的流量模式集合。对于其中一个tkTk，若会话k选择tk，则它将产生从PID-i到PID-j的P2P流量tijk，相应地边e上的流量总和为tek。P4P设计的理论基础iTracker收集网络状态信息：问题描述若采用传统的ISP流量工程目标，需要求解以下优化问题（最小化最大链路利用率）：改写以上优化问题为：问题描述若采用传统的ISP流量工程目标，需要求解以下优化问题问题分解对于公式（9）中的每一个约束条件，引入一个对偶变量pe0，定义拉格朗日对偶方程：为使方程有界，的系数必须为0，即：对偶方程简化如下：问题分解对于公式

38、（9）中的每一个约束条件，引入一个对偶变量piTracker与应用的交互会话 k 从 iTracker 获得本地计算 ，使满足iTracker获得应用反馈的 ，调整pe：更新pij，返回给查询的应用；应用更新tk。iTracker与应用的交互会话 k 从 iTracker 4.3 基于P4P架构的P2P流媒体系统P2P流媒体是结合流媒体技术与P2P技术的流媒体解决方案。基于组播树的P2P流媒体技术：构建以视频源为根的数据分发树；当节点收到数据包后，将数据包的拷贝转发给它的每一个子节点。（典型的数据推送方法）优点：拓扑结构简单。 缺点：拓扑维护开销大，可靠性差，不利于在大规模的实际环境中使用。4

39、.3 基于P4P架构的P2P流媒体系统P2P流媒体是结合流基于P4P架构的P2P流媒体系统（续）基于数据驱动的P2P流媒体技术：每一个频道看作是一个子覆盖网络，频道的媒体数据分割成chunk，节点间采用gossip协议分发数据。优点：不需要维护分发结构，系统健壮性好。缺点：随机推送导致大量冗余；没有明确的拓扑结构支持，最小化启动和传输时延成为主要问题。 改进：通过数据拉取技术解决传输冗余问题。节点维护一组伙伴，周期性地同伙伴交换数据可用性信息和数据。 基于P4P架构的P2P流媒体系统（续）基于数据驱动的P2P流一个融合P4P架构的P2P流媒体系统一个融合P4P架构的P2P流媒体系统如何发现iT

40、racker地址appTracker通过DNS解析P4P服务的域名，获取iTracker的IP地址。在appTracker上直接配置iTracker地址。如何发现iTracker地址appTracker通过DNS解4.4 基于P4P技术的Gnutella路由算法Gnutella 0.6引入了超级节点的概念：超级节点：叶子节点的代理，只在认为叶子节点能够响应查询请求时才向叶子节点转发查询请求；叶子节点：从不向超级节点转发查询请求。 4.4 基于P4P技术的Gnutella路由算法GnutelGnutella 0.6的工作原理节点加入：节点连接到网络后，使用Ping消息找到最近的超级节点；通过该超

41、级节点了解并连接更多的超级节点；选择一个超级节点，成为它的叶子节点。 查询转发：节点向自己的超级节点发送Query消息；若超级节点有符合查询要求的文件，发送QueryHit消息；超级节点递减Query的TTL值，若不为0，向相邻的超级节点及可能包含该文件的叶子节点转发Query消息。Gnutella 0.6的工作原理节点加入：使用P4P技术优化超级节点的选择在Gnutella网络中，满足以下条件的对等节点成为超级节点：主机没有处在防火墙内且运行合适的操作系统具有足够的带宽、机器性能和正常运行时间连接了不少于一定数量的客户节点可以利用P4P技术优化超级节点的选择：基于P4P技术获得的信息，选择那

42、些连通度较高的节点作为超级节点。使用P4P技术优化超级节点的选择在Gnutella网络中，满使用P4P技术优化节点加入在Gnutella协议中：节点从获得的超级节点中随机选择一个加入。利用P4P技术优化节点加入：基于P4P技术获得的网络信息，优先选择位于同一个ISP、（在同一个ISP时）同一个城市的超级节点加入。可减小超级节点和叶子节点的通信延迟，降低骨干网络间的通信流量。 使用P4P技术优化节点加入在Gnutella协议中：使用P4P技术优化查询请求的转发超级节点的路由表中维护了到其它超级节点的路由。 基于P4P技术获得的网络信息，超级节点可以计算到其它超级节点的通信代价，记录在路由表中。在

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

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

45、节点数）越多，则对等网络的服务能力越强。不同结构的P2P应用系统，容忍搭便车行为的能力有所不同。拱便车行为的数学建模有文献采用排队论对对等网络的服务能力进行搭便车节点比例与对等网络吞吐率的关系CIA：具有集中索引服务器的对等网络DIFA：分布式洪泛机制的对等网络DIHA：分布式哈希表索引的对等网络搭便车节点比例与对等网络吞吐率的关系CIA：具有集中索引服务BT的激励机制BT采用激励机制来抑制搭便车行为：节点以较大优先级选择向其提供了较大下载带宽的节点提供数据上传服务。在该机制下，单个搭便车节点能获取的最大带宽如下，是节点上传带宽，nu是单个节点最大并发下载连接数：直接提高nu即可降低搭便车者享

46、受的服务，但节点需支持较多的并发TCP连接数，易出现超时重传或拥塞现象，网络有效吞吐率下降。在BT中，nu设为4。BT的激励机制BT采用激励机制来抑制搭便车行为：节点以较大优搭便车行为对对等网络的影响大量搭便车节点可能使热心节点因长期过载而宕机，导致整个对等网络的连通性发生巨大变化。大量搭便车行为会降低对等网络的生命周期：热心节点因得不到资源而离开网络，并带走大量的资源，导致更多的节点离开。如果搭便车现象过于严重，对等网络将趋近客户机/服务器通信模式，其可用性甚至比传统的客户机/服务器通信模式更差。 搭便车行为对对等网络的影响大量搭便车节点可能使热心节点因长期为什么容忍搭便车现象的存在？多数对

47、等网络软件开发者容忍搭便车现象存在。以下三个因素值得考虑： 搭便车现象使对等网络抵御随机选择节点攻击的能力较强。 搭便车现象使得对等网络中节点的重要性不再均衡，管理者可以重点管理数量不多的热心节点。允许一定程度的搭便车现象，有利于吸引自私的节点用户加入到对等网络，提高对等网络的用户数量。为什么容忍搭便车现象的存在？多数对等网络软件开发者容忍搭便车搭便车行为抑制机制抑制搭便车行为的共同指导原则是：根据节点已做出的贡献，确定它能够享受服务的能力。 已提出的抑制机制分为三类：基于节点行为的激励机制基于博弈论的方法采用社会网络或经济模型的控制策略 搭便车行为抑制机制抑制搭便车行为的共同指导原则是：根据

48、节点已基于节点行为的激励机制激励机制的算法流程：不同激励机制之间的差异主要体现在效用函数定义、测量点选择等方面。 基于节点行为的激励机制激励机制的算法流程：效用函数设计效用函数：节点享受服务的能力与节点为系统已做贡献的关系。效用函数可能涉及以下自变量：节点共享文件的数量节点已下载文件的数量节点已上传文件数量节点已下载数据的大小节点已上传数据的大小等。定义计算复杂度小、又能客观反映搭便车控制关键问题的效用函数是激励机制设计的核心。 效用函数设计效用函数：节点享受服务的能力与节点为系统已做贡献测量点位置选择 自我测量：节点把自已每次提供服务或享受服务的行为记录下来，评价自己在网络中的贡献大小。工程

49、上容易实现，开销小，但很难对付恶意欺骗的节点。 相邻节点测量：每个节点对相邻节点进行测量和监督，各个节点的贡献大小由邻接节点评价。节点互相测量能有效防止少数节点的恶意欺骗，但分布式测量的系统开销比较大。 测量点位置选择 自我测量：自我测量的激励机制（1）效用函数一：|UList(Pi , T)|表示在 T 时刻节点 i 所提供的共享文件数量，是一个规范化系数（常量）。 节点能享受的服务质量正比于节点共享的文件数量。自我测量的激励机制（1）效用函数一：自我测量的激励机制（2）效用函数二：节点能享受的服务质量正比于节点共享的文件大小总量。 以上两个效用函数没有反映节点所提供的文件被其它节点下载次数的动态信息。 自我测量的激励机制（2）效用函数二：自我测量的激励机制（3）效用函数三：第一项是节点i在时刻T的奖励值，第二项是惩罚值，上传（下载）越多，奖励（惩罚）越多。 K可以用作在线时间的度量，实现免费赠品。自