视频监控系统中的VOD负载均衡改进算法

李 洪,陈耀武

(浙江大学数字技术及仪器研究所,杭州310027)

视频监控系统中的VOD负载均衡改进算法

李 洪,陈耀武

(浙江大学数字技术及仪器研究所,杭州310027)

在传统轻负载优先调度负载均衡算法中,存在用户点播响应时延长且负载均衡度不高的问题。为解决上速问题,提出一种静态负载调度和动态负载迁移相结合的负载均衡算法。静态调度算法采用基于视频点播(VOD)相似度的轻负载优先算法,将相似的点播请求调度至相同的视频点播上,提高VOD的缓存命中率,以缩短点播响应时延。动态负载迁移算法采用基于缓存考虑的REM负载迁移算法,将负载由高载VOD迁移到低载VOD上,以提高负载均衡程度。实验结果表明,在典型城域视频监控系统500路点播规模下,提出的负载均衡算法与传统轻负载优先算法相比,能够缩短17.5%的点播延迟时间,降低53.4%的集群负载方差,提高了系统的负载均衡度。

视频点播;请求调度;负载均衡;负载迁移;轻负载优先;视频监控

1 概述

轻负载优先调度是指客户端的视频点播请求到达时,调度中心将点播请求发送到流媒体服务器集群中负载最轻的媒体服务器上。传统的轻负载优先调度负载均衡算法没有考虑流媒体服务器缓存对用户点播响应时延的影响;也没有考虑用户VCR操作导致集群负载变化对系统负载均衡的影响,往往会造成性能浪费［1］。

本文在轻负载优先调度的基础上,考虑服务器缓存命中率［2］,提出基于视频点播相似度的轻负载优先调度算法。针对用户VCR等操作导致集群负载动态不均衡的情况,采用基于缓存考虑的REM负载迁移算法,以达到负载动态均衡。

2 VOD负载定义

在流媒体服务中,网络数据传输量大,网络带宽往往成为媒体服务器的限制因素［3］,因此,视频点播(Video-on-Demand,VOD)的负载必须考虑网络带宽的利用率。此外,视频监控系统中各个VOD服务器的处理能力和内存不尽相同,在考虑系统负载均衡时,有必要考虑这种服务器处理能力的异构特性。因此,流媒体服务器的负载应当包括VOD的CPU利用率、内存利用率和网络利用率［4］。

对于不同类型的系统应用,以上各个参数的重要程度也有所不同。为了方便在系统运行过程中针对不同的应用,对各个参数的比例进行适当调整,为每一个参数设定一个常量系数∂i,用来表示各个负载参数的重要程度,其中,∑∂i=1。任何一个流媒体服务器节点Ni的负载可以描述为［5］:

考虑缓存的影响,将媒体流分为2大类,一类通过网络从集中存储IPSAN获得,S∈Sipsan,一类是从本地内存获取的流,S∈SMem。对于S∈SMem的流,直接从内存获取,只消耗相应的网络带宽,将流发送给客户端,而对于 S∈Sipsan的流,需要服务器先从IPSAN获取,然后发送给客户端,故是S∈SMem的2倍。因此:

其中,Sj=VBRj/Bordi;VBRj表示 S的当前码率; Bordi表示服务器节点i的网络带宽。

将VOD的负载状态按照负载量分为轻载、适载和过载［6］,负载小于 Loadmin为轻载,负载大于Loadmax为过载,介于两者之间的为适载。

3 评价方法

本文提出的是基于缓存考虑的负载平衡策略。缓存主要影响视频数据的来源,即减小式(2)中S∈Sipsan,增大S∈SMem,故可以降低用户点播请求的时延。可以用服务器集群负载的平均方差λ的大小来衡量系统负载均衡程度。λ的值由式(3)计算。λ的大小一定程度上反映了系统的动态均衡情况,λ越小,说明系统的负载越均衡;反之,系统负载越不均衡［7］。

因此,可以从点播请求的平均响应时间和服务器集群负载的平均方差λ来衡量负载均衡算法的可用性。

4 VOD负载均衡改进算法

针对轻负载优先调度负载均衡算法,没有考虑流媒体服务器缓存命中率,导致大规模视频监控系统中用户点播响应时延长、负载均衡度不高的问题,本文综合考虑流媒体缓存和集群整体负载平衡,提出了一种静态负载调度和动态负载迁移相结合的负载均衡算法［8］。其中,静态负载调度算法［9］采用基于视频点播相似度的轻负载优先调度算法,它通过将同一摄像机相似的点播请求调度至相同VOD上,提高VOD的缓存命中率,以缩短点播响应时延;动态负载迁移算法采用基于缓存考虑的REM负载迁移算法,动态调整各服务器的负载,将负载由高载服务器迁移到低载服务器上,实现负载动态均衡［10］。

4.1 基于视频点播相似度的轻负载优先调度算法

视频监控系统中视频点播服务主要是以摄像机为对象的录像回放业务,摄像机编号和录像开始时间可以唯一确定一路点播请求。为了提高VOD服务器缓存命中率,可以将相近的点播请求调度至相同VOD上。目前,VOD普遍采用的是分段缓存策略,点播请求的开始时间与当前视频播放的时间越接近,缓存命中率越高［11］。为表征当前点播请求和VOD服务器已点播视频的相似程度,引入点播相似度FD,FD由式(4)计算得到。

其中,f(x)定义如下:

其中,T表示点播请求开始时间;Tmin表示缓存一定能命中的时间差;Tmax表示缓存一定不命中的时间差;M表示当前在回放该摄像机录像的VOD总数; Ti表示在当前VOD上播放的第i路视频的录像开始时间。

VOD周期性地向中心调度服务器发送负载信息,调度服务器为每个VOD维护负载数据(VOD_ID, Load,Bord),其中,VOD_ID表示VOD的编号;Bord是VOD的网络带宽;Load是按照式(1)计算出来的负载值。调度服务器还维护正在点播的节目数据(Camera_ID,VOD_ID,StartTimeList),其中,Camera_ ID为摄像机编号;VOD_ID是VOD服务器编号; StartTimeList表示各个录像的回放开始时间。

调度服务器接收客户端的视频点播请求,请求信息Req(Camera_ID,BeginTime)。Camera_ID是需要点播的摄像机编号,BeginTime为录像开始时间,具体调度算法描述如下:

Step 1 令VOD集群构成集合A,选择包含该Camera_ID的所有VOD组成集合B。

Step 2 如果集合A=1,则算法结束,点播请求被拒绝。如果集合B=1,则在A中选择负载最小的VOD为VODtmp,跳到Step4。

Step 3 如果集合B=1,按照式(4)计算FD值,并选取有最大FD的VOD作为VODtmp,进入下一步。

Step 4 估算请求调度到VODtmp之后的负载Load及其状态,如果是轻载状态,则进入下一步;如果是过载状态,则将VODtmp从A和B中删除,跳到Step2;如果是适载状态,则判断Load和当前集群中最小负载的差值有没有大于LD,若大于则将VODtmp从A和B中删除,跳到Step2,否则进入下一步。

Step 5 将调度请求发送给VODtmp,同时使用负载估算值更新VODtmp的负载值,以减少并发调用时, VOD未及时反馈负载信息的影响。

上述算法中LD表示系统允许的最大负载差值。算法估算负载时,增加的负载可仅仅考虑网络带宽的影响,由视频流的码率和VOD的带宽Bord不难估计该值。

4.2 基于缓存考虑的REM负载迁移算法

用户快进、快退等VCR操作,会造成用户点播的视频流码率变化,可能导致负载已经平衡的系统变为不均衡,甚至导致部分处于轻载或适载状态的VOD变为过载,影响服务质量。因此,在系统因VCR操作导致系统负载变化时,需要动态迁移负载,重新实现负载均衡。定义二次平均负载σ:

按二次平均负载σ将所有VOD节点分为3类: (1)高载节点类,其负载大于σ的;(2)饱和节点类,其负载恰好等于σ的;(3)低载节点类,负载小于σ的。发生负载迁移时,负载由高载节点类最终迁移到的轻载节点类［7］。

文献［12］提出了一种REM负载迁移算法,定义了低于服务能力上限的2个负载阈值,把迁移触发时机提前了很多,负载检测程序对比当前的负载和负载迁移上下限阈值,得到一定的迁移概率,如图1所示,并按照这个概率触发迁移流程。

图1 REM负载迁移概率

由图1可知迁移概率:

当VOD因为用户VCR操作导致服务器负载变化时,VOD将实时负载状态发送给调度服务器,调度服务器按下述算法对集群进行动态负载均衡。

动态负载迁移算法描述如下:

Step 1 按照式(6)计算二次平均负载σ,判断当前VOD是低载节点还是高载节点。如果是低载类节点,则无需迁移负载,算法结束;否则进入Step2。

Step 2 所有低载VOD构成集合A。从需要迁移的VOD中选择FD最小的Camera_ID,A中包含Camera_ID的VOD构成集合B。按照式(7)计算迁移概率p,p概率进入下一步,1-p概率则结束算法。

Step 3 若A=1,则算法结束,不进行任何负载迁移。若B=1,则从A中选择负载最小的VOD为VODtmp,跳转到Step5。

Step 4 若B=1,从B中选择FD最大的VOD为VODtmp。

Step 5 估算该路视频到VODtmp后,VODtmp的负载状态,若负载为过载状态,则将VODtmp从集合A和B中删除,跳转到 Step3;否则将负载迁移到VODtmp,进入下一步。

Step 6 使用负载估算值更新调度服务器中迁入迁出VOD的负载值,然后跳转到Step1。

5 实验结果与分析

基于青海省同德县治安监控项目对算法进行测试。其系统结构如图2所示。

图2 实验系统结构

集群系统包含1个调度中心服务器,5个VOD服务器,50个点播客户端,点播回放的录像段来自80个摄像机,每个摄像机5段录像,平均码率为2 Mb/s。服务器配置情况:戴尔PowerEdge R210,内存2 GB,千兆以太网,Centos6.0操作系统;采用DotHill3331 12盘位的IPSAN。并取∂1为0.1,∂2为0.2,∂3为0.7,Tmin为100 ms,Tmax为10 s,Loadmin为50,Loadmax为95,Pmax为0.8,LD为30。

实验时等概率选择摄像机和录像段,点播完后,随机选择其中20%做2倍速快放,10%做3倍速快放,10%做1/2倍速慢放,其他正常速度播放。

实验测试了采用轻负载优先调度策略和本文提出的负载均衡算法情况下,系统平均点播响应延时时间,如图3所示,以及集群负载的平均方差λ,如图4所示。

图3 点播响应时延随点播路数的变化

图4 集群负载方差随点播路数的变化

本文的请求调度算法将相近的点播请求发送到相同的VOD,使得点播时部分视频流的启动数据直接从VOD内存获取,可以缩短点播响应时延。从图3可以看出,本文算法在典型城域视频监控系统规模500路点播数时,同轻负载优先算法相比,能够缩短17.5%的点播响应延时,并且随着点播路数的继续增大,缩短的响应延时时间更长。

本文的负载迁移算法在VOD负载大于Loadmin时才会进行负载迁移,因此,点播路数低于300路时,集群负载方差大于轻负载优先算法。当负载大于Loadmin时,本文负载迁移算法会将负载由高载节点迁移到低载节点,实现负载动态均衡,因此,点播路数大于300路时,本文算法比轻负载优先算法有更小的集群负载方差。随着点播路数增大,两者集群方差比值越大,即随着点播路数的增大,本文算法能够到达更好的负载均衡程度。

6 结束语

本文提出一种静态负载调度和动态负载迁移相结合的负载均衡算法。其中静态负载调度算法采用基于视频点播相似度的轻负载优先调度算法,它通过将同一摄像机相似的点播请求调度至相同VOD上,以此提高VOD的缓存命中率,缩短了点播响应时延;动态负载迁移算法引入基于缓存考虑的REM负载迁移算法,将负载由高载服务器迁移到低载服务器上,实现了负载的动态均衡。实验结果表明,在典型城域视频监控系统中,本文算法能够有效缩短点播延迟时间,降低集群负载方差,达到了更高的负载均衡度。

［1］ 刘 侃.大规模流媒体服务器集群负载均衡研究［D］.合肥:中国科学技术大学,2008.

［2］ Chandra P K,Sahoo B.Performance Analysis of Load Balancing Algorithms for Cluster of Video on Demand Servers［C］//Proceedings of IEEE International Conference on Advance Computing.［S.l.］:IEEE Press,2009:408-412.

［3］ Vinay A,Bharath K,Saxena P,et al.Bandwidth Aware Load Balancing and OptimalBandwidth Allocation Techniques forVideo-on-Demand Systems［C］// Proceedings of IEEE InternationalConference on Communication Control and Computing Technologies.［S.l.］:IEEE Press,2010:425-430.

［4］ Moghal M R,Mian M S.Efficient Load Balancing in Distributed Video-on-Demand Multimedia System［C］// Proceedings of the 7th InternationalMultiTopic Conference.［S.l.］:IEEE Press,2003:164-169.

［5］ 刘康珍,杨格兰,张杰良,等.基于并行遗传算法的分布式VOD系统负载均衡研究［J］.计算机应用与软件,2009,26(9):46-54.

［6］ 李冬梅,施海虎.负载平衡调度问题的一般模型研究［J］.计算机工程与应用,2007,23(8):121-125.

［7］ 吴 伟.流媒体服务器迁移技术研究［D］.合肥:中国科学技术大学,2009.

［8］ Huang Yinfu,Fang C C.Load Balancing for Clusters of VOD Servers［C］//Proceedings of Conference on Internet and Multimedia Systems and Applications.［S.l.］:ACTA Press,2004:113-138.

［9］ 黄 河,周功业.分布式视频服务器及其负载均衡方法［J］.计算机工程与科学,2006,28(9):44-46.

［10］ Guo Jun,Wong W M,Chan S,et al.Combination Load Balancing for Video-on-Demand Systems［J］.IEEE Transactionson Circuits and Systems for Video Technology,2008,18(7):937-948.

［11］ 马 杰,樊建平.具有高缓存写入效率的流媒体分段缓存方法［J］.计算机学报,2007,30(4):588-595.

［12］ Zhao Yinqing,Kuo C C J.Video-on-Demand Server System Design with Random Early Migration［C］// Proceedings of International Symposium on Circuits and Systems.［S.l.］:IEEE Press,2005:640-643.

编辑 顾逸斐

Improved VOD Load Balancing Algorithm in Video Surveillance System

LI Hong,CHEN Yaowu
(Institute of Digital Technology and Instrument,Zhejiang University,Hangzhou 310027,China)

To solve the problem that the traditional minimum-load-priority load balancing algorithm has quite long response time of requests and low load balance degree,this paper proposes a load balancing algorithm which is the combination of static load scheduling and dynamic load migration.To reduce the response time of requests,a static load scheduling algorithm is used,which is based on the similarity of video requests.The algorithm aims to make full use of caching capacity on Video-on-Demand(VOD)by scheduling similar requests to the same VOD.The dynamic load migration algorithm,which is based on cache considering REM load migration,aims to improve the load balance degree by migrating load form high load VOD to low load VOD.By practical test,it proves that this algorithm can reduce the response time of requests by 17.5% and cluster load variance by 53.4% comparing with minimum-load-priority algorithm at typical scale of metro video surveillance system under the number 500 requests.

Video-on-Demand(VOD);request schedule;load balancing;load migration;minimum-load-priority; video surveillance

1000-3428(2014)11-0241-04

A

TP301.6

10.3969/j.issn.1000-3428.2014.11.048

国家自然科学基金资助项目(40927001)。

李 洪(1988-),男,硕士研究生,主研方向:视频监控,网络多媒体技术;陈耀武,教授、博士生导师。

2013-11-25

2013-12-22E-mail:lihongzju@gmail.com

中文引用格式:李 洪,陈耀武.视频监控系统中的VOD负载均衡改进算法［J］.计算机工程,2014,40(11):241-244.

英文引用格式:Li Hong,Chen Yaowu.Improved VOD Load Balancing Algorithm in Video Surveillance System［J］.Computer Engineering,2014,40(11):241-244.