Paper Title (use style: paper title)

Size: px

Start display at page:

Download "Paper Title (use style: paper title)"

弟茅
5 years ago
Views:

1 Transacons on Compuer Scence and Technology Sepember 2014, Volume 3, Issue 3, PP A Daa-Bloc Prory and Load Capacy-Based Schedulng Algorhm for P2P Meda Sreamng Aoz Gao, Jnyu Zhang Beng Jaoong Unversy, Beng , Chna # Emal: @bju.edu.cn Absrac Focus on he shorage of exsng P2P sreamng meda schedulng algorhm n acqure prory of daa bloc and peers load capacy, nroduced a daa schedulng algorhm base on urgency and scarcy degree of daa bloc, and a algorhmc mehod o calculae load capacy of neghbor peers ha can selec he approprae node and use push mehod o ransfer daa blocs o hose nodes. Wh he ulzaon of hs algorhm, hgher prory blocs and hgher capacy nodes were requesed, and he wang me o play was decreased. The smulaons ndcae ha he algorhm can reduce sar delay of sreamng meda and mae he playng fluen, can also acheve hgher peer hroughpu and more balanced load. Keywords: P2P Sreamng Meda; Prory; Daa Schedulng; Load Balance; Throughpu 基于数据块优先级与负载性能自适应 P2P 流媒体 * 数据调度算法高奥子, 张晋豫北京交通大学, 北京摘要 : 针对现有数据驱动型网络数据调度算法未能有效利用数据块优先级以及节点高负载的问题, 本文提出基于数据块优先级与节点负载性能的自适应数据调度算法该算法能够根据数据块稀缺度与紧迫度对所需数据块的优先级以及邻居节点负载状态进行评估, 充分利用数据块特性以及采用推的方式将数据块推送至相应的低负载节点, 以减少了数据块的等待时延并实现高负载的分担仿真实验表明, 该算法能够优化现有数据调度算法的不足, 使流媒体缓冲时延更小播放流畅, 实现流媒体系统负载均衡同时提高节点吞吐量关键词 :P2P 流媒体 ; 数据调度 ; 优先级 ; 负载均衡 ; 吞吐量引言随着互联网设施的不断完善,P2P 流媒体系统成为当前研究的热点,P2P 流媒体技术在传输方式方面打破了传统网络的服务器 / 客户端 (C/S) 模式的定式, 建立了客户端 / 客户端 (S/S) 的直接通信机制, 也为未来网络的发展提供了思路一方面,P2P 流媒体系统中的每一节点作为客户端的同时充当其他节点服务器, 在某种意义上, 每一结点处在同等地位另一方面,P2P 流媒体系统是对分布式概念的成功拓展, 它将传统服务器负载分配到网络中的每一节点上, 每一节点都将承担有限的存储与计算任务, 加入到网络中的节点越多, 节点贡献的资源也就越多, 其服务质量也就越高 [1] 目前以数据驱动型覆盖网络 (Daa-Drven Overlay Newor, DON) 的 P2P 流媒体技术得到了广泛的应用, 如 Coolsreamng [2],PPLve,Thunder,PPSream 等在 P2P 流媒体系统中, 流媒体文件被分成不同的数据块其中, 负责协调多个发送节点的数据块调度算法, 是影响视 * 基金资助 : 受国家自然科学基金项目支持资助 ( )

2 频播放质量的重要因素数据调度算法会直接影响到流媒体的播放质量, 因此受到了广泛关注, 国内外此方面研究成果颇多以最大限度提高视频质量为目的的数据块最优调度问题, 通常是 NP 问题, 大多采用启发式算法解决最优调度问题 [3] [4] 其中, 文献提出了根据节点的动态服务能力特性划分不同的等级, 并且采取随机行走的方式选 [5] 择邻居节点, 但是没有考虑数据块的优先级对邻居节点选择的影响文献提出了根据节点的上行带宽能力来选择邻居节点的方法, 按照上行带宽相似的节点各自划为一类, 优点是提高了带宽的利用率, 但同样 [6] 没有考虑到数据快的稀缺度和紧迫度特性文献提出了启发式算法来选择邻居借点, 但是只考虑了数据 [7] 的稀缺性, 没有考虑数据的紧迫性, 可能导致急需播放的数据块不能优先被请求文献提出了主动负载分担的 P2P 流媒体系统数据调度算法, 该算法有效提高了轻载节点带宽的利用率, 但为考虑数据块优先级的特性针对上述情况, 本文提出了一种基于数据块优先级和负载性能 (Daa-Bloc Prory and Load Capacy, DPLC) 的数据调度算法, 该算法考虑到视频的可变比特率问题, 允许数据块具有不同的大小 ; 同时定义数据块优先级, 评估节点的负载性能, 其中节点负载性能由节点的上行带宽利用率表示 ( 利用率越高负载越高 ) 本文为了方便评估将节点的负载性能, 因此将负载状态分为 3 个等级 (Hgh 状态,Mddle 状态,low 状态 ) Hgh Mddle 和 Low 状态分别依次代表状态代表高负载负载均衡低负载 1 DPLC 算法设计基于数据块优先级与节点负载性能的自适应 P2P 流媒体数据调度算法需要考虑以下问题 :1 选择适当的评估标准对数据块优先级进行评估 ;2 选择适当的评估标准确定节点负载等级 ;3 获取节点实时负载信息以选择邻居节点 ;4 数据块的转移实现高负载节点向低负载节点的数据转移 1.1 数据块优先级和请求频率的评估 P2P 流媒体系统中, 流媒体数据通常分成不同的数据块假设流媒体文件被分割成了大小相同的数据块每个数据块的大小为 M 字节, 由于媒体文件是按照一定的数据块的顺序进行播放, 所以按照播放顺序将各个块分别编号为 1,2,3,, m 其中 S m 表示对应流媒体数据块中的序号为第 m 个数据块另外, 为了反映节点拥有数据块的情况, 每个节点都有相应的滑动窗口 ( 如图一所示 ), 滑动窗口中包含了已播放过的数据块和即将播放的数据块在滑动窗口内, 数据块的可用信息用缓存映像 BufferMap (BM) 来表示,BM 中含有每个数据块的可用性信息, 节点通过 BM 来获知自身所缺失的数据块, 并通过与邻居节点相互交换 BM 得知邻居节点所包含数据块的情况假设节点的滑动窗口的大小为 L 个字节, 是数据块的整数倍, 滑动窗口以外的数据块不在节点请求的考虑范围之内, 所有节点的滑动窗口均以相同的速度向右移动同时为了减少传输开销, 算法利用一个字段来表示数据块信息 : 如果该数据块存在则其值为 1, 否则表示该数据块不存在则其值为 0 滑动窗口错过的数据块播放点已到达数据块缺失的数据块图 1 滑动窗口示意图在 DPLC 算法模型中定义以下参数, 如表 1 所示 DPLC 算法考虑数据块优先级与数据块的稀缺性和紧迫性两个因素相关, 因此给出数据块优先级计算方法如式 (1) 所示 :

3 其中 : D, j A DP (T T ), N (1) B D, j A D B 值越大, 数据块的稀缺度越高 ; (T T ) 值越大, 数据块的紧急度越高 D 数据块的请求频率是某个时间段内该数据块的请求次数, 因此可以给出数据块的请求频率的公式, 如式 (2) 所示 : AF N T 1 N V T, N (2) 其中 : V 表示数据块在单位时间内被请求的次数 ; N 表示总共的单位时间的个数 ; V N T 时间内数据块被请求的总次数符号表 1 参数定义 N 流媒体系统中所有节点的编号, 不包括源节点 (N {1,2,3,,n}) T 定义 M 流媒体文件中数据块的编号 (K {1,2,3,,}) D A 节点在一个调度周期内请求的数据块的集合节点的邻居节点集合 DP 节点缺失的数据块的优先级大小, 其中 D T 节点中数据块的播放时间点, 播放块的编号越大, 播放时间点越靠后, D T 节点的当前播放点的时间 B B AVG UR AF N T V 1.2 节点负载等级的评估 N T 1 表示在节点所要请求的数据块在邻居节点 j 的滑动窗口中是否存在, 存在值为 1, 否则为 0, 其中 D, j A 与 B 定义相反, 即 B 为 0 或 1 时, B 为 1 或 0 全局分布视图上行带宽利用率的平均值节点的上行带宽利用率数据块的请求频率某个时间段的单位时间个数数据块在单位时间内被请求的次数 P2P 流媒体系统中, 若多个节点同时对同一节点发送请求数据, 则导致被请求节点负载过高, 引发请求延时网络拥塞单点失效等情况针对节点异构的网络环境, 本文以上行带宽利用率表示节点负载, 用以下方法对节点负载等级进行评估负载等级分为三个等级 ( Hgh, Mddle, Low ) 首先取全局分布视图上行带宽利用率的平均值 AVG 作为负载等级的参考标准若节点的上行带宽利用率大于 AVG 的两倍, 则定义该节点的负载为 Hgh 等级 ; 若节点的上行带宽利用率小于 AVG 的一半, 则定义该节点的负载为 Low 等级 ; 在 Hgh 与 Low 等级之间的负载为 Mddle 等级 1.3 负载信息的传播每个节点维护一个全局负载分布视图, 节点之间利用 Gossp 协议交换信息基于六度空间理论, 同时考虑系统开销, 限定消息被其他节点转发的次数低于 6 [8] 每个节点维护的全局负载分布视图包含 2 个字段 : <ID, Rae> 其中,ID 和 Rae 分别表示该记录所对应的节点的标识和上行带宽利用率节点定期根据上行带宽利用率评估自身的负载状态, 从而不断更新自己的负载状态当节点的状态由 Hgh 状态变为 Low 状态或由 Low 状态变为 Hgh 状态时, 该节点就会通过 Gossp 协议向邻居节点传递负载信息每条负载信息包含

4 5 个字段 :<ID, Rae, Avalable_mgran, Reques_mgran, Sep> 其中, 当 Avalable_mgran 的值为 1 表示可以接收数据迁移, 值为 0 表示不接收数据迁移 ; 当 Reques_mgran 的值为 1 表示请求数据迁移, 值为 0 表示没有请求数据迁移 ; Sep 表示负载信息被转发的次数, 只将 Sep<6 的负载信息添加到视图中定义负载信息传播步骤如下 Sep1: 处于 Hgh 状态的 A 节点 ( 高负载节点 ) 查看自身的全局负载分布视图, 找出当前状态为 Low 的节点 ( 低负载节点 ), 并向这些节点发送 Reques _mgran 值为 1 的数据迁移的负载信息, 表示请求数据迁移, 分担负载压力 Sep2: 收到迁移请求负载信息的 B 节点则根据当前的负载状态, 如果当前为 Low 状态则将发送 Avalable_mgran 的值为 1 的负载反馈信息给 A 节点, 表示可以接受数据迁移, 反之, 当前状态为 Mddle 或者 Hgh, 则发送 Avalable_mgran 的值为 0 的负载反馈信息反馈信息给 A 节点, 表示不接受数据迁移 Sep3: 高负载节点 A 在收到负载反馈信息后, 根据 DPLC 算法的负载迁移策略选择相应的低负载节点发送数据块, 根据 DPLC 算法在自身数据请求列表中查找对数据块优先级要求比较高的请求, 并查看这些低负载节点的缓存映像中是否有该数据请求所需的数据, 如果没有就在全部可用的备选节点中选择数据迁移的目标结点, 把所请求的数据迁移到目标节点中. 循环往复, 直到节点自身的负载状态改变或者邻居节点的负载为 Hgh 状态 1.4 负载迁移过程在整个 P2P 系统中, 如图二所示, 由于多个节点 C D E F 同时向 B 节点发送数据请求,B 节点向它们发送所请求的数据块, 导致自身负载不断升高采用 DPLC 算法后,B 节点会选择向低负载邻居节点 A 发送 C 节点请求的优先级较低的数据块以及 B 节点中被请求频率较高的数据块, 然后通过 A 节点向 C 节点推送 C 请求的数据块, 以此来减少高负载节点 B 的负载压力, 从而实现整个系统的负载均衡为了保证流媒体流畅播放, 数据块要在播放之前按照一定的顺序到达, 因此数据块具有时效性因此算法选择负载迁移请求完成时间最小的节点 A 作为迁移的目标节点根据节点之间的负载信息传送的延时节点处理负载信息所花费的时间可给出负载迁移请求完成的时间, 如式 (3) 所示 j j j j AT D H,, j N (3) 其中, AT 表示从节点发送给节点 j 负载迁移请求到节点接收到反馈的时间 D 表示负载迁移请求的传输延时 H 表示节点 j 的请求处理时间 j j D 节点 A 节点 ( 低负载 ) B 节点 ( 高负载 ) F 节点 C 节点 E 节点 2 基于 PeerSm 的仿真与分析 2.1 仿真环境的搭建及参数设置图 2 负载迁移示意图

5 负载均衡指数为验证算法的性能, 本文采用 PeerSm (Peer-o-Peer Smulaor) 作为本次实验的仿真平台, 同时利用 GT- ITM 拓扑产生器构造物理网络拓扑结构 PeerSm 仿真器采用组件机制, 便于实现新的协议 ; 仿真的硬件环境是一台酷睿 2 双核 CPU( 主频 2.53GHz) 处理器 4GB 内存 64 位 Wn7 操作系统的 IBM 笔记本实验中算法的仿真环境参数按照表 2 进行设置, 系统随机产生 400 个数据请求, 每个节点的邻居节点为 20 个, 初始的数据请求指向系统的 40% 的节点, 将本文提出的 DPLC 算法与局部最少优先 (Local Rares Frs, LRF) [9] 算法进行仿真实验对比表 2 仿真参数定义参数名设定值单位跟踪服务器 1 个系统节点总数 1500 个数据块总数 5 邻居节点 20 个节点之间的带宽 10 Gbps 数据块大小 256 KB 滑动窗口大小 200 带宽统计时间 15 S 10 个 2.2 算法性能分析如图 3 所示,DPLC 算法的负载均衡要优于 LRF 算法, 因为 LRF 算法是根据数据块局部最少优先原则, 优先请求数据块集中的少数节点, 因此没有考虑节点负载情况, 造成系统的负载分布不均衡而 DPLC 算法将高负载节点的数据块推送到低负载节点上, 再由低负载节点推送到请求节点上, 以此减轻高负载节点的负载压力, 使部分负载分担到低负载节点上, 从而使节点间的负载均衡 LRF DPLC 比特率 (bps) 图 3 系统负载均衡比较如图 4 所示, 可以得出 DPLC 算法在吞吐量方面与 LRF 算法相比有所提高, 通过分析系统仿真运行时产生的日志, 可以得知 :LRF 算法使得拥有最少数据块的节点很容易负载过重而成为网络瓶颈, 造成系统负载不均衡同时还浪费了网络带宽 [8] 当 DPLC 算法向含有最少数据块的邻居节点请求数据时, 如果邻居节点为低负载状态, 节点发送请求数据给请求节点, 如果邻居借点为高负载状态, 此时, 节点将被请求数据块推送给相应的低负载节点, 再有低负载节点推送给请求节点, 这样就提高了系统的带宽利用率, 从而提高了整个系统的吞吐量

6 节点吞吐量 (bps) LRF DPLC 节点的编号 3 结语图 4 节点吞吐量的比较本文主要分析未充分利用数据块优先级和节点高负载导致缓冲延时长和带宽利用率低的相关数据调度算法策略通过分析, 根据数据块优先级和节点之间的负载性能的差异提出基于数据块优先级和负载性能的自适应 P2P 流媒体数据调度算法算法综合考虑了流媒体传输调度过程中的数据块的稀缺程度和紧迫程度以及邻节点负载能力等因素, 对高负载节点通过将自身被请求优先级高的数据块及请求频率高的数据块推送至低负载节点, 从而有效解决了访问热点问题引发的负载失衡问题和缓冲时延长问题通过仿真实验, 证明 DPLC 算法在系统负载均衡和系统吞吐量方面比 LRF 算法更加优越 REFERENCES [1] L Hao, Wang NngJun. Research on IPTV Based on Peer-o-Peer Newor, 2007 (6): [2] Zhang X, Lu J, L B, e al. CoolSreamng/DONe: A Daa-Drven Overlay Newor for Peer-o-Peer Lve Meda Sreamng[C] INFOCOM h Annual Jon Conference of he IEEE Compuer and Communcaons Socees. Proceedngs IEEE. IEEE, 2005, 3: [3] Le We, Zheng Quan. Conex-Aware Adapve Daa Schedulng Algorhm for P2P Sreamng Meda [J]. Compuer Applcaons and Sofware, 2012, 29(9). [4] Feng Zhenan, N Hong, Wang Jnln, You Jal. Adapve Neghbor Selecon Mehod for The P2P Meda Sreamng Sysem [J]. Journal of Xdan Unversy, 2012, 39(3): [5] Endo R, Taayama K, Saaa Y, e al. Neghbor Selecon Mehod Based on Sendng Capacy for P2P Lve Sreamng wh Layer Codng[C]//Ubquous Inellgence & Compung and 9h Inernaonal Conference on Auonomc & Trused Compung (UIC/ATC), h Inernaonal Conference on. IEEE, 2012: [6] Zhang, Meng, e al. "MMC03-4: On he Opmal Schedulng for Meda Sreamng n Daa-drven Overlay Newors." Global Telecommuncaons Conference, GLOBECOM'06. IEEE. IEEE, [7] Wen Qongfe, Zhu Yanqn, J Qn. A Daa Schedulng Algorhm Based on Acve Load Sharng n P2P Meda Sreamng Sysem [J]. Journal of Jangsu Unversy of Scence and Technology (Naural Scence Edon, 2012, 26(02): [8] Meng Xanfu, Chen Xaolng. Sraegy for Hospo Load Dynamc Mgraon n Srucured P2P Newor [J]. Aca Elecronca Snca, 2011, 39(10): [9] Tan Y, Wu D, Ng K W. Modelng, Analyss and Improvemen for Borren-Le Fle Sharng Newors[C]//INFOCOM h IEEE Inernaonal Conference on Compuer Communcaons. Proceedngs. IEEE, 2006:

7 作者简介 1 高奥子 (1988-), 男, 汉族, 硕士研究生, 研究方向为 P2P 流媒体传输协议 Emal: @bju.edu.cn 2 张晋豫 (1967-), 男, 汉族, 博士, 教授, 研究方向为计算机网络及通信技术 Emal: zjy@bju.edu.cn

KV-cache 1 KV-cache Fig.1 WorkflowofKV-cache 2.2 Key-value Key ; Key Mem-cache (FIFO) Value Value Key Mem-cache ( Value 256B 100 MB 20%

KV-cache 1 KV-cache Fig.1 WorkflowofKV-cache 2.2 Key-value Key ; Key Mem-cache (FIFO) Value Value Key Mem-cache ( Value 256B 100 MB 20% 38 11 2013 11 GeomaticsandInformationScienceofWuhanUniversity Vol.38No.11 Nov.2013 :1671-8860(2013)11-1339-05 :A GIS Key-value 1 1 1 1 (1 129 430079) : 设计了一种基于 Key-value 结构的缓存 KV-cache 旨在简化数据结构高效管理缓存数据