一種命名數據網絡的視頻全域協作緩存算法

胡亞萍,王子磊

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

0 概述

目前網絡中視頻流量呈迅速增長趨勢,傳統網絡已難以滿足用戶對視頻的需求。命名數據網絡[1](Named Data Networking,NDN)是一種以內容為中心的未來網絡架構,在NDN中,每個節點具有一定的緩存功能,緩存該視頻節點可以滿足用戶的視頻需求。緩存可以顯著降低用戶訪問時延,減小跨網間傳輸流量,減輕服務器負載[2]。然而,相對互聯網的海量視頻內容,節點內緩存容量有限。因此,如何制定緩存決定策略是NDN研究的關鍵問題之一。

NDN運行時默認采用全緩存(Leave Cache Everywhere,LCE)策略,該策略操作簡單,易于實現,但是其并未考慮與其他節點間的緩存協作,容易造成網絡中大量緩存內容冗余。文獻[3]提出一種概率型緩存方案ProbCache,綜合考慮節點緩存能力、待緩存節點到客戶端的距離等因素,從而確定內容緩存概率。此外,文獻[4]也做了相關研究。但是,上述方案都只進行了請求路徑上的協作緩存,并未實現更大規模(如自治域)的協作,冗余下降有限。針對NDN路徑緩存協作的局限性,研究者考慮將軟件定義網絡(Software Defined Networking,SDN)[5]和NDN進行結合[6-7],引入集中式控制器進行全域協作,從而提升緩存性能。為了實現視頻域內協作緩存,文獻[8]構建一種混合整數規劃模型,將內容簡單分組后使用優化器進行求解,但該模型限制了求解規模。文獻[9]構建一種全局協作緩存模型并提出OPT-GA求解算法,OPT-GA算法對請求內容按流行度排序,分別使用遺傳算法進行求解,導致熱門內容大量冗余,中等熱度內容沒有緩存,該算法未能充分利用緩存空間。

針對以上方案的不足,本文首先建立一種全域協作緩存模型,針對求解模型難度較大的特點,給出一種灰狼非法位置更正算法并引入sigmoid函數,然后在灰狼優化(Grey Wolf Optimization,GWO)算法的基礎上進行改進,得到二進制灰狼優化算法IBGWO,最后綜合IBGWO算法和貪心算法,提出用于模型求解的預留協作緩存算法RCC。

1 視頻緩存模型

本文將一個自治域看成一個協作緩存整體,每個緩存周期開始時執行視頻協作緩存算法,確定各個緩存節點應該緩存的視頻,然后緩存內容進行周期性更新。考慮到節點緩存空間有限,此處只考慮緩存目標周期內請求的熱門視頻。本文的優化目標是優化給定周期內給定熱門集的用戶請求視頻時延。

1.1 問題模型

1.2 數學模型

根據上述已知條件和變量假設,以最小化用戶請求熱門視頻時延(用跳數表示)為目標,給出目標函數及相關約束:

(1)

Subject to:

(2)

(3)

(4)

(5)

?m,v∈V,?n∈N

(6)

上述模型問題是一個整數規劃且屬于NP-hard[12]的問題,其隨著節點數和視頻數的增加,計算復雜度顯著增加。1.3節將提出一種新的預留協作緩存算法,用以較快求得該問題的近似最優解。

1.3 求解算法

考慮到少數視頻具有很高的流行度,因此,每個節點盡可能選擇本節點請求量較高的視頻進行緩存,從而減小請求跳數。但是,各個節點均獨立緩存,容易造成整體緩存冗余,因此,還需留一部分空間用于協作緩存,以增加緩存視頻的種類數,從而滿足視頻的覆蓋性要求。由于本地緩存的具體緩存空間大小難以控制,因此可優先滿足視頻覆蓋性要求,然后在各個節點剩余緩存空間貪心地緩存本節點尚未緩存的請求頻率高的視頻。這樣既滿足了本地緩存熱門視頻的需求,又實現了選中視頻集域內全覆蓋的目標。此外,將緩存空間分為2個部分,還能避免由全部空間用于全域協作緩存所帶來的高計算復雜度問題。具體求解步驟如下:

1)解決視頻覆蓋問題,思路是使視頻滿足覆蓋性要求,每個視頻只緩存一份,請求只能從緩存該視頻的唯一節點處獲得。此時,原問題轉化為:

(7)

Subject to:

(8)

(9)

(10)

顯然,該問題還是一個NP-hard問題,目前較少有很好的求解策略,只能通過啟發式算法來求解。

GWO算法[13]是一種基于灰狼群體捕食所設計的啟發式算法,具有原理簡單、全局搜索能力強等特點,在函數優化方面已被證明其收斂速度和求解精度均優于粒子群優化算法[14]。

GWO算法的基本思想是效仿灰狼捕食過程,其對候選解進行分級,將當前適應度值最佳、第二、第三的解分別記為α、β、δ,其余的候選解記為ω,獵物的位置即為問題的最優解。捕食(優化)過程中,ω依據α、β、δ更新自己的位置。具體的更新過程如圖1所示。

圖1 GWO算法位置更新示意圖

在搜索空間先隨機產生一群灰狼,進化過程中,由α、β、δ狼估計獵物(全局最優解)的位置,其他狼分別計算自己與α、β、δ狼的距離,以此來估計自身與獵物的距離,然后逐漸向獵物靠近、包圍,最終將獵物成功捕獲。

該算法數學描述為:

Dα=|C1·Xα(t)-X(t)|

(11)

Dβ=|C2·Xβ(t)-X(t)|

(12)

Dδ=|C3·Xδ(t)-X(t)|

(13)

(14)

(15)

(16)

(17)

式(11)～式(16)計算ω狼距離α、β、δ的距離,式(17)判斷ω狼向獵物移動的方向。其中,t為當前迭代次數,X(t)為灰狼當前位置,X(t+1)為灰狼下一次迭代位置,C=2r1,A=2ar2-a,a隨迭代次數在[2,0]間線性遞減,r1、r2為[0,1]間的隨機值。

2)使用GWO算法求解視頻覆蓋問題。每種緩存方案X對應一只灰狼,灰狼位置的變化對應緩存方案的更新。然而,要使用GWO算法進行求解,首先需要解決以下2個問題:

(1) GWO算法對應的位置更新函數(式(17))為連續函數,更新的位置可能是搜索空間中的任何一處,而本文求解的X中每個元素X(v,n)是一個非0即1的值,其是離散二進制的。

(2)GWO算法適用于求解無約束的優化問題,而本文適應度函數受式(8)～式(10)約束。

針對問題(1),本文使用sigmoid函數將灰狼位置由連續空間轉化到離散空間,且只在0和1間轉換。具體表示為:

(18)

(19)

其中,r為[0,1]間的隨機值,式(18)每次更新X中的一個元素值。

針對問題(2),灰狼在迭代更新位置時,如果位置不符合式(8)～式(10)的約束,則定義為非法位置,需要將位置調整到合法的搜索空間。式(8)表示X矩陣每一列的列和均為1,對應于灰狼每個列向量n的元素和為1;式(9)表示X矩陣每一行的行和均小于緩存容量,對應于灰狼的每個行向量v的元素和小于緩存容量;式(10)可以直接由式(18)保證。上述約束轉化為灰狼位置約束,即對于每只灰狼,其位置的每一行的和不能大于c,每一列的和必須等于1,否則為非法位置。

在灰狼位置更新過程中,采用如下算法對位置進行檢測與更正。

算法位置檢測與更正

1)計算X每一行的行和與每一列的列和;

2)初始化列j=1;

3)處理第j列;

4)如果j=|N|+1,即處理完所有列,轉到步驟14);如果第j列列和大于1,轉到步驟5);如果第j列列和等于1,轉到步驟12);如果第j列列和等于0,轉到步驟13);

5)初始化行i=1,初始化記錄行和合法的行號的集合Set為空集;

6)處理第i行;

7)如果i=|V|+1,即處理完該列所有行,跳到步驟9);否則判斷該行元素X(i,j)為否為1,為1則跳到步驟8),為0則更新行號i=i+1,跳到步驟6);

8)如果該行行和不合法即該節點緩存視頻數超過緩存容量,更新X(i,j)為0并更新該行的行和;否則用集合Set記錄該行行號,更新i=i+1,跳到步驟6);

9)如果集合Set不為空,從Set中隨機選擇一個元素l,保持X(l,j)為1,將Set中所有其他元素u對應的X(u,j)中的元素變為0,并更新u行行和;

10)如果集合Set為空,選擇行和最小的行l(如果有多個,隨機選一個),更新X(l,j)為1,并更新l行行和;

11)更新j=j+1,跳到步驟3);

12)遍歷行選擇X(i,j)為1的行i,如果該行行和合法,則更新j=j+1,跳到步驟3);否則更新X(i,j)為0并更新該行行和;

13)選取行和小于緩存容量的行的集合,從集合中隨機挑選一個行號l使得X(l,j)為1,并更新該行行和,更新j=j+1,跳到步驟3);

14)輸出X,結束算法。

該算法總體思想是對每個緩存矩陣X,以列為單位進行遍歷,即遍歷每個視頻,其域內緩存的數量只有3種情況:超過一份(執行步驟5)～步驟11)),正好一份(執行步驟12)～步驟13)),尚未緩存(執行步驟13))。當緩存超過一份時,選擇一個節點進行緩存,其余節點均不緩存(步驟8)～步驟10));當正好緩存一份時,如果緩存該視頻的節點未超過緩存容量,則不作處理,否則從緩存節點移除該視頻,隨機選取一個還剩有緩存空間的節點進行緩存(步驟13));當尚未緩存視頻時,直接執行步驟13)。

上述2個問題都解決后,將使用IBGWO算法求解視頻覆蓋問題。首先初始化k只灰狼,每次選取適應度最佳(式(7)最小)的3只狼,記為Xα、Xβ、Xδ,其他狼依據這3只狼的位置更新自己的位置信息,位置更新過程中使用位置檢測與更正算法對非法位置進行更正,逐次迭代,當達到最大迭代次數時,結束算法。IBGWO算法處理步驟如下:

1)使用只包含0、1元素的隨機矩陣初始化k只灰狼的初始位置Xi,i=1,2,…,k;

2)初始化參數a、A和C,初始化迭代次數iter=1;

3)將式(7)作為適應度函數,分別計算每只灰狼的適應度值,將適應度值最小、第二小、第三小的灰狼分別記為Xα、Xβ、Xδ,并記錄Xα的適應度值;

4)進行第iter次迭代;

5)對每只灰狼Xi使用式(18)更新位置信息,更新后使用位置檢測與更正算法更正不合法的位置信息;

6)更新a、A和C;

7)重新計算每只灰狼的適應度值,更新Xα、Xβ、Xδ,并記錄Xα的適應度值;

8)迭代次數加1,如果達到最大迭代次數,跳到步驟9);否則跳到步驟4);

9)輸出Xα及對應的適應度值,結束算法。

至此,視頻覆蓋問題已經解決,將它與貪心算法進行結合,得出求解原模型的RCC算法。總體思路是先求解視頻覆蓋問題,得到緩存矩陣X,隨后針對每個節點剩余的緩存空間,貪心緩存本節點覆蓋問題中未緩存的熱門請求視頻,直至用完緩存空間。結合兩者,得到最終的視頻緩存矩陣X。RCC算法具體步驟為:

1)使用IBGWO算法求解全局緩存問題,得到全域協作緩存矩陣X;

2)初始化路由器節點集合R=V;

3)如果R不為空,則從R中選擇一個路由器節點v,并從R中去除節點v;否則跳到步驟10);

5)將節點v上請求的視頻按請求頻率的降序進行排列;

6)初始化排序后的視頻編號i=1;

7)如果還剩余緩存空間,則執行步驟8);否則跳到步驟3);

8)如果X中未緩存編號i對應的視頻,則緩存,并更新X以及剩余的緩存空間c*=c*-1;

9)更新視頻編號i=i+1,跳到步驟7);

10)使用X利用式(6)得到矩陣Z,并計算式(1)的值;

11)輸出緩存矩陣X和對應的式(1)的值。

2 性能評價

2.1 仿真環境與評價指標

本文采用文獻[8]中所用的隨機網絡拓撲,該域共包含15個路由器,請求的視頻集為10 000個服從參數為0.8的Zipf分布視頻塊,每塊大小為15 MB,約等于YouTube視頻平均大小[15]。終端用戶發出視頻請求,請求服從λ=50個/s的泊松分布,總請求數為1 000 000。如果請求視頻域內尚未緩存,則從域外服務器獲取,域外響應跳數取網絡平均響應跳數,本文取12跳[16]。采用文獻[11]中所述的基于SDN的路由方式,即緩存視頻全域可見,可直接將請求路由到最近的緩存節點或網關節點。

為評價緩存策略的效果,本文采用緩存命中率和平均請求跳數2個評價指標。緩存命中率即域內服務的請求數與總請求數之比,其值越高,則有越多的請求在域內直接命中,可以節省域外流量,同時減小服務端負載,該值是一個重要的緩存性能指標;平均請求跳數即視頻從服務節點到客戶端經歷的總跳數與所有請求數之比,該值反映客戶端平均響應時延,對于視頻類請求而言,較大的響應時延將嚴重影響用戶體驗。

2.2 仿真結果

2.2.1 緩存性能對比

將RCC算法與NDN典型緩存策略LCE和ProbCache以及文獻[5]中使用的用遺傳算法實現全局緩存的方案(OPT-GA)作對比。RCC中熱門視頻數設為域內最大緩存容量數的0.9倍。RCC和OPT-GA仿真過程中基本不發生替換,LCE和ProbCache采用LRU替換策略。現有研究普遍認為緩存容量、內容總量和Zipf參數α對緩存性能影響很大,故本文著重驗證緩存容量和內容總量的比值與視頻流行度α對緩存性能的影響。

1)緩存大小對緩存性能的影響

選取視頻流行度參數α=0.8。緩存大小對緩存性能的影響如圖2所示。

圖2 緩存大小對緩存性能的影響

由圖2(a)可以看出,隨著域內節點緩存容量的增大,LCE算法、ProbCache算法、OPT-GA算法和RCC算法域內緩存命中率均有所提高,其中,RCC算法和OPT-GA算法整體比LCE算法和ProCache算法緩存命中率高,原因是前面2種算法實現了更大范圍的緩存,網絡中緩存冗余降低,緩存視頻種類數增多,導致緩存命中率增加。RCC算法比OPT-GA算法命中率高,原因是OPT-GA算法是按請求度由高到低對每個視頻分別使用遺傳算法進行求解,導致一些熱門影片緩存過多,一些中等熱度視頻沒有空間緩存,從而命中率低于RCC算法。由圖2(b)可以看出,平均請求跳數隨著緩存容量的增大而減小。緩存命中率越高,更多的請求在域內被命中,相對域外,所需接入跳數顯著減小。而隨著緩存空間的增大,RCC算法平均跳數有所減小,一方面因為局部緩存熱門視頻增多,更多請求直接在接入路由器節點命中,域內跳數減小;另一方面因為域內協作緩存視頻種類多,路由到域外的請求少,導致平均請求跳數減小。

2)視頻流行度α對緩存性能的影響

考慮到一般緩存空間占總的緩存容量的5%左右,本文選定緩存容量與內容總量的比值為6%。視頻流行度α對緩存性能的影響如圖3所示。

圖3 視頻流行度對緩存性能的影響

由圖3(a)可以看出,4種緩存方案的緩存命中率隨著視頻流行度α的變化情況是,α從0.8變化至2.0時,緩存命中率均有非常大的提升,當α較小時,RCC算法優勢明顯,此時RCC算法大幅度地增加了域內緩存視頻的種類數。當α為1.7時,4種算法緩存命中率都接近100%,原因是此時流行視頻很集中,緩存策略性能相差不大。圖3(b)也呈現類似的結果,α較小時,RCC算法優勢較大,因為緩存視頻種類多,域外請求數相對另外3種算法少,導致平均請求跳數少。

2.2.2 計算性能對比

為了驗證RCC算法的效率,選用CVX激活gurobi優化器對本文模型進行求解,gurobi能以較快的速度求解混合整數規劃問題,是目前最好的優化器之一。在相同條件下,將RCC算法與CVX分別從內存消耗、求解時間和解的質量三方面作對比,結果如表1～表3所示。

表1 消耗內存對比 GB

表2 消耗時間對比 s

表3 域內平均請求跳數對比

由表1可以看出,本文策略只消耗少量內存資源,因為求解過程中,其只存儲了少量的灰狼位置變量,而使用CVX優化器求解則非常消耗內存資源,特別是視頻種類數較多時,CVX消耗內存顯著增長。當緩存視頻數為5 000時,CVX優化器消耗的內存為RCC算法的114倍。實驗時緩存視頻種類數達到6 000時,使用CVX優化器求解時計算機顯示內存不足,而RCC算法仍只消耗少量內存,因此,RCC算法更適合求解大規模緩存問題,這也更符合現實情況。由表2可以看出,RCC算法求解時間始終小于CVX優化器,而且隨著域內緩存視頻種類數的增大,CVX優化器求解時間顯著增長。表3顯示兩者的求解質量,從中可以看出,使用RCC算法求解與使用CVX優化器求解,性能相差6%左右,因此,RCC算法能以較少的時間和較少的內存求得近似最優解,規模越大,其優勢越明顯。

3 結束語

為解決傳統視頻分發啟動時延遲較大等問題,本文針對NDN設計一種視頻協作緩存算法RCC。綜合使用貪心算法和改進的二進制灰狼算法,分別求解本地熱門緩存問題和全域協作緩存問題。仿真結果表明,相較于緩存策略LCE算法、ProbCache算法和OPT-GA算法,該算法在緩存命中率和平均請求跳數方面均有明顯提升。下一步將解決動態條件下用該視頻放置策略時的視頻請求調度和路由問題,即對于域內有多個緩存該視頻的節點,如何實時選擇合適的服務節點及相應的路由策略。

[1] ZHANG L,AFANASYEV A,BURKE J,et al.Named data networking[J].ACM SIGCOMM Computer Communication Review,2014,44(3):66-73.

[2] 曲 樺,王偉萍,趙季紅.內容中心網絡中一種改進型緩存機制[J].計算機工程,2015,41(3):41-46.

[3] PSARAS I,CHAI W K,PAVLOU G.Probabilistic in-network caching for information-centric networks[C]//Proceedings of the 2nd ICN Workshop on Information-centric Networking.New York,USA:ACM Press,2012:55-60.

[4] CHO K,LEE M,PARK K,et al.Wave:popularity-based and collaborative in-network caching for content-oriented networks[C]//Proceedings of 2012 IEEE Conference on Computer Communications Workshops.Washington D.C.,USA:IEEE Press,2012:316-321.

[5] MCKEOWN N.Software-defined networking[J].INFOCOM Keynote Talk,2009,17(2):30-32.

[6] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.

[7] SYRIVELIS D,PARISIS G,TROSSEN D,et al.Pursuing a software defined information-centric network[C]//Proceedings of 2012 European Workshop on Software Defined Networking.Washington D.C.,USA:IEEE Press,2012:103-108.

[8] KIM Y,YEOM I.Performance analysis of in-network caching for content-centric networking[J].Computer Networks,2013,57(13):2465-2482.

[9] 胡 騫.以內容為中心的網絡中緩存技術的若干問題研究[D].北京:北京郵電大學,2015.

[10] LIU R,YIN H,CAI X,et al.Cooperative caching scheme for content oriented networking[J].IEEE Communications Letters,2013,17(4):781-784.

[11] AUBRY E,SILVERSTON T,CHRISMENT I.SRSC:SDN-based routing scheme for CCN[C]//Proceedings of the 1st IEEE Conference on Network Softwarization.Washington D.C.,USA:IEEE Press,2015:1-5.

[12] BAEV I,RAJARAMAN R,SWAMY C.Approximation algorithms for data placement problems[J].SIAM Journal on Computing,2008,38(4):1411-1429.

[13] MIRJALILI S,MIRJALILI S M,LEWIS A.Grey wolf optimizer[J].Advances in Engineering Software,2014,69:46-61.

[14] 龍 文,趙東泉,徐松金.求解約束優化問題的改進灰狼優化算法[J].計算機應用,2015,35(9):2590-2595.

[15] CHE X,IP B,LIN L.A survey of current YouTube video characteristics[J].IEEE Multimedia,2015,22(2):56-63.

[16] FEI A,PEI G,LIU R,et al.Measurements on delay and hop-count of the Internet[EB/OL].[2017-04-05].http://nrlweb.cs.ucla.edu/nrlweb/publication/download/281/garyglcm98.pdf.