協(xié)作緩存及數(shù)學(xué)建模在CCN中的應(yīng)用

李 偉，潘沛生

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

隨著信息量的暴漲，當(dāng)前網(wǎng)絡(luò)架構(gòu)已經(jīng)不能滿足用戶的需求，對(duì)未來(lái)網(wǎng)絡(luò)架構(gòu)的研究開(kāi)始變得愈發(fā)重要。近年來(lái)，學(xué)術(shù)界提出的CCN網(wǎng)絡(luò)，成為未來(lái)網(wǎng)絡(luò)架構(gòu)領(lǐng)域中值得關(guān)注的熱點(diǎn)[1]。目前，CCN有兩種最基礎(chǔ)的緩存策略，分別為處處緩存策略(leave cache everywhere,LCE)[2]和向下拷貝策略(leave copy down,LCD)[3]。這兩種策略簡(jiǎn)單易行，但資源的利用率較低[4]。

為了解決節(jié)點(diǎn)之間完全獨(dú)立的現(xiàn)狀，對(duì)如何把自治系統(tǒng)的協(xié)作策略應(yīng)用到CCN網(wǎng)絡(luò)中進(jìn)行了研究。能夠?qū)崿F(xiàn)自治系統(tǒng)內(nèi)部各節(jié)點(diǎn)之間互相通信，使得節(jié)點(diǎn)收到請(qǐng)求之后，能夠更加快速智能地選擇存儲(chǔ)該請(qǐng)求內(nèi)容的節(jié)點(diǎn)，而不是直接使用最短路徑優(yōu)先策略來(lái)決定請(qǐng)求轉(zhuǎn)發(fā)路線，從而以較少的跳數(shù)和較小的延時(shí)得到請(qǐng)求內(nèi)容。對(duì)自治系統(tǒng)協(xié)作緩存策略(P-ASS)進(jìn)行定性分析。在實(shí)現(xiàn)自治系統(tǒng)集中控制之前，通過(guò)將網(wǎng)絡(luò)劃分為自治系統(tǒng)來(lái)實(shí)現(xiàn)顯式協(xié)作，減少緩存的冗余，提高緩存利用率和緩存命中率。在此策略下，同一AS中的節(jié)點(diǎn)相互合作，實(shí)現(xiàn)了CCN的緩存性能的增益。

為了使P-ASS更具普遍性，對(duì)P-ASS進(jìn)行定量計(jì)算時(shí)，針對(duì)任意網(wǎng)絡(luò)拓?fù)浣?shù)學(xué)模型，而不是僅針對(duì)二叉樹(shù)等幾種較為普遍的拓?fù)鋱D，使得仿真結(jié)果更具普遍性。最后計(jì)算并比較LCE、LCD及P-ASS的緩存命中率、平均跳數(shù)和延時(shí)時(shí)間，以驗(yàn)證P-ASS的性能。

1 自治系統(tǒng)協(xié)作緩存策略

1.1 基本思想

緩存策略對(duì)CCN的性能有決定性的影響。在傳統(tǒng)的CCN中，數(shù)據(jù)包沿返回路徑被緩存，并且只有傳輸路徑上的緩存可以用于服務(wù)響應(yīng)，缺乏節(jié)點(diǎn)之間必要的協(xié)作機(jī)制，使得系統(tǒng)緩存效率很低。此外，從相鄰節(jié)點(diǎn)獲取內(nèi)容的成本比從源服務(wù)器獲取它的成本便宜得多。而提出的協(xié)作緩存策略解決了節(jié)點(diǎn)之間缺乏有效協(xié)作的問(wèn)題，使得緩存得到了更有效的利用，以達(dá)到提高系統(tǒng)緩存效率的目的。

1.2 P-ASS詳述

1.2.1 AS的劃分

在P-ASS中，緩存系統(tǒng)分為幾個(gè)由控制節(jié)點(diǎn)集中控制的AS，如圖1所示。自治系統(tǒng)內(nèi)仍然使用OSPF協(xié)議[5]，利用最短路徑優(yōu)先算法決定請(qǐng)求路徑。

圖1 任意網(wǎng)絡(luò)拓?fù)?/p>

1.2.2 控制節(jié)點(diǎn)的選擇

控制節(jié)點(diǎn)的選擇決定網(wǎng)絡(luò)的性能，因此如何選擇控制節(jié)點(diǎn)變化變得尤為重要。下面介紹一種使用基于節(jié)點(diǎn)的中間性和緩存替換率[6]來(lái)選擇控制節(jié)點(diǎn)的方法。

CCN網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可以表示為無(wú)向圖G=(V,E)，其中V是CCN節(jié)點(diǎn)的集合，E是節(jié)點(diǎn)之間的邊集。C(v)是與節(jié)點(diǎn)v(v∈V)相連接的節(jié)點(diǎn)個(gè)數(shù)。一旦網(wǎng)絡(luò)建立，就很容易獲得C(v)。Cnor(v)是C(v)的歸一化，可以通過(guò)式1求得。

(1)

關(guān)于節(jié)點(diǎn)v，被替換的內(nèi)容ki的大小由S(ki)表示，節(jié)點(diǎn)v的緩存大小由Ca(v)表示。m是單位時(shí)間內(nèi)節(jié)點(diǎn)v的緩存內(nèi)容替換次數(shù)。Re(v)是節(jié)點(diǎn)v的緩存替換率，見(jiàn)式2。

(2)

Re(v)歸一化后的值表示為Renor(v)，見(jiàn)式3：

(3)

M(v)表示網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)作為控制節(jié)點(diǎn)的適應(yīng)度情況，由式4求得。

(4)

1.2.3 流行度計(jì)算及對(duì)應(yīng)策略

在P-ASS中，AS的控制節(jié)點(diǎn)需要具有計(jì)數(shù)內(nèi)容的流行度[7]的能力。使用式5和式6計(jì)算每個(gè)內(nèi)容的流行度。

(5)

[0,1]

(6)

其中，i表示請(qǐng)求內(nèi)容的名稱；Ri表示用戶在時(shí)間段t內(nèi)請(qǐng)求內(nèi)容i的次數(shù)[8]；I(i∈I)表示時(shí)間間隔t期間的所有內(nèi)容的集合。

實(shí)際上，Popu(i)是流行度，但是式6對(duì)Popu(i)進(jìn)行歸一化，得出Popularity(i)。Popularity(i)在以后更方便使用。

文中按照內(nèi)容流行度參數(shù)將內(nèi)容分為三類：高流行度內(nèi)容、中等流行度內(nèi)容和低流行度內(nèi)容。不同類型的內(nèi)容具有由控制節(jié)點(diǎn)確定的不同的緩存策略。如果Popularity(i)>0.5，則內(nèi)容i是高流行度內(nèi)容。它需要冗余的緩存來(lái)提高緩存命中率，因?yàn)樵S多用戶會(huì)請(qǐng)求它。圖1的內(nèi)容A就是一個(gè)示例。如果0.2< Popularity(i)<0.5，這意味著內(nèi)容i是中等流行度內(nèi)容。中等流行度內(nèi)容是減少冗余的主要部分。在P-ASS中，這些內(nèi)容在同一AS中僅會(huì)被緩存一次，以減少內(nèi)容緩存冗余。圖1中的B是中等流行度內(nèi)容。如果Popularity(i)<0.2，則內(nèi)容i被稱為低流行度內(nèi)容。因?yàn)榈土餍卸葍?nèi)容被請(qǐng)求的次數(shù)太少，容易被替換[9]，如圖1中的C，所以它們通常不在AS中緩存。

1.3 AS中的節(jié)點(diǎn)詳述

1.3.1 AS中各節(jié)點(diǎn)的結(jié)構(gòu)

節(jié)點(diǎn)結(jié)構(gòu)[10]如圖2所示。

圖2 CCN節(jié)點(diǎn)結(jié)構(gòu)

在AS中有兩種類型的節(jié)點(diǎn)，分別是控制節(jié)點(diǎn)和公共節(jié)點(diǎn)。AS中只有一個(gè)控制節(jié)點(diǎn)，而其他都是公共節(jié)點(diǎn)。控制節(jié)點(diǎn)的主要作用是控制整合該自治系統(tǒng)所有節(jié)點(diǎn)的存儲(chǔ)內(nèi)容，公共節(jié)點(diǎn)則定期向控制節(jié)點(diǎn)更新自己本地的信息。

下面是兩種類型節(jié)點(diǎn)的具體作用：

(1)控制節(jié)點(diǎn)：除了傳統(tǒng)的三個(gè)表[11](CS，PIT，F(xiàn)IB)之外，特別地，每個(gè)控制節(jié)點(diǎn)維護(hù)自己的緩存匯總表(CST)。它記錄所屬AS中各節(jié)點(diǎn)緩存的內(nèi)容信息。每個(gè)節(jié)點(diǎn)周期性地向控制節(jié)點(diǎn)報(bào)告其本地緩存信息。控制節(jié)點(diǎn)周期性地將自己的CST通告給公共節(jié)點(diǎn)。同時(shí)，控制節(jié)點(diǎn)計(jì)算自己已經(jīng)接收的每個(gè)內(nèi)容的流行度以確定不同內(nèi)容的緩存策略。

(2)公共節(jié)點(diǎn)：除了控制節(jié)點(diǎn)之外，AS中的其他節(jié)點(diǎn)是公共節(jié)點(diǎn)。公共節(jié)點(diǎn)保持四個(gè)表：CS，PIT，F(xiàn)IB和CST，用于記錄內(nèi)容的名稱及其獲得的位置。然而，LCST由控制節(jié)點(diǎn)發(fā)出。當(dāng)新內(nèi)容已被緩存時(shí)，公共節(jié)點(diǎn)向控制節(jié)點(diǎn)報(bào)告CS的信息。

1.3.2 通信包類型及作用

P-ASS是基于節(jié)點(diǎn)之間的相互通信提出的，則節(jié)點(diǎn)之間的通信內(nèi)容也會(huì)有所不同。在該策略中定義了六種類型的通信包，供不同的消息類型使用。分別是：興趣包、數(shù)據(jù)包、匯報(bào)包、更新包、探測(cè)包和確認(rèn)包。

(1)興趣包：興趣包由用戶發(fā)送，用于請(qǐng)求想要的網(wǎng)絡(luò)資源等。

(2)數(shù)據(jù)包：數(shù)據(jù)包是當(dāng)用戶請(qǐng)求在網(wǎng)絡(luò)中命中時(shí)，返回給用戶的數(shù)據(jù)信息。

(3)匯報(bào)包：公共節(jié)點(diǎn)在更新存儲(chǔ)的內(nèi)容時(shí)，會(huì)發(fā)送匯報(bào)包給控制節(jié)點(diǎn)，通知控制節(jié)點(diǎn)更新匯總表記錄。如果一定時(shí)間段內(nèi)沒(méi)有存儲(chǔ)內(nèi)容的更新，節(jié)點(diǎn)會(huì)定期發(fā)送匯報(bào)包，告訴控制節(jié)點(diǎn)，該節(jié)點(diǎn)還存在。

(4)更新包：控制節(jié)點(diǎn)周期性地將自己CST中的匯總信息同步給所屬自治系統(tǒng)中的各個(gè)公共節(jié)點(diǎn)。如果請(qǐng)求在控制節(jié)點(diǎn)命中，則控制節(jié)點(diǎn)立刻將請(qǐng)求轉(zhuǎn)發(fā)給相應(yīng)的公共節(jié)點(diǎn)。

(5)探測(cè)包：當(dāng)公共節(jié)點(diǎn)不能在自己的緩存中命中請(qǐng)求內(nèi)容，則會(huì)將請(qǐng)求轉(zhuǎn)發(fā)給控制節(jié)點(diǎn)，請(qǐng)求自己想要的內(nèi)容。如果一定時(shí)間內(nèi)，該節(jié)點(diǎn)沒(méi)有收到控制節(jié)點(diǎn)的確認(rèn)包或者數(shù)據(jù)包，則該節(jié)點(diǎn)會(huì)向控制節(jié)點(diǎn)發(fā)送探測(cè)包，以確認(rèn)控制節(jié)點(diǎn)是否已收到該節(jié)點(diǎn)的請(qǐng)求。

(6)確認(rèn)包：當(dāng)控制節(jié)點(diǎn)收到請(qǐng)求包時(shí)，控制節(jié)點(diǎn)在自己的CS，PIT，F(xiàn)IB和CST中查看該內(nèi)容。如果控制節(jié)點(diǎn)從請(qǐng)求該內(nèi)容的節(jié)點(diǎn)處收到探測(cè)包，則會(huì)發(fā)送確認(rèn)包，告訴該節(jié)點(diǎn)請(qǐng)求有沒(méi)有命中。

1.3.3 基本通信過(guò)程

情況1：如果控制節(jié)點(diǎn)收到用戶請(qǐng)求，首先計(jì)算該內(nèi)容的流行度以確定哪些節(jié)點(diǎn)適于緩存該內(nèi)容，以提高緩存利用率并增加緩存命中率。之后，作為傳統(tǒng)的CCN，它應(yīng)該依次查找CS、PIT、CST、FIB。如果緩存未命中，則控制節(jié)點(diǎn)將丟棄興趣包并發(fā)送確認(rèn)包以通知請(qǐng)求該內(nèi)容的節(jié)點(diǎn)自己處理。

情況2：如果接收機(jī)是公共節(jié)點(diǎn)，則應(yīng)當(dāng)搜索其CS、PIT、LCST作為傳統(tǒng)CCN來(lái)檢查其是否具有內(nèi)容。如果沒(méi)有匹配，則公共節(jié)點(diǎn)將向控制節(jié)點(diǎn)轉(zhuǎn)發(fā)興趣包。然后控制節(jié)點(diǎn)將像情況1一樣處理。公共節(jié)點(diǎn)在將興趣包轉(zhuǎn)發(fā)到控制節(jié)點(diǎn)之后等待數(shù)據(jù)包，如果等待超時(shí)，則公共節(jié)點(diǎn)將發(fā)送消息以確認(rèn)內(nèi)容是否命中。如果公共節(jié)點(diǎn)接收到控制節(jié)點(diǎn)的回復(fù)，并且被告知內(nèi)容未命中，則公共節(jié)點(diǎn)將如傳統(tǒng)CCN那樣檢查FIB。

此外，如果興趣包能夠匹配到CST中的內(nèi)容，則說(shuō)明內(nèi)容已被AS中的節(jié)點(diǎn)緩存，則會(huì)將興趣包轉(zhuǎn)發(fā)到該節(jié)點(diǎn)以獲得內(nèi)容。

2 對(duì)任意網(wǎng)絡(luò)拓?fù)浣?/h2>

在提出新的緩存策略之后，本節(jié)將針對(duì)任意網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行數(shù)學(xué)建模[12]。將網(wǎng)絡(luò)的數(shù)據(jù)傳輸通過(guò)概率論原理，用數(shù)學(xué)表達(dá)式表述。考慮CCN網(wǎng)絡(luò)的請(qǐng)求聚合能力，建立CCN在一般網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，基于迭代方法的MMAT傳輸模型。然后將所列數(shù)學(xué)表達(dá)式進(jìn)行迭代，直到未知量落入預(yù)先設(shè)定的誤差范圍終止。最后得到內(nèi)容的平均未命中率和時(shí)延。在該模型上，先后使用LCE、LCD和P-ASS三種策略進(jìn)行仿真。使用相同的計(jì)算模型，保證仿真數(shù)據(jù)更可靠，結(jié)論更客觀。

符號(hào)及意義見(jiàn)表1。

表1 符號(hào)及意義

兩相鄰節(jié)點(diǎn)vi和vj之間獲取的內(nèi)容k的往返時(shí)延是：

(7)

其中，tp為相鄰節(jié)點(diǎn)的傳播時(shí)延；tq為請(qǐng)求傳輸時(shí)延；tc為內(nèi)容傳輸時(shí)延。則節(jié)點(diǎn)v按照Pk,v在第j跳節(jié)點(diǎn)獲取內(nèi)容ck的往返時(shí)延表示為：

Tk,v,j=tv,Pk,v(2)+tPk,v(2),Pk,v(3)+…+tPk,v(j-1),Pk,v(j)

(8)

此時(shí)，便可得到VTk,v為Tk,v,j命中概率的加權(quán)。

下面對(duì)所提建模方案進(jìn)行詳細(xì)描述。設(shè)G(V,E)為一個(gè)CCN網(wǎng)絡(luò)，將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)看作由CS、PIT、FIB這三個(gè)過(guò)濾器組成。則具體建模步驟如下：

第一步：節(jié)點(diǎn)v收到對(duì)內(nèi)容k的請(qǐng)求率為：

(9)

第二步：計(jì)算請(qǐng)求在經(jīng)過(guò)CS后的輸出流。根據(jù)文獻(xiàn)[13]可得請(qǐng)求內(nèi)容在節(jié)點(diǎn)v處的概率為：

(10)

假設(shè)請(qǐng)求流服從泊松分布，根據(jù)文獻(xiàn)[14]可得內(nèi)容k的請(qǐng)求在節(jié)點(diǎn)v處未命中的概率為：

mk,v=Rk,v(1-qk,v)

(12)

第三步：請(qǐng)求通過(guò)CS到達(dá)PIT之后，PIT過(guò)濾被轉(zhuǎn)發(fā)之后還未收到回復(fù)的請(qǐng)求。則節(jié)點(diǎn)v處請(qǐng)求的聚合概率取決于PIT中記錄的生存時(shí)間T和VTk,v。當(dāng)數(shù)據(jù)在CS中的緩存時(shí)間遠(yuǎn)遠(yuǎn)小于VTk,v時(shí)，到達(dá)PIT的請(qǐng)求也滿足泊松分布，因此節(jié)點(diǎn)v請(qǐng)求內(nèi)容k的聚合概率為：(1-e-mk,vΔk,v)，其中Δk,v=min(T,VTk,v)。

第四步：將式7～12聯(lián)立,所有節(jié)點(diǎn)的CS和fk,v全部清零，然后迭代，直到兩次相鄰迭代的平均跳數(shù)、命中率和平均時(shí)延都小于所設(shè)定的閾值。

3 仿 真

為了分析P-ASS的性能，使用ccnSim平臺(tái)[15]進(jìn)行仿真。仿真網(wǎng)絡(luò)中設(shè)有400個(gè)節(jié)點(diǎn)，兩節(jié)點(diǎn)間帶寬為20 Mbps,傳播時(shí)延tp=5×10-4s，內(nèi)容大小為1 kb。本次性能評(píng)估的主要內(nèi)容是，不同的網(wǎng)絡(luò)緩存大小對(duì)各種策略性能的影響。與CCN中的兩種傳統(tǒng)緩存策略(LCE、LCD)進(jìn)行比較，結(jié)果如圖3～5所示。

圖3 命中率隨緩存大小的變化

圖4 平均往返時(shí)延隨緩存大小的變化

圖5 平均跳數(shù)隨緩存大小的變化

通過(guò)數(shù)據(jù)對(duì)比可以看出，與基本的LCE、LCD策略相比，隨著緩存大小的增長(zhǎng)，P-ASS在平均跳數(shù)、命中率和平均時(shí)延三方面的變化更具備優(yōu)越性。在緩存大小趨于無(wú)限大時(shí)，三種策略性能參數(shù)都趨于穩(wěn)定，但P-ASS性能最佳。

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

文中對(duì)CCN的兩種基本緩存策略進(jìn)行調(diào)研，得出幾種策略的不足之處，比如緩存冗余度高，只能沿單一路徑請(qǐng)求內(nèi)容，且節(jié)點(diǎn)之間相互獨(dú)立，缺少必要的協(xié)作通信，等等。在此基礎(chǔ)上，提出一種基于自治系統(tǒng)協(xié)作緩存的策略，使得相鄰節(jié)點(diǎn)之間可以實(shí)現(xiàn)相互通信，比較智能地就近選擇合適的節(jié)點(diǎn)，獲取用戶請(qǐng)求的內(nèi)容，實(shí)現(xiàn)以較少的跳數(shù)實(shí)現(xiàn)內(nèi)容的命中。三種策略在面向任意拓?fù)涞耐粋鬏斈Ｐ蜕线M(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，與現(xiàn)有基本策略相比，P-ASS可以得到更好的網(wǎng)絡(luò)性能參數(shù)，優(yōu)化網(wǎng)絡(luò)性能。未來(lái)網(wǎng)絡(luò)架構(gòu)還有很多方面值得研究，例如可以根據(jù)當(dāng)前網(wǎng)絡(luò)環(huán)境及內(nèi)容存儲(chǔ)的位置，更加智能地動(dòng)態(tài)選擇控制節(jié)點(diǎn)，以實(shí)現(xiàn)更好的性能增益，收獲更好的用戶體驗(yàn)。