趙輝,鄭慶華,張未展,李珍艷,葉舒雁

(1.西安交通大學(xué)計算機科學(xué)與技術(shù)系,710049,西安;2.陜西省天地網(wǎng)技術(shù)重點實驗室,710049,西安)

?

多版本視頻點播流媒體服務(wù)器集群資源分配方法

趙輝1,2,鄭慶華1,2,張未展1,2,李珍艷1,2,葉舒雁1,2

(1.西安交通大學(xué)計算機科學(xué)與技術(shù)系,710049,西安;2.陜西省天地網(wǎng)技術(shù)重點實驗室,710049,西安)

針對大規(guī)模移動學(xué)習(xí)應(yīng)用背景下流媒體服務(wù)器集群資源分配過量或不均的問題,提出了一種面向移動學(xué)習(xí)系統(tǒng)的多版本視頻點播流媒體服務(wù)器集群資源分配方法。該方法通過用戶歷史點播行為日志分析,挖掘在不同終端環(huán)境下用戶點播行為的特征和規(guī)律,在此基礎(chǔ)之上,采用排隊論理論進行多版本視頻點播中流媒體服務(wù)器集群資源分配建模,并通過實時預(yù)測用戶請求到達率的變化情況,動態(tài)調(diào)整資源的分配,從而實現(xiàn)了集群資源的動態(tài)配置。實驗結(jié)果表明,所提方法的平均服務(wù)拒絕率和資源利用率分別在1%和80%左右,既保證了用戶體驗滿意度,又降低了系統(tǒng)服務(wù)成本。

移動學(xué)習(xí)系統(tǒng);多版本視頻點播;用戶行為分析;排隊論;資源分配

隨著移動通信技術(shù)以及智能終端的發(fā)展,人們可以在移動設(shè)備上訪問視頻資源,推動了傳統(tǒng)的數(shù)字化學(xué)習(xí)(e-Learning)向移動學(xué)習(xí)(m-Learning)的轉(zhuǎn)變。由于終端分辨率、屏幕大小的不同和網(wǎng)絡(luò)的不同,需要為用戶提供不同碼率、分辨率的視頻流,即多版本視頻點播。多版本視頻點播的研究有以下幾種:①可分級視頻編碼技術(shù)[1];②實時視頻轉(zhuǎn)碼[2];③預(yù)存儲多版本視頻[3];④平衡視頻存儲和轉(zhuǎn)碼[4],少量的熱點視頻存儲多個版本,大量的非熱點視頻存儲高質(zhì)量版本,通過實時轉(zhuǎn)碼技術(shù)提供低質(zhì)量版本的點播。

正是在這種平衡視頻存儲與轉(zhuǎn)碼的多版本視頻點播背景下,移動學(xué)習(xí)系統(tǒng)需要分配轉(zhuǎn)碼計算資源和帶寬資源。本文提出了一種面向移動學(xué)習(xí)系統(tǒng)的多版本視頻點播流媒體服務(wù)器集群資源分配方法。首先,分析移動學(xué)習(xí)用戶歷史點播行為日志,挖掘用戶點播行為的特征和規(guī)律,建立用戶視頻點播行為模型。其次,采用排隊論理論進行多版本視頻點播流媒體服務(wù)器集群資源分配建模,并根據(jù)用戶到達率的變化情況動態(tài)地調(diào)整集群資源的分配。

1 相關(guān)工作

目前資源分配方法的研究分為:基于控制論的方法、基于性能模型的方法及基于負載預(yù)測的方法。

(1)基于控制論的方法。文獻[5]開發(fā)了一個管理框架為虛擬化應(yīng)用自動分配資源。文獻[6]通過經(jīng)典反饋控制論為系統(tǒng)提供服務(wù)質(zhì)量保證的資源分配方法。它們都依靠底層服務(wù)器系統(tǒng)的性能,適用于面向網(wǎng)頁鏈接等短時占用資源的應(yīng)用,不適用于流媒體點播持續(xù)性占用資源的應(yīng)用。

(2)基于性能模型的方法。文獻[7]提出基于群體智能的方法來決定服務(wù)器資源分配策略和作業(yè)調(diào)度方法,將資源分配問題模擬為生態(tài)現(xiàn)象,采用將混合離散粒子群體優(yōu)化與進化博弈論相結(jié)合的方法選擇性能適合的虛擬機。文獻[8]提出了一種動態(tài)資源縮放方案,利用前端負載平衡器統(tǒng)計活動會話,根據(jù)當前在線用戶活動會話的數(shù)量分配資源,在資源自動配置的基礎(chǔ)上根據(jù)當前活動會話的數(shù)量動態(tài)縮放虛擬機資源。由于流媒體點播需求具有較大的波動性,這類方法難以確定流媒體應(yīng)用中實時的性能閾值,無法準確地分配所需的資源。

(3)基于工作負載預(yù)測的方法。文獻[9]預(yù)測每個應(yīng)用程序?qū)淼呢撦d情況,以及預(yù)測每一個虛擬機將來的性能,然后分配每個應(yīng)用的資源量。文獻[10]通過跟蹤分析數(shù)據(jù)中心的應(yīng)用運行日志,提出基于馬爾可夫模型的工作負載模式,以時間相關(guān)性為特點,描述了虛擬機集群與工作負載模式的變化規(guī)律,進而根據(jù)工作負載模型預(yù)測應(yīng)用所需資源。這類方法的主要挑戰(zhàn)在于如何確定良好的預(yù)測模型,提出的工作負載模型復(fù)雜度特別高,不容易應(yīng)對用戶請求的實時變化,無法體現(xiàn)移動學(xué)習(xí)視頻點播應(yīng)用類型的工作負載規(guī)律。

綜上,已有的資源分配方法研究均未考慮移動學(xué)習(xí)系統(tǒng)及多版本視頻點播系統(tǒng)的特殊性,也未考慮如何利用用戶行為分析來分配資源。

2 流媒體服務(wù)器集群資源分配方法

視頻點播服務(wù)過程如圖1所示,一般可描述為排隊系統(tǒng)[11]。本文通過對歷史點播行為日志進行分析,得到排隊論所需的各個參數(shù)。

圖1 視頻點播服務(wù)過程圖

2.1 用戶點播行為分析

本文采用西安交通大學(xué)網(wǎng)絡(luò)教育學(xué)院移動學(xué)習(xí)系統(tǒng)的日志數(shù)據(jù),選取了從2014年12月1日至2015年1月31日期間產(chǎn)生的所有日志文件,共計0.98 GB。數(shù)據(jù)預(yù)處理后共有日志92 632條,其中電腦端日志66 424條,移動端日志26 208條,總課程數(shù)5 142節(jié)。

用戶請求到達率:選取若干天的點播日志進行統(tǒng)計,將1 min作為單位時間,計算單位時間內(nèi)用戶請求到達個數(shù),統(tǒng)計到達個數(shù)出現(xiàn)的概率。圖2為統(tǒng)計的用戶請求到達率分布,可以看出用戶請求到達率的分布近似于泊松分布[12]P(X=i)=(λi/i!)·e-λ,i=0,1,2,…。

圖2 用戶請求到達率的分布圖

視頻點播熱度分布為通過統(tǒng)計點播日志得出的所有視頻的點播熱度分布,呈現(xiàn)出明顯的“長尾”效應(yīng),如圖3所示。相關(guān)研究多使用Zipf-like分布[13]描述為

式中:pi表示視頻i的點播概率;si為視頻i的點播次數(shù);S為所有視頻的點播總次數(shù);M為視頻總數(shù);θ為分布參數(shù)。

圖3 視頻點播熱度分布圖

圖4 學(xué)習(xí)時長的分布

單個請求所占帶寬資源可根據(jù)每個視頻的每個版本的點播概率以及相應(yīng)的視頻碼率計算得到,一個點播請求所需占用的平均帶寬資源可表示為R=E[ri]=∑pi,jri,j,其中pi,j為第i個視頻的第j個版本的點播概率,ri,j為其碼率。

對于實時轉(zhuǎn)碼,不同碼率、分辨率的視頻之間轉(zhuǎn)碼所需的計算資源不同,版本i轉(zhuǎn)到版本j的轉(zhuǎn)碼權(quán)重為wi,j,可通過統(tǒng)計CPU利用率得到。所需的轉(zhuǎn)碼計算資源U=E[wi]=∑pi,jwi,j,則單位CPU能夠同時并發(fā)執(zhí)行的轉(zhuǎn)碼任務(wù)數(shù)為V=1/U。

用戶平均等待時長指從用戶發(fā)出點播請求開始,到服務(wù)器分配資源開始服務(wù)為止的這段時長。本文中,用戶平均等待時長是已知約束條件。

2.2 集群資源分配方法

采用排隊論模型建立集群資源分配的思路為:首先,訓(xùn)練不同的用戶請求到達率情況下的資源需求量;其次,預(yù)測用戶請求到達率的變化情況;最后,根據(jù)訓(xùn)練結(jié)果和用戶請求到達率,實時動態(tài)調(diào)整資源的分配。

2.2.1 排隊論模型訓(xùn)練 使用排隊論將該問題描述為用戶請求到達率服從參數(shù)為λ的泊松分布,實時轉(zhuǎn)碼的請求數(shù)占所有到達的請求數(shù)的比例為?(轉(zhuǎn)碼部分請求到達率服從參數(shù)為?λ的泊松分布),集群服務(wù)率為μ,請求服務(wù)時間是平均值為1/μ的一般分布,一個點播請求所需占用的平均帶寬資源為R,單位CPU能夠同時開啟的轉(zhuǎn)碼任務(wù)數(shù)為V,用戶平均等待時長為T時,計算至少需要分配的帶寬資源和計算資源?？捎肕/G/n排隊論模型[15]描述該問題,則請求等待概率為

(1)

隊列中正在等待的請求平均個數(shù)(隊列長度)

(2)

給定M/G/n排隊論模型相關(guān)參數(shù)后,分別采用逐步逼近法求出所需的服務(wù)器并行流化服務(wù)能力n1和并行轉(zhuǎn)碼能力n2。一個點播請求所需占用的平均帶寬資源為R,單位CPU能夠同時開啟的轉(zhuǎn)碼任務(wù)數(shù)為V,故所需的帶寬資源為B=n1R,所需的轉(zhuǎn)碼計算資源為C=n2/V。

2.2.3 動態(tài)資源分配 若用戶點播請求持續(xù)增加,當用戶點播請求到達率達到某種情況時,需及時地新增虛擬機,使其加入該集群提供服務(wù)。若用戶點播請求持續(xù)降低,集群資源利用率也會隨之降低,則需要回收虛擬機,其思路如下:

步驟1 維護最近n個統(tǒng)計時間段內(nèi)的請求到達率;

步驟2 若當前用戶請求到達率達到系統(tǒng)所能服務(wù)的最大到達率的1/2時,或當前用戶請求到達率降低到集群減少一臺虛擬機之后仍能滿足服務(wù)時,根據(jù)當前保存的請求到達率集合,利用二次指數(shù)平滑預(yù)測法來預(yù)測用戶請求到達率;

步驟3 若請求到達率呈降低趨勢,則需回收一臺虛擬機,使其撤出服務(wù)集群,此時選擇資源利用率最低的虛擬機作為待回收虛擬機提交給調(diào)度節(jié)點,調(diào)度節(jié)點將該虛擬機已有的請求遷移至其他虛擬機后,回收該虛擬機,并將其移出集群;

步驟4 若請求到達率呈現(xiàn)增長趨勢,則預(yù)測一段時間(虛擬機啟動延遲)后的用戶請求到達率,若其不小于集群所能承載的最大到達率,則新增虛擬機,并將其加入流媒體服務(wù)器集群。

3 實驗結(jié)果與分析

實驗數(shù)據(jù)采用西安交通大學(xué)網(wǎng)絡(luò)教育學(xué)院移動學(xué)習(xí)系統(tǒng)的日志數(shù)據(jù),實驗中的參數(shù)都是通過用戶點播歷史日志分析所得。本文從資源利用率和服務(wù)拒絕率兩個指標驗證分配的資源是否合適。

帶寬資源利用率Ub=b/B,計算資源利用率Uc=c/C。其中:b為已消耗的帶寬,B為分配的總帶寬;c為執(zhí)行轉(zhuǎn)碼任務(wù)的CPU核數(shù),C為分配的CPU總核數(shù)。

服務(wù)拒絕率J為視頻點播過程中由于請求在隊列中的等待時長超過最大限定值Twait而被系統(tǒng)拒絕的請求數(shù)量與到達的總請求數(shù)量之比,計算公式為J=nreject/ntotal。

3.1 排隊論模型訓(xùn)練結(jié)果分析

在第一個實驗中,首先限定請求等待時長為5 s,使用排隊論模型分別訓(xùn)練在不同的用戶請求到達率(個/s)的情況下,需要為系統(tǒng)分配的帶寬資源和CPU計算資源,結(jié)果如圖5所示。在第2個實驗中,設(shè)置用戶請求到達率為1個/s,通過改變平均等待時長從1 s到59 s,分別訓(xùn)練得到為系統(tǒng)分配的帶寬資源和CPU計算資源,結(jié)果如圖6所示。

由圖5、圖6可以看出:隨著請求到達率的增高,所需的帶寬資源和計算資源都逐步增大;隨著平均等待時長的增大,所需的資源逐步減少。

(a)請求到達率與帶寬資源的關(guān)系

(b)請求到達率與CPU資源的關(guān)系圖5 請求到達率與分配資源的關(guān)系

(a)平均等待時長與帶寬資源的關(guān)系

(b)平均等待時長與CPU資源的關(guān)系圖6 平均等待時長與分配資源的關(guān)系

(a)用戶請求到達率與服務(wù)拒絕率的關(guān)系

(b)用戶請求到達率與資源利用率的關(guān)系圖7 不同用戶請求到達率下的服務(wù)拒絕率和資源利用率

本文使用服務(wù)拒絕率與資源利用率來驗證資源分配是否合理。以帶寬資源為例,選取集群帶寬為200、400、600 Mb/s,并限定平均等待時長為5 s時,服務(wù)拒絕率和資源利用率的情況如圖7所示。由圖7可以看出:在系統(tǒng)帶寬資源為200 Mb/s時,當請求到達率小于0.5個/s,系統(tǒng)服務(wù)拒絕率較低,當請求到達率超過0.5個/s時,系統(tǒng)服務(wù)拒絕率開始出現(xiàn),并呈現(xiàn)快速上升趨勢;同樣,當用戶請求到達率小于0.5個/s時,資源利用率未到100%,而當請求到達率超過0.5個/s時,資源利用率幾乎達到100%。如圖5a所示,帶寬為200 Mb/s可服務(wù)的請求到達率最大值為0.62,與圖7中服務(wù)拒絕率和資源利用率出現(xiàn)拐點所對應(yīng)的請求到達率基本一致。同樣,當帶寬為400、600 Mb/s時,服務(wù)拒絕率和資源利用率出現(xiàn)拐點所對應(yīng)的請求到達率與圖5a中的結(jié)果也基本一致,說明本文分配的資源是合適的。

若限定請求到達率為1個/s,請求隊列平均等待時長t從1 s到60 s,當帶寬分別為100、200、300 Mb/s時,服務(wù)拒絕率和資源利用率情況如圖8所示。可以看出,當帶寬為100、200和300 Mb/s時,為使系統(tǒng)的服務(wù)拒絕率為0,則需要最小的平均等待時長分別為50、32和6 s,而圖6a中100、200和300 Mb/s帶寬可滿足的平均等待時長分別為52、35和5 s,它們基本上保持一致,說明我們分配的資源是合適的。

3.2 動態(tài)資源分配結(jié)果分析

用戶的點播次數(shù)隨時間具有較大的波動性,隨著用戶請求到達率的變化,系統(tǒng)需要進行動態(tài)資源分配,以實時調(diào)整集群資源量。圖9為某50 h隨著請求到達率的變化而動態(tài)調(diào)整集群資源量的變化情況,圖10為對應(yīng)的服務(wù)拒絕率和資源利用率。

(a)平均等待時長與服務(wù)拒絕率的關(guān)系

(b)平均等待時長與資源利用率的關(guān)系圖8 不同平均等待時長的服務(wù)拒絕率和資源利用率

圖9 動態(tài)帶寬分配

圖10 動態(tài)資源利用率和服務(wù)拒絕率

由圖10可見,隨著用戶請求到達率的變化,系統(tǒng)的服務(wù)拒絕率基本都很低,同時資源利用率基本在60%以上,平均拒絕率和資源利用率在1%和80%左右。當請求到達率經(jīng)過3個持續(xù)增大與減小過程時,系統(tǒng)帶寬資源量呈現(xiàn)出相同的變化趨勢。資源利用率在3個時刻出現(xiàn)100%的情況,而在相同的時刻,也出現(xiàn)了服務(wù)拒絕率10%左右的現(xiàn)象,這是因為在這3個時刻請求到達率持續(xù)變大,而此時新分配的資源還未加入服務(wù)。同理,在請求到達率持續(xù)變小時,可以看到資源利用率和服務(wù)拒絕率都比較低,這是由于分配的過多的資源還未及時回收。

4 結(jié) 論

本文以移動學(xué)習(xí)為應(yīng)用背景,針對多版本視頻點播系統(tǒng)提出了一種面向移動學(xué)習(xí)系統(tǒng)的多版本視頻點播流媒體服務(wù)器集群資源分配方法。通過分析用戶點播日志數(shù)據(jù),挖掘用戶點播行為規(guī)律與特征,建立用戶點播行為模型,采用排隊論模型來訓(xùn)練不同的用戶請求到達率情況下所需的資源,并實時預(yù)測用戶請求到達率變化情況,從而動態(tài)地為集群分配資源。最后,通過資源利用率和服務(wù)拒絕率兩個指標來驗證了所提方法的正確性和有效性。下一步我們將進一步挖掘移動用戶的行為特征,并豐富我們的資源分配方法。

[1] ZHU Zuqing, LI Suoheng, CHEN Xiaoliang. Design QoS-aware multi-path provisioning strategies for efficient cloud-assisted SVC video streaming to heterogeneous client [J]. IEEE Transactions on Multimedia, 2013, 15(4): 758-768.

[2] HSU T, LI Y. A weighted segment-based caching algorithm for video streaming objects over heterogeneous networking environments [J]. Expert Systems with Applications, 2011, 38(4): 3467-3476.

[3] MA Xiaoqiang, WANG Haiyang, LI Haitao, et al. Exploring sharing patterns for video recommendation on YouTube-like social media [J]. Multimedia Systems, 2014, 20(6): 675-691.

[4] ZHAO Hui, ZHENG Qinghua, ZHANG Weizhan, et al. A version-aware computation and storage trade-off strategy for multi-version VoD systems in the cloud [C]∥Proceedings of the 20th IEEE Symposium on Computers and Communication. Piscataway, NJ, USA: IEEE, 2015: 943-948.

[5] DUTREILH X, RIVIERRE N, MOREAU A, et al. From data center resource allocation to control theory and back [C]∥Proceedings of the 3rd IEEE International Conference on Cloud Computing. Piscataway, NJ, USA: IEEE, 2010: 410-417.

[6] PAN Wenping, MU Dejun, WU Hangxing, et al. Feedback control-based QoS guarantees in web application servers [C]∥Proceedings of the 10th IEEE International Conference on High Performance Computing and Communications. Piscataway, NJ, USA: IEEE, 2008: 328-334.

[7] LEBOUCHER C, CHELOUAH R, SIARRY P, et al. A swarm intelligence method combined to evolutionary game theory applied to the resources allocation problem [J]. International Journal of Swarm Intelligence Research, 2012, 3(2): 20-38.

[8] HUBER N, BROSIG F, KOUNEV S. Model-based self-adaptive resource allocation in virtualized environments [C]∥Proceedings of the 6th International Symposium on Software Engineering for Adaptive and Self-Managing Systems. Piscataway, NJ, USA: IEEE, 2011: 90-99.

[9] ARDAGNA D, GHEZZI C, PANICUCCI B, et al. Service provisioning on the cloud: distributed algorithms for joint capacity allocation and admission control [C]∥Proceedings of the 3rd European Conference on Towards a Service-Based Internet, Service Wave 2010. Berlin, Germany: Springer, 2010: 1-12.

[10]KHAN A, YAN Xifeng, TAO Shu, et al. Workload characterization and prediction in the cloud: a multiple time series approach [C]∥Proceedings of the IEEE Network Operations and Management Symposium. Piscataway, NJ, USA: IEEE, 2012: 1287-1294.

[11]NAN Xiaoming, HE Yifeng, GUAN Ling. Queueing model based resource optimization for multimedia cloud [J]. Journal of Visual Communication and Image Representation, 2014, 25(5): 928-942.

[12]凌強, 張逸成, 嚴金豐, 等. 視頻點播系統(tǒng)用戶行為模型的構(gòu)建與應(yīng)用 [J]. 小型微型計算機系統(tǒng), 2013, 34(3): 548-552. LING Qiang, ZHANG Yicheng, YAN Jinfeng, et al. Construction and application of users’ behavior model in the video on demand system [J]. Journal of Chinese Computer Systems, 2013, 34(3): 548-552.

[13]CIULLO D, MARTINA V, GARETTO M, et al. How much can large-scale Video-on-Demand benefit from users’ cooperation? [C]∥Proceedings of the IEEE INFOCOM. Piscataway, NJ, USA: IEEE, 2013: 2724-2732.

[14]SHEN B, LEE S J, BASU S. Caching strategies in transcoding-enabled proxy systems for streaming media distribution networks [J]. IEEE Transactions on Multimedia, 2004, 6(2): 375-386.

[15]曹永榮, 胡偉. 基于現(xiàn)場服務(wù)排隊近似M/G/m模型的CSR配置 [J]. 重慶師范大學(xué)學(xué)報: 自然科學(xué)版, 2010, 4: 36-40. CAO Yongrong, HU Wei. Customer service representative staffing based on after-sales field service queuing approximation M/G/m model [J]. Journal of Chongqing Normal University: Natural Science, 2010, 4: 36-40.

(編輯 武紅江)

A Resource Allocation Method for Clusters of Streaming Media Servers in Multi-Version VoD

ZHAO Hui1,2,ZHENG Qinghua1,2,ZHANG Weizhan1,2,LI Zhenyan1,2,YE Shuyan1,2

(1. Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, China;2. Shaanxi Province Key Laboratory of Satellite and Terrestrial Network Tech. R&D, Xi’an 710049, China)

A resource allocation method for clusters of streaming media servers in multi-version VoD is proposed to solve the problem of the inappropriate resources allocation for clusters of streaming media servers in large-scale mobile learning (m-learning) system. The method analyzes user’s historical learning logs and mines user’s behavior characteristics, and then it utilizes the queueing theory to establish a resource allocation model for the cluster of streaming media servers. The method uses the model to predict the user arrival rate in real-time and then allocates appropriate resources dynamically. Simulation results show the correctness and efficiency of the proposed method. The average service rejection rate and average resource utilization rate are around 1% and 80% respectively. The proposed method can ensure the user experience satisfaction and reduce service cost.

m-learning; multi-version VoD; user behavior analysis; queueing theory; resource allocation

2015-12-11。 作者簡介:趙輝(1983—),男,博士生;鄭慶華(通信作者),男,教授,博士生導(dǎo)師。 基金項目:國家自然科學(xué)基金資助項目(61472317,61532015);教育部創(chuàng)新團隊發(fā)展計劃資助項目(IRT13035);陜西省重點實驗室資助項目(2013 SZS05-Z01)。

時間:2016-04-15

10.7652/xjtuxb201606005

TP391

A

0253-987X(2016)06-0030-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160415.1612.006.html