一種命名數(shù)據(jù)網(wǎng)絡(luò)的視頻全域協(xié)作緩存算法

胡亞萍,王子磊

(中國(guó)科學(xué)技術(shù)大學(xué) 自動(dòng)化系,合肥 230027)

0 概述

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

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

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

1 視頻緩存模型

本文將一個(gè)自治域看成一個(gè)協(xié)作緩存整體,每個(gè)緩存周期開(kāi)始時(shí)執(zhí)行視頻協(xié)作緩存算法,確定各個(gè)緩存節(jié)點(diǎn)應(yīng)該緩存的視頻,然后緩存內(nèi)容進(jìn)行周期性更新。考慮到節(jié)點(diǎn)緩存空間有限,此處只考慮緩存目標(biāo)周期內(nèi)請(qǐng)求的熱門(mén)視頻。本文的優(yōu)化目標(biāo)是優(yōu)化給定周期內(nèi)給定熱門(mén)集的用戶請(qǐng)求視頻時(shí)延。

1.1 問(wèn)題模型

1.2 數(shù)學(xué)模型

根據(jù)上述已知條件和變量假設(shè),以最小化用戶請(qǐng)求熱門(mén)視頻時(shí)延(用跳數(shù)表示)為目標(biāo),給出目標(biāo)函數(shù)及相關(guān)約束:

(1)

Subject to:

(2)

(3)

(4)

(5)

?m,v∈V,?n∈N

(6)

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

1.3 求解算法

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

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

(7)

Subject to:

(8)

(9)

(10)

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

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

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

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

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

該算法數(shù)學(xué)描述為:

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)計(jì)算ω狼距離α、β、δ的距離,式(17)判斷ω狼向獵物移動(dòng)的方向。其中,t為當(dāng)前迭代次數(shù),X(t)為灰狼當(dāng)前位置,X(t+1)為灰狼下一次迭代位置,C=2r1,A=2ar2-a,a隨迭代次數(shù)在[2,0]間線性遞減,r1、r2為[0,1]間的隨機(jī)值。

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

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

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

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

(18)

(19)

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

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

在灰狼位置更新過(guò)程中,采用如下算法對(duì)位置進(jìn)行檢測(cè)與更正。

算法位置檢測(cè)與更正

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

2)初始化列j=1;

3)處理第j列;

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

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

6)處理第i行;

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

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

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

10)如果集合Set為空,選擇行和最小的行l(wèi)(如果有多個(gè),隨機(jī)選一個(gè)),更新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)選取行和小于緩存容量的行的集合,從集合中隨機(jī)挑選一個(gè)行號(hào)l使得X(l,j)為1,并更新該行行和,更新j=j+1,跳到步驟3);

14)輸出X,結(jié)束算法。

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

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

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

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

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

4)進(jìn)行第iter次迭代;

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

6)更新a、A和C;

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

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

9)輸出Xα及對(duì)應(yīng)的適應(yīng)度值,結(jié)束算法。

至此,視頻覆蓋問(wèn)題已經(jīng)解決,將它與貪心算法進(jìn)行結(jié)合,得出求解原模型的RCC算法?？傮w思路是先求解視頻覆蓋問(wèn)題,得到緩存矩陣X,隨后針對(duì)每個(gè)節(jié)點(diǎn)剩余的緩存空間,貪心緩存本節(jié)點(diǎn)覆蓋問(wèn)題中未緩存的熱門(mén)請(qǐng)求視頻,直至用完緩存空間。結(jié)合兩者,得到最終的視頻緩存矩陣X。RCC算法具體步驟為:

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

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

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

5)將節(jié)點(diǎn)v上請(qǐng)求的視頻按請(qǐng)求頻率的降序進(jìn)行排列;

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

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

8)如果X中未緩存編號(hào)i對(duì)應(yīng)的視頻,則緩存,并更新X以及剩余的緩存空間c*=c*-1;

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

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

11)輸出緩存矩陣X和對(duì)應(yīng)的式(1)的值。

2 性能評(píng)價(jià)

2.1 仿真環(huán)境與評(píng)價(jià)指標(biāo)

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

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

2.2 仿真結(jié)果

2.2.1 緩存性能對(duì)比

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

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

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

圖2 緩存大小對(duì)緩存性能的影響

由圖2(a)可以看出,隨著域內(nèi)節(jié)點(diǎn)緩存容量的增大,LCE算法、ProbCache算法、OPT-GA算法和RCC算法域內(nèi)緩存命中率均有所提高,其中,RCC算法和OPT-GA算法整體比LCE算法和ProCache算法緩存命中率高,原因是前面2種算法實(shí)現(xiàn)了更大范圍的緩存,網(wǎng)絡(luò)中緩存冗余降低,緩存視頻種類數(shù)增多,導(dǎo)致緩存命中率增加。RCC算法比OPT-GA算法命中率高,原因是OPT-GA算法是按請(qǐng)求度由高到低對(duì)每個(gè)視頻分別使用遺傳算法進(jìn)行求解,導(dǎo)致一些熱門(mén)影片緩存過(guò)多,一些中等熱度視頻沒(méi)有空間緩存,從而命中率低于RCC算法。由圖2(b)可以看出,平均請(qǐng)求跳數(shù)隨著緩存容量的增大而減小。緩存命中率越高,更多的請(qǐng)求在域內(nèi)被命中,相對(duì)域外,所需接入跳數(shù)顯著減小。而隨著緩存空間的增大,RCC算法平均跳數(shù)有所減小,一方面因?yàn)榫植烤彺鏌衢T(mén)視頻增多,更多請(qǐng)求直接在接入路由器節(jié)點(diǎn)命中,域內(nèi)跳數(shù)減小;另一方面因?yàn)橛騼?nèi)協(xié)作緩存視頻種類多,路由到域外的請(qǐng)求少,導(dǎo)致平均請(qǐng)求跳數(shù)減小。

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

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

圖3 視頻流行度對(duì)緩存性能的影響

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

2.2.2 計(jì)算性能對(duì)比

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

表1 消耗內(nèi)存對(duì)比 GB

表2 消耗時(shí)間對(duì)比 s

表3 域內(nèi)平均請(qǐng)求跳數(shù)對(duì)比

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

3 結(jié)束語(yǔ)

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

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

[2] 曲 樺,王偉萍,趙季紅.內(nèi)容中心網(wǎng)絡(luò)中一種改進(jìn)型緩存機(jī)制[J].計(jì)算機(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] 胡 騫.以內(nèi)容為中心的網(wǎng)絡(luò)中緩存技術(shù)的若干問(wèn)題研究[D].北京:北京郵電大學(xué),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)化問(wèn)題的改進(jìn)灰狼優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,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.