視頻點(diǎn)播系統(tǒng)中視頻分片協(xié)同存儲(chǔ)方案研究

趙曉明，周顥，何軍，趙保華

（1. 中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，230027，合肥；2. 安徽省計(jì)算與通訊軟件重點(diǎn)實(shí)驗(yàn)室，230027，合肥）

隨著無線網(wǎng)絡(luò)的迅猛發(fā)展，無線網(wǎng)絡(luò)提供的高速率傳輸使得視頻點(diǎn)播系統(tǒng)(Video on Demand，VoD)業(yè)務(wù)呈現(xiàn)爆炸性增長。如何利用有限的資源將海量的視頻數(shù)據(jù)存儲(chǔ)起來成為研究熱點(diǎn)[1-4]。

目前VoD視頻存儲(chǔ)研究的主流是利用服務(wù)器網(wǎng)絡(luò)內(nèi)部的高速鏈路來整合各個(gè)節(jié)點(diǎn)的存儲(chǔ)能力從而能夠勝任大規(guī)模的視頻庫存儲(chǔ)，即協(xié)同存儲(chǔ)。這需要考慮多方面的因素，例如服務(wù)器容量限制、鏈路帶寬限制、視頻內(nèi)容流行程度分布等。本文將視頻協(xié)同存儲(chǔ)與網(wǎng)絡(luò)編碼[5]相結(jié)合，提出了一種視頻分塊協(xié)同存儲(chǔ)最大本地命中算法，能夠得到最優(yōu)化的解決方案，并且當(dāng)視頻的總?cè)萘颗c服務(wù)器的總?cè)萘恐容^大時(shí)，依然有較好的表現(xiàn)。

1 背景以及相關(guān)工作

1.1 研究背景

無線互聯(lián)網(wǎng)正在蓬勃發(fā)展中，視頻流量出現(xiàn)爆炸性增長。VoD系統(tǒng)由于擺脫了時(shí)間、空間的限制，具有方便、快捷的優(yōu)點(diǎn)，因而具有廣泛的應(yīng)用。如圖1所示是一種應(yīng)用場景，利用長期演進(jìn)（Long Term Evolution，LTE）網(wǎng)絡(luò)中服務(wù)網(wǎng)關(guān)上的存儲(chǔ)能力為用戶提供視頻緩存服務(wù)。

圖1 VoD系統(tǒng)在長期演進(jìn)LTE網(wǎng)絡(luò)的應(yīng)用場景

在LTE網(wǎng)絡(luò)及其他VoD系統(tǒng)應(yīng)用場景下，為有效存入海量視頻庫，引入了協(xié)同存儲(chǔ)方案。每個(gè)服務(wù)器存儲(chǔ)視頻庫的一個(gè)子集，并將其存儲(chǔ)內(nèi)容通過直接響應(yīng)的方式為用戶提供服務(wù)或者通過協(xié)作請(qǐng)求為其他的服務(wù)器提供服務(wù)。對(duì)于用戶發(fā)出的視頻請(qǐng)求，如果對(duì)應(yīng)的服務(wù)器上有這個(gè)視頻的備份，則稱之為本地命中；否則，需要從其他的服務(wù)器上獲取該視頻，稱之為非本地命中。因此，如何將這些視頻分布式協(xié)同存儲(chǔ)到服務(wù)器網(wǎng)絡(luò)中有重要意義。

1.2 相關(guān)工作

在視頻協(xié)同存儲(chǔ)中，對(duì)不同的目標(biāo)進(jìn)行了研究。Applegate等基于硬盤空間、鏈路帶寬、視頻內(nèi)容流行程度等約束條件以最小化總的數(shù)據(jù)量為目標(biāo)進(jìn)行研究[1];Borst 等將協(xié)作存儲(chǔ)和路由聯(lián)系起來，以最大化服務(wù)節(jié)點(diǎn)能夠提供的流量并最小化總帶寬的花費(fèi)為目標(biāo)進(jìn)行了探討[3]。然而，他們所提算法復(fù)雜度太高，應(yīng)用場景也有局限。Xie等基于底層、非結(jié)構(gòu)化的簡單網(wǎng)絡(luò)利用交通工程和協(xié)作存儲(chǔ)從ISP的角度以最小化最大的擁塞程度為目標(biāo)進(jìn)行研究[2]。該算法需要判斷請(qǐng)求的模式，這顯然不實(shí)際。He等提出以最大化系統(tǒng)本地命中率為目標(biāo)的快速近似最優(yōu)的存儲(chǔ)方法，以提高系統(tǒng)本地命中率為目標(biāo)提出了一個(gè)快速貪婪算法[6]。

1.3 基于網(wǎng)絡(luò)編碼的視頻協(xié)同存儲(chǔ)算法

傳統(tǒng)的通信網(wǎng)絡(luò)傳送數(shù)據(jù)的方式是存儲(chǔ)轉(zhuǎn)發(fā)，即中間節(jié)點(diǎn)不對(duì)數(shù)據(jù)內(nèi)容做任何處理，只進(jìn)行轉(zhuǎn)發(fā)。網(wǎng)絡(luò)編碼[5](Network Coding, NC)通過中繼節(jié)點(diǎn)對(duì)接收到的信息進(jìn)行編碼來達(dá)到提高多播網(wǎng)絡(luò)容量。在網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)上對(duì)各條信道上收到的信息進(jìn)行線性或非線性的處理，然后轉(zhuǎn)發(fā)給下游節(jié)點(diǎn)。

在VoD系統(tǒng)中，可以利用網(wǎng)絡(luò)編碼預(yù)先將視頻進(jìn)行分片編碼。在接收到視頻請(qǐng)求時(shí)，將編碼后的視頻片發(fā)給用戶。客戶端接收到足夠的視頻片后可進(jìn)行解碼，從而得到完整的視頻。

采用NC編碼能有效提高存儲(chǔ)效率，提高系統(tǒng)可靠性。本文研究的目標(biāo)是將前期的問題[7]與NC編碼的分塊存儲(chǔ)相結(jié)合，提出基于NC編碼的視頻分塊協(xié)同存儲(chǔ)方案，使得本地命中率最大。

2 系統(tǒng)建模

建立一個(gè)VoD系統(tǒng)，視頻集合為N，視頻ni∈N原始的大小是si。采用NC編碼，每個(gè)切片的大小為。由NC編碼的原理可知，對(duì)于視頻ni，系統(tǒng)中可以產(chǎn)生任意數(shù)目的切片。而在這些切片中，用戶至少需要獲得才能恢復(fù)出視頻。

服務(wù)器集合M用來存儲(chǔ)視頻，服務(wù)器mt∈M的可用容量為Wt。在實(shí)際中，si＜＜Wt。假定視頻ni在服務(wù)器mt上的訪問頻率為，視頻ni在服務(wù)器mt上存放的視頻切片塊數(shù)為。定義變量如表1所示。

表1 各種變量的定義列表

在VoD協(xié)同存儲(chǔ)中，本地命中越多，網(wǎng)絡(luò)中流量就會(huì)變得越少，從而節(jié)省大量的帶寬。因此，提出基于分片的最大命中問題(Maximum Hit Problem based on Segment，MHPS)的表達(dá)式為

約束條件(a)表示對(duì)于服務(wù)器mt，所存儲(chǔ)的視頻的總?cè)萘坎坏么笥趍t的容量；約束條件(b)表示對(duì)于視頻ni，在服務(wù)器mt上放置的片段數(shù)目不得大于Ri；約束條件(c)表示對(duì)于視頻ni，系統(tǒng)中所存儲(chǔ)切片總數(shù)必須能夠保證恢復(fù)出該視頻。

3 基于最小費(fèi)用流問題的MHPS

最小費(fèi)用流問題是指在給定網(wǎng)絡(luò)中求從一個(gè)源節(jié)點(diǎn)到目的節(jié)點(diǎn)流值為某一常數(shù)的流，使其費(fèi)用最小[7]。該問題有著廣泛的應(yīng)用，例如物流管理、供應(yīng)鏈研究等領(lǐng)域。

本節(jié)構(gòu)造出一個(gè)資源分配有向圖GMHPS，證明了圖GMHPS上最小費(fèi)用流問題的解就是問題(1)的解，然后給出相應(yīng)的算法。

3.1 資源分配有向圖MHPSG

定義圖GMHPS=(V,E)，其頂點(diǎn)集合為V=M∪N∪ {s,t} ∪ {sremain,vremain}，其中，sremain、vremain為虛擬節(jié)點(diǎn)，|V| =O(N+M)。

圖GMHPS的邊主要由7類組成，如表2所示。

表2 GMHPS 邊的類型

假設(shè)邊e的起始頂點(diǎn)為estart，終止頂點(diǎn)為eend，邊e的容量函數(shù)為

邊e花費(fèi)函數(shù)為

當(dāng) |M|=2，|N|=3時(shí)，GMHPS系統(tǒng)如圖 2所示。

圖2 | M |=2,| N |=3時(shí) GMHPS 圖

GMHPS中，從s節(jié)點(diǎn)流入的流量即為系統(tǒng)中服務(wù)器的總?cè)萘俊到mt邊的容量為服務(wù)器mt所能存放的切片數(shù)，即。由于從s流入的流量為所有s到mt的邊容量的和，所以每個(gè)s到mt邊的流量也一定是mt能夠存放的切片數(shù)目。

邊mt到ni的容量是恢復(fù)ni所需要的最小切片數(shù)，而其上的流量則表示ni在mt上放置的片數(shù)。邊ni到t的容量是恢復(fù)ni所需要的最小切片數(shù)，由于網(wǎng)絡(luò)流的流量守恒特性以及vremain到t的容量可知，邊ni到t的流量等于邊的容量。

此時(shí)，視頻ni在服務(wù)器mt上的存放片數(shù)kti即為從服務(wù)器mt到該視頻ni的流量（GMHPS圖中網(wǎng)絡(luò)流的單位為切片的大小），從而求解出MHPS問題。例如，圖 3表示GMHPS的一個(gè)實(shí)例，邊上的數(shù)字表示分配的流量，其中，視頻n1從服務(wù)器m1和服務(wù)器m2上分別得到流量為 4和 3，則對(duì)應(yīng)的分配方案就是=4，=3，其他同理。

因此，若圖GMHPS上可行解為ψ，邊 ＜mt,ni＞的流量為MHPS中kti的值。由kti組成的解決方案為MHPS的解。

3.2 GMHPS最小費(fèi)用流的解為MHPS問題的解

設(shè)ψ是GMHPS的一個(gè)解，ξ是MHPS的一個(gè)解。下面從兩個(gè)方面來證明ψ與ξ一一對(duì)應(yīng)。

圖3 圖 GMHPS 與分配方案的關(guān)系

引理1GMHPS的解ψ是MHPS的解ξ。

假定ψ是GMHPS的一個(gè)解，根據(jù)GMHPS中E1集合的容量函數(shù)定義可知，服務(wù)器mt的流量最大為，滿足約束條件（a）；同時(shí)，根據(jù)GMHPS中E2集合容量函數(shù)定義可知，視頻ni放在服務(wù)器mt上的數(shù)目不超過Ri，滿足約束條件（b）；由vremain到t的容量限制可知，每一個(gè)視頻ni到t的流量至少為Ri，滿足約束條件（c）。因此，ψ中服務(wù)器到視頻集合的分配方案是MHPS的一個(gè)解ξ。

引理2MHPS的解ξ是GMHPS的解ψ。

假定ξ是MHPS的一個(gè)解，根據(jù)ξ中視頻到服務(wù)器的分配方案，依照GMHPS的定義，可以構(gòu)建出一個(gè)對(duì)應(yīng)的圖G的一個(gè)解ψ。因此，由ξ構(gòu)造的解ψ是GMHPS的一個(gè)解。

綜上，GMHPS的解與MHPS的解一一對(duì)應(yīng)。因此，定理1顯然得證。

定理1由GMHPS上最小費(fèi)用流問題的解是MHPS問題的最優(yōu)解。

3.3 算法及其時(shí)間復(fù)雜度

最小費(fèi)用流問題已經(jīng)有較多的實(shí)現(xiàn)[8-9]，Orlin等提出了多項(xiàng)式時(shí)間的原始網(wǎng)絡(luò)單純形算法[8]。在仿真實(shí)驗(yàn)中，利用LEMON[10]函數(shù)庫進(jìn)行求解。

GMHPS中 ，|V|=O(N+M)，|E|=O(NM)，GMHPS時(shí)間復(fù)雜度為O(NM)。LEMON庫基于網(wǎng)絡(luò)單純形算法，其復(fù)雜度[8]是O(t2s2logt))，其中t和s分別是網(wǎng)路中節(jié)點(diǎn)數(shù)和邊數(shù)。因此本算法時(shí)間復(fù)雜度是O((NM)2(N+M)2log(N+M))。在實(shí)際系統(tǒng)中，|N|＞＞|M|，所以本算法的時(shí)間復(fù)雜度為O(N4M2logN)。

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

4.1 仿真環(huán)境

在仿真試驗(yàn)中，建立一個(gè)VoD緩存系統(tǒng)，其中，單個(gè)服務(wù)器的容量大小從120 G到240 G隨機(jī)分布。單個(gè)視頻大小從20 M到400 M隨機(jī)分布。

4.2 性能比較

這里將MHPS算法和兩種算法進(jìn)行了比較。第一種是文獻(xiàn)[6]中提出的MHP算法，不考慮視頻切片問題，直接將完整的視頻存儲(chǔ)于某個(gè)服務(wù)器。第二種算法是貪心算法MHPSG，即以訪問頻率的大小順序來遍歷視頻庫，將其存放到各個(gè)最優(yōu)的服務(wù)器上，從而保證系統(tǒng)中存入了完整的視頻庫，運(yùn)用多重背包問題將服務(wù)器剩余的空間盡可能多存儲(chǔ)。

圖4繪制了在服務(wù)器數(shù)目分別為10和20的情況下，當(dāng)視頻數(shù)目從100變到1 600時(shí)3種算法的性能。由圖 4可見，①當(dāng)服務(wù)器的數(shù)目和容量保持不變的時(shí)候，系統(tǒng)所獲的收益呈現(xiàn)下降趨勢，這是由于大量的低價(jià)值的視頻分片占據(jù)了系統(tǒng)的容量，當(dāng)視頻片段數(shù)目達(dá)到一定的數(shù)目時(shí)，由于視頻片段的總空間大于服務(wù)器的總空間，因而出現(xiàn)無解的情況；②對(duì)比不同的算法可以看出，MHPS算法優(yōu)于MHP和 MHPSG算法。隨著視頻總?cè)萘康脑黾樱琈HPS算法的優(yōu)勢更加明顯。例如當(dāng)視頻總?cè)萘窟_(dá)到服務(wù)器總?cè)萘康?90 %左右時(shí)，MHPS算法的性能超過MHP算法 10 %以上。

對(duì)于MHPS，顯然，切片大小對(duì)系統(tǒng)的性能有影響。圖5中繪制了在不同系統(tǒng)規(guī)模下，切片大小對(duì)系統(tǒng)性能的影響。

當(dāng)切片數(shù)目過小時(shí)，由于大量收益低的視頻切片會(huì)降低整個(gè)視頻庫視頻切片的平均收益，從而導(dǎo)致系統(tǒng)性能下降。當(dāng)切片數(shù)目過大時(shí)，容易造成系統(tǒng)空間浪費(fèi)，導(dǎo)致系統(tǒng)性能下降。由圖5可見，當(dāng)切片大小為1 M，系統(tǒng)具有最佳的性能。因此，本文中選擇了1 M作為默認(rèn)的切片大小。

圖4 不同算法獲得收益的比較

圖5 不同系統(tǒng)規(guī)模下切片大小對(duì)系統(tǒng)性能的影響

5 結(jié) 論

VoD視頻協(xié)同存儲(chǔ)對(duì)于提高服務(wù)質(zhì)量、提升用戶體驗(yàn)、減小等待延遲等具有重要的意義，本文通過基于NC編碼，對(duì)VoD視頻協(xié)同存儲(chǔ)問題進(jìn)行了探究，提出了一個(gè)VoD系統(tǒng)中基于分片的視頻協(xié)同存儲(chǔ)解決方案 MHPS，該算法具有多項(xiàng)式時(shí)間復(fù)雜度。通過仿真，可以看出MHPS能夠?qū)崿F(xiàn)最優(yōu)化的收益，該算法優(yōu)于MHP算法，特別是在視頻庫的容量接近服務(wù)器的總?cè)萘康那闆r下，MHPS算法能夠提供較大的收益提升。

[1]APPLEGATE D, ARCHER A, GOPALAKRISHNAN V, et al. Optimal content placement for a large-scale VoD system[C]// Proceedings of the 6th International Conference on Emerging Networking Experiments and Technologies.New York, USA:ACM, 2010：4.

[2]XIE Haiyong, SHI Guangyu, WANG Pengwei. TECC:towards collaborative in-network caching guided by traffic engineering[C]//Proceedings of the International Conference on Computer Communications. Piscataway, NJ,USA:IEEE, 2012:2546-2550.

[3]BORST S, GUPTA V, WALID A. Distributed caching algorithms for content distribution networks[C]//Proceedings of the International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2010:1-9.

[4] ADAMIC L A. Zipf, power-laws, and pareto-a ranking tutorial [EB/OL]. (2000-04-10) [2013-11-16].http://impact.asu.edu/cse591sp11/ZipfParetoPowerranking.pdf.

[5]AHLSWEDE R, CAI Ning, LI S Y R, et al. Network information flow [J]. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216.

[6]HE Jun, ZHAO Xiaoming, ZHAO Baohua. A fast, simple and near-optimal content placement scheme for a large-scale VoD system[C]// Proceedings of the 2012 IEEE International Conference on Communication Systems.Piscataway, NJ, USA:IEEE, 2012:378-382.

[7]AHUJA R K, MAGNANTI T L, ORLIN J B. Network flows:theory, algorithms, and applications [J]. Journal of the Operational Research Society, 1994, 45(11):1340-1340.

[8]ORLIN J B. A polynomial time primal network simplex algorithm for minimum cost flows [J]. Mathematical Programming, 1997, 78(2):109-129.

[9]DANTZIG G B. Linear programming and extensions[M].Berlin，Germany：Springer-Verlag, 1998:404-412.

[10]Egerváry research group on combinatorial optimization.Library for efficient modeling and optimization in networks [EB/OL]. (2011-06-07) [2013-11-16].http://lemon.cs.elte.hu.