視頻網(wǎng)格中流媒體業(yè)務(wù)的流量模型

高偉濤,崔占忠,張海旸

(1.北京理工大學(xué) 宇航學(xué)院, 北京 100081； 2.北京郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 北京 100876)

網(wǎng)格是目前比較熱門的一個(gè)研究領(lǐng)域,它被普遍認(rèn)為是下一代的互聯(lián)網(wǎng). 網(wǎng)格最大的特點(diǎn)是各種資源的充分共享,這種共享是智能的、普遍的和便利的,這使得網(wǎng)絡(luò)上的各種資源可以得到充分有效的利用,并且精簡(jiǎn)了網(wǎng)絡(luò)終端的功能. 在網(wǎng)格中較為普遍的一種服務(wù)就是VoD服務(wù),因此針對(duì)多媒體服務(wù)中的視頻流進(jìn)行研究，可以為這種多媒體服務(wù)提供更好的QOS保證.

在網(wǎng)格中服務(wù)的方式采用多對(duì)多服務(wù)模式,也就是多個(gè)服務(wù)器對(duì)多個(gè)用戶進(jìn)行并行服務(wù). 這樣可以充分、有效地利用這多個(gè)服務(wù)器的資源,并且可以為用戶提供更穩(wěn)定、優(yōu)良的服務(wù)質(zhì)量. 在這種服務(wù)模式下,Internet網(wǎng)絡(luò)的多媒體VoD的視頻流模型已經(jīng)不再適用,為此作者在已有VoD視頻流模型的基礎(chǔ)上，提出了三層隨機(jī)過程描述方式,對(duì)網(wǎng)格中的VoD服務(wù)中的視頻流進(jìn)行建模.

較早的視頻業(yè)務(wù)流量模型是由Maglaric等人提出的一階自回歸AR模型[1],在此基礎(chǔ)上R.Grunenfelder和徐樹公等分別提出了ARMA模型及基于Gamma分布的AR模型[2-3]. 這些模型將視頻數(shù)據(jù)流量視為一個(gè)平穩(wěn)隨機(jī)過程,只適合于無場(chǎng)景變化的視頻源. 而實(shí)際的視頻流大多是非平穩(wěn)隨機(jī)過程,文獻(xiàn)[4-5]中根據(jù)I幀或GOP的數(shù)據(jù)量大小,通過閾值分割法,將這一非平穩(wěn)隨機(jī)過程劃分為一段段近似平穩(wěn)隨機(jī)過程,但是這種分割方法的閾值不易確定. 文獻(xiàn)[6]中提出了基于視頻圖像內(nèi)容的分割方法,提出了由AR模型調(diào)制的半馬爾可夫隨機(jī)過程,它可以適合于各種場(chǎng)景的視頻業(yè)務(wù)流量模型.

作者針對(duì)網(wǎng)格中不同的流媒體服務(wù)方式,對(duì)AR模型進(jìn)行了改進(jìn),提出了復(fù)合AR模型(MAR). 在視頻圖像分割方法的基礎(chǔ)上,將一段視頻分割成為多個(gè)視頻片斷,把每一個(gè)視頻流片斷內(nèi)部當(dāng)作平穩(wěn)過程看待,采用AR模型來描述,把每一個(gè)視頻流片段之間近似看作是半馬爾可夫過程. 并且考慮到了不同視頻流段的來源不同，從而僅在每一個(gè)視頻流段中視頻流片斷符合半馬爾可夫過程,而在整個(gè)視頻流中各個(gè)視頻流片斷符合泊松分布.

1 網(wǎng)格中的VoD服務(wù)模式

在網(wǎng)格中有多個(gè)VoD服務(wù)器對(duì)用戶同時(shí)提供服務(wù)，在此只考慮一個(gè)用戶情況下的服務(wù)模式,將多對(duì)多模型簡(jiǎn)化成為多對(duì)一的服務(wù)模型. 不失一般性,假設(shè)有3個(gè)VoD服務(wù)器,通過3條不同帶寬、不同延遲和不同丟包率的鏈路來同時(shí)為一個(gè)用戶提供服務(wù). 這3個(gè)服務(wù)器分別為S1,S2,S3,3個(gè)鏈路的帶寬分別為B1,B2,B3,3個(gè)鏈路的延遲分別為τ1,τ2,τ3,3個(gè)鏈路的丟包率分別為ε1,ε2,ε3. 網(wǎng)格中的VoD的多對(duì)一的服務(wù)種類有2種：一為多個(gè)VoD服務(wù)器,每個(gè)根據(jù)自身的帶寬、延遲和丟包率分別傳輸一段視頻流給用戶,在客戶端將這些視頻流進(jìn)行合成；二為從這些VoD服務(wù)器中選擇一個(gè)性能最優(yōu)的服務(wù)器來為用戶提供服務(wù),在其它的服務(wù)器中選擇一個(gè)備份服務(wù)器組提供各種備份流以保證不同的服務(wù)質(zhì)量要求.

本文中討論多個(gè)VoD服務(wù)器，每個(gè)服務(wù)器根據(jù)自身的帶寬、延遲和丟包率的合成函數(shù),分別傳輸一段視頻流V1,V2,V3,在客戶端將這些視頻流段進(jìn)行合成. 每個(gè)視頻流段的時(shí)間長(zhǎng)度用式(1)計(jì)算

t=C1B+C2τ+C3ε.

(1)

式中C1,C2,C3分別為帶寬、延遲和丟包率在計(jì)算視頻流段時(shí)間長(zhǎng)度時(shí)的權(quán)值. 帶寬、延遲和丟包率分別為歸一化值,折合為時(shí)間量. 在VoD點(diǎn)播中,帶寬為主要因素,帶寬直接決定可用的傳輸速率. 延遲和丟包率對(duì)于VoD業(yè)務(wù)的質(zhì)量、傳輸速率有較小的影響,對(duì)視頻流的抖動(dòng)有一定影響,因此C1的值應(yīng)該比C2,C3大一些,其確切值由實(shí)際VoD服務(wù)進(jìn)行測(cè)定.

2 網(wǎng)格中的MAR流媒體服務(wù)模型

假設(shè)各個(gè)VoD服務(wù)器和客戶端之間的鏈路是穩(wěn)定的,不會(huì)發(fā)生故障,鏈路的帶寬、延遲和丟包率也是恒定的不隨時(shí)間改變的,因而各個(gè)VoD服務(wù)器提供的視頻流段長(zhǎng)度固定且不隨時(shí)間變化.

在VoD視頻流中,當(dāng)量化尺度及GOP格式固定后,其輸出的數(shù)據(jù)比特流的大小主要由視頻圖像紋理的復(fù)雜度和圖像運(yùn)動(dòng)的復(fù)雜度決定. 因此可以根據(jù)圖像復(fù)雜度將視頻流分割成一段段近似平穩(wěn)的視頻片斷. 為簡(jiǎn)化起見,將視頻片斷分為高、中、低復(fù)雜度3種類型(H,M,L). 在視頻片斷內(nèi)部,數(shù)據(jù)流可以假設(shè)為平穩(wěn)的,因此可以用一階自回歸AR模型進(jìn)行模擬[6]. 對(duì)于MPEG壓縮方式的VoD視頻流,假設(shè)GOP格式為IBBPBBPBBPBB,因此可用3個(gè)一階AR模型分別對(duì)I，P和B幀進(jìn)行模擬. 則一個(gè)視頻片斷可定義為[2-3]

X(i)=[ARIARPARBt(i)].

(2)

式中t(i)為每個(gè)視頻段持續(xù)的時(shí)間. AR模型定義為

λ(k)=aλ(k-1)+bw(k),|a|<1.

(3)

式中：λ(k)為壓縮后第k幀每個(gè)像素的平均比特?cái)?shù)；a,b為常數(shù)；w(k)為均值為η,方差為1的正態(tài)高斯白噪聲.λ(k)的均值、方差和自相關(guān)函數(shù)分別為

E(λ)=bη/(1-a),

(4)

(5)

(6)

每個(gè)來自于某個(gè)VoD服務(wù)器的視頻流段由若干個(gè)視頻片斷組成,每一個(gè)視頻片斷分別屬于{H,M,L}這3個(gè)狀態(tài),并且更新間距為：t={τn,n=0,1,2,…}. 令隨機(jī)序列X={Xn,n≥0}具有狀態(tài)空間為視頻片斷復(fù)雜度于視頻片斷來源的組合：{H1,H2,H3,M1,M2,M3,L1,L2,L3},下標(biāo)1,2,3分別代表來自不同的VoD視頻服務(wù)器. 對(duì)于確定的一個(gè)視頻流片斷,它只能在{H,M,L}3個(gè)狀態(tài)之間進(jìn)行轉(zhuǎn)換,由于這3個(gè)狀態(tài)之間的相關(guān)性與實(shí)際的視頻流的內(nèi)容有關(guān),因此只能根據(jù)統(tǒng)計(jì)來確定這些狀態(tài)之間的轉(zhuǎn)移概率矩陣Pij,i,j∈{H,M,L}.

由于在每個(gè)視頻片斷的轉(zhuǎn)移與前面的視頻片斷的狀態(tài)無關(guān),因此可以將隨機(jī)序列X看做是馬爾可夫鏈. 而在一個(gè)視頻流段內(nèi)部的視頻流片斷序列定義為隨機(jī)過程

B={Bt,t≥0,且Bt=Xn,當(dāng)τn-1≤t≤τn}.

(7)

隨機(jī)過程B即為由馬爾可夫鏈調(diào)制的半馬爾可夫過程.

對(duì)于每一個(gè)VoD服務(wù)器提供的視頻流來說,雖然每個(gè)視頻流段的時(shí)間長(zhǎng)度不同,但是這個(gè)長(zhǎng)度是相對(duì)固定的. 因此可以把整個(gè)視頻流看作是這些視頻流段組成的Poisson過程. 來自3個(gè)VoD服務(wù)器的視頻流的長(zhǎng)度固定為Tv1,Tv2,Tv3,而且假設(shè)視頻流的順序?yàn)槿我獾?即V1,V2,V3,可以隨機(jī)排列. 每?jī)蓚€(gè)視頻流之間的間隔為tSi. 這樣,當(dāng)把視頻流段的長(zhǎng)度和間隔看成是對(duì)于視頻流段到達(dá)的隨機(jī)時(shí)間,則整個(gè)視頻流所包含的視頻流段數(shù){N(t),t≥0}可以看成是一個(gè)Poisson過程.

(8)

λ=E{N(t)}/t.

(9)

E{S(t)}=(λt)E{Yn},

(10)

(11)

而考慮到視頻流片斷之間是半馬爾可夫過程，以及視頻流片斷內(nèi)部是平穩(wěn)隨機(jī)過程,則整個(gè)視頻流可以表示為三重的隨機(jī)過程：在最高層,視頻流可以看作由視頻流段組成的類似復(fù)合泊松過程,而每個(gè)視頻流段可以看成由視頻流片斷組成的半馬爾可夫過程,最后,每個(gè)視頻流片斷的內(nèi)部可以看成是平穩(wěn)過程.

3 仿真實(shí)驗(yàn)

由于網(wǎng)格規(guī)模龐大,要在網(wǎng)格上實(shí)現(xiàn)較好的流媒體服務(wù),對(duì)流媒體調(diào)度算法的要求非常高,在調(diào)度算法的研究中,無法直接應(yīng)用到大規(guī)模的實(shí)際網(wǎng)格中檢驗(yàn)其性能,必須通過仿真大規(guī)模網(wǎng)格,以及其上的流媒體業(yè)務(wù)模型來驗(yàn)證調(diào)度算法的性能.

在流媒體調(diào)度算法的實(shí)驗(yàn)中,對(duì)于流媒體的模型要求很高,需要更貼近實(shí)際的流媒體業(yè)務(wù)模型,以便更好地仿真出調(diào)度算法的性能,因此流媒體業(yè)務(wù)模型對(duì)于流媒體調(diào)度算法的研究意義非常重大. 在本文中,作者將在仿真環(huán)境中利用ARMA模型和本文提出的MAR模型對(duì)同一調(diào)度算法的性能進(jìn)行驗(yàn)證,并且在小規(guī)模的網(wǎng)格中實(shí)現(xiàn)該流媒體調(diào)度算法對(duì)兩種模型進(jìn)行評(píng)估,從而比較兩種模型與實(shí)際網(wǎng)格流媒體業(yè)務(wù)特征的吻合程度.

在仿真環(huán)境中使用GT-ITM生成Transit-Stub型網(wǎng)絡(luò)拓?fù)?網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模分別為20，40，60個(gè)節(jié)點(diǎn). 主干Transit網(wǎng)絡(luò)采用1Gbit或10Gbit網(wǎng)絡(luò),Transit網(wǎng)絡(luò)與Stub之間的鏈路采用100Mbit網(wǎng)絡(luò),Stub內(nèi)的各節(jié)點(diǎn)之間主要為100Mbit鏈路.

在實(shí)際網(wǎng)格中采用了60臺(tái)PC機(jī),配置從CPU：P43.0GHz,內(nèi)存：1GB,硬盤：200GB,到雙CPU：P43.2GHz,內(nèi)存：2GB. 整個(gè)網(wǎng)絡(luò)由3臺(tái)路由器將3個(gè)局域網(wǎng)連接起來,每個(gè)局域網(wǎng)中有20臺(tái)PC機(jī). 并采用Globus Toolkit3.2搭建網(wǎng)格平臺(tái).

在仿真實(shí)驗(yàn)中借用無縫切換 (seamless switch, SL-Switch)[11]算法來比較采用不同流媒體模型，使得切換算法的性能與實(shí)際網(wǎng)絡(luò)中性能的相似程度. 在SL-Switch算法中,將Buffer尺寸設(shè)為8min,并且將節(jié)點(diǎn)平均故障時(shí)間設(shè)為1000s,然后通過視頻流的接收幀的穩(wěn)定性來評(píng)估算法的性能,并且通過在ARMA模型和MAR模型下與實(shí)際網(wǎng)絡(luò)中的穩(wěn)定性差來評(píng)估流媒體模型與實(shí)際的相似程度.

圖1為ARMA, MAR模型與實(shí)際網(wǎng)絡(luò)中流媒體穩(wěn)定度的比較圖. 從圖1中可以看出,ARMA模型與實(shí)際網(wǎng)格中的平均穩(wěn)定性差較大,為0.15,而MAR模型與實(shí)際網(wǎng)絡(luò)中的平均穩(wěn)定性差較小，為0.90. 因而可以得出,在小規(guī)模網(wǎng)格中,對(duì)于多對(duì)一的流媒體服務(wù)模式，MAR模型比ARMA模型更接近于實(shí)際的流媒體業(yè)務(wù)特征.

圖1 ARMA，MAR模型與實(shí)際網(wǎng)絡(luò)中流媒體穩(wěn)定度的比較

4 結(jié) 論

提出的針對(duì)網(wǎng)格環(huán)境中多對(duì)一VoD服務(wù)中視頻流的多層模型,在考慮了面向內(nèi)容的多源視頻流分割和多源相關(guān)性后,提出了第1層為AR模型的平穩(wěn)隨機(jī)過程，第2層為半馬爾可夫過程，第3層為泊松過程的三重隨機(jī)過程模型. 將ARMA，MAR模型與網(wǎng)絡(luò)中流媒體的穩(wěn)定性進(jìn)行比較，結(jié)果表明，該模型可在網(wǎng)格環(huán)境下更準(zhǔn)確有效地描述網(wǎng)格環(huán)境下多對(duì)一VoD服務(wù)中的視頻流,為更有效和更高質(zhì)量地提供VoD服務(wù)打下了基礎(chǔ).

參考文獻(xiàn)：

[1]Maglaris B. Performance models of statistical multiplexing in packet video communication[J]. IEEE Trans on Comm,1988,36(7):834-843.

[2]Grunenfelder R. Characterization of video codes as autoregressive moving average process and related queuing system performance[J]. IEEE JSAC,1989,7:752-760.

[3]徐樹公,黃載祿.一種新的ATM網(wǎng)VBR視頻業(yè)務(wù)模型[J].電子學(xué)報(bào),1997,25(10):102-105.

Xu Shugong, Huang Zailu. A sort of new ATM net VBR video frequency operation model[J]. Electronics Transaction,1997,25(10):102-105. (in Chinese)

[4]Manzoni P. Workload models of VBR video traffic and their use in resource allocation policies[J]. IEEE/ACM Trans on Networking,1999,7(3):387-397.

[5]Jelenkocvic P R. The effect of multiple time scales and subexponentiality in MPEG video streams on queueing behavior[J]. IEEE JSAC,1997,15(6):1052-1071.

[6]陸大金.隨機(jī)過程及其應(yīng)用[M].北京：清華大學(xué)出版社,1986．

Lu Dajin. Stochastic process and application[M]. Beijing: Tsinghua University Press,1986. (in Chinese)

[7]王玉孝.概率論與隨機(jī)過程[M].北京：北京郵電大學(xué)出版社,2000．

Wang Yuxiao. Probability theory & stochastic process[M]. Beijing: Beijing University of Posts and Telecommunications Press,2000. (in Chinese)

[8]Calvert K L, Doar M B, Zegura E, Modeling internet topology[J]. IEEE Communications Magazine,1997,35(6):160-162．

[9]Sun Xiaoyan, Wu Feng, Li Shipeng. Seamless switching of scalable video bitstreams for efficient streaming[J]. IEEE Trans on Multimedia,2004,6(2):291-303．