李 偉，潘沛生

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

0 引 言

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

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

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

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

1.1 基本思想

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

1.2 P-ASS詳述

1.2.1 AS的劃分

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

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

(5)

[0,1]

(6)

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

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

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

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

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

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

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

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

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

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

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

1.3.2 通信包類型及作用

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

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

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

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

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

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

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

1.3.3 基本通信過程

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

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

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

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

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

符號及意義見表1。

表1 符號及意義

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

(7)

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

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

(8)

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

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

第一步：節(jié)點v收到對內(nèi)容k的請求率為：

(9)

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

(10)

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

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

(12)

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

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

3 仿 真

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

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

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

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

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

4 結(jié)束語

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