1
网络技术基础
第十三讲 P2P系统及其应用
3
应用层在网络中的位置
物理层：邻接节点的数据通信 数据链路层：局域网中的资源争用 (MAC)，邻接节点的可靠传输 (LLC) 网络层 (IP)：子网间的数据中转，异质网络的互通互联 传输层 (TCP)：端到端的可靠传输，端到端的资源争用 应用层：复杂多样的应用 ...
中心化 ! 去中心化 协调 ! 协作 控制 ! 激励
17
P2P的应用领域
文件共享：Napster，Gnutella，BitTorrent 信息管理：无中心的管理形式
在席（Presence）信息：哪个对等点和哪个资源是可用的，ICQ 分布式的文档管理：Opencola（关键字，兴趣网络） 协作：Groove (Microsoft Office SharePoint Workspace)，无中心的协作
14
哪里有压迫，哪里就有斗争！ P2P应用背后强有力的需求动力，指示了网络应用的方向
RIAA)*Nepster +," 1999 Gnutella-./0 1" 2000 Nepster %&'( $" 1999 Metallica)*Nepster 2" 2000
Nepster %&3427.956789 ," 2001 Nepster :);<=>?4Gnutella%& @" 2001 Gnutella %&3430.55A8967 B" 2001
37
结构化P2P系统
38
基于DHT的P2P系统
DHT (Distributing Hash Table) 分布式散列表 通过适当地规划数据项D的存 储位置可以显著地降低其他 节点B查询D所付出的代价 到达目标D的步数：O(log2N) 系统扩展性的提高
节点A在哪里存储数据项D？ 其他节点B如何发现D的位置？ 如何组织分布式系统才能保证 规模扩展性和效率？
生成小世界网络，仅仅需要了解相邻节点的信息和少量远程节点的信息 很可能可以自组织地形成
32
在小世界网络中航行
Milgram实验的启示自发形 Nhomakorabea的社会网络存在小世界的特征 随机的“捷径”是形成小世界网络的关键
问题：信件转发的过程中，转发者如何能够通过少量的信息发现这些捷径？
33
在小世界网络中航行
可“航行”的小世界网络
30
小世界网络
六度分离，小世界（Small World）模型 通过在规则网络中添加若干条“捷径”能够大大缩减网络的“直径”
31
小世界网络和P2P系统
邮件转寄和转发式查询的类比
通过适当地组织Overlay Network的拓扑，可以有效地缩减网络半径 网络半径的缩减 ! 查询转发次数的缩减
小世界网络的生成模型
模型可扩展到高维，仅在新边生成概率上略有区别
35
Kleiberg模型的可航行性
所需信息
节点 i 的局部连接情况 目标 t 在网格中的坐标 无需全局信息
方法：选择距目标 t 最近的邻居作为下一个转发者 结果：到达目标的步数O(log2N)
36
Kleiberg模型的应用问题
将资源映射到一个k维网格，并建立坐标 在两个坐标之间建立度量
9
P2P的特征
去中心的资源利用
资源：信息、数据、带宽、处理能力 去中心：终端既是资源的使用者又是资源的提供者
去中心的自组织管理
管理：有效地查找和定位资源，主机的寻址 ! 资源的寻址 去中心：任意一个节点的离开不影响系统的可用性
10
应用层架构的转变
CS模式
混合模式
11
应用层架构的转变
混合模式
纯P2P模式
超级对等端（Superpeers） 叶子节点（Leafnodes）
新的信令
ROUTE_TABLE_UPDATE
27
层叠网络（Overlay Network）
Site 2 Site 3 N
N ISP1 Site 1 N ISP3 N
ISP2 N
• • •
节点通过PING/PONG过程建立层叠网络 层叠网络是应用层的虚拟网络 查询消息在层叠网络中转发
第二代P2P 混合P2P
• • • •
对等点既是资源的使 用者又是资源的提供 者（SERVENT) 动态的中心实体（超 级对等层） 能够去掉任何终端实 体而不损失功能 典型系统： Gnutella 0.6，JXTA
结构化P2P 基于DHC的P2P
• • • • •
对等点既是资源的使 用者又是资源的提供 者（SERVENT) 没有中心实体 能够去掉任何终端实 体而不损失功能 资源在P2P网络中的 位置经过预先规划 典型系统： Chord，CAN
纯粹P2P
• • • •
对等点既是资源的使 用者又是资源的提供 者（SERVENT) 没有中心实体 能够去掉任何终端实 体而不损失功能 典型系统： Gnutella 0.4， Freenet
• • • •
对等点既是资源的使 用者又是资源的提供 者（SERVENT) 必须存在中心实体 中心实体是某种索引 和分类数据库 典型系统：Napster
no
应用
文件的特征标识 CAM (Content Addressable Memory)
nod
40
DHT
散列表，分布式散列表
Key CS10 CS15 CS30 CS100 CS250 CS310 Value Algorithms Networking Distributed Sys. Peer-to-Peer Operating Sys. Grid Computing
39
散列函数
散列函数（Hash映射）：将变长字符串 映射成一个m位的数值
Key，Value
Key CS10 CS15 CS30 CS100 CS250 CS310
Value Algorithms Networking Distributed Sys. Peer-to-Peer Operating Sys. Grid Computing
4. Client sends results back to server
2. SETI client (screen Saver) starts
19
P2P系统的基本问题
在分布式系统中，在哪里存储以及如何寻找一个特定的数据项？ 数据的分布式管理和检索：节点A拟在分布式系统中存储一个数据项D， 节点B拟在没有D当前位置的先验知识的情况下检索D
18
P2P的应用领域
P2P计算
1996，SETI@home，寻找外星智慧生物的无线电信号，超过3百万用户
1. Install Screen Server
SETI@Home Main Server
Radio-telescope Data
3. SETI client gets data from server and runs
寻找一种简单的网络生成原则，具有小的平均路径长度（小世界特征），并 且能够利用无中心的算法寻找到捷径
34
Kleiberg的小世界模型
Kleiberg的小世界模型（2维模型）
n!n网格中分布一些节点，节点距离可用“格点步数”度量 以如下规则生成边，构建网络
节点 i 连接所有距离小于 q 的邻居 对于每个节点 i，依概率建立p条新边，选择新边的对端 j 的概率和距离d (i , j) 的平方成反比
中心化目录模型：Napster 非结构化的洪泛请求模型：Gnutella 结构化的资源路由模型：DHT
21
文件共享系统的技术演进
第一代P2P 客户/服务器 中心化P2P
• • • • •
服务器是中心实体， 是服务和内容的唯一 提供者 网络由服务器管理 服务器具有更高的性 能 客户端性能较低 典型系统：WWW
选择P2P作为应用层技术的代表进行介绍
-
代表着一种重要的应用趋势，代表着一种典型的分布式算法
4
应用的发展变化
传统应用
e-mail, FTP, Web, DNS ... 关键词：通信，资源共享
新的趋势
Web 2.0, Social Networks ... 关键词：互动，分享，关系，大范围协作 ...
12
Napster的故事
1999.5， Napster ，Shawn Fenning
第一个大规模应用的P2P系统 提供音乐文件下载和共享 SERVENT， SERVer + cliENT 混合结构：分布式的文件存储，通过中心式的目录服务器提供文件检索服务
13
Napster的故事
1999.12，美国唱片工业协会（RIAA）起诉Napster
-----Clay Shirky
Here Comes Everybody: The Power of Organizing Without Organizations what happens when people are given the tools to do things together, without needing traditional organizational structures
22
非结构化P2P系统
23
非结构化P2P系统的工作原理
节点A在哪里存储数据项D？ 其他节点B如何发现D的位置？ 如何组织分布式系统才能保证 规模扩展性和效率？
数据产生者A在本地存储D B通过洪泛请求消息查找D 可能通过层叠网络的结构 控制可扩展性
24
非结构P2P网络中的洪泛查询
25
Gnutella 0.4 网络
中心目录服务器成为RIAA诉讼的目标
技术方案的变化