信息中心網(wǎng)絡(luò)的內(nèi)容流行度評(píng)估算法

張送柱，王興偉，黃 敏

1(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110169) 2(東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng) 110819)

1 引 言

近年來(lái)，信息中心網(wǎng)絡(luò)(Information-Centric Networking,ICN)作為一股清流的革命網(wǎng)絡(luò)范式被學(xué)術(shù)界率先推崇，究其歷史，ICN的雛形可追溯到2001年，源于Gritter和Cheriton撰寫的開創(chuàng)性文章[1]；而其概念的提出卻源于2009年Jacobson發(fā)表在CoNEXT上的一篇會(huì)議論文[2].拋開通信模式的獨(dú)特性，我們認(rèn)為ICN最有價(jià)值的地方是其標(biāo)新立異的網(wǎng)內(nèi)緩存特征[3].然而網(wǎng)內(nèi)緩存是指網(wǎng)內(nèi)的路由器(內(nèi)容路由器)具有緩存內(nèi)容副本的能力，即一個(gè)內(nèi)容能夠存在于網(wǎng)內(nèi)的多個(gè)路由器中，以供用戶方便地使用.當(dāng)然這里所指的網(wǎng)內(nèi)緩存并非傳統(tǒng)路由器中設(shè)置的buffer，也非內(nèi)容分發(fā)網(wǎng)中的服務(wù)器.進(jìn)一步地，ICN緩存技術(shù)有助于降低獲取內(nèi)容所需的網(wǎng)絡(luò)時(shí)延、均衡整個(gè)網(wǎng)絡(luò)的業(yè)務(wù)流量以及減少由于鏈路或者節(jié)點(diǎn)失效對(duì)內(nèi)容獲取(分發(fā))帶來(lái)的負(fù)面影響等[4].

ICN緩存技術(shù)[5]的研究范疇大致包括緩存資源分配、緩存放置、緩存替換和緩存協(xié)作等.首先，緩存資源分配著眼于對(duì)不同的路由器分配不同大小的緩存空間以及在內(nèi)容分發(fā)前預(yù)分配哪些內(nèi)容資源到哪些路由器；其次，緩存放置主要研究在眾多路由器中哪里開辟緩存的問(wèn)題；再次，緩存替換旨在選擇怎樣的替換算法進(jìn)行緩存內(nèi)容的更新.最后，緩存協(xié)作涉及到集中式存儲(chǔ)和分布式存儲(chǔ)(如同構(gòu)協(xié)作、同構(gòu)非協(xié)作、異構(gòu)協(xié)作、異構(gòu)非協(xié)作等).總結(jié)來(lái)看，這四種緩存機(jī)制分別回答了緩存多少、哪里能夠緩存、緩存什么以及如何緩存的問(wèn)題.

對(duì)ICN緩存技術(shù)中緩存替換策略的研究極為重要，因?yàn)榫彺娴木唧w內(nèi)容決定了緩存的命中率也進(jìn)一步?jīng)Q定了整個(gè)路由的效率和網(wǎng)絡(luò)性能.據(jù)我們所知，大多數(shù)緩存替換策略都是基于訪問(wèn)頻率或者訪問(wèn)時(shí)間制定的，因?yàn)榫彺嫣鎿Q算法應(yīng)盡可能的簡(jiǎn)單高效才能保證ICN的線速執(zhí)行.幾種常見的且具有代表性的緩存替換策略可歸納為：最近最少使用[6]、基于自適應(yīng)模糊推理[7]和基于內(nèi)容流行度預(yù)測(cè)[8].從性能上來(lái)看，很難講清楚哪一種替換策略更有價(jià)值，唯一可以用于評(píng)判的標(biāo)準(zhǔn)恐怕只有應(yīng)用場(chǎng)景.

雖然內(nèi)容是ICN的第一實(shí)體，且能夠以任何形式出現(xiàn)，但在實(shí)際的應(yīng)用中，內(nèi)容往往指的是視頻流.例如思科視覺(jué)網(wǎng)絡(luò)指數(shù)預(yù)測(cè)到2020年平均每年的全球移動(dòng)數(shù)據(jù)流量能達(dá)到366.8EB，其中僅視頻就能占到75%[9].更為重要的是大多數(shù)用戶通常采用點(diǎn)播的形式觀看部分視頻，不再是整個(gè)完整的視頻.這就需要路由器去緩存一些熱點(diǎn)片段，進(jìn)而最大程度地滿足更多用戶的需求.事實(shí)上，熱點(diǎn)片段正是流行的內(nèi)容片段，這說(shuō)明基于流行度預(yù)測(cè)的替換策略才是當(dāng)前甚至未來(lái)一段時(shí)間的主要潮流.盡管已經(jīng)有一些ICN的緩存替換策略是基于流行度開展的，但是這些研究并沒(méi)有給出如何評(píng)價(jià)內(nèi)容的流行度、或者僅僅簡(jiǎn)單地使用訪問(wèn)次數(shù)來(lái)代表流行度.鑒于此，本文繼續(xù)研究面向ICN緩存替換的流行度預(yù)測(cè)方案，并給出一種新型的內(nèi)容流行度評(píng)估模型.

2 相關(guān)工作

針對(duì)ICN緩存替換策略的研究，比較成熟且較早的是其內(nèi)置的最近最少使用策略[6]，它不僅適用于ICN，也同樣適合于其他具有緩存能力的網(wǎng)絡(luò)和系統(tǒng).雖然這種策略很大程度上能夠滿足用戶對(duì)熱點(diǎn)內(nèi)容的獲取，但同樣也存在時(shí)間局部性和空間局部性的限制，很難應(yīng)對(duì)突發(fā)流量的情況.為此，文獻(xiàn)[7]提出一種自適應(yīng)模糊推理的策略來(lái)預(yù)測(cè)用戶請(qǐng)求的分布.首先，基于神經(jīng)模糊推理系統(tǒng)分析緩存的內(nèi)容從而挑選出比較受歡迎的內(nèi)容類型；然后，再次啟用推理系統(tǒng)分析剩余的內(nèi)容，以此類推將所有的內(nèi)容進(jìn)行分類.一旦內(nèi)容到達(dá)路由節(jié)點(diǎn)，系統(tǒng)會(huì)自適應(yīng)地判斷該內(nèi)容的類型以及過(guò)往的訪問(wèn)歷史，進(jìn)而決定是否緩存.文獻(xiàn)[10]基于流量負(fù)載和用戶偏好程度，根據(jù)網(wǎng)絡(luò)環(huán)境實(shí)時(shí)調(diào)整內(nèi)容的緩存位置，這使得緩存替換的利用率更高.文獻(xiàn)[11]提出了一個(gè)基于貪心的上下游協(xié)作的緩存替換策略，其將流行的內(nèi)容緩存在邊緣節(jié)點(diǎn)，其余的內(nèi)容緩存在中間核心節(jié)點(diǎn).文獻(xiàn)[12]提出了一個(gè)機(jī)會(huì)式的緩存替換策略，根據(jù)局部概率將頻繁請(qǐng)求的內(nèi)容緩存起來(lái).雖然以上緩存替換策略能夠大幅度提高緩存的命中率，然而執(zhí)行效率變低，使用戶不能及時(shí)獲取所需的內(nèi)容.

事實(shí)上，ICN要想完全實(shí)際應(yīng)用且兼容當(dāng)前的IP網(wǎng)絡(luò)，必然要重點(diǎn)解決當(dāng)前盛行的互聯(lián)網(wǎng)視頻流業(yè)務(wù)，這同樣會(huì)導(dǎo)致前兩種緩存替換策略效果不佳.這種環(huán)境下，涌現(xiàn)了一些基于內(nèi)容流行度預(yù)測(cè)的緩存策略.例如，文獻(xiàn)[8]證明了通過(guò)內(nèi)容流行度的預(yù)測(cè)能夠極大地提高緩存的利用率.文獻(xiàn)[13]提出基于軟件定義網(wǎng)絡(luò)(Software-Defined Networking，SDN)和深度學(xué)習(xí)(Deep Learning,DL)的流行度預(yù)測(cè)方法(SDN-DL)，它采用交換機(jī)的計(jì)算資源和配置資源，通過(guò)SDN構(gòu)建一個(gè)集中式的深度學(xué)習(xí)網(wǎng)絡(luò).文獻(xiàn)[14]提出一種具有節(jié)能水準(zhǔn)的流行度預(yù)測(cè)算法(Energy-Efficient Prediction Algorithm，EPA)，用于平衡整個(gè)系統(tǒng)的流量，從而達(dá)到節(jié)能的效果.文獻(xiàn)[15]將布隆過(guò)濾器和壓縮感知技術(shù)結(jié)合，利用SDN的集中控制能力使緩存信息保持一致，提出一個(gè)緩存內(nèi)容快速定位機(jī)制，有效地提高了緩存的利用率.文獻(xiàn)[16]提出一種基于Q路由的方法來(lái)預(yù)測(cè)內(nèi)容的流行度，通過(guò)對(duì)路徑的不斷增強(qiáng)學(xué)習(xí)，以達(dá)到更好的路由效果和更高的緩存命中率.雖然這些具體的流行度預(yù)測(cè)方案能夠較大程度地提高緩存利用率和命中率，然而它們都是籠統(tǒng)的介紹流行度預(yù)測(cè)的依賴指標(biāo)，卻忽略了流行度的具體評(píng)價(jià)方式.鑒于此，本文將著重解決這一問(wèn)題，即研究流行度的評(píng)估模型.

3 內(nèi)容流行度建模

本節(jié)為內(nèi)容流行度建模，首先進(jìn)行流行度衰減和流行度上升建模.其中，流行度衰減啟發(fā)于酒精揮發(fā)模型，流行度上升啟發(fā)于物體吸熱模型.特別地，鑒于內(nèi)容的流行度是短暫的且具有時(shí)效性，故也對(duì)流行度的周期進(jìn)行建模，即計(jì)算內(nèi)容流行的時(shí)長(zhǎng).

3.1 流行度衰減建模

內(nèi)容處于無(wú)人問(wèn)津的狀態(tài)時(shí)，其流行度通常會(huì)隨著時(shí)間的推移而減弱，這就相當(dāng)于一個(gè)醉酒的人，他身上的酒濃度會(huì)隨著時(shí)間的推移而變淡，這是因?yàn)檎麄€(gè)自然過(guò)程中，酒精發(fā)生了揮發(fā).此外需要指出是，酒精揮發(fā)因子可類比成流行度衰減因子，且在整個(gè)過(guò)程中，衰減的快慢不等，即衰減因子應(yīng)是一個(gè)變量.假設(shè)流行度的衰減因子為ρ，根據(jù)酒精揮發(fā)模型，它與內(nèi)容的當(dāng)前流行度T(t)成正比，則得到公式(1)如下：

(1)

其中，α為大于0的調(diào)解參數(shù)，通過(guò)求解微分方程(1)，可得到公式(2)如下：

T(t)=Ce-αt

(2)

假設(shè)初始時(shí)刻內(nèi)容的流行度為T0，將公式(2)變形可得到公式(3)如下：

T(t)=T0e-αt

(3)

將公式(3)代入到公式(1)，顯而易見ρ是一個(gè)變量.

3.2 流行度上升建模

內(nèi)容處于頻繁訪問(wèn)狀態(tài)時(shí)，其流行度通常會(huì)出現(xiàn)上升趨勢(shì)，這相當(dāng)于一個(gè)物體內(nèi)在地做吸熱操作，其溫度自然而然地要不斷上升.物體的吸熱過(guò)程如公式(4)所示：

Q=cmΔt

(4)

其中，Q為每一次加熱物體吸收的熱量，c是比熱容，m是物體質(zhì)量，Δt為兩個(gè)連續(xù)時(shí)刻的溫差變化.倘若把物體的吸熱過(guò)程類比到內(nèi)容被訪問(wèn)帶來(lái)的流行度上升過(guò)程，那么可以有如下表述：Q為內(nèi)容被連續(xù)訪問(wèn)后的即時(shí)流行度；m為內(nèi)容的大小，通常情況下，內(nèi)容越大其流行度越高，這是因?yàn)榘那衅蕉嗥浞秶酱笤交\統(tǒng)(例如，10分鐘電影的流行度要高于該10分鐘內(nèi)某兩分鐘的流行度)；c能表達(dá)內(nèi)容的類型，是內(nèi)容類型參數(shù)，即不同的內(nèi)容類型具有不同的參數(shù)值，且比較流行的內(nèi)容類型應(yīng)該有更高的對(duì)應(yīng)參數(shù)值；Δt是連續(xù)的兩個(gè)時(shí)刻.基于上述描述，可以將公式(4)改寫成公式(5)如下：

Q(t)=cmt

(5)

假設(shè)從零時(shí)刻到t′時(shí)刻，內(nèi)容處于無(wú)人訪問(wèn)狀態(tài)，而從t′時(shí)刻后，內(nèi)容處于頻繁的訪問(wèn)狀態(tài)，那么可以得到綜合的內(nèi)容流行度，如公式(6)所示：

(6)

其中，前半部分表示內(nèi)容在自然狀態(tài)下其流行度的變化情況，后半部分表示內(nèi)容在頻繁訪問(wèn)狀態(tài)下其流行度的上升情況.

3.3 流行度周期建模

在實(shí)際的應(yīng)用環(huán)境中，內(nèi)容流行度的衰減情況和上升情況是不同的.如果內(nèi)容長(zhǎng)時(shí)間不被訪問(wèn)，其流行度會(huì)下降到零，并且這種情況是常見的；相反，內(nèi)容流行度并不會(huì)一直呈現(xiàn)出上升趨勢(shì)，而是在達(dá)到最高值的短暫時(shí)間后開始逐漸下降[17]，這說(shuō)明內(nèi)容的流行度具有時(shí)效性和短暫性，即時(shí)間周期性.舉例講，電影院新上映的電影，剛開始會(huì)隨著觀看次數(shù)的增多而變得非常流行，然而久而久之該電影下線之后，它的流行度就會(huì)瞬間衰減.因此，很有必要對(duì)流行度的周期進(jìn)行分析，即公式(6)中t的建模.如上所述，流行度周期的產(chǎn)生源于流行度的上升，故流行度的周期建模必然要考慮流行度的上升速度；此外，流行度的周期其實(shí)就是個(gè)時(shí)間時(shí)效，它與當(dāng)前的內(nèi)容流行度T(t)緊密聯(lián)系.鑒于此，流行度周期與流行度的上升速度和當(dāng)前的流行度密切相關(guān).

假設(shè)內(nèi)容流行度的上升速度不能超過(guò)給定的值p，則得到關(guān)于兩個(gè)連續(xù)時(shí)刻的邊界方程如公式(7)所示：

(7)

將公式(6)的上升部分代入到公式(7)，可使t具體化如公式(8)所示：

(8)

綜上所述，本節(jié)建立了三個(gè)流行度模型，其中第一個(gè)模型是指內(nèi)容流行度會(huì)隨著時(shí)間的推移而減弱，第二個(gè)模型是指內(nèi)容流行度會(huì)隨著訪問(wèn)次數(shù)的增多而上升，第三個(gè)模型是指內(nèi)容流行度的持續(xù)不是長(zhǎng)久的而是短暫的.

4 仿真結(jié)果

4.1 實(shí)驗(yàn)設(shè)置

本文提出的內(nèi)容流行度評(píng)估算法用于ICN的緩存替換中，算法用C++編寫，仿真環(huán)境基于NS3，硬件配置為Intel(R)Xeon e5-2680,2.39 GHz CPU,7.99 GB RAM.此外，本文選擇文獻(xiàn)[13](SDN-DL)和文獻(xiàn)[14](EPA)作為對(duì)比基準(zhǔn)，其中，緩存命中率、路由時(shí)延和網(wǎng)絡(luò)能效作為三個(gè)評(píng)價(jià)指標(biāo).

本文的仿真是基于真實(shí)的YouTube數(shù)據(jù)集[18]，該數(shù)據(jù)集包括60萬(wàn)條興趣請(qǐng)求、26條內(nèi)容(80%的內(nèi)容小于12M)、1563個(gè)服務(wù)器、89個(gè)網(wǎng)段和2377個(gè)用戶.然而該數(shù)據(jù)集沒(méi)有展示具體的網(wǎng)絡(luò)拓?fù)?，為此我們引入Deltacom網(wǎng)絡(luò)拓?fù)?如圖1所示，包括97節(jié)點(diǎn)和124條邊)，并將該數(shù)據(jù)集的數(shù)據(jù)特征均勻地分布在Deltacom網(wǎng)絡(luò)拓?fù)渲?

特別地，本文涉及的四個(gè)重要參數(shù)，即α、c、m和p的設(shè)置如表1所示.其中，α為隨機(jī)設(shè)置成定量100；c為集中測(cè)試的YouTube視頻流類型，隨機(jī)設(shè)置成定量2000；為了兼容當(dāng)前IP網(wǎng)絡(luò)的包級(jí)別的傳輸，m設(shè)置成定量1500B；p設(shè)置為變量，是要看不同流行度上升速度對(duì)流行度周期的影響，繼而觀測(cè)網(wǎng)絡(luò)的性能.

圖1 2010年Deltacom網(wǎng)絡(luò)拓?fù)?/p>

表1 仿真參數(shù)設(shè)置

Table 1 Parameter settings

參數(shù)設(shè) 置α100c2000m1500Bp1%,5%,8%,10%,15%

4.2 緩存命中率測(cè)試

緩存命中率能直觀地反映出緩存策略的好壞，緩存命中率高說(shuō)明流行度評(píng)估準(zhǔn)確，且路由器總能實(shí)時(shí)緩存流行度高的內(nèi)容.緩存命中率chr定義如公式(9)所示：

(9)

其中，分子是路由器(不包括服務(wù)器源)緩存命中的次數(shù)，分母是總的請(qǐng)求次數(shù).三種算法在不同p值下的緩存命中率對(duì)比結(jié)果如圖2所示.

圖2 三種算法的緩存命中率

通過(guò)圖2可以看出，本文提出的流行度評(píng)估算法能夠促進(jìn)更高的緩存命中率，SDN-DL次之，EPA再次之，這是因?yàn)楸疚挠幸惶淄暾牧餍卸仍u(píng)估模型，包括衰減模型、上升模型和周期模型.尤其對(duì)流行度周期模型的建模，能夠很好地預(yù)測(cè)熱點(diǎn)內(nèi)容的生存周期，從而根據(jù)需求實(shí)時(shí)地調(diào)整緩存的內(nèi)容，進(jìn)一步提高緩存的命中率.此外，還可以看出隨著p值的增大緩存命中率也會(huì)隨之變高，然而當(dāng)p達(dá)到一定的值(8%)后緩存命中率增加緩慢，這說(shuō)明內(nèi)容的緩存周期并不是越長(zhǎng)越好，至于設(shè)置多長(zhǎng)最佳，這與緩存的大小、興趣請(qǐng)求的特征以及內(nèi)容的地理位置分布密切相關(guān)，對(duì)此本文不做詳細(xì)的討論.

4.3 路由時(shí)延測(cè)試

路由時(shí)延用來(lái)評(píng)定緩存策略對(duì)整個(gè)ICN內(nèi)容的獲取過(guò)程是否有改進(jìn)效果，它的定義如公式(10)所示：

Δmt=tend-tstart

(10)

其中，后者是興趣請(qǐng)求發(fā)出的時(shí)刻，前者是用戶獲取內(nèi)容的時(shí)刻.三種算法在不同p值下的路由時(shí)延對(duì)比結(jié)果如圖3所示.

圖3 三種算法的路由時(shí)延

通過(guò)圖3可以看出，本文算法在路由時(shí)延方面具有明顯優(yōu)勢(shì)，尤其在p=15%時(shí)，僅僅用了大約18ms就完成內(nèi)容的獲取，這說(shuō)明本文的流行度評(píng)估算法將絕大多數(shù)熱點(diǎn)內(nèi)容在路由器上進(jìn)行了緩存，以此滿足了大多數(shù)后續(xù)相同的興趣請(qǐng)求.正因如此，便省去了多余的興趣請(qǐng)求路徑和內(nèi)容分發(fā)路徑，自然地也節(jié)省了路由時(shí)延.然而SDN-DL和EPA沒(méi)有很好地關(guān)注熱點(diǎn)內(nèi)容的緩存和預(yù)測(cè)，導(dǎo)致后續(xù)一段時(shí)間內(nèi)相同的興趣請(qǐng)求不能被中間的路由器滿足，從而加大了路由時(shí)延.

4.4 網(wǎng)絡(luò)能效測(cè)試

網(wǎng)絡(luò)能效是指節(jié)能的效果，測(cè)試這個(gè)指標(biāo)是因?yàn)榫G色節(jié)能是ICT的主要話題之一，它的定義如公式(11)所示：

(11)

其中，Eused是采用流行度預(yù)測(cè)后網(wǎng)絡(luò)消耗的能量，Enused是未采用流行度預(yù)測(cè)時(shí)網(wǎng)絡(luò)消耗的能量，它們的計(jì)算可參考文獻(xiàn)[19].三種算法在不同p值下的網(wǎng)絡(luò)能效對(duì)比結(jié)果如圖4所示.

圖4 三種算法的網(wǎng)絡(luò)能效

通過(guò)圖4可以看出，本文算法的加入對(duì)網(wǎng)絡(luò)能耗的節(jié)約有最好的效果，EPA和SDN-DL分別次之.特別地，當(dāng)p=15%時(shí)，本文算法的節(jié)能效果能達(dá)到41%.事實(shí)上，由于基于牛頓冷卻定律評(píng)估流行度而帶來(lái)的緩存替換效果明顯，一方面某些路由器不必再專門消耗能量去重新啟動(dòng)，另一方面大多數(shù)鏈路也不必再進(jìn)一步地轉(zhuǎn)發(fā)多余的興趣請(qǐng)求以及浪費(fèi)帶寬去分發(fā)多余的流量，這樣一來(lái)一往就卸載了路由器的操作能耗和鏈路傳輸流量所需的能耗.

5 結(jié) 語(yǔ)

在視頻流分發(fā)業(yè)務(wù)盛行的當(dāng)下，ICN有限的緩存空間對(duì)熱點(diǎn)內(nèi)容的把持顯得尤為重要.本文提出了一種評(píng)估內(nèi)容的流行度的新型方法，從而有效地執(zhí)行緩存替換，將流行度高的熱點(diǎn)內(nèi)容緩存在ICN路由器中.針對(duì)內(nèi)容流行度，建立了三種不同的模型，即流行度衰減模型、流行度上升模型和流行度周期模型：第一個(gè)模型是指內(nèi)容流行度會(huì)隨著時(shí)間的推移而減弱，第二個(gè)模型是指內(nèi)容流行度會(huì)隨著訪問(wèn)次數(shù)的增多而上升，第三個(gè)模型是指內(nèi)容流行度的持續(xù)是短暫的不是長(zhǎng)久的.采用YouTube數(shù)據(jù)集和Deltacom網(wǎng)絡(luò)拓?fù)鋵?shí)施仿真，實(shí)驗(yàn)結(jié)果表明本文提出的流行度評(píng)估算法是可行的且有效的.然而，本文也存在一些缺憾，如沒(méi)有給出內(nèi)容緩存周期的理論分析.從理論上講，它與緩存的大小、興趣請(qǐng)求的特征以及內(nèi)容的地理位置分布密切相關(guān).這是一個(gè)較為復(fù)雜的數(shù)學(xué)問(wèn)題，對(duì)此，我們將開展后續(xù)的研究工作.