王興偉，王子健，李福亮，黃 敏

(1. 東北大學(xué) 軟件學(xué)院， 遼寧 沈陽(yáng) 110004； 2. 東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 遼寧 沈陽(yáng) 110004；3. 東北大學(xué) 信息科學(xué)與工程學(xué)院， 遼寧 沈陽(yáng) 110004)

信息中心網(wǎng)絡(luò)(Information-Centric Networking, ICN)被認(rèn)為是一個(gè)能夠較好地滿足用戶對(duì)信息傳遞的需求的新型網(wǎng)絡(luò)體系結(jié)構(gòu)[1]。在眾多的ICN架構(gòu)中，命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Networking, NDN)[2]成為研究熱點(diǎn)。NDN來(lái)源于更早期的項(xiàng)目——內(nèi)容中心網(wǎng)絡(luò) (Content-Centric Networking, CCN)[3]，由Van Jacobson在2006年首次提出，NDN架構(gòu)延續(xù)了CCN架構(gòu)的設(shè)計(jì)理念與原則。

在ICN中，網(wǎng)內(nèi)緩存已經(jīng)成為提高網(wǎng)絡(luò)整體性能的核心特性之一。ICN的緩存策略根據(jù)數(shù)據(jù)緩存位置可以分為路徑緩存(on-path)與非路徑緩存(off-path)[4]。on-path的存儲(chǔ)方式將數(shù)據(jù)沿途存儲(chǔ)在請(qǐng)求來(lái)時(shí)的路徑中，因此其命名解析與數(shù)據(jù)路由是同步的。這種策略雖然很簡(jiǎn)單，但導(dǎo)致了網(wǎng)內(nèi)數(shù)據(jù)副本數(shù)量過(guò)高。而off-path的存儲(chǔ)方式可以將數(shù)據(jù)存儲(chǔ)在請(qǐng)求路徑以外的緩存節(jié)點(diǎn)中，因此其命名解析與數(shù)據(jù)路由可以同步或者異步。這種方式雖然很靈活，但需要一種緩存感知的機(jī)制來(lái)使路由器能夠感知周圍節(jié)點(diǎn)的緩存信息。ICN的緩存具有透明、泛在、細(xì)粒度三大特性[5]，由于“泛在緩存”的特性，ICN網(wǎng)絡(luò)中數(shù)據(jù)冗余的現(xiàn)象頻頻出現(xiàn)，導(dǎo)致其數(shù)據(jù)副本率過(guò)高，緩存空間不能被充分利用。除此之外，部署如此規(guī)模的緩存空間也是一種浪費(fèi)，并且高昂的開(kāi)銷與所獲取的收益不成正比。

國(guó)內(nèi)外許多學(xué)者已經(jīng)對(duì)ICN中的網(wǎng)內(nèi)緩存進(jìn)行了廣泛的研究。文獻(xiàn)[6]倡導(dǎo)“l(fā)ess for more”的理念，即針對(duì)某一請(qǐng)求路徑，選取在一些比較合適的節(jié)點(diǎn)緩存數(shù)據(jù)，提出了一種基于介數(shù)中心性的緩存策略，每次在緩存數(shù)據(jù)時(shí)都進(jìn)行決策。文獻(xiàn)[7]提出了，一種基于內(nèi)容空間劃分與Hash路由的協(xié)作式網(wǎng)內(nèi)緩存模式，有效地提高了網(wǎng)絡(luò)整體的緩存命中率。文獻(xiàn)[8]關(guān)注于緩存的一致性問(wèn)題，提出了一種具有高性價(jià)比基于流行度的緩存一致性機(jī)制。該機(jī)制能夠在緩存一致性與相關(guān)代價(jià)中做出權(quán)衡，保證了ICN路由器中所緩存內(nèi)容的新鮮度。文獻(xiàn)[9]通過(guò)一個(gè)統(tǒng)一的方法緊密地集成了緩存與擁塞控制，利用由擁塞控制反饋出的可用擁塞定價(jià)來(lái)引導(dǎo)在每個(gè)內(nèi)容路由器上的緩存決策，提高了網(wǎng)絡(luò)的吞吐量并且減少了網(wǎng)絡(luò)擁塞。文獻(xiàn)[10]提出了一種流行內(nèi)容分布的分析框架，基于博弈論的思想制定了ICN中的緩存與定價(jià)策略。

以上工作側(cè)重于對(duì)緩存策略的研究，即在哪些節(jié)點(diǎn)或?qū)δ男﹥?nèi)容進(jìn)行緩存所獲得的收益更高，并未涉及其前置工作——緩存空間的部署分配問(wèn)題。目前，在緩存空間部署分配問(wèn)題上的研究還較少[11]。文獻(xiàn)[12]研究了如何在一個(gè)給定存儲(chǔ)預(yù)算的網(wǎng)絡(luò)中為路由器分配存儲(chǔ)空間，通過(guò)建立數(shù)學(xué)模型分析求解得出網(wǎng)絡(luò)拓?fù)?、網(wǎng)絡(luò)規(guī)模、內(nèi)容流行度等都對(duì)緩存分配產(chǎn)生一定的影響，不存在一體適用的策略。文獻(xiàn)[13]首次研究了CCN中的緩存空間分配問(wèn)題，采用了節(jié)點(diǎn)中心性的一些度量，比如度中心性、介數(shù)中心性、接近中心性，根據(jù)中心性的不同按相應(yīng)比例異構(gòu)地分配緩存空間。文獻(xiàn)[14]從經(jīng)濟(jì)的角度出發(fā)，建立優(yōu)化模型來(lái)研究在預(yù)算限制的情境下ICN的遷移問(wèn)題。文獻(xiàn)[15]是研究緩存空間分配的開(kāi)篇之作，但其針對(duì)的是傳統(tǒng)網(wǎng)絡(luò)，目的在于選取合適的緩存位置來(lái)降低網(wǎng)絡(luò)流量。這也對(duì)之后ICN中緩存空間放置問(wèn)題的研究打下了堅(jiān)實(shí)的基礎(chǔ)。

然而，尋求一種高效的緩存策略是毋庸置疑的，但這個(gè)問(wèn)題是由ICN緩存“普遍存在”的特性引起的，因此尋求一種高效的緩存空間分配策略才是解決問(wèn)題的根本。而上述緩存空間分配方面的工作并未綜合考慮網(wǎng)絡(luò)中不同角色的利益(文獻(xiàn)[14]僅僅進(jìn)行了經(jīng)濟(jì)層面的考慮)，本文將從用戶、網(wǎng)絡(luò)運(yùn)營(yíng)商、服務(wù)提供商三者的角度出發(fā)，在網(wǎng)絡(luò)性能與經(jīng)濟(jì)中做出權(quán)衡，在網(wǎng)絡(luò)中選擇適宜的節(jié)點(diǎn)開(kāi)辟緩存空間，使三方都能夠最大限度地從中受益，從而在根本上對(duì)ICN緩存進(jìn)行優(yōu)化。

因此，本文基于on-path緩存策略，建立基于用戶-服務(wù)提供商的緩存位置模型和基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置模型，進(jìn)而將其結(jié)合成為多目標(biāo)優(yōu)化模型，并通過(guò)算法求解得出最優(yōu)緩存節(jié)點(diǎn)位置集合。本文的貢獻(xiàn)與創(chuàng)新點(diǎn)如下：

1)緩存節(jié)點(diǎn)的選擇充分考慮了網(wǎng)絡(luò)中用戶、服務(wù)提供商、網(wǎng)絡(luò)運(yùn)營(yíng)商三方的利益，從三方不同的利益角度出發(fā)進(jìn)行建模；

2)采用帕累托模型進(jìn)行求解，從而得到對(duì)于網(wǎng)絡(luò)中各方都比較均衡的解集，使三方能夠最大限度地從中受益；

3)對(duì)ICN原生的緩存空間放置策略進(jìn)行了優(yōu)化，這對(duì)未來(lái)ICN的實(shí)際部署有著一定的參考價(jià)值。

1 問(wèn)題描述

緩存節(jié)點(diǎn)位置選擇可歸結(jié)為資源分配問(wèn)題，該類問(wèn)題也是云環(huán)境下研究的重點(diǎn)問(wèn)題[16-17],即在資源有限的環(huán)境下，如何合理地分配資源，提高資源利用率，并最大限度地改善系統(tǒng)性能。而在ICN中選擇合適的位置開(kāi)辟緩存空間受多重因素的影響，不存在通用的策略。除此之外，不同的角色對(duì)于開(kāi)辟緩存空間所需要獲得的收益也是不同的。處于用戶的視角，看重的是響應(yīng)時(shí)間；處于網(wǎng)絡(luò)運(yùn)營(yíng)商的視角，應(yīng)從經(jīng)濟(jì)的角度出發(fā)，以最小的成本獲取最大的利益；而處于服務(wù)提供商的視角，降低服務(wù)器的負(fù)載，提高效率才是最主要的。但無(wú)論從哪一方的角度出發(fā)，開(kāi)辟合適的緩存空間最終目的還是為了提高網(wǎng)絡(luò)整體性能，使三方都從中受益。

1.1 網(wǎng)絡(luò)模型

將網(wǎng)絡(luò)建模成為一個(gè)無(wú)向連接圖G=(V,E)，其中V為網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E為網(wǎng)絡(luò)中的鏈路集合。將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)分為三種類型：用戶節(jié)點(diǎn)vc∈C、路由器節(jié)點(diǎn)vr∈R、服務(wù)器節(jié)點(diǎn)vs∈S(C、R、S分別為用戶節(jié)點(diǎn)集、路由器節(jié)點(diǎn)集、服務(wù)器節(jié)點(diǎn)集)，且V=(C∪R∪S)。

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

在建立模型之前，首先給出模型的假設(shè)：

1)不考慮路由器負(fù)載；

2)路由最短路徑是唯一的；

3)傳輸中以內(nèi)容大小近似代替數(shù)據(jù)包的大小。

1.2.1 基于用戶-服務(wù)提供商的緩存位置模型

用戶關(guān)注的是響應(yīng)時(shí)間，即用戶請(qǐng)求能夠在短時(shí)間內(nèi)被響應(yīng)；而服務(wù)提供商關(guān)注的是服務(wù)器的負(fù)載。在ICN中，數(shù)據(jù)包轉(zhuǎn)發(fā)給某一路由器時(shí)會(huì)首先檢查內(nèi)容存儲(chǔ)器(Content Store, CS)中是否有所需要的數(shù)據(jù)，如果命中則直接將數(shù)據(jù)路由給用戶，不需要訪問(wèn)目標(biāo)服務(wù)器。假設(shè)用戶請(qǐng)求的內(nèi)容都會(huì)在中間節(jié)點(diǎn)上被滿足，且該節(jié)點(diǎn)離用戶只有一跳的距離，此時(shí)用戶的響應(yīng)時(shí)間和服務(wù)器的負(fù)載都會(huì)得到極大的提升。因此，該位置的選取應(yīng)該離用戶越近越好，而離服務(wù)器越遠(yuǎn)越好。

基于以上思想，給出模型中消耗的定義。最優(yōu)位置集合Xp={v1,v2,…,vp}?R(其他符號(hào)定義見(jiàn)表1)，則在R中選擇位置p開(kāi)辟緩存空間時(shí)，用戶c請(qǐng)求內(nèi)容oi的消耗如式(1)所示。

表1 符號(hào)說(shuō)明

(1-hoi)·[d(vc,vp)+d(vp,s(oi))]+

(1)

目標(biāo)函數(shù)：

[ωp·d(vc,s(oi))]}

(2)

約束條件：

vp∈R∩{Path(vc,s(oi))},vc∈C,s(oi)∈S

(3)

(4)

(5)

(6)

式(3)限制了位置p應(yīng)從c到s路由的最短路徑上選取，并假設(shè)該路徑是唯一的。式(4)考慮到用戶不可能對(duì)所有內(nèi)容都感興趣，因此用二進(jìn)制變量來(lái)表示用戶是否有請(qǐng)求某個(gè)內(nèi)容的需求。在數(shù)據(jù)路由方面采用與命名解析耦合的方式，其意味著請(qǐng)求路徑與數(shù)據(jù)路由路徑是對(duì)稱的，即d(vp,s(oi))=d(s(oi),vp)。式(5)的意義是為了讓其滿足on-path策略。式(6)限制了開(kāi)辟緩存的總預(yù)算不多于BM。

將式(2)進(jìn)一步化簡(jiǎn)可得：

(7)

由式(7)可得出在請(qǐng)求某一緩存命中率較大的內(nèi)容時(shí)(該內(nèi)容在網(wǎng)絡(luò)中較為流行)，請(qǐng)求數(shù)據(jù)量與用戶到緩存路由器距離的乘積越小且請(qǐng)求數(shù)據(jù)量與服務(wù)器到緩存路由器距離的乘積越大，則目標(biāo)函數(shù)值越小。

1.2.2 基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置模型

在網(wǎng)絡(luò)運(yùn)營(yíng)商的角度，所需要考慮的是經(jīng)濟(jì)問(wèn)題，即用最少的錢做更多的事。針對(duì)該問(wèn)題，考慮網(wǎng)絡(luò)中傳輸所有流量的費(fèi)用與開(kāi)辟緩存空間的費(fèi)用，建立模型。

目標(biāo)函數(shù)：

(8)

進(jìn)一步細(xì)化公式：

(9)

約束條件：

vp∈R∩{Path(vc,s(o))},vc∈C,s(oi)∈S

(10)

pi,j>0,?i,j∈E

(11)

(12)

(13)

(14)

式(8)中只考慮請(qǐng)求路徑的費(fèi)用消耗，而不考慮數(shù)據(jù)路由路徑的費(fèi)用消耗，這是因?yàn)椴扇〉氖菙?shù)據(jù)路由與命名解析耦合方式，請(qǐng)求路徑與數(shù)據(jù)路由路徑是對(duì)稱的。 式(9)中的koi是代表內(nèi)容對(duì)象大小，雖然用戶請(qǐng)求時(shí)發(fā)出興趣包的大小并不等同于該請(qǐng)求內(nèi)容大小，但在該模型中用內(nèi)容對(duì)象大小近似地代替請(qǐng)求包的大小，以便體現(xiàn)出用戶請(qǐng)求不同內(nèi)容的差異性。 式(10)、式(12)～(14)中的約束定義與基于用戶-服務(wù)提供商的緩存位置模型中一致。 式(11)則限定了鏈路傳輸單元流量的費(fèi)用應(yīng)為正數(shù)。 該模型中將緩存預(yù)算進(jìn)行了限制，而對(duì)于網(wǎng)絡(luò)中傳輸流量的費(fèi)用并未限制，因?yàn)檫@部分費(fèi)用是運(yùn)營(yíng)商必須要支付的，用來(lái)滿足用戶數(shù)據(jù)傳輸?shù)男枨蟆?/p>

將式(9)進(jìn)一步化簡(jiǎn)可得：

(15)

從式(15)可以看出，內(nèi)容對(duì)象的緩存命中率越大，并且在緩存路由器到服務(wù)器的鏈路上傳輸該內(nèi)容所支付的費(fèi)用越高，則該目標(biāo)函數(shù)值越小。

1.2.3 多目標(biāo)優(yōu)化模型

以上給出了兩個(gè)基于不同角度的單目標(biāo)優(yōu)化模型：基于用戶-服務(wù)提供商的緩存位置模型和基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置模型。對(duì)于多目標(biāo)優(yōu)化問(wèn)題來(lái)說(shuō)，單個(gè)目標(biāo)最優(yōu)并不能保證其他目標(biāo)也是最優(yōu)的，因此需要一種折中方案。在這里引入多目標(biāo)優(yōu)化模型中的經(jīng)典模型——帕累托模型[19]，并以帕累托優(yōu)勝的概念來(lái)衡量解的優(yōu)劣，以此得到最終的帕累托最優(yōu)解集合，即對(duì)于兩個(gè)目標(biāo)而言都比較均衡的解集。

2 信息中心網(wǎng)絡(luò)緩存節(jié)點(diǎn)位置選擇算法

基于帕累托模型求解方法中數(shù)學(xué)規(guī)劃法的思想設(shè)計(jì)了信息中心網(wǎng)絡(luò)緩存節(jié)點(diǎn)位置選擇算法。

2.1 緩存節(jié)點(diǎn)位置選擇算法主流程

帕累托模型的求解方法主要有三種：兩兩比較法、數(shù)學(xué)規(guī)劃法和基于進(jìn)化算法求解[19]?？紤]到帕累托模型的解空間一般來(lái)說(shuō)都相對(duì)較大，采用數(shù)學(xué)規(guī)劃法進(jìn)行求解。該方法的解空間相對(duì)來(lái)說(shuō)較小，求解難度適中。下面給出基于數(shù)學(xué)規(guī)劃法的緩存節(jié)點(diǎn)位置選擇算法主流程。在該算法流程中，目標(biāo)一為基于用戶-服務(wù)提供商的緩存位置模型的優(yōu)化目標(biāo)，目標(biāo)二為基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置模型的優(yōu)化目標(biāo)。求解時(shí)首先忽略目標(biāo)二，僅考慮目標(biāo)一，并采用基于用戶-服務(wù)提供商的緩存位置選擇算法來(lái)求解得到L個(gè)最優(yōu)解，進(jìn)而計(jì)算出這L個(gè)最優(yōu)解分別對(duì)應(yīng)的目標(biāo)一與目標(biāo)二的值，并通過(guò)帕累托選擇得到帕累托優(yōu)勝解集；接著忽略目標(biāo)一，僅考慮目標(biāo)二，并采用基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置選擇算法來(lái)求解得到L個(gè)最優(yōu)解，進(jìn)而計(jì)算出這L個(gè)最優(yōu)解分別對(duì)應(yīng)的目標(biāo)一與目標(biāo)二的值，并通過(guò)帕累托選擇得到帕累托優(yōu)勝解集；最后根據(jù)以上得到的所有解集進(jìn)行帕累托選擇得到最終解集。

帕累托解的優(yōu)劣很大程度由L決定，當(dāng)L取值較大時(shí)，能夠得到較多的候選解集，相對(duì)來(lái)說(shuō)解更優(yōu)，但這會(huì)增大算法的復(fù)雜度和運(yùn)行時(shí)間；而當(dāng)L取值較小時(shí)，盡管能提高效率降低運(yùn)行時(shí)間，但由于所得到的帕累托候選解太少會(huì)影響解的優(yōu)劣。因此對(duì)于L參數(shù)的選擇需要在運(yùn)行時(shí)間與解的優(yōu)劣上進(jìn)行權(quán)衡。

此外，在路由算法上采用基于任意兩點(diǎn)間最短路徑算法Floyd算法[20]。

2.2 基于用戶-服務(wù)提供商的緩存位置選擇算法

本節(jié)主要針對(duì)基于用戶-服務(wù)提供商的緩存位置模型的求解算法進(jìn)行設(shè)計(jì)，該模型可歸結(jié)為線性整數(shù)規(guī)劃模型，對(duì)于此類問(wèn)題可采取確定式求解與啟發(fā)式求解，啟發(fā)式求解是一種近似求解，其又可以分為傳統(tǒng)啟發(fā)式(貪心算法等)與元啟發(fā)式(蟻群算法[21-22]等)。考慮到確定式求解算法的開(kāi)銷十分巨大，而元啟發(fā)式算法的復(fù)雜度較高，收斂速度較慢。因此，本節(jié)設(shè)計(jì)了一種基于隨機(jī)貪心啟發(fā)策略的傳統(tǒng)啟發(fā)式算法來(lái)進(jìn)行求解，算法具體步驟參見(jiàn)算法1。

算法1 基于用戶-服務(wù)提供商的緩存位置選擇算法

2.3 基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置選擇算法

基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置模型與0-1背包模型類似，因此解決此類多階段決策問(wèn)題采用動(dòng)態(tài)規(guī)劃法[23](Dynamic Programming, DP)求解最為適宜。

2.3.1 動(dòng)態(tài)規(guī)劃子問(wèn)題定義

根據(jù)動(dòng)態(tài)規(guī)劃思想需要將該問(wèn)題拆分成多個(gè)階段，每個(gè)階段有相應(yīng)的子問(wèn)題。

子問(wèn)題F[i][j]：在剩余預(yù)算j的限制下，在前i個(gè)路由器中選取若干個(gè)開(kāi)辟緩存空間所能得到的最大收益。

該類問(wèn)題存在一個(gè)特點(diǎn)就是第i時(shí)刻的狀態(tài)只與第i-1時(shí)刻的狀態(tài)有關(guān)，因此處于空間復(fù)雜度的考慮可采取一維數(shù)組來(lái)存儲(chǔ)求解過(guò)程中的狀態(tài)，即只存儲(chǔ)F[i][j]中第二維的信息，第一維默認(rèn)是第i-1時(shí)刻的狀態(tài)，故不需要進(jìn)行存儲(chǔ)。定義F[j]的狀態(tài)轉(zhuǎn)移方程為：

F[j]=Max{F[j]，不在第i個(gè)路由器開(kāi)辟緩存

F[j-C[i]]+V[i](j≥C[i]) ，在第i個(gè)路由器開(kāi)辟緩存}

(16)

式中，C[i]為路由器i開(kāi)辟緩存空間的費(fèi)用，V[i]為在第i個(gè)路由器開(kāi)辟緩存空間所得到的收益。

2.3.2 算法描述

接下來(lái)給出基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置選擇算法，算法具體步驟參見(jiàn)算法2。

算法2 基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置選擇算法

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

3.1 評(píng)價(jià)基準(zhǔn)與指標(biāo)

評(píng)價(jià)基準(zhǔn)方面，以所提ICN最優(yōu)位置選擇(ICN Optimal Cache Location Selection， ICN OCLS)算法與ICN的原生特性(Native Feature， NF)即默認(rèn)在所有節(jié)點(diǎn)都開(kāi)辟緩存空間進(jìn)行對(duì)比。

主要有以下四個(gè)評(píng)價(jià)指標(biāo)：

1)網(wǎng)絡(luò)消耗值(Network Consumption Value， NCV)。網(wǎng)絡(luò)消耗值刻畫(huà)了網(wǎng)絡(luò)中的全局流量消耗。其定義如式(17)所示。

NCV=TC

(17)

式中，TC為網(wǎng)絡(luò)中全局流量消耗。

2)網(wǎng)絡(luò)費(fèi)用開(kāi)銷(Network Expense， NE)。網(wǎng)絡(luò)費(fèi)用開(kāi)銷描述了當(dāng)前網(wǎng)絡(luò)狀況下網(wǎng)絡(luò)運(yùn)營(yíng)商所需支付的費(fèi)用。其定義如式(18)所示。

NE=TE+CE

(18)

式中，TE為網(wǎng)絡(luò)傳輸流量的費(fèi)用開(kāi)銷，CE為開(kāi)辟緩存的費(fèi)用開(kāi)銷。

3)流量性價(jià)比(Traffic Cost-Effective， TCE)。流量性價(jià)比描述了每臺(tái)緩存路由器在流量方面所帶來(lái)的平均收益值，故該性價(jià)比越高越好，其定義如(19)所示。

(19)

式中，0_traffic為網(wǎng)絡(luò)中不存在緩存路由器時(shí)的全局流量，x_traffic為網(wǎng)絡(luò)中存在x臺(tái)緩存路由器時(shí)的全局流量，amount為網(wǎng)絡(luò)中緩存路由器的數(shù)量。

4)網(wǎng)絡(luò)費(fèi)用開(kāi)銷比(Network Expense Ratio, NER)。網(wǎng)絡(luò)費(fèi)用開(kāi)銷比刻畫(huà)了隨著緩存路由器數(shù)量的增加，網(wǎng)絡(luò)費(fèi)用開(kāi)銷相對(duì)于無(wú)緩存網(wǎng)絡(luò)的變化情況，其定義如式(20)所示。

(20)

式中，x_expense為存在x臺(tái)緩存路由器時(shí)網(wǎng)絡(luò)的費(fèi)用開(kāi)銷，0_expense為不存在緩存路由器時(shí)網(wǎng)絡(luò)的費(fèi)用開(kāi)銷。

3.2 實(shí)驗(yàn)拓?fù)渑c參數(shù)設(shè)置

實(shí)驗(yàn)部分采用東北大學(xué)校園網(wǎng)拓?fù)洌鐖D1所示。其中存在2臺(tái)服務(wù)器與12臺(tái)路由器。14個(gè)用戶(教學(xué)樓與宿舍樓)并未給出，其均勻分布在圖一的最底層。

圖1 東北大學(xué)校園網(wǎng)拓?fù)鋱DFig.1 Northeastern University campus network topology

針對(duì)該問(wèn)題采用Zipf分布[24]產(chǎn)生內(nèi)容集，并簡(jiǎn)單地認(rèn)為該內(nèi)容越流行、越重要，其緩存命中率也會(huì)越大，以此來(lái)確定緩存命中率。在用戶請(qǐng)求內(nèi)容方面，根據(jù)2/8原則思想，認(rèn)為某個(gè)內(nèi)容越重要?jiǎng)t用戶請(qǐng)求該內(nèi)容所花費(fèi)的流量也就越多，對(duì)總流量按比例進(jìn)行劃分以得出用戶請(qǐng)求不同內(nèi)容所消耗的流量。傳輸單元流量的費(fèi)用參照Amazon CloudFront的定價(jià)[25]，由于其在不同的地區(qū)收費(fèi)不同，在這里取其平均值折合為人民幣大約為0.57元/GB。為每臺(tái)路由器選擇開(kāi)辟1TB High-Speed SSD的緩存空間，其所需要支付的費(fèi)用大約為20萬(wàn)元[26]。在建立基于用戶-服務(wù)提供商的緩存位置模型時(shí)，是用數(shù)據(jù)量與距離的乘積來(lái)定義消耗，而本實(shí)驗(yàn)利用的是實(shí)際網(wǎng)絡(luò)流量數(shù)據(jù)，所以在本實(shí)驗(yàn)中將該模型的消耗式(1)重新定義為流量消耗。

(21)

式中，trafficc,p表示節(jié)點(diǎn)c與節(jié)點(diǎn)p之間的流量。而對(duì)于基于網(wǎng)絡(luò)運(yùn)營(yíng)商的緩存位置模型來(lái)說(shuō)，只需要將式(9)中的內(nèi)容大小koi替換為請(qǐng)求該內(nèi)容實(shí)際的流量即可。

3.3 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)中默認(rèn)的參數(shù)設(shè)置如表2所示。

表2 實(shí)驗(yàn)?zāi)J(rèn)參數(shù)設(shè)置

3.3.1 緩存路由器數(shù)量的影響

實(shí)驗(yàn)結(jié)果如圖2所示。由圖2(a)與(b)可知，在ICN OCLS策略中隨著緩存路由器數(shù)量的增加，流量性價(jià)比呈下降趨勢(shì)，網(wǎng)絡(luò)費(fèi)用開(kāi)銷比先下降后上升。在部署1臺(tái)緩存路由器時(shí)，流量性價(jià)比和網(wǎng)絡(luò)費(fèi)用開(kāi)銷比都是最優(yōu)的。因?yàn)檫x擇在拓?fù)鋱D中的16節(jié)點(diǎn)開(kāi)辟緩存空間，而該節(jié)點(diǎn)位于網(wǎng)絡(luò)中的“核心”，是兩個(gè)校區(qū)流量進(jìn)出口的樞紐，所以在該節(jié)點(diǎn)部署緩存空間會(huì)使用戶都能從中受益。從圖2(a)中可看出，部署3～9臺(tái)緩存路由器時(shí)ICN OCLS的網(wǎng)絡(luò)費(fèi)用開(kāi)銷比相對(duì)較低，且要優(yōu)于ICN NF，即網(wǎng)絡(luò)運(yùn)營(yíng)商會(huì)從中獲益更多。從圖2(b)中可看出，ICN OCLS隨著緩存路由器數(shù)量的增加，流量性價(jià)比逐漸降低最終與ICN NF的一致，這說(shuō)明了部署過(guò)多的緩存路由器會(huì)使每臺(tái)緩存路由器的平均收益值降低。而且，在緩存路由器數(shù)量為1～5時(shí)其效果最好，即用戶和服務(wù)提供商會(huì)從中獲益更多。因此，綜合三方利益來(lái)看，緩存路由器數(shù)量在3～5范圍內(nèi)會(huì)使三方最大限度地從中受益。

3.3.2 Zipf分布α參數(shù)的影響

在ICN OCLS算法中緩存路由器數(shù)量設(shè)置為6，其他參數(shù)見(jiàn)表2。由圖2(c)可知，隨著參數(shù)的增大，兩種策略所對(duì)應(yīng)的流量性價(jià)比也隨之增大，并且ICN OCLS的性價(jià)比要一直優(yōu)于ICN NF，因此在Zipf分布α參數(shù)較大的網(wǎng)絡(luò)中ICN OCLS帶來(lái)的流量性價(jià)比更高。

由圖2(d)與(e)可知，隨著α參數(shù)的增大，兩種策略在兩圖中都呈下降趨勢(shì)。這是因?yàn)棣羺?shù)越大，內(nèi)容分布的“重尾現(xiàn)象”會(huì)越嚴(yán)重，意味著網(wǎng)絡(luò)中流行的內(nèi)容數(shù)量會(huì)越來(lái)越少，只有少數(shù)流行度較高的內(nèi)容才會(huì)被用戶請(qǐng)求，因此緩存路由器通過(guò)緩存這些少數(shù)的重要內(nèi)容來(lái)滿足用戶的請(qǐng)求，大多數(shù)的用戶請(qǐng)求都會(huì)被網(wǎng)內(nèi)緩存滿足，這樣不但降低了網(wǎng)絡(luò)全局流量，而且降低了網(wǎng)絡(luò)運(yùn)營(yíng)商傳輸流量的費(fèi)用。

(a) 不同緩存路由器數(shù)量下的網(wǎng)絡(luò)費(fèi)用開(kāi)銷比(a) Network expense ratio for the different number of cache routers

(b) 不同緩存路由器數(shù)量下的流量性價(jià)比(b) Traffic cost-effective for the different number of cache routers

(c) 不同α下的流量性價(jià)比(c) Traffic cost-effective for different α

(d) 不同α下的網(wǎng)絡(luò)費(fèi)用開(kāi)銷(d) Network expense for different α

(e) 不同α下的網(wǎng)絡(luò)消耗值(e) Network consumption value for different α

(f) 不同內(nèi)容數(shù)量下的流量性價(jià)比(f) Traffic cost-effective for the different number of contents

(g) 不同內(nèi)容數(shù)量下的網(wǎng)絡(luò)費(fèi)用開(kāi)銷(g) Network expense for the different number of contents

(h) 不同內(nèi)容數(shù)量下的網(wǎng)絡(luò)消耗值(h) Network consumption value for the different number of contents圖2 實(shí)驗(yàn)結(jié)果Fig.2 Experimental results

3.3.3 內(nèi)容數(shù)量的影響

在ICN OCLS算法中緩存路由器數(shù)量設(shè)置為6，其他參數(shù)見(jiàn)表2。從圖2(f)、(g)、(h)可知，內(nèi)容對(duì)象數(shù)對(duì)兩種策略是基本沒(méi)有影響的，這是因?yàn)樵搶?shí)驗(yàn)中利用的流量數(shù)據(jù)是東北大學(xué)校園網(wǎng)的年平均流量數(shù)據(jù)，網(wǎng)絡(luò)中的總流量是恒定的，內(nèi)容數(shù)量的增多僅僅會(huì)造成用戶請(qǐng)求的多樣化，而其分布規(guī)律是不變的(Zipf分布α參數(shù)不變)。因此，圖中指標(biāo)幾乎不會(huì)受到影響。

4 結(jié)論

本文通過(guò)考慮網(wǎng)絡(luò)中多方角色的利益，基于不同角度建立了數(shù)學(xué)模型，并將其結(jié)合為多目標(biāo)優(yōu)化模型，基于帕累托求解方法中數(shù)學(xué)規(guī)劃法的思想設(shè)計(jì)了緩存節(jié)點(diǎn)位置選擇算法來(lái)解決ICN中過(guò)度的緩存冗余問(wèn)題。實(shí)驗(yàn)結(jié)果表明，在流量性價(jià)比方面，所提出的最優(yōu)緩存位置選擇算法要完全優(yōu)于ICN原生特性；而在網(wǎng)絡(luò)費(fèi)用開(kāi)銷方面，所提出的算法更適用于只有少數(shù)內(nèi)容較為流行(Zipf分布α參數(shù)較大)的網(wǎng)絡(luò)中，而對(duì)于所有內(nèi)容都流行(Zipf分布α參數(shù)較小)的網(wǎng)絡(luò)中，ICN原生特性更為適宜。

此外，本文解決ICN中過(guò)度的緩存冗余問(wèn)題的方法，僅僅是從開(kāi)辟緩存空間的角度進(jìn)行研究的，而這只是解決該問(wèn)題策略中的一部分，更為完備的解決方案是：選擇節(jié)點(diǎn)開(kāi)辟緩存空間→為已開(kāi)辟緩存空間的節(jié)點(diǎn)分配存儲(chǔ)容量→對(duì)內(nèi)容的放置進(jìn)行決策。該方案能夠更加全面、更加完備地解決ICN中過(guò)度的緩存冗余問(wèn)題，這也將是本文未來(lái)所要研究的重點(diǎn)內(nèi)容。