協作緩存及數學建模在CCN中的應用

李 偉，潘沛生

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

0 引 言

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

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

為了使P-ASS更具普遍性，對P-ASS進行定量計算時，針對任意網絡拓撲建立數學模型，而不是僅針對二叉樹等幾種較為普遍的拓撲圖，使得仿真結果更具普遍性。最后計算并比較LCE、LCD及P-ASS的緩存命中率、平均跳數和延時時間，以驗證P-ASS的性能。

1 自治系統協作緩存策略

1.1 基本思想

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

1.2 P-ASS詳述

1.2.1 AS的劃分

在P-ASS中，緩存系統分為幾個由控制節點集中控制的AS，如圖1所示。自治系統內仍然使用OSPF協議[5]，利用最短路徑優先算法決定請求路徑。

圖1 任意網絡拓撲

1.2.2 控制節點的選擇

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

CCN網絡的拓撲結構可以表示為無向圖G=(V,E)，其中V是CCN節點的集合，E是節點之間的邊集。C(v)是與節點v(v∈V)相連接的節點個數。一旦網絡建立，就很容易獲得C(v)。Cnor(v)是C(v)的歸一化，可以通過式1求得。

(1)

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

(2)

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

(3)

M(v)表示網絡中每個節點作為控制節點的適應度情況，由式4求得。

(4)

1.2.3 流行度計算及對應策略

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

(5)

[0,1]

(6)

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

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

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

1.3 AS中的節點詳述

1.3.1 AS中各節點的結構

節點結構[10]如圖2所示。

圖2 CCN節點結構

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

下面是兩種類型節點的具體作用：

(1)控制節點：除了傳統的三個表[11](CS，PIT，FIB)之外，特別地，每個控制節點維護自己的緩存匯總表(CST)。它記錄所屬AS中各節點緩存的內容信息。每個節點周期性地向控制節點報告其本地緩存信息。控制節點周期性地將自己的CST通告給公共節點。同時，控制節點計算自己已經接收的每個內容的流行度以確定不同內容的緩存策略。

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

1.3.2 通信包類型及作用

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

(1)興趣包：興趣包由用戶發送，用于請求想要的網絡資源等。

(2)數據包：數據包是當用戶請求在網絡中命中時，返回給用戶的數據信息。

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

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

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

(6)確認包：當控制節點收到請求包時，控制節點在自己的CS，PIT，FIB和CST中查看該內容。如果控制節點從請求該內容的節點處收到探測包，則會發送確認包，告訴該節點請求有沒有命中。

1.3.3 基本通信過程

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

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

此外，如果興趣包能夠匹配到CST中的內容，則說明內容已被AS中的節點緩存，則會將興趣包轉發到該節點以獲得內容。

2 對任意網絡拓撲建模

在提出新的緩存策略之后，本節將針對任意網絡拓撲結構進行數學建模[12]。將網絡的數據傳輸通過概率論原理，用數學表達式表述。考慮CCN網絡的請求聚合能力，建立CCN在一般網絡拓撲結構下，基于迭代方法的MMAT傳輸模型。然后將所列數學表達式進行迭代，直到未知量落入預先設定的誤差范圍終止。最后得到內容的平均未命中率和時延。在該模型上，先后使用LCE、LCD和P-ASS三種策略進行仿真。使用相同的計算模型，保證仿真數據更可靠，結論更客觀。

符號及意義見表1。

表1 符號及意義

兩相鄰節點vi和vj之間獲取的內容k的往返時延是：

(7)

其中，tp為相鄰節點的傳播時延；tq為請求傳輸時延；tc為內容傳輸時延。則節點v按照Pk,v在第j跳節點獲取內容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命中概率的加權。

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

第一步：節點v收到對內容k的請求率為：

(9)

第二步：計算請求在經過CS后的輸出流。根據文獻[13]可得請求內容在節點v處的概率為：

(10)

假設請求流服從泊松分布，根據文獻[14]可得內容k的請求在節點v處未命中的概率為：

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

(12)

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

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

3 仿 真

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

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

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

圖5 平均跳數隨緩存大小的變化

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

4 結束語

文中對CCN的兩種基本緩存策略進行調研，得出幾種策略的不足之處，比如緩存冗余度高，只能沿單一路徑請求內容，且節點之間相互獨立，缺少必要的協作通信，等等。在此基礎上，提出一種基于自治系統協作緩存的策略，使得相鄰節點之間可以實現相互通信，比較智能地就近選擇合適的節點，獲取用戶請求的內容，實現以較少的跳數實現內容的命中。三種策略在面向任意拓撲的同一傳輸模型上進行仿真實驗，結果表明，與現有基本策略相比，P-ASS可以得到更好的網絡性能參數，優化網絡性能。未來網絡架構還有很多方面值得研究，例如可以根據當前網絡環境及內容存儲的位置，更加智能地動態選擇控制節點，以實現更好的性能增益，收獲更好的用戶體驗。