1、对等网络Peer-to-Peer Networks（P2P）1.概述o传统的因特网应用采用客户-服务器模式：n所有内容与服务在服务器上，客户向服务器请求内容或服务，客户自己的资源不共享。n这种集中式结构面临服务器负载过重、拒绝服务攻击、网络带宽限制等难以解决的问题。对等计算模型o在对等网络中：n每个节点都有一些资源（处理能力、存储空间、网络带宽、内容等）可以提供给其它节点。n节点之间直接共享资源，不需要服务器参与。n所有节点地位相等（称对等方），具备客户和服务器双重特性。n可缓解集中式结构的问题，充分利用终端的丰富资源。P2P技术的发展oP2P技术的第一个应用是Napster文件共享系统（19
2、99-2000），用户通过该系统交换音乐文件。o自1999年以来，P2P研究得到学术界和商业组织的广泛关注，同时该技术也一直饱受争议。oP2P技术被广泛应用于计算机网络的各个应用领域，如文件共享、流媒体直播与点播、分布式科学计算、语音通信、在线游戏支撑平台等。o目前以文件共享为代表的P2P应用已成为因特网上增长最迅速的应用。P2P技术的应用（1）o提供文件或其它内容共享，如Napster、Gnutella、eDonkey、emule、BitTorrent等。oBitTorrent是最流行的P2P文件共享系统之一：n种子节点（保存完整的文件拷贝）把一个文件分成N个分片（默认为256KB）。n节点
3、X从种子节点随机下载第L个分片，Y 随机下载第M个分片，然后节点X与Y 交换彼此拥有的分片。n减轻了种子节点的负担，提高了节点下载的速度与效率。P2P技术的应用（2）oP2P媒体网：nP2P也非常适合流媒体直播与点播，因此P2P研究热点迅速转移到P2P的流媒体上。n目前P2P非常广泛的一个应用是网上实时电视，提供节目的成本很低，用户却可以得到较好的收视质量。n流行的软件包括Coolstreaming、AnySee、Gridmedia、PPLive和PPStream等。P2P技术的应用（3）o基于P2P方式的协同处理与服务共享平台：nP2P技术将众多终端空闲的CPU资源联合起来，服务于一个共同的
4、计算。n计算任务（包括逻辑与数据等）划分成多个片，分配到参与计算的P2P节点上；计算结果返回给一个或多个服务器；众多结果整合得到最终结果。n最著名的P2P分布式科学计算系统为搜索外星文明的SETIhome科学实验。P2P技术的应用（4）o即时通信交流：nVoIP是一种全新的网络电话通信业务，Skype就是一款典型的P2P VoIP软件。nSkype的出现给传统电信业带来强烈的冲击，截至2011年年底，Skype占有全球长途通话时长的33%。nSkype仍在迅速向各个国家渗透。P2P系统的定义oP2P系统是一个由直接相连的节点所构成的分布式系统，这些节点能够为了共享内容、CPU时间、存储或者带宽
5、等资源而自组织形成一定的网络拓扑结构，能够在适应节点数目的变化和失效的同时维持可以接受的连接能力和性能，并且不需要一个全局服务器或者权威的中介支持。2.P2P网络的拓扑结构oP2P系统的主要概念之一是分散，包括分布式存储、处理、信息共享和控制信息。o根据P2P系统的分散程度，可以将P2P架构分成纯分散式和混合式。o根据结构关系可以将P2P系统细分为四种拓扑形式：n中心化拓扑n全分布式非结构化拓扑n全分布式结构化拓扑n半分布式拓扑2.1 中心化拓扑o最早出现的P2P网络结构，也称集中目录式结构，或非纯粹的P2P结构。o优点：n维护简单，资源发现效率高。o缺点：n单点故障；扩放性差；版权问题。o对
6、小型网络而言在管理和控制方面有一定优势，不适合大型网络应用。Napster文件共享系统o中央索引服务器保存所有用户上传的音乐文件索引和存放位置。o用户需要某个音乐文件时，先查询中央索引服务器，得到存有该文件的节点信息。o用户选择合适的节点建立直接连接。oNapster首先实现了文件查询与文件传输的分离。Napster的拓扑结构2.2 全分布式非结构化拓扑 o也称纯P2P结构，取消了中央服务器，每台机器是真正的对等关系（称为对等机）。o每个用户随机接入网络，并与自己相邻的一组节点通过端-端连接构成一个逻辑覆盖网络。o对等节点之间的内容查询和内容共享均直接通过相邻节点广播接力传递。o每个节点记录搜
7、索轨迹，防止产生搜索环路。oGnutella是应用最广泛的全分布式非结构化拓扑。Gnutella早期的拓扑结构o要下载文件的计算机以文件名或关键字生成一个查询，发送给与它相连的所有计算机。o存在该文件的计算机与查询机器建立连接；否则继续向自己的邻居节点洪泛。o重复该过程，直至找到文件为止。o一般通过TTL值控制查询的深度。全分布式非结构化拓扑的特点o将覆盖网络看成完全随机图，节点之间的链路没有遵循某些预先定义的拓扑来构建。o优点：n解决了网络结构中心化的问题，扩展性和容错性较好；n支持复杂的查询（如多关键词查询、模糊查询等）。o缺点：n查询结果可能不完全，查询速度较慢；n网络规模较大时，消耗网
8、络带宽多，易造成部分低带宽节点因过载而失效，影响网络的可用性；n容易受到垃圾信息甚至是病毒的恶意攻击。2.3 全分布式结构化拓扑 o采用分布式散列表（DHT）组织网络中的节点：nDHT是由广域范围内大量节点共同维护的巨大散列表。n散列表被分割成不连续的块，每个节点被分配一个散列块，并成为这个散列块的管理者。n每个节点按照一定的方式被赋予一个惟一的Node ID。n资源对象的名字或关键词通过一个散列函数映射为128位或160位的散列值，资源对象存储在Node ID与其散列值相等或相近的节点上。n需要查找资源时，采用同样的方法定位到存储该资源的节点。基于DHT的节点组织o每个节点通过散列其IP地址
9、，得到一个128位的节点标识符。o所有节点标识符形成一个环形的node ID空间，其中只有一部分对应了实节点。oKey的散列值为d46a1c的内容存放在节点d467c4上。全分布式结构化拓扑的特点o优点：n采用确定性拓扑结构，DHT可以提供精确发现。o缺点：n维护机制较复杂，尤其是节点频繁加入/退出造成的网络波动会极大地增加维护DHT的代价。n仅支持精确关键词匹配查询，无法支持内容/语义等复杂查询。o这种结构目前还没有大规模成功应用的实例。2.4 半分布式结构o亦称混合结构，吸取了中心化结构和全分布式非结构化的优点。o选择性能（处理、存储、带宽）较高的节点作为超级节点，各个超级节点上存储其它部
10、分节点的信息。o发现算法仅在超级节点之间转发，超级节点再将查询请求转发给适当的叶子节点。o半分布式结构是一种层次式结构：n超级节点之间构成一个高速转发层n超级节点和所负责的普通节点构成若干层次Kazaa的拓扑结构o节点按能力不同区分为普通节点和搜索节点。o搜索节点与其临近的若干普通节点构成一个自治的簇：n簇内采用中心化P2P结构n簇之间通过纯P2P结构将搜索节点连接起来Kazaa的特点o自动将性能好的机器当成超级节点，采用Gnutella的全分布式结构，不需要中央索引服务器。o超级节点存储离它最近的叶子节点的文件信息，其索引功能使得搜索效率大大提高。o文件搜索先在本地簇内进行，必要时再通过搜索
11、节点进行有限的泛洪，消除了纯P2P结构中泛洪算法带来的网络拥塞、搜索迟缓等不利影响。o搜索节点监控着簇内所有普通节点的行为，一些攻击行为能在网络局部得到控制。o超级节点的存在一定程度上提高了网络的负载平衡。Gnutella后期的结构o计算能力较强的节点加入网络时，立即成为一个超级对等节点（SuperPeer），并与其它SuperPeer建立连接，同时设置一个使其保持SuperPeer所需的最小客户节点数目。o当该节点在一个规定的时间内收到不少于该数目的客户连接请求时，它继续成为SuperPeer，否则变为一个普通的客户节点。o如果没有可用的SuperPeer，它又会在一个给定的时间内担当Sup
12、erPeer。Skype网络结构oSkype是P2P技术演进到混合模式后的典型应用：n登录服务器：惟一的集中服务器，存储用户名和密码信息，保证登录名全球惟一，进行用户身份认证等。n用户节点：分为普通节点和超级节点。o普通节点：下载了skype应用的普通终端。o超级节点：具有公网IP地址和足够资源（CPU、存储空间、网络带宽）的普通节点均可为超级节点的候选。Skype网络结构示意图o普通节点必须连接到一个超级节点上，通过超级节点：n向登录服务器认证自己n向好友发送在线信息n查找用户n检测NAT和防火墙类型Skype的通信过程o初始化：询问skype的最新版本o登录：连接到超级节点，进行身份认证等
13、o用户搜索：查找用户o呼叫与终止：与通信方建立与终止连接o媒体传输：传输音频信息登录o客户端启动后连接到超级节点，向登录服务器发送身份认证信息。o登录服务器验证用户名和密码的合法性。o客户端向好友及其它对等节点发送在线信息。o客户端与超级节点交换消息，检测NAT和防火墙类型。o客户端发现拥有公网IP地址的在线Skype节点。连接到超级节点o客户端在主机缓存中维护一个超级节点列表，包含一系列超级节点的。o初次安装客户端软件后，超级节点列表中至少包含7个，这些便是初始的超级节点。o登录时，客户端试图同列表中的每一个表项（超级节点）建立连接。oSkype没有默认的服务端口号，在安装客户端软件时随机选
14、择（或设置）一个端口号监听，同时监听80和443端口。向好友发送在线信息oSkype采用路由缓存机制：n超级节点缓存查找到的用户信息（缓存72小时）。n用户登录后，其状态信息可以通过超级节点通知到好友终端，也可以得到好友的状态。o一旦缓存超时，需通过其它超级节点查找用户。查找用户o具有公网地址的客户端，查找用户的过程：n向超级节点（SN）发送要查找的用户信息；n若不成功，从SN获取四个节点地址，发送用户信息；n若不成功，报告SN，获取八个节点地址，发送用户信息；nn成功或失败返回o位于私网内的受限客户端，查找用户的过程：n客户端将需要查找的用户信息发送给其超级节点；n超级节点完成查找后，返回给
15、私网内的客户端。呼叫建立和释放 主、被叫都在公网内呼叫建立和释放（续）主、被叫至少有一方在私网内Skype的技术优势o较强的NAT和防火墙穿越能力：首先识别NAT和防火墙类型，然后动态选择信令和媒体代理。o快速路由机制：采用全球索引技术，用户路由信息分布式存储于网络节点中。o结合互联网特点的语音编解码算法：引入专门针对互联网特点的语音质量增强软件。o很低的运行成本：很多工作下放给网络节点完成，大大降低了中心服务器的负担，减少了维护和管理成本。2.5 四种拓扑结构的对比中心化全分布式非结构化全分布式结构化半分布式可扩展性差差好中可靠性差好好中可维护性最好最好好中发现算法效率最高中高中复杂查询支持
16、支持不支持支持3 P2P网络的资源发现机制o中心化结构：集中式索引和存储o分布式非结构化：查询请求的洪泛广播o分布式结构化：内容可寻址网络3.1 集中式索引和存储o一个集中的目录服务器保存所有资源的位置和使用信息：n网络中所有文件的元数据（文件名、创建时间等）索引；n登录用户的连接信息表（IP地址、连接速度等）；n每个用户拥有并愿意共享的文件列表。o起始时，客户与目录服务器建立连接，报告其保存的文件列表。o当目录服务器收到来自用户的查询时，查找索引表，返回存有所需文件的用户列表。o用户选择其中一个对等方建立直接连接，下载文件。Napster中的资源发现3.2 查询请求的洪泛广播o洪泛查询的过程
17、：n在覆盖网络上，查询节点将一个资源发现请求发送给与其直接相连的所有节点；n这些节点再向其直接相连的邻居洪泛该请求；nn直到请求被响应或达到最大洪泛次数。o早期的Gnutella使用洪泛机制发现网络中的文件。Gnutella使用的消息oPing：节点使用该消息宣告自己。oPong：对Ping的响应，包含响应主机的IP地址、能接受响应的端口、本机共享文件数量及所占空间大小。oQuery：搜索请求，包含一个搜索字符串和对响应主机的最小速度要求。oQueryHit：对Query的响应，包含响应主机的IP地址、能接受连接的端口、连线速度、查询结果集（包含匹配的文件数量以及每个匹配文件的索引、文件大小及
18、文件名）。Gnutella查询与响应过程o一个节点与自己所知道的每一个节点建立TCP/IP连接。o节点向每一个连接的节点发送Ping消息；收到Ping消息的节点发送一个Pong消息，同时将Ping消息继续向其邻居传播。o节点使用Query查询文件，Query使用相同的洪泛方式传输。oTTL被用来限制Ping和Query的传播范围。每个消息携带全局唯一的标识符，用于检测和丢弃重复的消息。o当收到QueryHit时，表明在响应主机上找到了文件。3.3 内容可寻址网络o分布式P2P系统的核心是一个将文件名映射到文件存放位置的索引系统。o查找服务通过将对等节点组织到一个有结构的覆盖网络中，并将消息通过
19、覆盖网络路由到相关对等节点来实现。o到目前为止，已经有多个研究项目实现了分布式P2P查找服务。Content-Addressable Network（CAN）oCAN类似于一张大哈希表，基本操作包括插入、查找和删除对：n关键字可能是部分或完整的文件名n值可能为获取该文件所需的信息（如大小、位置等）o网络中每个节点保存哈希表的一块（区）。o对一个特定关键字的请求（插入、查找或删除）由中间CAN节点路由到包含该关键字的目标CAN节点。CAN的坐标空间oCAN基于一个虚拟的d维笛卡尔坐标空间来组织数据和实现查找功能：n整个坐标空间被动态分配给系统中的所有节点；n每个节点都拥有独立和不相交的一块区域；
20、n如果两个区域在（d-1）维上跨度相同，而在另一个维度上相邻，就称这两个区域相邻；n若两个节点拥有的区域相邻，就称这两个节点在坐标空间中相邻。一个二维的CAN坐标空间示例名字到位置的映射o存储对的方法：n使用一个均匀哈希函数将key映射成坐标空间中的一个点P，被保存在P所在区域对应的CAN节点中。o查询关键字Key：n使用相同的哈希函数得到点P，从P所在区域对应的CAN节点中得到Value。o如果P不在查询节点所拥有的区域中，查询请求通过CAN网络路由到包含P的CAN节点。CAN路由oCAN中的节点自动形成一个表示虚拟坐标空间的覆盖网络：n每个节点学习并维护坐标空间中相邻节点的IP地址和虚拟坐
21、标区域，这组邻居节点就形成了坐标路由表。o每条CAN消息都包含目的点P的坐标。o节点利用坐标路由表，使用贪婪转发机制将消息转发给距离P最近的邻居节点。一个CAN查找的例子节点加入CANo找到一个已有节点：n在DNS中查找CAN的域名，得到一个引导节点的IP地址。n引导节点随机选择当前系统中几个节点的IP地址，提供给新节点。o找到一个要分裂的区域：n在坐标空间中随机选择一个点P，向P发送一个加入请求。n该消息通过已有节点送入CAN，路由到P所在区域的CAN节点。n该节点将它的区域分裂成两半，将一半分配给新节点。o加入路由：n新节点向区域的原节点了解其邻居节点的IP地址，形成自己的邻居集合；原节点
22、也要更新自己的邻居集合。n新老节点将自己当前分配的区域告知其邻居。新节点加入的例子 节点7加入前 节点7加入后节点离开CANo正常的做法：n节点显式地将其区域和相关的数据库转交给一个邻居节点。n如果某个邻居节点的区域可以和该节点的区域合并成一个合法的区域，转交完成。否则，n该区域转交给当前区域最小的节点，这个节点要临时接管两个区域。o节点通过周期性更新消息，告知邻居自己的区域坐标和其邻居节点的区域坐标。o当节点失效时，其邻居之一要立即接管失效节点的区域，但失效节点中保存的丢失。CAN的缺点o经过哈希之后，节点的位置信息被破坏了，来自同一个子网的站点很可能节点号相距很远，这不利于查询性能的优化。
23、o基于哈希表的系统不能利用应用本身的信息，许多应用（如文件系统）的数据本身是按照层次结构组织的，而使用哈希函数后这些层次信息就丢失了。4 P4P技术oP2P带宽吞噬问题：nP2P流量已经占到整个互联网流量的50%左右，且仍在持续增长。nP2P流量大量占用宝贵的骨干网带宽资源，尤其是互联互通出口及国际出口的带宽，极大地增加了投资成本压力，并造成运营成本上升。n用户正常的上网业务的服务质量难以得到有效保障。带宽吞噬问题的根源P2P的交换机制oP2P过于强调对等，它对资源在网络中的位置不作区分，一律平等地返回给用户，而用户随机选择一个节点交换。o节点之间的交换完全是无序的，无序的交换导致无谓的跨地区
24、甚至是跨国的“流量旅行”，耗费了宝贵的国内和国际带宽资源。依靠P2P应用的解决方案o基于局部性原则选择节点：n如优先选择相同子网、相同ISP内的节点交换文件片段。n若不考虑链路流量、不同链路的通信开销，可能会给骨干网带来拥塞或造成不必要的费用开销。o基于逆向流量工程的流量走向调整：n应用发送探测消息收集和推测底层网络状态，确定流量走向。n依赖网络测量技术，而测量会消耗带宽，且不能完全反映网络的真实状态。n一些新技术（如MPLS）对探测消息不响应。n无法推测ISP运营商的策略信息。基于ISP的流量控制o目前因特网上的流量控制主要是ISP的责任：n应用给出网络流的目的地址及流量需求模式，ISP根据
25、当前网络状态确定最有效的路由。oP2P模式改变了传统的流量控制问题：n应用需要的数据可以从很多节点、以很多种方式得到，每一种方式都会产生一种不同的流量需求模式并导致不同的网络使用效率。nP2P的动态流量模式能够自动适应网络变化，但也使得ISP估计网络状态并确定最佳路由的努力无效。基于ISP和P2P应用合作的P4P技术o网络运营商和P2P应用应合作解决流量吞噬问题：n网络运营商将底层网络状态及策略信息提供给P2P应用nP2P应用根据这些信息智能地选择数据交换对象oP4P（Proactive network Provider Participation for p2p）：n一个旨在同时优化ISP和
26、P2P系统性能的网络架构n已集成到一些具有代表性的P2P软件中，在商业测试中表现出色。4.1 P4P架构oP4P是一个允许网络运营者向新型应用显式提供网络信息、策略及能力的通用框架，除P2P之外可支持各种高带宽应用。oP4P由控制面、管理面和数据面组成：n数据面（可选）：区分应用流和设定应用流的优先级n控制面：通过iTracker向应用提供网络信息n管理面：监视控制面的行为 P2P控制面中的实体oiTracker：代表一个网络运营商oappTracker：代表一个P2P应用oPeer：代表P2P客户o对等客户从appTracker或iTracker（若无appTracker）获得必要的信息，并
27、帮助分发信息。iTracker提供的接口o策略接口：用于向对等客户或appTracker提供网络使用策略和指导意见。oP4P距离接口：用于查询对等客户之间的开销和网络距离。o能力接口：用于对等客户或内容接供商向运营商请求能力（资源）。appTracker使用接口的例子4.2 P4P距离（p-distance）oP4P架构中最核心的接口是P4P距离：n运营商通过该接口告诉应用当前网络中域内和域间的网络开销。n应用使用P4P距离来优化连接，提高网络通信效率。oP4P接口有两个视图：niTracker看到的内部视图n应用看到的外部视图内部视图o内部视图是一个网络拓扑G=（V,E），其中V是节点集合，
28、E是链路集合。oV中的节点称为PID（opaque ID），有以下几种类型：n汇聚节点：代表一组客户（如一个网点或网络状态相同的一组节点），对外部是可见的。n核心路由器：对应用和客户不可见。n外部域节点：对应用和客户不可见。oiTracker在内部视图中连接两个PID（如果这样连接是有意义的），并给每条PID层次的链路指定一个p-距离。外部视图oiTracker提供的外部视图是一个全连接的网状网络：n给定一对外部可见的PID i和j，iTracker给出从PID-i到PID-j的p-距离（pij）。npij是iTracker根据网络内部距离和路由计算出来的，iTracker可以给这个距离一个干
29、扰来增强隐秘性。p4p距离的指定oISP可以有很多种方法来指定p-距离，比如：n从OSPF权值和BGP偏好来得到p-距离n给具有较高成本或接近拥塞的链路指定较大的p-距离n按照某种优化目标计算p-距离P-距离信息的分发oISP可从以下几个方面控制p-距离信息的分发：nPID的聚合粒度：控制粒度 vs 扩放性和用户隐私。n网络信息的粒度和语义：简单、健壮 vs 控制粒度和信息语义。n信息的接收者：安全、隐私保护 vs 信息的中立性。o使用p-距离接口的权衡涉及扩放性、语义和隐私。o接口本身是简单、灵活和标准化的（易于互操作），复杂性体现在如何使用，而如何使用是由ISP决定的。使用P-距离接口选择
30、对等客户（1）o按p-距离选择对等客户：nPID-i客户选择PID-j客户的概率为pij的递减函数。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选择P
31、2P对等客户的问题描述为以下优化问题：有上/下载流量匹配要求的应用（续）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可以接受的流量模式
32、集合。o对于其中一个tkTk，若会话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架构的P2
33、P流媒体系统oP2P流媒体是结合流媒体技术与P2P技术的流媒体解决方案。o基于组播树的P2P流媒体技术：n构建以视频源为根的数据分发树；当节点收到数据包后，将数据包的拷贝转发给它的每一个子节点。（典型的数据推送方法）n优点：拓扑结构简单。n缺点：拓扑维护开销大，可靠性差，不利于在大规模的实际环境中使用。基于P4P架构的P2P流媒体系统（续）o基于数据驱动的P2P流媒体技术：n每一个频道看作是一个子覆盖网络，频道的媒体数据分割成chunk，节点间采用gossip协议分发数据。n优点：不需要维护分发结构，系统健壮性好。n缺点：随机推送导致大量冗余；没有明确的拓扑结构支持，最小化启动和传输时延成为主
34、要问题。n改进：通过数据拉取技术解决传输冗余问题。节点维护一组伙伴，周期性地同伙伴交换数据可用性信息和数据。一个融合P4P架构的P2P流媒体系统如何发现iTracker地址oappTracker通过DNS解析P4P服务的域名，获取iTracker的IP地址。o在appTracker上直接配置iTracker地址。4.4 基于P4P技术的Gnutella路由算法oGnutella 0.6引入了超级节点的概念：n超级节点：叶子节点的代理，只在认为叶子节点能够响应查询请求时才向叶子节点转发查询请求；n叶子节点：从不向超级节点转发查询请求。Gnutella 0.6的工作原理o节点加入：n节点连接到网络
35、后，使用Ping消息找到最近的超级节点；n通过该超级节点了解并连接更多的超级节点；n选择一个超级节点，成为它的叶子节点。o查询转发：n节点向自己的超级节点发送Query消息；n若超级节点有符合查询要求的文件，发送QueryHit消息；n超级节点递减Query的TTL值，若不为0，向相邻的超级节点及可能包含该文件的叶子节点转发Query消息。使用P4P技术优化超级节点的选择o在Gnutella网络中，满足以下条件的对等节点成为超级节点：n主机没有处在防火墙内且运行合适的操作系统n具有足够的带宽、机器性能和正常运行时间n连接了不少于一定数量的客户节点o可以利用P4P技术优化超级节点的选择：n基于P
36、4P技术获得的信息，选择那些连通度较高的节点作为超级节点。使用P4P技术优化节点加入o在Gnutella协议中：n节点从获得的超级节点中随机选择一个加入。o利用P4P技术优化节点加入：n基于P4P技术获得的网络信息，优先选择位于同一个ISP、（在同一个ISP时）同一个城市的超级节点加入。n可减小超级节点和叶子节点的通信延迟，降低骨干网络间的通信流量。使用P4P技术优化查询请求的转发o超级节点的路由表中维护了到其它超级节点的路由。o基于P4P技术获得的网络信息，超级节点可以计算到其它超级节点的通信代价，记录在路由表中。o在向其它超级节点转发查询请求时，选择通信代价较小的超级节点转发查询请求。5
37、搭便车现象及抑制机制oP2P通信模式倡导的理念是协作和共享，但P2P网络的理性用户更多地表现出自主性和自私性，只想索取资源而不愿贡献资源。o节点只享受服务而不为系统做贡献的行为称为搭便车（free riding），大量搭便车现象将导致P2P网络效用大幅降低。oP2P网络中还存在大量不可靠的服务以及欺诈行为。o必须考虑P2P网络中节点的自主行为，激励节点之间有效合作并合理使用网络资源。搭便车行为的研究进展o第一阶段：试图测量不同对等网络中的搭便车现象，分析其数学特征。o第二阶段：一些搭便车行为的抑制机制被提出，其中少数已应用到真实系统中。o第三阶段：意识到还没有哪一种方法可以彻底解决对等网络中的
38、搭便车行为，应更深入地研究抑制机制，并在真实系统中验证有效性。搭便车现象的测量结果o极少数热心节点维持了大量的连接。o测量结果表明，搭便车现象在对等网络中广泛存在。拱便车行为的数学建模o有文献采用排队论对对等网络的服务能力进行了数学建模，研究表明：n提供服务的节点数越多、单一文件的拷贝数量（网络中包含该文件的节点数）越多，则对等网络的服务能力越强。n不同结构的P2P应用系统，容忍搭便车行为的能力有所不同。搭便车节点比例与对等网络吞吐率的关系oCIA：具有集中索引服务器的对等网络oDIFA：分布式洪泛机制的对等网络oDIHA：分布式哈希表索引的对等网络BT的激励机制oBT采用激励机制来抑制搭便车
39、行为：节点以较大优先级选择向其提供了较大下载带宽的节点提供数据上传服务。o在该机制下，单个搭便车节点能获取的最大带宽如下，是节点上传带宽，nu是单个节点最大并发下载连接数：o直接提高nu即可降低搭便车者享受的服务，但节点需支持较多的并发TCP连接数，易出现超时重传或拥塞现象，网络有效吞吐率下降。在BT中，nu设为4。搭便车行为对对等网络的影响o大量搭便车节点可能使热心节点因长期过载而宕机，导致整个对等网络的连通性发生巨大变化。o大量搭便车行为会降低对等网络的生命周期：热心节点因得不到资源而离开网络，并带走大量的资源，导致更多的节点离开。o如果搭便车现象过于严重，对等网络将趋近客户机/服务器通信
40、模式，其可用性甚至比传统的客户机/服务器通信模式更差。为什么容忍搭便车现象的存在？o多数对等网络软件开发者容忍搭便车现象存在。以下三个因素值得考虑：n搭便车现象使对等网络抵御随机选择节点攻击的能力较强。n搭便车现象使得对等网络中节点的重要性不再均衡，管理者可以重点管理数量不多的热心节点。n允许一定程度的搭便车现象，有利于吸引自私的节点用户加入到对等网络，提高对等网络的用户数量。搭便车行为抑制机制o抑制搭便车行为的共同指导原则是：根据节点已做出的贡献，确定它能够享受服务的能力。o已提出的抑制机制分为三类：n基于节点行为的激励机制n基于博弈论的方法n采用社会网络或经济模型的控制策略 基于节点行为的
41、激励机制o激励机制的算法流程：o不同激励机制之间的差异主要体现在效用函数定义、测量点选择等方面。效用函数设计o效用函数：节点享受服务的能力与节点为系统已做贡献的关系。o效用函数可能涉及以下自变量：n节点共享文件的数量n节点已下载文件的数量n节点已上传文件数量n节点已下载数据的大小n节点已上传数据的大小等。o定义计算复杂度小、又能客观反映搭便车控制关键问题的效用函数是激励机制设计的核心。测量点位置选择 o自我测量：n节点把自已每次提供服务或享受服务的行为记录下来，评价自己在网络中的贡献大小。n工程上容易实现，开销小，但很难对付恶意欺骗的节点。o相邻节点测量：n每个节点对相邻节点进行测量和监督，各
42、个节点的贡献大小由邻接节点评价。n节点互相测量能有效防止少数节点的恶意欺骗，但分布式测量的系统开销比较大。自我测量的激励机制（1）o效用函数一：n|UList(Pi,T)|表示在 T 时刻节点 i 所提供的共享文件数量，是一个规范化系数（常量）。n节点能享受的服务质量正比于节点共享的文件数量。自我测量的激励机制（2）o效用函数二：n节点能享受的服务质量正比于节点共享的文件大小总量。o以上两个效用函数没有反映节点所提供的文件被其它节点下载次数的动态信息。自我测量的激励机制（3）o效用函数三：n第一项是节点i在时刻T的奖励值，第二项是惩罚值，上传（下载）越多，奖励（惩罚）越多。nK可以用作在线时间
43、的度量，实现免费赠品。自我测量的激励机制（4）o考虑节点异构性的效用函数值比较：nCi(t)是节点所做绝对贡献值，di是节点最大可支持物理带宽。邻居节点测量o测量方法：n节点观察其邻居节点发送、转发信令包和数据包的行为（节点可以仅对通过自己转发的报文做日志记录）；n根据日志记录定期计算邻居节点的效用函数，发现搭便车者。三类搭便车者o发出响应报文次数极低的节点，表明该节点一般没有提供共享信息资源，或仅共享了不被其它用户访问的资源。o从邻接节点获得的资源数量远大于它为其它节点提供服务的报文数量。o转发信令报文非常少的节点，该节点不为整个对等网络承担路由维护义务。三个层次的惩罚方案o第一个层次：n快
44、速降低搭便车者发出的查询请求消息的TTL值，降低报文在网络中的传播范围。o第二个层次：n忽略自私节点的查询请求。o第三个层次：n直接取消与搭便车者的连接，将其清除出对等网络。基于激励的抑制机制面临的困难o自我测量的激励机制：n效用函数严格程度的选择，在如何抑制搭便车行为与鼓励用户加入对等网络之间存在两难。n位于防火墙或NAT之后的节点会被认定搭便车者。o分布式测量与监视机制：n节点之间互相监视开销大。n对连接数很高的节点，监视邻接节点会增加节点负担。博弈论方法o博弈论是分析社会群体和经济活动中，个体和群体选择最优行为策略的有效数学工具。o利用博弈论方法建模，一个节点的行为选择与同时在线的其它节
45、点的行为选择紧密相关。o节点在对等网络中的行为可以建模为长期博弈过程，节点可在包括热心为系统做贡献、贪婪下载、贡献收益平衡等多种行为策略集合中找到有利于最大化自身收益的策略选择。博弈论方法的困难o采用博弈论作为数学工具，定量化分析程度高，但在实际系统开发过程中面临以下问题：n一般需要整个对等网络系统的全局知识，难以满足。n一些假设太严格，与真实环境差异很大，结果未必具有指导意义。社会网络和经济模型o对等网络中的节点存在的自私行为，是节点用户个人心理因素的一种延伸。o一些来自经济学、公共策略管理领域的学者讨论利用社会网络模型、经济模型、价格机制等方法来抑制搭便车现象。o已提出的一些方案包括利用市
46、场管理技术促进节点之间的协作、利用市场机制模型抑制搭便车现象、采用社会经济生活中审计、竞价等机制抑制搭便车行为等。社会网络方法面临的困难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 对等网络中的搭便车行为分析与抑制机制综述。
