一種基于多服務器的DASH客戶端優化算法

吳如亮,王子磊,奚宏生

(中國科學技術大學 自動化系,合肥 230027)

0 概述

近年來,一種稱之為HAS(HTTP Adaptive Streaming)的流媒體傳輸標準出現,并且很快變成了流媒體傳輸的主要方式。據Cisco[1]估計,到2019年視頻流量將占據互聯網數據傳輸總流量的80%,網絡運營商也試圖尋找新的方式以更好地利用網絡容量。2011年,MPEG結合3GPP開發出一套標準化的解決方案——基于HTTP的動態自適應流媒體(Dynamic Adaptive Streaming over HTTP,DASH)[2]。在DASH標準中,原視頻被分割成2 s～10 s的視頻分片并以不同的碼率等級進行編碼,生成的分片存儲在服務器上,客戶端則根據網絡狀況及自身狀態動態調整請求的視頻質量。隨著業務規模的擴大,DASH服務模式開始從單服務器向多服務器轉變。多服務器能夠提供更大的帶寬,傳輸路徑更加多樣化,服務質量也更加可靠。但是,由于服務器間的帶寬差異,如何減少客戶端視頻碼率的頻繁波動,保證客戶端體驗質量(Quality of Experience,QoE),仍是一個挑戰。

相關算法[3]已被提出用來解決單服務器場景下的質量波動問題。現有多服務器場景下DASH客戶端方法主要是在最大化帶寬利用率的前提下,提高客戶端視頻質量,但是往往忽視了視頻質量頻繁波動的問題。文獻[4]為了優化多個服務器間的資源分配問題和提高客戶端視頻質量,提出了一種協同多尺度調度算法,該算法能夠平衡服務器負載,優化整體視頻質量。文獻[5]針對多服務器場景下的公平、效率和穩定性問題,提出了一種新的協議Presto,提高了用戶體驗質量。上述優化方法均是在傳統網絡下進行,由于視頻下載的間歇性,客戶端對帶寬的估計往往不準確。近年來,軟件定義網絡(Software-Defined Network,SDN)出現,由于其集中控制機制及其在網絡資源調度和網絡狀態監測等方面的智能性和靈活性,在流媒體視頻領域越來越受歡迎[6]。文獻[7]提出了一種OpenFlow協助下的QoE優化框架,減少了客戶端和SDN控制器間的頻繁通信,能夠有效分配網絡資源,但因其請求模式是單服務器,并沒有解決多服務器場景下的質量波動問題。

針對上述問題,本文提出一種多服務器場景下基于SDN的視頻分片請求調度算法。該算法將多個分片組成一個視頻塊,并把這多個分片分配至多個服務器,利用這種以視頻塊為單位的調度策略實現同一視頻塊內視頻分片的碼率同步,減少視頻質量的波動。同時,在客戶端通過使用Q學習訓練碼率決策矩陣,當新的分片請求到達時,通過查詢該矩陣找到當前狀態下Q值最大的動作作為最優碼率。

1 基于SDN的DASH系統框架

1.1 問題描述

動態自適應碼率切換算法是當前DASH技術研究的一個熱點。但是目前很多算法[4-5,8]是純客戶端驅動,即僅僅依賴客戶端及其獲悉的網絡狀態來動態調整視頻比特率,可能由于帶寬估計不準確導致客戶端頻繁切換視頻比特率,影響客戶端QoE。

在DASH多服務器場景下,客戶端同時向多個服務器發起視頻分片請求。但是由于客戶端到各個服務器的帶寬多樣性,可能會出現分片失序到達的情況,此時若緩沖區耗盡,則視頻播放會中斷,從而引入不必要的時延。文獻[9]為解決并行多服務器下視頻塊順序下載的問題,提出一種概率分片調度方法,該方法根據時變帶寬概率模型,估計在視頻緩沖區耗盡之前視頻分片成功下載的概率來優化視頻傳輸。此外,由于多個服務器間服務帶寬的差異性,往往會導致視頻質量的頻繁波動。文獻[8]針對多個服務器服務能力的動態變化的情況,提出一種動態服務器選取策略來協助客戶端選擇服務能力最優的視頻傳輸服務器,解決了傳統DASH自適應策略僅選取視頻碼率的問題。這種方案在網絡狀況較好時每次都能請求最高的視頻碼率,但在網絡環境較差的情況下,視頻質量仍然會出現頻繁波動的情況。

以上研究對DASH多服務器場景下的分片失序到達、視頻質量波動等問題做出了一定的改善,但是由于傳統網絡的限制,不能從全局角度對系統進行優化,同時,帶寬大多是基于預測手段獲取,往往存在偏差,制約了優化效果。

本文研究內容可以描述為:在SDN網絡中,客戶端同時發起多個視頻分片請求,分片調度算法將多個請求分配至多個服務器,以減少客戶端視頻質量的波動,同時客戶端采用Q學習算法決策視頻碼率,為用戶提供更佳的QoE。

1.2 系統模型

OpenFlow[10]網絡中的動態自適應視頻播放系統模型如圖1所示。整個系統由視頻服務器、Web代理服務器、視頻客戶端、OpenFlow控制器及交換機組成。其中:視頻服務器負責向視頻客戶端提供視頻服務;Web代理服務器負責將用戶的視頻分片請求以及將請求下發給OpenFlow控制器;視頻客戶端是視頻請求的發起者;OpenFlow控制器負責分片調度算法的決策,負責控制視頻分片請求的下發;OpenFlow交換機負責根據流表完成數據的轉發。

圖1 DASH系統模型

本文的工作是設計視頻分片請求調度算法和客戶端碼率決策算法。整個視頻請求過程可以描述為:首先客戶端向Web代理服務器發起視頻請求,代理服務器將此請求轉發至控制器,控制器根據收集的各個服務器帶寬信息,執行分片調度算法,決策出需要請求的分片數及服務器數,并通過OpenFlow協議與交換機進行指令下發和信息收集;然后客戶端根據Q學習算法決策出要請求的視頻碼率,根據控制器下發的指令開始向視頻服務器發起視頻傳輸請求。視頻塊請求分配示意圖如圖2所示。把多個視頻分片組成一個視頻塊,每次對一塊視頻進行調度,下文將給出調度策略的具體描述。

圖2 視頻塊請求分配示意圖

2 視頻分片調度策略

視頻分片調度策略首先動態選擇視頻塊的長度(分片個數)及所請求的服務器;然后采用視頻分片請求調度算法將各個分片請求分配至多個服務器。

2.1 視頻塊長度及服務器選取算法

多服務器請求模式為:一個客戶端同時向多個服務器發起多個視頻分片的請求,服務器分配的請求分片數與服務器可用帶寬成正比,這樣確保了多個服務器完成下載的時間幾乎是同步的。但是隨著時間的變化,服務帶寬也在變化,同一視頻塊內的各個分片可能無法以預定同步的時間完成下載。因此,設置了視頻塊長度的上限閾值Nmax。同時,將帶寬最小的服務器分配一個分片,其他服務器按照此帶寬成比例依次分配視頻分片數。

假設存儲客戶端請求視頻的服務器有S個,第i個服務器可用帶寬為ci,降序排列使得c1≥c2≥…≥cS。令Sk表示請求第k塊視頻所用服務器數,顯然Sk≤S。將第k塊視頻包含的分片數記為Nk。下面將詳細描述視頻塊長度Nk及服務器個數Sk的選取過程。

算法1視頻塊長度及服務器選取算法

輸入視頻服務器個數S,各服務器可用帶寬c={c1,c2,…,cS}

輸出視頻塊長度Nk,服務器個數Sk

1.Initialize:

2.Sk←S

3.while TRUE do

4.nSk←1;

5.for i←1 to Sk-1 do

6.ni=?ci/cSk」;

7.end for

9.if Nk>Nmaxthen

10.Sk←Sk-1

11.else

12.return Nk,Sk;

13.end if

14.end while

對算法1的解釋如下:

算法第1行～第2行:算法開始時獲取各個服務器可用帶寬集合{c1,c2,…,cS},并初始化本次請求所用服務器數目Sk為S。

算法第9行～第14行:判斷分片總數Nk是否大于視頻塊長度的上限閾值Nmax。若Nk小于等于Nmax,返回視頻塊長度Nk和服務器個數Sk,程序結束;否則,若Nk大于Nmax,舍棄帶寬最小的服務器,更新可用服務器數目Sk為Sk-1,程序跳轉到第3行繼續執行。

2.2 視頻分片請求調度算法

確定視頻塊長度Nk和服務器個數Sk后,下一步的目標是將Nk個視頻分片合理分配至Sk個服務器,使得分片下載時間最短。

綜上所述,以服務器分配矩陣A作為決策變量,視頻分片請求的調度模型為:

Subject to:

aij∈{0,1},i=1,2,…,Nk,j=1,2,…,Sk

t(n)

上述優化問題是一個NP難問題,無法直接使用凸優化理論進行求解,本文在此給出了啟發式算法。求解時,借助于貪心算法的思想,對矩陣A逐行求解,將分片從前往后依次分配給各個服務器,分配策略如算法2所示。

算法2視頻分片請求調度算法

輸入請求分片數Nk,服務器數Sk,各服務器可用帶寬c={c1,c2,…,cSk}

輸出服務器分配矩陣A

1.Initialize:

2.A←0

3.for i←1 to Nkdo

5.aij*=1;

6.end for

7.return A;

對算法2的解釋如下:

算法開始時獲取算法1 的輸出結果,即視頻塊長度Nk、服務器數Sk,將其作為本算法的輸入,同時將服務器可用帶寬c={c1,c2,…,cSk}作為算法的輸入。

算法第2行:初始化分片分配矩陣A=0,開始對Nk個視頻分片進行分配。

算法第7行:當Nk個視頻分片分配完成之后,返回分片分配矩陣A。

3 基于Q學習的客戶端算法

當DASH客戶端請求視頻時,由于視頻碼率的多樣性,往往需要一個客戶端算法對視頻碼率進行決策。本文采用Q學習算法作為客戶端碼率決策算法[11-12]。

3.1 基于Q學習的決策

Q學習是強化學習[13]的一個分支,它需要解決如下問題:一個能夠感知環境的自治智能體,根據當前的環境狀態,通過學習選擇一個最優動作,使得智能體獲取的回報值最大。

基于Q學習,客戶端碼率選取過程為:根據環境狀態(帶寬、客戶端緩沖區和視頻碼率等),采取某一動作(選擇視頻碼率),使得回報值(QoE)最大。式(1)給出了智能體在狀態s下,采取動作a獲取回報值r時Q值的更新方式。其中,(s,a)是狀態-動作對,α∈[0,1]是學習速率,表示新獲取信息覆蓋舊信息的程度,α越大保留之前訓練的效果就越少;γ∈[0,1]是折扣因子,決定了對未來回報的重視程度。

Q(s,a)=(1-α)Q(s,a)+α[r+γQ(s′,a′)]

(1)

基于學習到的Q值可選擇要請求的碼率。在DASH系統中,需要為每個動作a分配一個回報值r用來更新學習Q,其中,回報值r是通過回報函數來確定的,下面將給出回報函數的定義。

3.2 回報函數

客戶端算法的優化目標是最大化QoE,因此,本文定義的回報函數是QoE的一種度量,主要包括3個方面[14]:1)視頻質量等級;2)視頻質量波動;3)緩沖區下溢。下面分別介紹這三方面對應的回報函數。

3.2.1 視頻質量等級

文獻[15]表明客觀PSNR值和主觀平均意見得分(MOS)之間存在類似線性的關系。因此,本文建立的視頻質量等級對應的回報函數Rquality為一個線性函數,見式(2)。其中,視頻有L個質量等級,QLi表示請求第i個分片的質量等級,且QLi

Rquality=-(QLL-QLi)

(2)

3.2.2 視頻質量波動

在DASH系統中,由于帶寬的波動,請求的視頻質量等級會隨之變化,導致視頻質量發生波動,影響用戶體驗質量。本文建立了質量波動對應的回報函數Roscillation為波動值的線性函數,見式(3)。當無波動發生時,回報為0;當有波動時,波動越大回報越小。

Roscillation=-|QLi+1-QLi|

(3)

3.2.3 緩沖區下溢

緩沖區下溢導致視頻播放中斷是影響QoE的第3個方面,因此,緩沖區下溢也成為回報函數的一個組成部分。當客戶端緩沖區耗盡時,視頻播放中斷,重緩沖事件發生。定義回報函數時,本文考慮根據緩沖區長度大小,將緩沖區下溢對應的回報函數分段定義。當緩沖區長度Bi低于緩沖區總長度Bmax的10%時,給予-100的懲罰;否則,將回報函數定義為一個線性函數,見式(4)。

(4)

3.2.4 總回報函數

最終的回報函數可以歸結為以上三者的線性疊加之和,見式(5),其中C1、C2、C3為權重因子。

R=C1Rquality+C2Roscillation+C3Rbuffer

(5)

3.3 環境狀態

在構建環境狀態時,結合回報函數的定義,本文采用視頻質量等級和緩沖區長度作為環境狀態。此外,因為帶寬也是碼率選擇中的一個重要因素,所以將帶寬也加入到環境狀態中。表1給出了環境狀態的定義。

表1 環境狀態定義

Q學習的算法描述詳見算法3,算法維護一個狀態空間和行動集構成的矩陣S×A來存儲Q值,下面對整個算法進行詳細描述。

算法3基于Q學習的客戶端碼率選擇算法

1.Initialize:

2.Q←0

3.for each episode//video start play

4.s←randSelectState();

5.for each step of episode//request segment

6.a=selectAction(s);//use ε-greedy

7.calculate R by formula (5)

8.calculate Q by formula (1)

9.s←s′

10.end for

11.end for//video end

12.return Q;

對算法3的解釋如下:

首先將Q值矩陣初始化為全0元素矩陣,episode為智能體學習的次數,算法第3行開始對智能體進行訓練,第4行是從所有碼率中隨機選擇一個碼率作為初始狀態。

算法第5行～第10行:每一次的碼率請求對應一步,對于每一次的碼率請求,智能體使用ε-greedy方法選擇一個碼率作為下一時刻要請求的視頻碼率,根據式(5)計算該碼率對應的回報值R,根據式(1)更新Q值矩陣,同時,將當前的狀態s進行更新,然后進行下一步的循環過程。

當設定的episode循環結束之后,Q學習過程結束。將最終訓練得到的Q值矩陣作為客戶端的碼率決策依據。當客戶端請求到來時,根據客戶端不同的狀態,查詢Q值矩陣找到當前狀態下效用值最大的動作為最優碼率。

4 仿真與分析

4.1 仿真參數說明與設定

仿真實驗不考慮鏈路的連接關系,使用的拓撲包含4個服務器,各個服務器的帶寬數據基于中國科學技術大學校園網絡內某一服務器的真實網絡帶寬情況。選取1個客戶端發起DASH視頻請求。視頻選擇開源視頻源“Big Buck Bunny”,該視頻由2 s長的視頻分片組成,并且每一個視頻分片被編碼成7個質量等級:300,400,600,800,1 200,1 500,1 800,單位為Kb/s。客戶端播放器的緩沖區上限閾值設置為30 s(15個分片)。通過調整實驗參數進行多次實驗,獲得一組比較好的設置參數。本文最終回報函數中參數C1、C2、C3均設置為1。式(1)中的α設置為0.1,γ設置為0.5。

實驗的流程共分為3個階段:訓練學習獲取碼率決策矩陣,即Q值矩陣,根據分片調度算法獲取分片分配矩陣A,根據環境狀態及Q值矩陣選擇碼率并按分配矩陣A中分配方式發起視頻請求。

1)客戶端學習算法

本算法是在Ubuntu14.04系統下通過編寫python腳本實現的,主要是調用python下的工具包numpy,同時在實驗中episode設置為200 000,step設置為100 000,數值較大,運算時間較長,而python腳本執行速度較快。因此,本文選擇使用python執行Q學習算法。

2)分片調度算法

本算法是DASH流媒體視頻傳輸系統中的重要一步。在實驗中,采用真實的服務器帶寬進行實驗,另外,由于Matlab具有強大的矩陣處理能力,因此本文選擇在Matlab上執行分片調度算法。在執行分片調度算法的過程中,通過改變服務器帶寬進行多次實驗,觀察客戶端質量變化及緩沖區變化情況。

3)客戶端碼率決策

客戶端碼率決策是實驗的最后一步,決策過程是在Matlab上執行的。首先根據客戶端當前環境狀態,查詢Q值矩陣中對應的狀態行,找到該狀態下效用值最大碼率作為本次要請求的視頻碼率,然后根據分片分配矩陣A向服務器發起視頻分片請求。客戶端維護著請求的視頻質量列表,作為客戶端性能評估的依據。

在仿真實驗過程中,具體的測試環境及軟硬件配置信息如表2所示。

表2 實驗配置

4.2 仿真結果分析

使用真實服務器帶寬進行仿真實驗時,考慮到真實服務器帶寬和本文給定的視頻碼率不匹配問題,對真實數據進行了線性放大處理。在放大實際數據量的同時,保留了原始數據良好的周期性及波動性。本文實驗拓撲結構如圖3所示,設置了4個DASH服務器,選取1個客戶端發起視頻請求。

圖3 實驗拓撲

首先,本文運行客戶端上的Q學習算法訓練學習客戶端碼率選擇過程,訓練參數設置已在4.1節描述,最終得到訓練的Q值,作為本文后續實驗的碼率選擇依據;然后,客戶端發起視頻分片請求,運行控制器上的分片調度算法,算法決策出應該向哪幾個服務器發起視頻分片請求,接著,客戶端根據控制器收集的帶寬信息和客戶端自身的狀態信息,查詢Q值矩陣中對應的狀態行,找到該狀態下效用值最大碼率作為本次要請求的視頻碼率,開始視頻傳輸服務。

實驗將客戶端QoE作為性能指標,分別測量了客戶端平均視頻質量等級、平均緩沖區大小和碼率切換次數。此外,為了更好地反映本文策略的效果,仿真實驗中加入了一組對照實驗:協同多尺度調度算法[4],該算法也是針對DASH多服務器場景,能夠平衡服務器負載,自適應各個服務器帶寬,優化視頻服務質量。實驗將碼率等級從低到高依次編號,從1開始,得到7個質量等級,實驗結果如表3～表5所示。表中第1行給出了服務器帶寬的放大倍數x,下面2行分別對應不同策略下的實驗結果。

表3 平均質量等級對比

表4 不同策略平均緩沖區大小對比 s

表5 不同策略碼率切換次數對比

實驗結果表明,本文提出的分片調度算法能夠在SDN控制器指導下有效改善客戶端QoE。在不同的帶寬放大倍數下,本文策略在平均視頻質量、碼率切換次數和平均緩沖區大小等方面均有所優化,其中分片調度算法保證了連續幾個分片的碼率一致性,使得碼率切換頻率明顯降低。

另外,為了更直觀地反映本文策略的實驗效果,本文在服務器帶寬倍數設置為4.90時,對客戶端碼率等級和緩沖區波動情況進行了圖形化展示。圖4對比了2種不同方案下的質量等級隨時間波動情況。圖5對比了2種不同方案下的客戶端緩沖區的變化情況。

圖4 質量等級波動圖

圖5 客戶端緩沖區波動圖

圖4表明,在視頻播放過程中,本文算法下視頻質量波動次數明顯減少,并且在波動幅度上相對于協同調度算法也略有減少,進而提高了用戶體驗質量。圖5表明,協同多尺度調度算法下客戶端緩沖區的波動更加劇烈,而本文算法下客戶端緩沖區波動稍緩慢,這主要得益于本文中客戶端Q學習算法將緩沖區狀態引入了環境狀態中,當緩沖區狀態很低時,會給系統一個較大的懲罰。

5 結束語

本文提出了一種基于多服務器的DASH客戶端優化算法,借助于SDN,實現了對服務器可用帶寬的準確測量。通過將多個視頻分片組成一個視頻塊,并對這個視頻塊中的碼率進行統一化處理,一方面減少了客戶端視頻碼率的頻繁切換,另一方面提高了總體視頻質量。同時,本文采用Q學習算法,通過自我學習訓練Q值矩陣,為每一個視頻塊選擇合適的碼率,大幅提高了碼率選擇的效率。下一步將考慮客戶端和服務器之間的路徑規劃問題,使客戶端能夠自動切換到網絡狀況較好的傳輸路徑上。