Peer-to-Peer Networks （P2P）

Presentation on theme: "Peer-to-Peer Networks （P2P）"— Presentation transcript:

1 Peer-to-Peer Networks （P2P）
对等网络 Peer-to-Peer Networks （P2P）

2 1. 概述 传统的因特网应用采用客户-服务器模式： 所有内容与服务在服务器上，客户向服务器请求内容或服务，客户自己的资源不共享。
这种集中式结构面临服务器负载过重、拒绝服务攻击、网络带宽限制等难以解决的问题。

3 对等计算模型 在对等网络中： 每个节点都有一些资源（处理能力、存储空间、网络带宽、内容等）可以提供给其它节点。
节点之间直接共享资源，不需要服务器参与。 所有节点地位相等（称对等方），具备客户和服务器双重特性。 可缓解集中式结构的问题，充分利用终端的丰富资源。

4 P2P技术的发展 P2P技术的第一个应用是Napster文件共享系统（1999-2000），用户通过该系统交换音乐文件。

5 P2P技术的应用（1） 提供文件或其它内容共享，如Napster、Gnutella、eDonkey、emule、BitTorrent等。
BitTorrent是最流行的P2P文件共享系统之一： 种子节点（保存完整的文件拷贝）把一个文件分成N个分片（默认为256KB）。 节点X从种子节点随机下载第L个分片，Y 随机下载第M个分片，然后节点X与Y 交换彼此拥有的分片。 减轻了种子节点的负担，提高了节点下载的速度与效率。 “BT”是BitTorrent的简称，BitTorrent是由Bram Cohen提出的第二代混合式P2P网络，由于其简单易用性、文件分片下载的高效性和“Tit for Tat”（TFT，以同样的方式回报）的激励机制而成为目前最为流行的P2P应用之一。 BT网络主要由Torrent服务器、Tracker服务器、种子节点和下载节点组成（如图所示）。Torrent服务器负责Torrent文件的存储和检索，Tracker服务器负责维护网络中的节点，种子节点负责提供一份文件的完整内容。

6 P2P技术的应用（2） P2P媒体网： P2P也非常适合流媒体直播与点播，因此P2P研究热点迅速转移到P2P的流媒体上。
流行的软件包括Coolstreaming、AnySee、Gridmedia、PPLive和PPStream等。

7 P2P技术的应用（3） 基于P2P方式的协同处理与服务共享平台： P2P技术将众多终端空闲的CPU资源联合起来，服务于一个共同的计算。

8 P2P技术的应用（4） 即时通信交流： VoIP是一种全新的网络电话通信业务，Skype就是一款典型的P2P VoIP软件。
Skype的出现给传统电信业带来强烈的冲击，截至2011年年底，Skype占有全球长途通话时长的33%。 Skype仍在迅速向各个国家渗透。

9 P2P系统的定义 P2P系统是一个由直接相连的节点所构成的分布式系统，这些节点能够为了共享内容、CPU时间、存储或者带宽等资源而自组织形成一定的网络拓扑结构，能够在适应节点数目的变化和失效的同时维持可以接受的连接能力和性能，并且不需要一个全局服务器或者权威的中介支持。

10 2. P2P网络的拓扑结构 P2P系统的主要概念之一是分散，包括分布式存储、处理、信息共享和控制信息。
中心化拓扑 全分布式非结构化拓扑 全分布式结构化拓扑 半分布式拓扑

11 2.1 中心化拓扑 最早出现的P2P网络结构，也称集中目录式结构，或非纯粹的P2P结构。 优点： 缺点：
维护简单，资源发现效率高。 缺点： 单点故障；扩放性差；版权问题。 对小型网络而言在管理和控制方面有一定优势，不适合大型网络应用。 Napster使用一个中央索引服务器保存所有Napster用户上传的音乐文件索引和存放位置。当用户需要某个音乐文件时，先查询Napster中央索引服务器，服务器返回存有该文件的节点信息。用户再根据网络流量和延迟等信息选择合适的节点建立直接连接，而不必再经过中央索引服务器。 Napster首先实现了文件查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了文件传输延时。 中心化拓扑结构的最大优点是维护简单，资源发现效率高，但存在以下问题： 1）单点故障。中央索引服务器的瘫痪容易导致整个网络崩溃，因此可靠性和安全性较低。 2）扩放性差。随着网络规模的扩大，中央索引服务器的维护成本急剧增加。 3）版权问题。中央索引服务器的存在常引起版权问题上的纠纷，服务提供商容易被追究法律责任。 中心化拓扑结构对小型网络而言在管理和控制方面有一定优势，但不适合大型网络应用。

12 Napster文件共享系统 中央索引服务器保存所有用户上传的音乐文件索引和存放位置。
用户需要某个音乐文件时，先查询中央索引服务器，得到存有该文件的节点信息。 用户选择合适的节点建立直接连接。 Napster首先实现了文件查询与文件传输的分离。 Napster的拓扑结构

13 2.2 全分布式非结构化拓扑 也称纯P2P结构，取消了中央服务器，每台机器是真正的对等关系（称为对等机）。
每个用户随机接入网络，并与自己相邻的一组节点通过端-端连接构成一个逻辑覆盖网络。 对等节点之间的内容查询和内容共享均直接通过相邻节点广播接力传递。 每个节点记录搜索轨迹，防止产生搜索环路。 Gnutella是应用最广泛的全分布式非结构化拓扑。

14 Gnutella早期的拓扑结构 要下载文件的计算机以文件名或关键字生成一个查询，发送给与它相连的所有计算机。
存在该文件的计算机与查询机器建立连接；否则继续向自己的邻居节点洪泛。 重复该过程，直至找到文件为止。 一般通过TTL值控制查询的深度。

15 全分布式非结构化拓扑的特点 将覆盖网络看成完全随机图，节点之间的链路没有遵循某些预先定义的拓扑来构建。 优点： 缺点：
解决了网络结构中心化的问题，扩展性和容错性较好； 支持复杂的查询（如多关键词查询、模糊查询等）。 缺点： 查询结果可能不完全，查询速度较慢； 网络规模较大时，消耗网络带宽多，易造成部分低带宽节点因过载而失效，影响网络的可用性； 容易受到垃圾信息甚至是病毒的恶意攻击。

16 2.3 全分布式结构化拓扑 采用分布式散列表（DHT）组织网络中的节点： DHT是由广域范围内大量节点共同维护的巨大散列表。
散列表被分割成不连续的块，每个节点被分配一个散列块，并成为这个散列块的管理者。 每个节点按照一定的方式被赋予一个惟一的Node ID。 资源对象的名字或关键词通过一个散列函数映射为128位或160位的散列值，资源对象存储在Node ID与其散列值相等或相近的节点上。 需要查找资源时，采用同样的方法定位到存储该资源的节点。

17 基于DHT的节点组织 每个节点通过散列其IP地址，得到一个128位的节点标识符。
所有节点标识符形成一个环形的node ID空间，其中只有一部分对应了实节点。 Key的散列值为d46a1c的内容存放在节点d467c4上。

18 全分布式结构化拓扑的特点 优点： 缺点： 这种结构目前还没有大规模成功应用的实例。 采用确定性拓扑结构，DHT可以提供精确发现。
仅支持精确关键词匹配查询，无法支持内容/语义等复杂查询。 这种结构目前还没有大规模成功应用的实例。

19 2.4 半分布式结构 亦称混合结构，吸取了中心化结构和全分布式非结构化的优点。
选择性能（处理、存储、带宽）较高的节点作为超级节点，各个超级节点上存储其它部分节点的信息。 发现算法仅在超级节点之间转发，超级节点再将查询请求转发给适当的叶子节点。 半分布式结构是一种层次式结构： 超级节点之间构成一个高速转发层 超级节点和所负责的普通节点构成若干层次

20 Kazaa的拓扑结构 节点按能力不同区分为普通节点和搜索节点。 搜索节点与其临近的若干普通节点构成一个自治的簇： 簇内采用中心化P2P结构

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

22 Gnutella后期的结构 计算能力较强的节点加入网络时，立即成为一个超级对等节点（SuperPeer），并与其它SuperPeer建立连接，同时设置一个使其保持SuperPeer所需的最小客户节点数目。 当该节点在一个规定的时间内收到不少于该数目的客户连接请求时，它继续成为SuperPeer，否则变为一个普通的客户节点。 如果没有可用的SuperPeer，它又会在一个给定的时间内担当SuperPeer。

23 Skype网络结构 Skype是P2P技术演进到混合模式后的典型应用： 普通节点：下载了skype应用的普通终端。
登录服务器：惟一的集中服务器，存储用户名和密码信息，保证登录名全球惟一，进行用户身份认证等。 用户节点：分为普通节点和超级节点。 普通节点：下载了skype应用的普通终端。 超级节点：具有公网IP地址和足够资源（CPU、存储空间、网络带宽）的普通节点均可为超级节点的候选。

24 Skype网络结构示意图 普通节点必须连接到一个超级节点上，通过超级节点： 向登录服务器认证自己 向好友发送在线信息 查找用户
检测NAT和防火墙类型

25 Skype的通信过程 初始化：询问skype的最新版本 登录：连接到超级节点，进行身份认证等 用户搜索：查找用户
呼叫与终止：与通信方建立与终止连接 媒体传输：传输音频信息

26 登录 客户端启动后连接到超级节点，向登录服务器发送身份认证信息。 登录服务器验证用户名和密码的合法性。
客户端向好友及其它对等节点发送在线信息。 客户端与超级节点交换消息，检测NAT和防火墙类型。 客户端发现拥有公网IP地址的在线Skype节点。

27 连接到超级节点 客户端在主机缓存中维护一个超级节点列表，包含一系列超级节点的<IP地址，端口>。
登录时，客户端试图同列表中的每一个表项（超级节点）建立连接。 Skype没有默认的服务端口号，在安装客户端软件时随机选择（或设置）一个端口号监听，同时监听80和443端口。

28 向好友发送在线信息 Skype采用路由缓存机制： 一旦缓存超时，需通过其它超级节点查找用户。 超级节点缓存查找到的用户信息（缓存72小时）。
用户登录后，其状态信息可以通过超级节点通知到好友终端，也可以得到好友的状态。 一旦缓存超时，需通过其它超级节点查找用户。

29 查找用户 具有公网地址的客户端，查找用户的过程： 位于私网内的受限客户端，查找用户的过程： 向超级节点（SN）发送要查找的用户信息；
…… 成功或失败返回 位于私网内的受限客户端，查找用户的过程： 客户端将需要查找的用户信息发送给其超级节点； 超级节点完成查找后，返回给私网内的客户端。

30 呼叫建立和释放 Skype的呼叫信令都采用TCP封装，而媒体流则使用UDP封装。当有任何一方位于限制UDP包的防火墙内时，媒体流就会采用TCP封装。 主、被叫都在公网内

31 呼叫建立和释放（续） 主、被叫至少有一方在私网内
当Skype用户至少有一方位于私网内时，所有的信令和媒体消息都经过一个或多个中间节点转发。此时无需担心用户通话的媒体流经过中间节点转发时被窃听，因为Skype对消息进行了端到端加密。 主、被叫至少有一方在私网内

32 Skype的技术优势 较强的NAT和防火墙穿越能力：首先识别NAT和防火墙类型，然后动态选择信令和媒体代理。
快速路由机制：采用全球索引技术，用户路由信息分布式存储于网络节点中。 结合互联网特点的语音编解码算法：引入专门针对互联网特点的语音质量增强软件。 很低的运行成本：很多工作下放给网络节点完成，大大降低了中心服务器的负担，减少了维护和管理成本。 Skype之所以引起不小的轰动是因为它的互联网特性，即免费、开放和较好的业务质量。事实上，Skype最大的意义在于，它开创了将P2P技术引入到话音通信的先河。网络中所有节点都动态参与到路由、信息处理和带宽增强等工作中，而不是单纯依靠服务器来完成这些工作，因此其管理成本大大降低，同时又保证了语音质量。 从技术上看，Skype具有以下技术优势。其中第1条保证了通信无障碍，无论终端处于何种网络条件，都不会影响用户使用Skype提供的业务。第2条和第3条保证了Skype较好的业务服务质量。第4条使得Skype可以轻松面对挑战。第5条则给了Skype更强大的生命力，使其更加灵活，具有更好的可扩展性。 半分布式结构的优点是可扩展性好，容易管理；但对超级节点依赖性大，易于受到攻击，容错性也受到影响。

33 2.5 四种拓扑结构的对比 差 好 中 最好 最高 高 支持 不支持 中心化 全分布式非结构化 全分布式结构化 半分布式 可扩展性 可靠性
可维护性 最好 发现算法效率 最高 高 复杂查询 支持 不支持 在实际应用中,每种拓扑结构的P2P网络都有其优缺点。下表从可扩展性、可靠性、可维护性、发现算法的效率、复杂查询等方面比较了这四种拓扑结构的综合性能。

34 3 P2P网络的资源发现机制 中心化结构：集中式索引和存储 分布式非结构化：查询请求的洪泛广播 分布式结构化：内容可寻址网络

35 3.1 集中式索引和存储 一个集中的目录服务器保存所有资源的位置和使用信息： 起始时，客户与目录服务器建立连接，报告其保存的文件列表。
网络中所有文件的元数据（文件名、创建时间等）索引； 登录用户的连接信息表（IP地址、连接速度等）； 每个用户拥有并愿意共享的文件列表。 起始时，客户与目录服务器建立连接，报告其保存的文件列表。 当目录服务器收到来自用户的查询时，查找索引表，返回存有所需文件的用户列表。 用户选择其中一个对等方建立直接连接，下载文件。 该机制应用于中心化拓扑结构中。

36 Napster中的资源发现

37 3.2 查询请求的洪泛广播 洪泛查询的过程： 早期的Gnutella使用洪泛机制发现网络中的文件。
在覆盖网络上，查询节点将一个资源发现请求发送给与其直接相连的所有节点； 这些节点再向其直接相连的邻居洪泛该请求； …… 直到请求被响应或达到最大洪泛次数。 早期的Gnutella使用洪泛机制发现网络中的文件。 该机制应用于分布式非结构化拓扑中。查询节点在覆盖网络上发送一个资源发现请求，该请求被洪泛到直接相连的所有节点，这些节点再向其直接相连的邻居洪泛该请求，直到该请求被响应或达到最大洪泛次数。 最早的Gnutella使用洪泛机制发现网络中的文件。

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

39 Gnutella查询与响应过程 一个节点与自己所知道的每一个节点建立TCP/IP连接。
节点向每一个连接的节点发送Ping消息；收到Ping消息的节点发送一个Pong消息，同时将Ping消息继续向其邻居传播。 节点使用Query查询文件，Query使用相同的洪泛方式传输。 TTL被用来限制Ping和Query的传播范围。每个消息携带全局唯一的标识符，用于检测和丢弃重复的消息。 当收到QueryHit时，表明在响应主机上找到了文件。

40 3.3 内容可寻址网络 分布式P2P系统的核心是一个将文件名映射到文件存放位置的索引系统。
查找服务通过将对等节点组织到一个有结构的覆盖网络中，并将消息通过覆盖网络路由到相关对等节点来实现。 到目前为止，已经有多个研究项目实现了分布式P2P查找服务。

41 Content-Addressable Network（CAN）
关键字可能是部分或完整的文件名 值可能为获取该文件所需的信息（如大小、位置等） 网络中每个节点保存哈希表的一块（区）。 对一个特定关键字的请求（插入、查找或删除）由中间CAN节点路由到包含该关键字的目标CAN节点。 在P2P共享文件系统中，关键字可能是部分或完整的文件名，值可能为获取该文件所需的信息（如大小、位置等）。

42 CAN的坐标空间 CAN基于一个虚拟的d维笛卡尔坐标空间来组织数据和实现查找功能： 整个坐标空间被动态分配给系统中的所有节点；
每个节点都拥有独立和不相交的一块区域； 如果两个区域在（d-1）维上跨度相同，而在另一个维度上相邻，就称这两个区域相邻； 若两个节点拥有的区域相邻，就称这两个节点在坐标空间中相邻。

43 一个二维的CAN坐标空间示例 图中给出了一个2维的[0,1]×[0,1]笛卡尔空间在5个CAN节点之间划分的情形。 节点D和E拥有的区域相邻，而节点D和A拥有的区域不相邻，因此D和E相邻，而D和A不相邻。

44 名字到位置的映射 存储<key，value>对的方法：
使用一个均匀哈希函数将key映射成坐标空间中的一个点P，<Key, value>被保存在P所在区域对应的CAN节点中。 查询关键字Key： 使用相同的哈希函数得到点P，从P所在区域对应的CAN节点中得到Value。 如果P不在查询节点所拥有的区域中，查询请求通过CAN网络路由到包含P的CAN节点。

45 CAN路由 CAN中的节点自动形成一个表示虚拟坐标空间的覆盖网络： 每条CAN消息都包含目的点P的坐标。
每个节点学习并维护坐标空间中相邻节点的IP地址和虚拟坐标区域，这组邻居节点就形成了坐标路由表。 每条CAN消息都包含目的点P的坐标。 节点利用坐标路由表，使用贪婪转发机制将消息转发给距离P最近的邻居节点。

46 一个CAN查找的例子

47 节点加入CAN 找到一个已有节点： 找到一个要分裂的区域： 加入路由： 在DNS中查找CAN的域名，得到一个引导节点的IP地址。
在坐标空间中随机选择一个点P，向P发送一个加入请求。 该消息通过已有节点送入CAN，路由到P所在区域的CAN节点。 该节点将它的区域分裂成两半，将一半分配给新节点。 加入路由： 新节点向区域的原节点了解其邻居节点的IP地址，形成自己的邻居集合；原节点也要更新自己的邻居集合。 新老节点将自己当前分配的区域告知其邻居。

48 新节点加入的例子 图示为新节点7加入到节点1所在区域的例子。加入前，节点1的坐标邻居集合为{2,3,4,5}。加入后，节点1的坐标邻居集合为{2,3,4,7}，节点7的坐标邻居集合为{1,2,4,5}。 节点7加入前 节点7加入后

49 节点离开CAN 正常的做法： 节点通过周期性更新消息，告知邻居自己的区域坐标和其邻居节点的区域坐标。
节点显式地将其区域和相关的<key，value>数据库转交给一个邻居节点。 如果某个邻居节点的区域可以和该节点的区域合并成一个合法的区域，转交完成。否则， 该区域转交给当前区域最小的节点，这个节点要临时接管两个区域。 节点通过周期性更新消息，告知邻居自己的区域坐标和其邻居节点的区域坐标。 当节点失效时，其邻居之一要立即接管失效节点的区域，但失效节点中保存的<关键字，值>丢失。 当节点离开CAN时，要确保该节点占有的区域被剩下的节点接管。

50 CAN的缺点 经过哈希之后，节点的位置信息被破坏了，来自同一个子网的站点很可能节点号相距很远，这不利于查询性能的优化。
基于哈希表的系统不能利用应用本身的信息，许多应用（如文件系统）的数据本身是按照层次结构组织的，而使用哈希函数后这些层次信息就丢失了。

51 4 P4P技术 P2P带宽吞噬问题： P2P流量已经占到整个互联网流量的50%左右，且仍在持续增长。
用户正常的上网业务的服务质量难以得到有效保障。

52 带宽吞噬问题的根源—P2P的交换机制 P2P过于强调对等，它对资源在网络中的位置不作区分，一律平等地返回给用户，而用户随机选择一个节点交换。
节点之间的交换完全是无序的，无序的交换导致无谓的跨地区甚至是跨国的“流量旅行”，耗费了宝贵的国内和国际带宽资源。

53 依靠P2P应用的解决方案 基于局部性原则选择节点： 基于逆向流量工程的流量走向调整： 如优先选择相同子网、相同ISP内的节点交换文件片段。
若不考虑链路流量、不同链路的通信开销，可能会给骨干网带来拥塞或造成不必要的费用开销。 基于逆向流量工程的流量走向调整： 应用发送探测消息收集和推测底层网络状态，确定流量走向。 依赖网络测量技术，而测量会消耗带宽，且不能完全反映网络的真实状态。 一些新技术（如MPLS）对探测消息不响应。 无法推测ISP运营商的策略信息。

54 基于ISP的流量控制 目前因特网上的流量控制主要是ISP的责任： P2P模式改变了传统的流量控制问题：
应用需要的数据可以从很多节点、以很多种方式得到，每一种方式都会产生一种不同的流量需求模式并导致不同的网络使用效率。 P2P的动态流量模式能够自动适应网络变化，但也使得ISP估计网络状态并确定最佳路由的努力无效。

55 基于ISP和P2P应用合作的P4P技术 网络运营商和P2P应用应合作解决流量吞噬问题：
P4P（Proactive network Provider Participation for p2p）： 一个旨在同时优化ISP和P2P系统性能的网络架构 已集成到一些具有代表性的P2P软件中，在商业测试中表现出色。

56 4.1 P4P架构 P4P是一个允许网络运营者向新型应用显式提供网络信息、策略及能力的通用框架，除P2P之外可支持各种高带宽应用。
数据面（可选）：区分应用流和设定应用流的优先级 控制面：通过iTracker向应用提供网络信息 管理面：监视控制面的行为

57 P2P控制面中的实体 iTracker：代表一个网络运营商 appTracker：代表一个P2P应用 Peer：代表P2P客户
对等客户从appTracker或iTracker（若无appTracker）获得必要的信息，并帮助分发信息。 每个网络运营者（商业网络提供商、大学校园网、虚拟服务提供商等）为其网络维护一个iTracker，iTracker的IP地址可以通过DNS获得。从容错和可扩放性角度考虑，对于一个给定的域可以有几个iTracker。 图示为在P2P的应用场景下，P4P控制面中可能存在的实体和信息流，其中iTracker代表一个网络运营商，appTracker代表一个P2P应用，Peer代表P2P客户。 在一个给定的设置中，不是每个实体间都有交互。比如，在基于appTracker的P2P应用中，appTracker和iTracker相互作用并将P4P控制面中的信息分发给客户；而在无appTracker的P2P应用中，对等客户直接从iTracker获得必要的信息。以上两种情形中，对等客户均会帮助分发信息（如通过gossips）。iTracker也可以由一个可信的第三方来运行。也可以有一个综合者汇总几个iTracker的信息，与应用交互。 P4P没有规定确切的信息流，只是提供了一个公共的消息传递框架。

58 iTracker提供的接口 策略接口：用于向对等客户或appTracker提供网络使用策略和指导意见。
能力接口：用于对等客户或内容接供商向运营商请求能力（资源）。 P4P的主要思想就是在应用与网络运营商之间开启显式的通信接口，应用的客户可以调用该接口得到网络信息，从而能够更有效地利用网络资源，提升应用性能。 ITracker提供了三个接口。网络运营商可以只实现接口的一个子集，可以对接口执行某种访问控制来保护安全和隐私（如只允许可信的appTracker访问接口），也可以对某些内容执行访问控制。

59 appTracker使用接口的例子 图中给出了一个appTracker使用策略接口和/或P4P距离接口请求网络策略和/或代价的例子。
一个P2P群跨了两个网络运营商A和B，每个运营商运行一个iTracker。对等客户a首先注册到appTracker，appTracker查询iTracker A和iTrackerB，然后根据应用需求和iTracker的信息为a选择一个对等客户b。如果没有appTracker，则a查询iTracker A，然后通过一个本地决策来选择其对等客户。

60 4.2 P4P距离（p-distance） P4P架构中最核心的接口是P4P距离： P4P接口有两个视图：
运营商通过该接口告诉应用当前网络中域内和域间的网络开销。 应用使用P4P距离来优化连接，提高网络通信效率。 P4P接口有两个视图： iTracker看到的内部视图 应用看到的外部视图

61 内部视图 内部视图是一个网络拓扑G =（V, E），其中V是节点集合，E是链路集合。
V中的节点称为PID（opaque ID），有以下几种类型： 汇聚节点：代表一组客户（如一个网点或网络状态相同的一组节点），对外部是可见的。 核心路由器：对应用和客户不可见。 外部域节点：对应用和客户不可见。 iTracker在内部视图中连接两个PID（如果这样连接是有意义的），并给每条PID层次的链路指定一个p-距离。 客户通过查询网络（如iTracker）得到自己的PID和AS号。当客户第一次获取其IP地址时，就会得到这些信息。如果IP地址到PID的映射是动态可变的，则客户需要周期性地刷新该映射。 内部视图中还包括代表核心路由器和外部域节点的PID，这些PID对外是不可见的。

62 外部视图 iTracker提供的外部视图是一个全连接的网状网络：
给定一对外部可见的PID i和j，iTracker给出从PID-i到PID-j的p-距离（pij）。 pij是iTracker根据网络内部距离和路由计算出来的，iTracker可以给这个距离一个干扰来增强隐秘性。

63 p4p距离的指定 ISP可以有很多种方法来指定p-距离，比如： 从OSPF权值和BGP偏好来得到p-距离

64 P-距离信息的分发 ISP可从以下几个方面控制p-距离信息的分发： 使用p-距离接口的权衡涉及扩放性、语义和隐私。
PID的聚合粒度：控制粒度 vs 扩放性和用户隐私。 网络信息的粒度和语义：简单、健壮 vs 控制粒度和信息语义。 信息的接收者：安全、隐私保护 vs 信息的中立性。 使用p-距离接口的权衡涉及扩放性、语义和隐私。 接口本身是简单、灵活和标准化的（易于互操作），复杂性体现在如何使用，而如何使用是由ISP决定的。 PID的聚合粒度：最细的聚合粒度是一个PID只代表一个节点，优点是允许细粒度的控制，缺点是会带来扩放性和用户隐私泄露的问题。 网络信息的粒度和语义：最粗的粒度是iTracker给每个PID指定一个等级，如1、2、3等。这种方式简单，健壮性好。缺点是粒度粗，比如第二级的P-距离可能和第一级的P-距离一样好，也可能差得很多，因此没有办法进行精确的流量控制（如20%的流量到PID-1，80%的流量到PID-2等）。划分等级的另一个问题是信息的语义较弱。假定按等级从高到低的排序为PID-1、PID-2、PID-3，如果一个客户集合由PID-1中的一个客户和PID-3中的3个客户组成，而另一个客户集合由PID-2中的4个客户组成，则无法比较这两个客户集合。当应用建立某种数据分发结构（如树结构）时会出现这样的集合，另外在许多应用的优化问题中也很难使用等级信息进行描述。

65 使用P-距离接口选择对等客户（1） 按p-距离选择对等客户： PID-i客户选择PID-j客户的概率为pij的递减函数。
当来自PID-i的一个客户加入一个P2P会话时，appTracker查询iTracker，得到从PID-i到其它PID的p-距离。 如果iTracker指定PID-i内的p-距离最小，到其它PID的p-距离次之，到外部网络的p-距离最高，则应用可减少穿过PID和自治系统的流量。

66 使用P-距离接口选择对等客户（2） 有上/下载流量匹配要求的应用：
假设P2P会话k计算出PID-i到其它PID的上载容量为uik，下载容量为dik，从PID-i到PID-j的流量为tijk。不考虑网络效率，会话k选择P2P对等客户的问题描述为以下优化问题：

67 有上/下载流量匹配要求的应用（续） 若考虑ISP的优化目标，会话k可选择在满足一定流量的前提下最大化网络效率，则以上优化问题变为：

68 使用P-距离接口选择对等客户（3） 有鲁棒性要求的应用： PID-i中的客户应与其它PID中一定数量的客户连接。
引入变量ρijk：PID-i客户到PID-j客户的流量应占PID-i客户到所有其它PID客户流量的最小比例。 如果单纯考虑网络效率（ISP的优化目标），可能会导致较差的鲁棒性。为避免这种情况，一个PID中的客户可能需要与其它PID中一定数量的对等客户连接。

69 P4P设计的理论基础 iTracker收集网络状态信息： Tk为会话k可以接受的流量模式集合。
be：边e上的背景流量（非P2P流量） ce：边e的容量 Ie(i,j)：指示边e是否在从PID-i到PID-j的路由上。 Tk为会话k可以接受的流量模式集合。 对于其中一个tk∈Tk，若会话k选择tk，则它将产生从PID-i到PID-j的P2P流量tijk，相应地边e上的流量总和为tek。 这个问题的集中式求解要求iTracker和每个应用会话共享所有的信息，这是做不到的。作者通过引入对偶变量将该全局优化问题分解为每个应用会话独立的优化问题。

70 问题描述 若采用传统的ISP流量工程目标，需要求解以下优化问题（最小化最大链路利用率）： 改写以上优化问题为：

71 问题分解 对于公式（9）中的每一个约束条件，引入一个对偶变量pe>0，定义拉格朗日对偶方程： 为使方程有界，α的系数必须为0，即：
对偶方程简化如下：

72 iTracker与应用的交互 会话 k 从 iTracker 获得 本地计算 ，使满足 iTracker获得应用反馈的 ，调整{pe}：
本地计算 ，使满足 iTracker获得应用反馈的 ，调整{pe}： 更新{pij}，返回给查询的应用； 应用更新tk。

73 4.3 基于P4P架构的P2P流媒体系统 P2P流媒体是结合流媒体技术与P2P技术的流媒体解决方案。 基于组播树的P2P流媒体技术：
构建以视频源为根的数据分发树；当节点收到数据包后，将数据包的拷贝转发给它的每一个子节点。（典型的数据推送方法） 优点：拓扑结构简单。 缺点：拓扑维护开销大，可靠性差，不利于在大规模的实际环境中使用。

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

75 一个融合P4P架构的P2P流媒体系统 节点索引服务器（PMS）相当于appTracker，它将经过iTracker（按照策略）排序的对等客户列表返回给P2P客户端，从而对P2P流媒体服务进行控制和管理。 ITracker对P2P流媒体系统的控制流程如下： （1）用户向appTracker请求获取某资源对应的对等客户列表。 （2）appTracker在本地资源索引中找到某资源对应的对等客户列表，然后请求iTracker对对等客户列表进行排序。 （3）iTracker把排序后的等客户列表返回给appTracker。iTracker与appTracker之间遵循IETF ALTO协议。 （4）appTracker把排序后的等客户列表返回给用户。

76 如何发现iTracker地址 appTracker通过DNS解析P4P服务的域名，获取iTracker的IP地址。
在appTracker上直接配置iTracker地址。

77 4.4 基于P4P技术的Gnutella路由算法 Gnutella 0.6引入了超级节点的概念：
超级节点：叶子节点的代理，只在认为叶子节点能够响应查询请求时才向叶子节点转发查询请求； 叶子节点：从不向超级节点转发查询请求。

78 Gnutella 0.6的工作原理 节点加入： 查询转发： 节点连接到网络后，使用Ping消息找到最近的超级节点；
通过该超级节点了解并连接更多的超级节点； 选择一个超级节点，成为它的叶子节点。 查询转发： 节点向自己的超级节点发送Query消息； 若超级节点有符合查询要求的文件，发送QueryHit消息； 超级节点递减Query的TTL值，若不为0，向相邻的超级节点及可能包含该文件的叶子节点转发Query消息。

79 使用P4P技术优化超级节点的选择 在Gnutella网络中，满足以下条件的对等节点成为超级节点： 可以利用P4P技术优化超级节点的选择：
主机没有处在防火墙内且运行合适的操作系统 具有足够的带宽、机器性能和正常运行时间 连接了不少于一定数量的客户节点 可以利用P4P技术优化超级节点的选择： 基于P4P技术获得的信息，选择那些连通度较高的节点作为超级节点。

80 使用P4P技术优化节点加入 在Gnutella协议中： 利用P4P技术优化节点加入： 节点从获得的超级节点中随机选择一个加入。
基于P4P技术获得的网络信息，优先选择位于同一个ISP、（在同一个ISP时）同一个城市的超级节点加入。 可减小超级节点和叶子节点的通信延迟，降低骨干网络间的通信流量。

81 使用P4P技术优化查询请求的转发 超级节点的路由表中维护了到其它超级节点的路由。
在向其它超级节点转发查询请求时，选择通信代价较小的超级节点转发查询请求。

82 5 搭便车现象及抑制机制 P2P通信模式倡导的理念是协作和共享，但P2P网络的理性用户更多地表现出自主性和自私性，只想索取资源而不愿贡献资源。 节点只享受服务而不为系统做贡献的行为称为搭便车（free riding），大量搭便车现象将导致P2P网络效用大幅降低。 P2P网络中还存在大量不可靠的服务以及欺诈行为。 必须考虑P2P网络中节点的自主行为，激励节点之间有效合作并合理使用网络资源。

83 搭便车行为的研究进展 第一阶段：试图测量不同对等网络中的搭便车现象，分析其数学特征。
第二阶段：一些搭便车行为的抑制机制被提出，其中少数已应用到真实系统中。 第三阶段：意识到还没有哪一种方法可以彻底解决对等网络中的搭便车行为，应更深入地研究抑制机制，并在真实系统中验证有效性。

84 搭便车现象的测量结果 极少数热心节点维持了大量的连接。 测量结果表明，搭便车现象在对等网络中广泛存在。

85 拱便车行为的数学建模 有文献采用排队论对对等网络的服务能力进行了数学建模，研究表明：
提供服务的节点数越多、单一文件的拷贝数量（网络中包含该文件的节点数）越多，则对等网络的服务能力越强。 不同结构的P2P应用系统，容忍搭便车行为的能力有所不同。

86 搭便车节点比例与对等网络吞吐率的关系 CIA：具有集中索引服务器的对等网络 DIFA：分布式洪泛机制的对等网络
DIHA：分布式哈希表索引的对等网络

87 BT的激励机制 BT采用激励机制来抑制搭便车行为：节点以较大优先级选择向其提供了较大下载带宽的节点提供数据上传服务。
在该机制下，单个搭便车节点能获取的最大带宽如下，μ是节点上传带宽，nu是单个节点最大并发下载连接数： 直接提高nu即可降低搭便车者享受的服务，但节点需支持较多的并发TCP连接数，易出现超时重传或拥塞现象，网络有效吞吐率下降。在BT中，nu设为4。

88 搭便车行为对对等网络的影响 大量搭便车节点可能使热心节点因长期过载而宕机，导致整个对等网络的连通性发生巨大变化。
大量搭便车行为会降低对等网络的生命周期：热心节点因得不到资源而离开网络，并带走大量的资源，导致更多的节点离开。 如果搭便车现象过于严重，对等网络将趋近客户机/服务器通信模式，其可用性甚至比传统的客户机/服务器通信模式更差。

89 为什么容忍搭便车现象的存在？ 多数对等网络软件开发者容忍搭便车现象存在。以下三个因素值得考虑：
搭便车现象使对等网络抵御随机选择节点攻击的能力较强。 搭便车现象使得对等网络中节点的重要性不再均衡，管理者可以重点管理数量不多的热心节点。 允许一定程度的搭便车现象，有利于吸引自私的节点用户加入到对等网络，提高对等网络的用户数量。

90 搭便车行为抑制机制 抑制搭便车行为的共同指导原则是：根据节点已做出的贡献，确定它能够享受服务的能力。 已提出的抑制机制分为三类：
基于节点行为的激励机制 基于博弈论的方法 采用社会网络或经济模型的控制策略

91 基于节点行为的激励机制 激励机制的算法流程： 不同激励机制之间的差异主要体现在效用函数定义、测量点选择等方面。

92 效用函数设计 效用函数：节点享受服务的能力与节点为系统已做贡献的关系。 效用函数可能涉及以下自变量：
节点共享文件的数量 节点已下载文件的数量 节点已上传文件数量 节点已下载数据的大小 节点已上传数据的大小等。 定义计算复杂度小、又能客观反映搭便车控制关键问题的效用函数是激励机制设计的核心。

93 测量点位置选择 自我测量： 相邻节点测量： 节点把自已每次提供服务或享受服务的行为记录下来，评价自己在网络中的贡献大小。
工程上容易实现，开销小，但很难对付恶意欺骗的节点。 相邻节点测量： 每个节点对相邻节点进行测量和监督，各个节点的贡献大小由邻接节点评价。 节点互相测量能有效防止少数节点的恶意欺骗，但分布式测量的系统开销比较大。

94 自我测量的激励机制（1） 效用函数一： |UList(Pi , T)|表示在 T 时刻节点 i 所提供的共享文件数量，α是一个规范化系数（常量）。 节点能享受的服务质量正比于节点共享的文件数量。

95 自我测量的激励机制（2） 效用函数二： 以上两个效用函数没有反映节点所提供的文件被其它节点下载次数的动态信息。
节点能享受的服务质量正比于节点共享的文件大小总量。 以上两个效用函数没有反映节点所提供的文件被其它节点下载次数的动态信息。

96 自我测量的激励机制（3） 效用函数三： 第一项是节点i在时刻T的奖励值，第二项是惩罚值，上传（下载）越多，奖励（惩罚）越多。
K可以用作在线时间的度量，实现免费赠品。

97 自我测量的激励机制（4） 考虑节点异构性的效用函数值比较： Ci(t)是节点所做绝对贡献值，di是节点最大可支持物理带宽。

98 邻居节点测量 测量方法： 节点观察其邻居节点发送、转发信令包和数据包的行为（节点可以仅对通过自己转发的报文做日志记录）；
根据日志记录定期计算邻居节点的效用函数，发现搭便车者。

99 三类搭便车者 发出响应报文次数极低的节点，表明该节点一般没有提供共享信息资源，或仅共享了不被其它用户访问的资源。
从邻接节点获得的资源数量远大于它为其它节点提供服务的报文数量。 转发信令报文非常少的节点，该节点不为整个对等网络承担路由维护义务。

100 三个层次的惩罚方案 第一个层次： 第二个层次： 第三个层次： 快速降低搭便车者发出的查询请求消息的TTL值，降低报文在网络中的传播范围。
忽略自私节点的查询请求。 第三个层次： 直接取消与搭便车者的连接，将其清除出对等网络。

101 基于激励的抑制机制面临的困难 自我测量的激励机制： 分布式测量与监视机制：
效用函数严格程度的选择，在如何抑制搭便车行为与鼓励用户加入对等网络之间存在两难。 位于防火墙或NAT之后的节点会被认定搭便车者。 分布式测量与监视机制： 节点之间互相监视开销大。 对连接数很高的节点，监视邻接节点会增加节点负担。

102 博弈论方法 博弈论是分析社会群体和经济活动中，个体和群体选择最优行为策略的有效数学工具。
利用博弈论方法建模，一个节点的行为选择与同时在线的其它节点的行为选择紧密相关。 节点在对等网络中的行为可以建模为长期博弈过程，节点可在包括热心为系统做贡献、贪婪下载、贡献收益平衡等多种行为策略集合中找到有利于最大化自身收益的策略选择。

103 博弈论方法的困难 采用博弈论作为数学工具，定量化分析程度高，但在实际系统开发过程中面临以下问题：
一般需要整个对等网络系统的全局知识，难以满足。 一些假设太严格，与真实环境差异很大，结果未必具有指导意义。

104 社会网络和经济模型 对等网络中的节点存在的自私行为，是节点用户个人心理因素的一种延伸。
一些来自经济学、公共策略管理领域的学者讨论利用社会网络模型、经济模型、价格机制等方法来抑制搭便车现象。 已提出的一些方案包括利用市场管理技术促进节点之间的协作、利用市场机制模型抑制搭便车现象、采用社会经济生活中审计、竞价等机制抑制搭便车行为等。

105 社会网络方法面临的困难 大多假设对等网络软件具有对节点的行为审计和微支付功能，在大规模对等网络中基本难以满足。
尽管提出了一些模型，但定量化分析和工程实现方面研究较少。

106 参考文献 [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] 对等网络中的搭便车行为分析与抑制机制综述。