- 1 -
中国科技论文在线
全分布式 P2P 与 CDN 融合的性能分析#
张莹，王洪波，程时端，林宇*
基金项目：高等学校博士学科点专项科研基金（200800131019），新世纪优秀人才支持计划(NECT-07-0109)，
中兴通讯研究基金
作者简介：张莹，(1986-)，女，在读硕士研究生，P2P 技术
（北京邮电大学网络与交换技术国家重点实验室，北京 100876）
摘要：目前，IPTV普遍采用 CDN 系统作为其构建方案，但随着用户量不断增加，CDN 系统面
临着可扩展性差的问题。而 P2P，尤其是全分布式架构 P2P 具有高可扩展性的优势。将全分
布式 P2P 应用到 CDN系统可以弥补其扩展性不足的缺点。本文首先介绍全分布式 P2P 中的主
流算法，然后提出一种 P2P-CDN 融合架构，并将部分全分布式 P2P 算法应用到该架构中，进
一步通过仿真实验对其性能进行分析比较。仿真结果表明：针对 CDN 特殊的应用场景，单跳
算法在带宽消耗，查找跳数等方面表现出更多的优势。
关键词：对等网络；分布式哈希；内容分发网络
中图分类号：
Analysis of Distrbuted Peer-to-Peer Effect on CDN
Zhang Ying, Wang Hongbo, Cheng Shiduan, Lin Yu
(State Key Laboratory of Networking and Switching Technology, Beijing University of Posts &
Telecommunications, Beijing 100876)
Abstract: At present, IPTV system commonly uses CDN system as its construction scheme, but with
users increasing, they face the problem of scalability. Instead, P2P, especially distributed P2P
architecture, shows more advantage in scalability. So, it is useful to apply distributed P2P architecture
to CDN system. Therefore, this paper briefly introduces some popular distributed P2P algorithms, then
presents a P2P-CDN integration framework and applies a few algorithms to it. At last its performance
is analyzed through simulation. Simulation results show that onehop algorithm performs better than
other in consumed bandwidths, searching hops, and so on.
Keywords:P2P; DHT; CDN
0 引言
现在，IPTV 正在开始逐渐地走进人们的日常生活，它提供了一种主动、交互式的电视
收看模式，彻底颠覆了传统被动、单向的模式，允许用户使用节目点播、回看等功能。由于
IPTV 业务的用户数量大、用户分布分散以及服务质量要求高等特性，在构建 IPTV 系统时
普遍采用 CDN 系统作为其具体实施方案[1]，而 CDN 系统由于其服务器分级、负载均衡和边
缘节点内容推送等特点也很好地适应了 IPTV 业务的需求。然而随着业务、用户数量规模的
不断扩大以及相关新业务对系统性能更高的要求，现有 CDN 系统也面临着可扩展性不足，
系统升级成本过高等问题。因此需要从技术上对现有 CDN 系统进行改进。
现今，P2P 应用如迅雷，BT，Skype 及流媒体软件 PPLive，PPStream 等得到广泛使用,
同时，它们给互联网带来了前所未有的影响[2]。P2P 技术的核心是在用户间按照对等方式共
享资源，它完全不同与传统的 Client/Server 模式。在 P2P 网络中每个节点既作为客户端从其
他节点下载资源，同时它还是一个服务器为其他节点提供服务。这样将 C/s 模式中服务器的
压力均分到了用户身上，实现了“去中心化”，从而避免了系统瓶颈问题。
目前用于解决 CDN 系统扩展性问题的一种方法便是引入 P2P 技术，形成新的 P2P-CDN
系统，利用 P2P 技术自身极强的可扩展性弥补 CDN 系统的缺陷。然而，虽然 P2P-CDN 系
统这一概念已经被广泛地接受，但目前仍然缺乏基础的、数据上量化的分析。
- 2 -
中国科技论文在线
1 全分布式 P2P
全分布式 P2P 总体上分为两个类别：一类是全分布式非结构化 P2P 网络，另一种是全
分布式结构化 P2P。第一类 P2P 采用随机图方式组织节点，对网络的动态变化体现出较好的
容错能力，因此可用性较好。但洪泛(Flooding)的定位方式造成网络流量急剧增加，导致其
可扩展性不好，同时查询结果可能不完全，查询速度较慢。第二类 P2P 网络主要采用分布
式哈希表(Distributed Hash Table，简写成 DHT)技术来组织节点。DHT 是一个由广域范围大
量节点共同维护的巨大散列表。它能自适应节点的动态加入和退出，有良好的可扩展性，并
且其发现准确性得到了保证。目前，采用 DHT 技术的 P2P 得到广泛应用，不同 DHT 的区
别体现在其查找方法上。下面简单介绍几种 DHT 算法。
Chord
Chord 在 2001 年由麻省理工学院提出的[3]。它使一致性哈希算法为每个节点和关键字分
配 m 位的标识符，把节点和键值映射到一个大小为 m2 的环形空间上。节点标识符可通过散
列节点 IP 地址产生，关键字的标识符则可以直接散列此关键字。其中标识符长度 m 必须足
够长，这样可以保证两个节点或者关键字散列到同一个标识符上的概率小到可以忽略不计。
在一致性哈希中，每个关键字保存在它的后继(successor)节点中，后继节点是节点标识
符大于或等于关键字 k 标识符的第一个节点，可表示为 successor( k)。如果标识符采用 m 位
二进制数表示，并且从 0 到 2m-1 排列成一个圆圈，那么 succesor(k)是从 k 开始顺时针方向
距离其最近的节点，如图 1 所示。
图 1 Chord 环结构
Chord 中每个节点维护一个后继节点表和一张路由表(finger table)。后继节点表保存标识
符空间中顺时针方向紧跟在其后的节点。路由表保存顺时针方向距离当前点 12i− (1≤i≤m)
的标识符及该标识符的后继节点，其间距将成 i2 的关系排列。这样的路由关系实际上是折
半查找算法的排列关系。Fingertable 中具体内容如表 1 所示。
在查询过程中，请求被发送到与键值最接近的节点上。收到查询请求的节点如果发现自
身存储被查询的信息，可直接回应查询节点；如果被查询信息不在本地，则根据查询表将请
求转发到与键值最接近的节点上。这个过程持续到找到相应节点为止。从前述过程可以看出，
Chord 查询跳数为 (log n)O (n 为节点总数)。
- 3 -
中国科技论文在线
表 1 Chord 中节点路由表结构
域名 定义
finger[k].start (n+
12i− )mod2m,1<=k<=m
finger[k].node Finger[k].start 的后继节点
finger[k].interval [finger[k].start,finger[k+1].start)
successor 本节点后继，也等于 finger[1].node
predecessor 本节点前驱
Kademlia
Kademlia 是一种典型的结构化 P2P 覆盖网络(Structured P2P Overlay Network)，是美国
纽约大学在 2002 年发布的一项研究结果[4]。它是一种分布式哈希表(DHT)技术，它以异或算
法(XOR)为距离度量基础，建立起一种全新的 DHT拓扑结构，从而大大提高查询速度。
网络中每个节点拥有一个专属 ID，它是一个大小为 160 位的比特串。两个节点距离定
义为其 ID 值的异或运算结果。一个条目被存放到与 Key 值距离最近的 k 个节点上。Kademlia
中的路由是通过 k 桶来进行。每一个节点负责维护 160 个 list(列表)，每个 list 被称为一个
k-bucket(K-桶)，如图 2 所示。
图 2 K-bucket 的结构
其中，第 i 个 list 记录与该节点的距离在2i～ 12i+ 之间的 k 个节点信息，即保存的节点
ID 满足以下条件：前 i-1 个比特位与当前节点 ID 的前 i-1 位比特取值相同，第 i 位是其第 i
位比特值取反的结果，从第 i 位开始可以取任意值。每一个 list 中最多存放 k 个节点信息(k
是一个系统参数,其取值准则为：任意选择至少 k 节点，使它们在任意时刻同时不在线的几
率接近 0)。每个 K 桶内部节点信息的存放位置是根据上次访问时间进行的排序，最先
(least-recently)访问的放在头部，最后(most-recently)访问的放在尾部，并按 LRU 策略更新。
此外，Kademlia 提供快速的节点查找机制，采用并行查找返回节点本身或最近的 k 个
节点，其查找速度可通过参数调节。
与 chord 相比，Kademila 能获得与其相同的运行性能，但其路由表更为灵活，它采用并
行查找返回 k 个最接近的节点并将 key 存放在最接近的 k 个节点上，因此，保证它具有较好
- 4 -
中国科技论文在线
的容错性能。
单跳
大多经典 DHT 算法是在节点频繁加入，退出的情形下提出的，如网络抖动。每个节点
仅保存网络中一些特定节点的信息，查找一般在 O(logN)跳内完成，这种方式能有效减少带
宽资源，但它是以降低性能为代价来换取带宽的节约。
近年来，存储设备价格日益下降，网络带宽逐渐变大。最近研究表明：在网络扰动率不
高的情况下，可在每个节点维护全局路由表以实现单跳查询。它能有效降低查找延时，提高
用户感知体验。
单跳算法要求每个节点存储一张全局路由表[5]，包含所有其他节点的相关信息，如 ip
地址，端口号等。因此查找算法是直接的，节点在全局路由表中直接取到最优节点信息，在
本地便可结束查找。实际上，所谓单跳并非是绝对的，而是很大比例的查找，如 99%，都
能在一跳内完成，这个比例是由路由表的准确程度决定的[5]。为此，每个节点不仅要保存一
张全局路由表，还需维护它的状态，使其能较为及时，准确地反应当前网络中节点的状态信
息。因此，在有节点加入退出时，所有节点均要及时更新本地路由表。目前采用的更新路由
表的主要方法有：配置服务，广播树，令牌环传递以及 EDRA(Event Detection and Reporting
Algorithm)。
2 CDN 架构
图 3 是 CDN 在 IPTV 系统中部署的一种实际体系架构。其中，CDN 系统的节点分为两
个层次，分别称为内容源服务器、底层服务器。其中底层服务器存储部分媒体数据，并向终
端用户提供流媒体服务，但只有底层服务器直接面向最终用户，为用户提供直接数据服务。
内容源服务器在性能上好于底层服务器，存储全部的媒体内容。这样，当底层服务器不能满
足用户需求时，则由内容源服务器为其提供数据支持服务，而在底层服务器接收到上层传递
来的数据后再为用户提供服务。这便是目前在 IPTV 体系结构中 CDN 结构的基本模型。
内容源服务器
底层服务器
底层服务器
底层服务器
图 3 全分布式的 P2P CDN 架构
这种情况下，在底层服务器不满足请求时，将请求全部转发给内容源服务器，这样会导
致内容源的负载过大。但如果将 P2P 技术引入到 CDN 系统后，在底层服务器之间共享资源，
- 5 -
中国科技论文在线
会降低内容源服务器请求量。
这里只是在边缘节点这一层引入了 P2P 技术，因为这层节点数量上最多，性能上最低，
并且直接面向用户，因此，其性能需要得到保证，而上两层节点由于数量较少，且平均性能
较强，因此暂时不需要加入新的网络结构。
3 实验仿真
仿真工具选取 BISON 项目组提供的 PeerSim[6],它是一个模拟 P2P overlay 网络的软件，
支持结构化和非结构化 P2P 网络模拟。PeerSim 有两种模拟方式，cycle-based 和 event-driven。
event-driven 模式相对精确，cycle-based 模式缺少传输层的模拟而且不能起到并发控制的作
用，但占用资源少以适合于大规模的模拟。本次仿真实验利用了 PeerSim 中有关网络节点的
一些通用功能模块，并采用 Java 语言扩充其底层传输模块、实现基于事件的协议。最终仿
真模拟了应用较为广泛的 Kademlia 与单跳算法。
仿真过程关注的是 DHT 查找过程，不同算法的查找策略不同。在对比分析两种算法时，
需要考虑如下方面的性能：定位跳数，查找和维护带宽开销。跳数是为了找到保存关键字的
节点信息而在查找过程中访问过的节点个数。查找带宽主要考虑的是查找过程中的定位消息
开销，其实它与查找跳数明显相关，跳数越多，开销就越大，反之就小。维护开销主要是关
键字在节点之间的分布式存储(发布消息)以及节点信息更新消息的开销。
从图 4 可以看出，单跳算法的平均查找跳数在 1 附近，并且较为稳定，而 Kademlia 算
法的查找跳数波动性较大，并且明显比单跳的查找速度要慢。这主要是由于单跳算法的路由
表包含整个域中所有节点的信息，最多经过一次路由表查找过程便可获得请求媒体的文件信
息。而在 Kademlia 算法中网络中每个节点只保存部分邻居节点的信息，查询过程需要经过
多跳（最大查找跳数为参数 a，实验过程中取 a = 4）。
0 5 10 15 20 25
ho
p
nu
m
be
r
t/h
Kademlia
OneHop
图 4 Kademlia 与 OneHop 的平均查找跳数比较
从图 5、图 6 可以看出，无论是在查找带宽还是维护带宽的比较上，单跳算法都比
Kademlia 更具优势。单跳算法查找跳数较少导致其查找开销比 Kademlia 小。Kademlia 算法
采用并行查找以及周期性更新其 K 桶，因此，其维护开销稍大。
总之，通过仿真实验结果可以得出，在CDN 环境下，单跳算法性能上明显优于Kademlia，
- 6 -
中国科技论文在线
它更适合 CDN。实际上，这是由于 CDN 的特殊性所导致的。首先 CDN 中的节点长时间在
线，其生命期为几周甚至几个月，加入退出很少发生，因此其结构较为稳定，于是 Kademlia
中的定期更新开销就没有必要。第二，CDN 节点单位时间查询次数非常大，如果采用多跳
DHT，查询流量会远远占很大比例的带宽。第三，对查询的时延要求高，单跳查询几乎可以
达到集中式查询的效果。所以，单跳 DHT 算法更适用于 CDN。
0 5 10 15 20 25
0
1
2
3
4
5
6
ba
nd
w
id
th
/k
bp
s
t/h
Kademlia
OneHop
图 5 Kademlia 与 OneHop 的查找开销比较
0 5 10 15 20 25
ba
nd
w
id
th
/k
bp
s
t/h
Kademlia
OneHop
图 6 Kademlia 与 OneHop 的维护开销比较
4 结论
虽然 CDN 系统在一定程度上可以提高 IPTV 系统中用户的服务质量，但是随着用户量
的增加，其仍然表现出较差的可扩展性。而全分布式 P2P 天生具有较好的可扩展性。因此，
将 P2P 引入到 CDN 中，在 CDN 中应用 DHT 算法，已经成为一种趋势。
本文给出各种 DHT 算法的内容存储及查找过程的简单介绍，并以 IPTV 业务为例给出
- 7 -
中国科技论文在线
其 CDN 结构图，之后在其边缘节点间引入 P2P。最后通过仿真实验分析给出针对 Kademlia
及单跳算法的仿真实验结果。仿真结果表明在 CDN 这种较为稳定的服务器系统中，单跳在
定位跳数，维护及查找开销上表现出更多的优势。因此，单跳算法更适用于 CDN，能够有
效解决 CDN 中的可扩展性问题。
[参考文献] (References)
[1] Mukaddim Pathan, Rajkumar Buyya, Athena Vakali. Content Delivery Networks: State of the Art, Insights,
and Imperatives[Z]. 2008, Lecture Notes Electrical Engineering, Volume 9.
[2] 龚海刚，刘明，毛莺池，等. P2P 流媒体关键技术的研究进展计算机研究与发展[J]. ISSN 100021239/ CN
1121777/ TP，2005 年，42 (12)：2033～2040.
Gong Haigang, Liu Ming, Mao Yingchi1, et al. Research Advances in Key Technology of P2P2Based Media
Streaming[J]. Journal of Computer Research and Development. ISSN 100021239/ CN 1121777/ TP，2005 年，
42 (12)：2033～2040.
[3] lon Stoica, Robert Morris, David Karger, et al. Chord: A Scalable Peer-to-Peer Lookup Service for Internet
Applications[Z]. SIGCOMM’01, August 27-31, 2001, California, USA.
[4] Petar Maymounkov, David Mazieres. Kademlia: A Peer-to-peer Information System Based on the XOR
Metric[R]. Technical Report,2002
[5] Luiz R. Monnerat, Claudio L. Amorim. D1HT: A Distributed One Hop Hash Table[R]. Technical Report,
ES-676/05 - May 2005, COPPE/UFRJ 2005.
[6] Mark Jelasity, Alberto Montresor, Gian Paolo Jesi, et al.
