胡亞萍,王子磊

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

0 概述

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

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

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

1 視頻緩存模型

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

1.1 問題模型

1.2 數學模型

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

(1)

Subject to:

(2)

(3)

(4)

(5)

?m,v∈V,?n∈N

(6)

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

1.3 求解算法

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

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

(7)

Subject to:

(8)

(9)

(10)

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

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

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

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

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

該算法數學描述為:

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中每個元素X(v,n)是一個非0即1的值,其是離散二進制的。

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

針對問題(1),本文使用sigmoid函數將灰狼位置由連續(xù)空間轉化到離散空間,且只在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)如果該行行和不合法即該節(jié)點緩存視頻數超過緩存容量,更新X(i,j)為0并更新該行的行和;否則用集合Set記錄該行行號,更新i=i+1,跳到步驟6);

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

10)如果集合Set為空,選擇行和最小的行l(wèi)(如果有多個,隨機選一個),更新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種情況:超過一份(執(zhí)行步驟5)～步驟11)),正好一份(執(zhí)行步驟12)～步驟13)),尚未緩存(執(zhí)行步驟13))。當緩存超過一份時,選擇一個節(jié)點進行緩存,其余節(jié)點均不緩存(步驟8)～步驟10));當正好緩存一份時,如果緩存該視頻的節(jié)點未超過緩存容量,則不作處理,否則從緩存節(jié)點移除該視頻,隨機選取一個還剩有緩存空間的節(jié)點進行緩存(步驟13));當尚未緩存視頻時,直接執(zhí)行步驟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算法?？傮w思路是先求解視頻覆蓋問題,得到緩存矩陣X,隨后針對每個節(jié)點剩余的緩存空間,貪心緩存本節(jié)點覆蓋問題中未緩存的熱門請求視頻,直至用完緩存空間。結合兩者,得到最終的視頻緩存矩陣X。RCC算法具體步驟為:

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

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

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

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

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

7)如果還剩余緩存空間,則執(zhí)行步驟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 仿真環(huán)境與評價指標

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

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

2.2 仿真結果

2.2.1 緩存性能對比

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

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

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

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

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

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

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

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

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

2.2.2 計算性能對比

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

表1 消耗內存對比 GB

表2 消耗時間對比 s

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

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

3 結束語

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

[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] 龍 文,趙東泉,徐松金.求解約束優(yōu)化問題的改進灰狼優(yōu)化算法[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.