P2P流媒体系统服务器部署的优化设计

A L . 每个区域 A i 的流量需求为 w i ( i = 1 , 2 , …, L ) ,
部署的服务器个数为 ni . 网络内总流量需求 w =
w 1 + w 2 + … + w L , 负荷均值为 w ,则 n 1 + n2 + …+ nL
2
1 模型建立
1. 1 问题建模
最优化目标为 :
Yang Yahui1 , Niu Zhenying1 , and Xu Ke2
1 2
( S chool of S of t w a re an d M icroelect ronics , Peki n g U ni versit y , B ei j i n g 102600) ( De p art ment of Com p uter S cience an d Technolog y , Tsi n g hua U ni versit y , B ei j i n g 100084)
nupper 值只具有参考意义 .
1 . 2 优化目标 1. 2. 1 均衡性 P2 P 应用服务的提供商在部署服务器时主要考
虑均衡性和带宽费用 ,这里主要从 P2 P 应用的角度 讨论服务器部署的均衡性 . 定义 1. 一个区域内的流量需求和这个区域内 服务器的个数的比值称为服务器的负荷 ; 整个网络 内流量需求和网络内服务器总数的比值称为服务器 的负荷均值 ; 服务器的负荷与负荷均值的差的平方 称为服务器的负荷方差 . 定义 2. 所有的服务器的负荷方差之和最小的 方案称为最均衡的部署方案 . 假设网络中有 L 个区域 , 分别为 A 1 , A 2 , …,
1. 2. 2 主干网内流量最小
与 P2 P 应用提供者不同 , ISP 希望 P2 P 流量是 可控可管的 , 下面从流量管理的角度来分析服务器 部署的问题 . 我们的目标是令主干网内的流量最小 . 假设一个 ISP 共有 E 台 P E 路由器 ; 用 y i 表示路由 器 R i 处是否部署服务器的标志 , y i 取值为 0 或 1 , 如 果 y i 为 1 , 表示要部署服务器 ; 路由器 R i 到路由器
收稿日期 :2009 - 04 - 20 ; 修回日期 :2009 - 12 - 08 基金项目 : 国家自然科学基金项目 (60970104)
器的负担 ,提高了视频播放的质量 ,让大规模的视频 共享成为可能 . 为了优化流量在网络中的传输 ,需要 部署一定数目的内容镜像服务器 , 用于驱动数据的 扩散 、 存储源数据和传输过程中的数据补给[ 1 ] . 当前很多研究致力于发掘 P2 P 系统的潜力 ,
计算机研究与发展 Journal of Comp uter Research and Develop ment
ISSN 100021239Π CN 1121777Π TP ( ) 47 7 : 1219 - 1224 , 2010
P2P 流媒体系统服务器部署的优化设计
杨雅辉
1 2
1
钮振瑛 徐 恪
L
min
i =1
∑
wi w ni n1 + n2 + … + nL
.
( 5)
为了简化问题的讨论 , 有以下假设 [ 10 ] : 1 . 不考虑 peer 的加入和离开 ; 不考虑重复下 载 ; 传输的速率是相对稳定的 . 2 . 系统中有 N 台服务器 , 第 i 台服务器的最大 上传能力为 S i , 其实际上传速率为 si ; 有 M 个 peer , 第 j 个 peer 的上传速率为 uj , 下载速率为 d j ; 在整 个系统的后备能力的上限为 C. 这样有如下的判断条件 : 1 . 当式 ( 1) 成立时 , 表示服务器的供应能力不
j
其中 , r 为直播的速率 , 为了简化这里假定速率相 同 , 如果不一样 , 通过下标区分 . 没有部署服务器的
P E 要向有部署服务器的 P E 请求速率为 r 的播放
2 优化算法
2. 1 最均衡部署服务器的贪心算法
服务 , 这些请求都要流经主干网络 , 这样式 ( 6 ) 以这 些流量之和最小为优化目标 , 约束条件为 :
摘 要 P2 P 流媒体系统中 ,内容服务器提供源数据并驱动数据扩散 ,是系统的重要组成部分 ,其部署方
案会影响整个系统的流量变化 . 分析了服务器的优化部署问题 ,从服务器负载均衡 、 主干网内流量最小 和调度代价最小 3 个优化目标建立系统模型 ,并给出了各个优化目标的算法实现 ,包括基于负载均衡的 贪心算法和基于 021 规划的分支定界算法 . 最后 , 通过仿真实验验证了服务器部署方案对系统的影响 , 实验结果表明不同的优化目标满足了不同的部署需求 .
R j 的最短路径记为 l ij ( j ≠i) , 对应的 Cost 记为 Cost ( l ij ) , 经由路由器 R i 的所有的最短路径中的最小值
杨雅辉等 : P2 P 流媒体系统服务器部署的优化设计
1221
记为 min ( l ij ) , 对应的 Cost 记为 Cost [ min ( l ij ) ]. 简
1
2
( 北京大学软件与微电子学院 北京 102600) ( 清华大学计算机科学与技术系 北京 100084) ( yhyang @ss. p ku. edu. cn)
Optimizing Design of Server Deployment in P2 P Streaming System
j j
便起见 , 我们以直播为例建立最优化目标 :
E
min
L
1
L
L i
N + n i =1
∑∑y
j =1
・y j ・Cost ij +
( 10 )
min
i =1
∑( 1 -
y i ) ・Cost [ min ( l ij ) ] ・r ,
j
( 6)
i =1
∑( 1 -
y i ) ・Cost i [ min ( l ij ) ].
1220
计算机研究与发展 2010 , 47 ( 7)
提高peer 的上传能力 , 从而节省服务器的带宽 [ 223 ] . 例如 : PPLive 在实施了一系列优化措施后 , P2 P 视 频系统的带宽节省率达到了 90 %以上 . 对 P2 P 系统 的优化已经接近于极限 , 需要把关注点放到服务器 的部署策略上 . 在 P2 P 应用中 , 关于服务器的部署 对整个系统的影响方面的研究很少 ,而且 P2 P 服务 提供者也没有统一的服务器部署方案 . 当服务器资 源不足时 ,就请求新的设备 , 这种方式缺少整体统 筹 ,具有一定的盲目性和滞后性 . 为此 , 需要对服务 器的部署问题进行深入研究 , 提出有效可行的服务 器部署方案 . 在 P2 P 技术与服务器相关的研究中 , 文献 [ 1 ] 主要研究如何在多频道的直播系统中分配服务器带 宽 ; 文献 [ 3 ] 主要研究 CDN 辅助的 P2 P 服务选择问 题 ; 文献 [ 4 ] 主要研究服务器参与下的数据调配的优 化算法 . 专门讨论 P2 P 系统服务器部署的研究文献 很少 ,本文主要讨论服务器部署的优化策略问题 . 在 服务器部署的优化设计研究方面 ,一方面以文献 [ 2 ] 对 P2 P 系统分析与拓扑形成的研究成果和文献 [ 52 7 ] 在服务选择策略与存储策略方面的研究成果为理 论基础 ; 另一方面服务器部署的优化问题只考虑 P2 P 应用是狭隘的 ,还需要兼顾 SIP 的利益 ,在这点 上结合 P4 P 技术 [ 829 ] , 探讨将流量管理的思想加入 到 P2 P 应用中 ,为服务器部署问题的解决拓展新的 思路 . 本文通过对于服务器部署问题建模 ,提出了均衡 性、 主干网内流量最小和调度代价最小优化目标 ,实 现了对应的优化算法 ,最后结合教育网 CERN ET2 的 实际进行了仿真分析 ,实验结果表明 : 通过优化算法 在 3 个优化目标方面 ,与不考虑优化有明显的差异 , 可以更好满足服务器部署优化目标 .
关键词 P2 P 应用 ; 服务器部署 ; 负荷均衡 ; 流量管理 ; 优化算法 中图法分类号 TP309
术为视频共享提供了一种有效的方式 , 减轻了服务
0 引 言
Internet 上基本的流 媒体 传输 模型 是 CΠ S模
型 ,缺点是 : 每个客户端直接从服务器下载数据 , 造 成服务器的负担过重 ,不利于大规模的应用 . P2 P 技
足 , 需增加服务器 .
N ∑
M
uj -
j =1
∑d
M
j
≤ C.
( 1)
2 . 系统增加的设备数 n 要满足式 ( 2) :
N +n
si +
i =1
j =1
∑
M
uj -
j =1
∑d
M
j
≥ C.
( 2)
因为 S i > si ( i = 1 , 2 , …, N + n) , 则可以推出 :
N+n i =1
∑
Si +
j =1
∑
uj -
j =1
∑d
j
≥ C.
( 3)
假设各服务器的上传速率均为 S , 则可得到系 统对设备的预估需求上限 :
M M
( nupper =
j =1
∑
dj -
j =1
∑u
j
+ C) - N. ( 4)
S
在实际系统中 , 由于 S i 与 s i 的差距颇大 , 所以
Abstract In P2 P st reaming systems , co ntent server s which supply t he so urce data and drive t he data to sp read in t he whole system , are important co mpo nent s. The deployment of t he server s o bvio usly affect s t he network t raffic which is related wit h t he benefit s of bot h P2 P applicatio n p rovider s and Internet service p rovider s. But lit tle research wo rk focuses o n t he server deployment areas. The aut hor s discuss t he p ro blem o n server deployment f ro m t hree optimizatio n directio ns : load balance , minimum t raffic in core net wo rk and minimum allocatio n co st s. The adaptive algorit hms , including load2balance2based greedy algorit hms and t he 021 linear2p rogramming2based branch and bo und algorit hm , are p resented. So me experiment s are co nducted to p rove t he effect s of server deployment s o n t he system , and it can be seen t hat different optimizatio ns can achieve t he different o bjectives. Key words P2 P applicatio n ; server deployment ; load balance ; t raffic management ; optimizing algorit hm