考慮擦除編碼可靠視頻流三步式內凸逼近優化

朱雯曦 黃煜棟 黃長城

1(紹興職業技術學院信息工程學院 浙江 紹興 312000)2(杭州科技職業技術學院信息工程學院 浙江 杭州 310000)3(溫州大學數理與電子信息工程學院 浙江 溫州 325000)

0 引 言

近年來，視頻流服務的需求急劇上升，全球視頻流市場預計將以每年18.3%的速度增長。隨著視頻流服務的擴散和進步，基于云的視頻已得到廣泛推廣。在云存儲系統中，與復制系統相比，擦除編碼已經迅速成為降低給定可靠性的存儲成本的有前途的技術。它已被廣泛采用在現代存儲系統中的，如臉譜網、微軟、谷歌等。本文考慮當視頻流內容被放置在云服務器上時擦除編碼的實現問題，給出了停頓持續時間的界限，并使用它來提出優化的流服務，使客戶端的平均體驗質量指標(QoE)最小化。

本文考慮兩個QoE度量的失速持續時間測量方法：(1) 平均失速持續時間，幾乎每個觀看者都能夠將停頓時間作為觀看視頻的體驗質量；(2) 失速持續時間的概率，其決定了失速時間尾概率。實驗結果顯示，在Bing、Facebook和Amazon的零售平臺等現代Web應用程序中，延遲的長尾尤其令人關注。因此，失速時間尾概率的QoE度量變得重要。本文通過理論分析得出了以上兩個QoE度量的上界。量化擦除編碼存儲的服務等待時間是一個開放的問題，尾部延遲也是如此。本文向前邁進了一步，探索視頻流的概念，而不是視頻下載。因此，找到確切的QoE度量是一個開放的問題。本文研究了QoE度量的界，實際系統中的數據塊傳輸時間遵循移位指數分布，這促使選擇每個視頻服務器的服務時間分布是移位指數分布。此外，假設每個視頻的請求到達率是泊松分布的。使用(n，k)擦除碼對視頻片段進行編碼，并將編碼片段放置在n個不同的服務器上。當請求視頻時，需要從n個服務器中的k分段進行請求。選擇這些服務器的最優策略需要Markov方法，并存在狀態爆炸問題，因為相應的隊列模型的狀態不僅必須封裝當前系統的映射中，而且還必須封裝包括塊放置和排隊請求。很多文獻都對該問題進行研究，例如，文獻[7]提出的隨機布局優化訪問策略(RP-OA)，位置采取隨機方式進行選擇，其中為每個文件選擇m個服務器中的任何n個，但是該算法不進行布局結構的優化。文獻[8]提出投影均等優化布局訪問(OPE-PEA)，利用設置中提到的π、t和s優化策略。然后對布局和t進行交替優化，缺點是算法較為復雜。文獻[9]提出投影均等隨機布局訪問(RP-PEA)，位置采取隨機選擇方式，但是需要假定每個選擇都有相同概率，有一定局限性。文獻[10]提出投影服務速率比例分配優化布局策略(OPPSP)，聯合請求調度器選擇接入概率與存儲節點的服務速率成比例，對于均勻隨機放置的文件具有較高的算法性能。文獻[11]提出隨機布局PSP(RP-PSP)策略，進行加權平均失速時間和失速持續時間尾概率的優化，但是需要設定額外的輔助變量。上述算法雖可取得一定的效果，但是均存在一定的局限性。

本文提出一種考慮擦除編碼可靠視頻流三步式內凸逼近優化方法，利用對擦除編碼塊的選擇的有序統計量來對每個視頻片段的編碼塊的下載時間進行表征，利用失速持續時間上的矩生成函數的界限來界定平均失速持續時間。同時，設計了一種三步式內凸逼近優化算法，以聯合最小化在視頻內容的放置和訪問期間在所有請求上平均的兩個QoE度量的凸組合，實驗結果驗證了所提算法的性能優勢。

1 系統模型

圖1 視頻片段和擦除編碼過程

圖2 分布式存儲系統的例證

假設每個服務器的文件按照先入先出(FIFO)的請求順序策略服務。此外，按照持續時間的順序處理不同的塊。這在圖3中進行了描述，對于服務器q，當請求文件i時，所有塊都放在隊列中，在此之前尚未被服務的其他視頻請求正在等待。

圖3 服務器q上的即時隊列狀態

為了將視頻文件i的請求調度到ki服務器，選擇ni服務器的ki-out-of-ni非常重要。本文使用一種稱為概率調度的策略，該策略允許以一定的概率選擇ki節點的每一個可能子集。當視頻文件i到達時，隨機地分配成批的ki塊請求來使節點集合(由文件i的服務器集合Ai表示)具有預定概率(集合Ai和文件i的概率為P(Ai))。然后，每個節點在本地隊列中緩沖請求，并按照先前解釋的順序進行獨立處理。具有可行概率{P(Ai)∶?i,Ai}的概率調度策略存在條件概率πij∈[0,1]，?i,j，滿足充要條件：

(1)

式中：πij=0(j?Si)。換句話說，用概率πij選擇每個節點j將產生{P(Ai)∶?i,Ai}的可行選擇。因此，考慮請求概率πij作為請求視頻文件i使用服務器j的概率。在使用概率調度給出文件下載延遲上限的同時，本文利用概率調度給出了視頻流QoE上限。

(2)

指數分布βj=0是一個特殊情況。注意到，像網絡延遲這樣的常數延遲和解碼時間可以很容易地被考慮為具有移位的指數分布。令Mj(t)=E[etXj]是Xj的矩生成函數。則Mj(t)可表示為：

(3)

到達速率是根據視頻文件給出的，并且上面的服務速率是根據每個服務器上的編碼塊來提供的。客戶端在下載了該段的所有ki塊之后并播放前一段視頻段。還假設視頻中存在一個啟動延遲，這是內容可以被緩沖但不播放的持續時間。本文將描述這種設置的失速持續時間和失速持續時間尾概率。

2 塊的下載和播放時間

為了得到暫停時間，需要知道不同編碼塊的下載時間和視頻的不同段的播放時間。

2.1 服務器塊下載時間

(4)

視頻文件i由服務器j((ni,ki))上的Li編碼塊組成。如果從服務器j進行服務請求，則視頻文件i的總服務時間STi,j計算時間為：

(5)

視頻文件的服務時間可計算為：

Rj=STi,j

(6)

(7)

令t=-s，則根據式(7)可得從服務器j請求視頻文件服務時間的矩生成函數Bj(t)的計算形式為：

(8)

(9)

(10)

(11)

(12)

2.2 視頻片段播放時間

(13)

(14)

式(14)給出遞推方程，具體形式為：

(15)

(16)

其中:

(17)

接下來，給出pi,j,z的矩生成函數，這些函數將在下一節中用于計算QoE度量。首先給出pi,j,z的矩生成函數形式為：

(18)

其中:

(19)

(20)

可使用這個失速時間來確定平均失速持續時間和失速持續時間尾概率的界限。

2.3 平均失速時間

在本節中，我們將提供第一個QoE度量的界限，這是文件ki的平均停滯時間。發現概率調度是有界的，并且由于概率調度是一種可行策略，所以所得到的界是最優策略的上界。基于式(20)，文件j的預期停機時間如下：

(21)

由于不同j和z值的pjz隨機變量之間的相關性，很難對Li段的播放時間進行準確的評估，其中z∈(1,2,…,Li+1)、j∈Ai，因此，我們得出分段Li的播放時間的上界如下：

(22)

(23)

注意到這里唯一的不等式是用和值代替最大值。因為這個項是在平均失速延遲的對數之內，所以這個項和它的界之間的間隙變成加性而不是乘性。根據式(22)-式(23)可得：

(24)

(25)

(26)

2.4 失速持續尾概率

(27)

(28)

使用Markov定理，可得到：

(29)

(30)

對于下載而不是流式傳輸文件的場景，常選的度量是延遲尾概率，即文件下載延遲大于x的概率。這是特殊情況，每個視頻片段的數目是1個，或Li=1。

3 優化問題的制定與算法

3.1 問題模型化

(31)

s.t.

(32)

(33)

(34)

(35)

(36)

(37)

(38)

(39)

(40)

(41)

πi,j=0 ifj?Si,πi,j∈[0,1]

(42)

|Si|=ni?i

(43)

(44)

(45)

θ∈[0,1]，在極小化問題中是一個權衡因素，它決定了失速持續時間的平均概率和尾概率的相對重要性。當θ=0到θ=1變化時，式(31)的解將平均失速持續時間最小化的解擴展到失速持續時間尾概率最小化的解。式(41)給出服務器j的負載強度，式(42)給出給定概率調度概率πij和到達率λi下每個節點的總到達率Λj。式(42)-式(43)保證調度概率是可行的。式(44)-式(45)確保在式(18)中給出的矩生成函數存在。對參數π的優化有助于降低目標函數，并且比選擇用于訪問文件的最低隊列服務器具有更大的靈活性。視頻文件S的放置有助于在不同服務器上分離高度訪問的文件，從而減少了目標。最后，在輔助變量t上的優化給出了目標函數的更嚴格的界。注意到文件i的QoE指標可利用公式中的到達率參數λi來衡量。

注意，所提出的優化問題是一個混合整數非凸優化問題，因為我們在n個服務器上放置了式(44)和式(45)，并且約束(π,t)是非凸的。此外，可以同時為多個聚合虛擬機確定布局，并且可能不是單個聚合虛擬機的參數。在這種情況下，所提出的算法仍然可以在沒有優化的情況下使用視頻文件的放置。在下一節中，將對所提優化算法進行描述。

3.2 三步式優化分解

Step2：如果算法未收斂，則反復執行下列過程：

算法1:內凸逼近策略數據初始化:γv∈(0,1],x0∈χ,v=0;1 如果xv是式(31)的平穩解,則終止算法;2 計算x^(xv),可得式(31)的解;3 設置xv+1=xv+γv(x^(xv)-xv);4 v←v+1,并返回s.1;

4 實驗分析

4.1 實驗設置

(1) 投影均等優化布局訪問(OP-PEA)：該策略利用設置中提到的π、t和s優化策略。然后，使用所提出的算法對布局和t進行交替優化。

(4) 隨機布局PSP(RP-PSP)策略：與OP-PSP策略相比，塊被隨機地均勻放置。在輔助變量t的選擇上，優化了加權平均失速時間和失速持續時間尾概率。

4.2 平均失速持續時間優化

在本節中，只通過設置θ=1來最小化所有文件的平均停頓持續時間，即不考慮停頓持續時間尾概率。將所提算法與五個基線策略進行比較，實驗4所示結果顯示對于平均失速持續時間的QoE度量，所提出的算法優于選取的對比策略。因此，文件的存取和放置對于減少平均失速時間都是非常重要的。此外，平均失速持續時間隨著到達率指標的增加而增加。由于平均失速持續時間在高到達率時更為顯著，因此與隨機布局和預計的平等接入策略相比，在圖4中的最高到達率時，平均失速持續時間顯著提高了約60%(大約從250 s提高到600 s)。

圖4 不同視頻長度的不同視頻到達速率的平均失速持續時間

4.3 失速時間尾概率優化

在這個小節中，考慮在式(31)中設置θ=0，最大限度地減少失速持續尾概率，P(Γ(i)≥x)。圖5顯示了加權失速持續時間尾概率相對于x(以秒為單位)的衰減情況對比。為了放大小的差異，繪制y軸的對數刻度。實驗結果顯示，與選取的對比策略相比，所提出的算法在失速持續時間尾概率方面給出了順序改進。

圖5 不同x值的失速持續尾概率

4.4 折衷性能對比

圖6 平均失速時間和失速持續時間尾概率之間的權衡

5 結 語

本文考慮了在分布式服務器上對內容進行擦除編碼的云上視頻流，提出了一個優化問題，用于優化兩個QoE度量的凸組合，以選擇從服務器放置和訪問內容，并提出了求解優化問題的有效算法，數值結果顯示了該算法相對于對比策略的性能優勢。本文的主要貢獻包括：(1) 本文設計了基于擦除編碼云存儲系統的視頻流模型。(2) 表征了對應于服務器的每個視頻片段的塊的下載時間的隨機變量模型。利用有序統計，找到對應于每個視頻片段回放時間的隨機變量，可進一步用于導出視頻的平均失速持續時間和視頻失速持續時間尾概率的上界。(3) 利用QoE度量，對視頻片段的布局選擇、概率調度訪問策略和與矩生成函數相關的有界參數等系統優化問題進行描述。(4) 數值結果表明，所提出的算法在幾次迭代中收斂。此外，與所考慮對比策略相比，QoE度量顯示出顯著的性能改善。例如，與隨機布局和投影等接入概率策略相比，該算法的平均失速持續時間小60%，失速持續時間尾概率好幾個數量級。