視頻監控系統中的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.