受限洪泛策略的內(nèi)容中心網(wǎng)絡(luò)路由算法

吳文剛 王慶生

1(山西經(jīng)濟管理干部學(xué)院電子信息工程系 山西 太原 030024)

2(太原理工大學(xué)信息與計算機學(xué)院 山西 太原 030024)

0 引 言

隨著網(wǎng)絡(luò)日益扁平化和網(wǎng)絡(luò)連接資源的日趨豐富，網(wǎng)絡(luò)拓撲結(jié)構(gòu)也變得愈加復(fù)雜，獲取網(wǎng)絡(luò)資源所需要的網(wǎng)絡(luò)跳數(shù)也愈來愈少[1]。面對網(wǎng)絡(luò)扁平化的趨勢，TCP/IP網(wǎng)絡(luò)提出了一系列的新型網(wǎng)絡(luò)協(xié)議[2-3]，例如：P2P協(xié)議提供對等網(wǎng)絡(luò)進行去中心化的數(shù)據(jù)傳輸以進行直接的共享資源與服務(wù);CDN協(xié)議則通過DNS重定向技術(shù)在網(wǎng)絡(luò)中部署節(jié)點服務(wù)器以便于域內(nèi)獲取網(wǎng)絡(luò)數(shù)據(jù)與資源等。然而，內(nèi)容中心網(wǎng)絡(luò)(Content-Centric Network,CCN)作為一種未來網(wǎng)絡(luò)體系架構(gòu)，仍然采用基于最優(yōu)路徑的方式獲取數(shù)據(jù)[4]。如果以內(nèi)容提供商作為根節(jié)點，以請求該內(nèi)容提供商數(shù)據(jù)的用戶為葉節(jié)點，那么網(wǎng)絡(luò)中所有針對該內(nèi)容提供商的數(shù)據(jù)請求路徑將構(gòu)成一顆請求樹。顯然，這樣的樹狀數(shù)據(jù)請求結(jié)構(gòu)無法更好地適應(yīng)日益突出的扁平化網(wǎng)絡(luò)結(jié)構(gòu)，如何探索網(wǎng)絡(luò)中其他位置的緩存內(nèi)容成為了提升CCN轉(zhuǎn)發(fā)效率最重要的挑戰(zhàn)[5]。

為了解決上述挑戰(zhàn)，本文采用探索的方法，盡可能地獲取網(wǎng)絡(luò)最近副本的位置，這需要在網(wǎng)絡(luò)轉(zhuǎn)發(fā)的策略上進行改變和創(chuàng)新。當前的CCN網(wǎng)絡(luò)層中，轉(zhuǎn)發(fā)一個興趣包時，主要有兩種轉(zhuǎn)發(fā)策略可以選用：最優(yōu)路徑算法和多路徑轉(zhuǎn)發(fā)。

最優(yōu)路徑算法類似于IP網(wǎng)絡(luò)中的最長掩碼匹配，即根據(jù)路由表提供的路由信息自適應(yīng)地選擇最優(yōu)的轉(zhuǎn)發(fā)路徑。國內(nèi)外一些研究結(jié)合了CCN網(wǎng)絡(luò)的特性，針對最優(yōu)路徑算法提出了一系列自適應(yīng)的、有狀態(tài)的轉(zhuǎn)發(fā)策略，使CCN轉(zhuǎn)發(fā)層相比于IP網(wǎng)絡(luò)的轉(zhuǎn)發(fā)層更加智能[6-9]。然而，最優(yōu)路徑算法目前仍然無法支持最近副本路由，這使得對于熱門數(shù)據(jù)，除非最優(yōu)轉(zhuǎn)發(fā)路徑的緩存中存在相應(yīng)的副本，否則大量的網(wǎng)絡(luò)緩存對于用戶來說全部是透明的，這極大程度地限制了網(wǎng)絡(luò)的性能[10-11]。

相比之下，多路徑轉(zhuǎn)發(fā)則可以盡可能地返回最近的內(nèi)容副本。作為多路徑轉(zhuǎn)發(fā)最極端的情況，洪泛算法釆用廣播的方式，雖然可以最大程度地利用網(wǎng)絡(luò)資源，返回最近的內(nèi)容副本，但是由于多路徑路由帶來了較大的開銷，在實際網(wǎng)絡(luò)中并不能得到真正應(yīng)用。

由此可見，多路徑路由可以從本質(zhì)上解決CCN網(wǎng)絡(luò)無法支持最近副本路由的問題，但是采用多路徑路由的最大挑戰(zhàn)是：如何在盡可能保證性能的前提下，最大程度地降低多路徑路由帶來的開銷。為了解決這一問題，本文基于多路徑路由中最簡單的洪泛算法，提出了一種受限洪泛策略來極大地減小原始的洪泛算法的開銷。使用洪泛算法有以下幾個優(yōu)點[12-14]：

1) 降低復(fù)雜性。洪泛算法可以極大地降低協(xié)議復(fù)雜性并簡化協(xié)議設(shè)計。特別地，文獻[11]中指出，洪泛算法在某些不穩(wěn)定的網(wǎng)絡(luò)環(huán)境中最適用。

2) 發(fā)現(xiàn)鄰居內(nèi)容。在CCN中，除了路徑緩存外，用戶請求同樣需要處理強大的空間位置[14]。換言之，就是說在某一路由器周圍的路由器中很大可能地緩存了用戶請求的某些熱門數(shù)據(jù)。如果對于用戶，這些鄰居中緩存的數(shù)據(jù)是透明的，那么洪泛算法是最適合發(fā)現(xiàn)鄰居節(jié)點緩存內(nèi)容的算法。

3) 減小路由狀態(tài)。相對于最優(yōu)路徑算法，洪泛算法在基于路由的內(nèi)容發(fā)現(xiàn)機制方面，所需要維護的網(wǎng)絡(luò)狀態(tài)相對比較少。

4) 降低通信成本。在CCN中，利用相近鄰居互相交換數(shù)據(jù)，相比于使用回程的方法，開銷相對比較低。

本文針對CCN網(wǎng)絡(luò)轉(zhuǎn)發(fā)層存在的問題，結(jié)合洪泛算法和最優(yōu)路徑算法，通過控制洪泛區(qū)域降低開銷的方法，提出了新型的RFS算法來解決網(wǎng)絡(luò)無法獲取鄰居節(jié)點緩存副本的問題。提出的RFS*算法在開銷幾乎不變的條件下，大幅降低分發(fā)數(shù)據(jù)獲取的網(wǎng)絡(luò)時延。

1 RFS算法與理論分析

1.1 RFS算法

1.1.1參數(shù)定義

在描述RFS算法與理論分析之前，先定義一些算法中需要用到的參數(shù)。

定義1域內(nèi)洪泛算法。相對于傳統(tǒng)的粗暴型洪泛(不受任何限制的洪泛算法)，將洪泛范圍縮小至某一可控區(qū)域內(nèi)的洪泛算法稱為域內(nèi)洪泛算法。

定義2洪泛生存時間FTTL(Flooding TTL)、最大洪泛生存時間mFTTL(Maximal FTTL)、洪泛數(shù)量NF(Number of Flooding)。在域內(nèi)洪泛算法中，F(xiàn)TTL代表洪泛包當前的生存時間；mFTTL代表FTTL上限；NF代表當一個路由器收到某一興趣包時，洪泛至上游路由器的最大數(shù)量。

在域內(nèi)洪泛算法中，F(xiàn)TTL(mFTTL)和NF分別從洪泛的深度和廣度兩個角度來控制洪泛算法的區(qū)域。假如針對某一興趣包采用基于域內(nèi)洪泛算法的轉(zhuǎn)發(fā)策略，且mFTTL=3、NF=2，則在當路由器收到該興趣包時，首先檢查當前的洪泛生存時間是否已經(jīng)達到最大的洪泛深度，即比較FTTL與mFTTL。如果FTTL

定義3R-路由器。對于某一給定的興趣包，沿最優(yōu)轉(zhuǎn)發(fā)路徑的第一臺上游路由器(即與用戶最近的路由器)定義為R-路由器。

定義4F-深度。對于某一給定的興趣包和當前收到該興趣包的路由器，從R-路由器開始，沿著該興趣包到達該路由器的轉(zhuǎn)發(fā)路徑所需要的跳數(shù)定義為F-深度。特別地，R-路由器的F-深度定義為0。

定義5B-路徑、F-路徑、B-路由器、F-路由器。對于某一給定的興趣包：1) 如果根據(jù)路由表，沿著最佳路徑轉(zhuǎn)發(fā)的路線，從R-路由器開始直至內(nèi)容提供者，這段路徑定義為B-路徑，其路徑上的路由器定義為B-路由器；2) 如果采用域內(nèi)洪泛算法，從R-路由器開始直至F-深度為mFTTL的路由器，這段路徑定義為F-路徑，其路徑上的路由器定義為F-路由器。

值得注意的是，對于某一給定的興趣包，其B-路徑至多只有一條，而F-路徑可以有多條。另外，對于某些路由器，有可能既是B-路由器，也是F-路由器。

定義6k-F-子路徑。對于某一給定的興趣包，在其某一條F-路徑上，從F-深度為k-1的F-路由器到F-深度為k的F-路由器的這條路徑定義為k-F-子路徑。

如圖1所示，對于某一興趣包釆用域內(nèi)洪泛算法，并定義mFTTL=3、NF=1?？梢钥吹?，圖中共有1條B-路徑、3條F-路徑、3臺B-路由器和5臺F-路由器。

圖1 RFS相關(guān)定義示意圖

1.1.2算法描述

RFS算法偽代碼如算法1所示。

算法1RFS算法

RFS(Interestinterest,intf_depth)

//如果為F-路由器

ifinterest.lable==F

interest.f_ttl++;

ifinterest.f_ttl

//隨機選擇NF臺下一跳路由器進行洪泛

RamdomFlooding(interest,NF);

else

Drop(inte);

endif

//如果為B-路由器

else

ifR-router

interest.f_ttl=0;

else

interest.f_ttl++;

endif

//首先沿B-路徑轉(zhuǎn)發(fā)

BestRoute(interest);

ifinterest.f_ttl

//增加F標簽并進行洪泛

f_interest=interest.getCopy();

f_interest.lable=F;

RamdomFlooding(f_interest,NF);

endif

endif

基于上文的若干定義，對于某一給定的興趣包，RFS算法描述如下：

初始化：

將興趣包的FTTL初始化為0。

算法開始：

1) 如果當前路由器為R-路由器或B-路由器，則:

① 如果當前路由器為R-路由器，則FTTL=0，否則FTTL增加1。

② 根據(jù)路由表，沿B-路徑轉(zhuǎn)發(fā)該興趣包。

③ 比較當前興趣包的FTTL與mFTTL的大小。如果FTTL

2) 如果當前路由器為F-路由器(即檢測到興趣包帶有標簽F)，則:

①FTTL增加1。

② 比較當前興趣包的FTTL與mFTTL的大小。如果FTTL

算法結(jié)束：用戶收到興趣包對應(yīng)的數(shù)據(jù)包。

1.2 理論分析

本節(jié)將從理論上分析RFS的性能和開銷。在進行理論分析之前，先給出一些參數(shù)定義和符號定義。

定義7洪泛覆蓋。對于某一給定的興趣包，釆用RFS算法后，其洪泛包的總數(shù)定義為洪泛覆蓋。

顯然，洪泛覆蓋代表使用RFS算法產(chǎn)生的額外開銷，即網(wǎng)絡(luò)額外產(chǎn)生的興趣包數(shù)量。

定義8路徑長度比率。對于某一給定的興趣包，路徑長度比率η定義為:

(1)

定義9流量比率。對于某一給定的興趣包，流量比率ξ定義為：

(2)

基于上述定義，先給出幾個基本的定理。

定理1在RFS算法中，令N代表洪泛數(shù)量NF，T代表最大洪泛生存時間mFTTL,C代表洪泛覆蓋,則C滿足：

(3)

證明：首先考慮一個F-深度為m(m

(4)

考慮到在B-路徑上至多有T個節(jié)點可以觸發(fā)轉(zhuǎn)發(fā)洪泛包的機制來產(chǎn)生上述的N叉樹，這些節(jié)點的F-深度0≤m

(5)

證畢。

在進一步理論分析前，令pi代表某一緩存i的緩存命中概率(Probability of cache-hit)。因此，根據(jù)定理1，在RFS算法中，所有的F-路由器(共C臺)的緩存命中概率分別表示為p1,p2，…，pC。為了簡化分析過程，本節(jié)對所有緩存命中概率pi做出以下假設(shè)。

假設(shè)1假設(shè)網(wǎng)絡(luò)中所有的緩存命中概率相等。

p1=p2=…=pC=phit

(6)

定理2在RFS算法中，令T代表最大洪泛生存時間mFTTL，L代表內(nèi)容提供商的F-深度，則路徑長度比率η滿足：

(7)

證明：對于某一給定興趣包，在RFS算法中，域內(nèi)洪泛的興趣包均沒有命中緩存的概率P為:

P=(1-p1)(1-p2)…(1-pC)=(1-phit)C

(8)

因此，在域內(nèi)洪泛中，至少有一個興趣包命中緩存的概率為1-P。注意到F-路由器的F-深度最大值為T，因此可以算出使用PRS算法匹配數(shù)據(jù)成功的F-深度的期望值EPRS。

EPRS≈LP+T(1-P)=T+(L-Y)P

(9)

因此，根據(jù)定義8，路徑長度比率η為：

(10)

理想情況下，C→∞，則(1-phit)C→0，因此可以得到EPRS和η下限值：

(11)

(12)

證畢。

根據(jù)定理2可以得出結(jié)論：在理想情況下，使用RFS算法獲取數(shù)據(jù)包所需要的跳數(shù)平均最少需要最優(yōu)路徑算法獲取數(shù)據(jù)包所需要的跳數(shù)的T/L。顯然，T越小，η的下限T/L越小，但是在實際情況下，T越小通常也意味著洪泛覆蓋C越小，這樣EPRS和η都很難逼近理論下界。因此，如何最優(yōu)化T值需要結(jié)合式(3)和式(10)進行仿真分析。

假設(shè)2假設(shè)網(wǎng)絡(luò)中所有興趣包大小Mint相等，所有數(shù)據(jù)包大小Mdata相等，且滿足：

Mdata=50Mint

(13)

定理3在RFS算法中，令T代表最大洪泛生存時間mFTTL，L代表內(nèi)容提供商的F-深度，phit代表平均緩存命中概率，C代表洪泛覆蓋，則流量比率ξ滿足以下公式：

(14)

證明：針對某一特定興趣包產(chǎn)生網(wǎng)絡(luò)的總流量，在未使用RFS時，總流量為L·Mdata,使用RFS時，除了產(chǎn)生這部分流量以外，還需要額外產(chǎn)生流量。

T·(1-phit)C·Mdata+C·Mint

(15)

因此，根據(jù)定義9，網(wǎng)絡(luò)的流量比率ξ為:

(16)

整理后即得式(14)。

證畢。

結(jié)合定理2和定理3，可以通過仿真計算找到最優(yōu)化的(T,N)數(shù)據(jù)對，使得η和ξ的值盡可能小。假設(shè)內(nèi)容提供商的F-深度L=8，命中率phit分別為0.1、0.05、0.01。通過計算，得到了若干有意義的(T,N)數(shù)據(jù)對，如表1所示?？梢钥闯?，考慮所有不同的緩存命中率的情況下，當(T,N)=(2,5)時，在得到接近最優(yōu)性能的同時，開銷也控制在相對比較低的水平。從分析可以發(fā)現(xiàn)，緩存命中率phit對性能和開銷的影響均比較大，因此采用什么樣的緩存策略也將較大地影響算法的最終效果。

表1 RFS算法(T,N)數(shù)據(jù)對

1.3 RFS算法觸發(fā)條件

1.3.1觸發(fā)條件

值得注意的是，針對某一興趣包，雖然網(wǎng)絡(luò)總流量增加并不多，但網(wǎng)絡(luò)的轉(zhuǎn)發(fā)壓力陡增。以命中率phit=0.01為例，本節(jié)選擇最優(yōu)的方案(T,N)=(2,5)，盡管此時網(wǎng)絡(luò)的總流量比率ξ=1.263并不是特別高，即在可接受范圍內(nèi)，但是對于某一興趣包，由于RFS算法引發(fā)的網(wǎng)絡(luò)中額外的興趣包數(shù)量(即洪泛覆蓋)為C=35，而不使用RFS算法時網(wǎng)絡(luò)中該興趣包數(shù)量為L=8，因此，網(wǎng)絡(luò)轉(zhuǎn)發(fā)壓力變?yōu)樵瓉淼?37.5%。

顯然，為了提高網(wǎng)絡(luò)性能，額外增加這樣大的網(wǎng)絡(luò)開銷是不能接受的，因此何種情況才能觸發(fā)RFS算法是需要考慮的問題。值得注意的是，由于網(wǎng)絡(luò)協(xié)議限制，網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)包大小有上限(例如4 096 KB)，因此，當用戶請求相對較大的數(shù)據(jù)時，需要發(fā)送多個興趣包才能將全部數(shù)據(jù)取回。這樣，用戶請求較大的數(shù)據(jù)所發(fā)出的興趣包可以分為以下兩種：

1) 新興趣包：當用戶請求某一數(shù)據(jù)時，第一個發(fā)出的興趣包定義為新興趣包。通常來說，新興趣包的名字中的序列編號為0。

2) 后續(xù)興趣包：當用戶請求某一數(shù)據(jù)且已經(jīng)發(fā)出了第一個興趣包，后續(xù)再發(fā)出的請求該數(shù)據(jù)剩余數(shù)據(jù)塊的興趣包定義為后續(xù)興趣包。

由于RFS算法的根本目的是探索網(wǎng)絡(luò)數(shù)據(jù)副本的緩存位置，因此針對某一興趣包，采用RFS算法有效的條件包括以下兩點：

1) 興趣包所請求的數(shù)據(jù)在網(wǎng)絡(luò)非轉(zhuǎn)發(fā)路徑的位置中有可能存在被緩存的副本。

2) 興趣包所請求的數(shù)據(jù)尚未使用過RFS算法進行轉(zhuǎn)發(fā)，否則只需要繼續(xù)沿著上次執(zhí)行RFS算法找到的位置獲取數(shù)據(jù)即可。

由此，得出觸發(fā)RFS算法的兩個必要條件：

1) 興趣包為新興趣包。

2) 所請求的數(shù)據(jù)為分發(fā)數(shù)據(jù)(即不是端到端數(shù)據(jù))。

算法觸發(fā)條件的偽代碼如算法2所示?；谠撚|發(fā)條件的RFS算法稱為修正條件下的RFS算法——RFS*算法。

算法2RFS觸發(fā)算法

RFSTrig(Interestinterest,intf_depth)

//如果不是新興趣包，采用BestRoute

ifinterest.name.seq_number!=0

BestRoute(interest);

Return；

endif

//如果不是分發(fā)數(shù)據(jù)

ifinterest.type==END_TO_END

BestRoute(interest);

Return；

endif

//如果滿足觸發(fā)條件

RFS(interest,f_depth);

1.3.2理論分析

考慮RFS觸發(fā)條件，對理論分析結(jié)果進行一定修正。顯然，修正的結(jié)果并不影響η值，因此僅需要考慮ξ值。

假設(shè)3假設(shè)網(wǎng)絡(luò)中分發(fā)數(shù)據(jù)平均為最大傳輸數(shù)據(jù)塊的K倍。

(17)

根據(jù)定理4，當K=25，取最優(yōu)數(shù)據(jù)對(T,N)=(2,5)時，網(wǎng)絡(luò)參數(shù)如表2所示?？梢钥吹剑谛拚龡l件下，網(wǎng)絡(luò)性能(獲取數(shù)據(jù)的平均跳數(shù))提升明顯的同時，網(wǎng)絡(luò)的額外開銷(網(wǎng)絡(luò)總流量)幾乎控制在可以忽略不計的范圍內(nèi)(1%)。

表2 RFS*算法相應(yīng)的最優(yōu)數(shù)據(jù)對(T,N)

2 仿真實驗

本節(jié)通過仿真軟件ndnSIM來對RFS算法和RFS*算法進行實驗驗證。最新版本的ndnSIM整合了CCN-cxx庫(CCN C++ library with experimental extensions)和CCN轉(zhuǎn)發(fā)進程NFD(CCN Forwarding Daemon)，以確保實驗采用模擬環(huán)境的實際代碼。

2.1 實驗設(shè)置

實驗環(huán)境：運行ndnSIM的計算機的配置包括中央處理器采用英特爾酷睿四核i7-4790處理器，內(nèi)存大小為8 GB。通過修改ndnSIM的底層代碼，使ndnSIM支持RFS算法所需要的所有參數(shù)。

網(wǎng)絡(luò)拓撲：所有仿真實驗中，并未使用復(fù)雜的真實網(wǎng)絡(luò)拓撲，而是采用了15×15的網(wǎng)格拓撲結(jié)構(gòu)。這225個節(jié)點中，四角的節(jié)點(0,0)、(0,14)、(14,0)和(14,14)作為網(wǎng)絡(luò)的內(nèi)容提供商，而其他221各節(jié)點中，隨機設(shè)置30%的節(jié)點作為用戶，70%的節(jié)點作為網(wǎng)絡(luò)路由器。其他網(wǎng)絡(luò)拓撲的參數(shù)均設(shè)為理想狀態(tài)下的參數(shù)，確保網(wǎng)絡(luò)任何環(huán)節(jié)(如轉(zhuǎn)發(fā)能力、帶寬等)均無瓶頸。

參數(shù)設(shè)定：取最優(yōu)數(shù)據(jù)對(T,N)=(2,5)，內(nèi)容提供商的F-深度L=8，緩存命中率phit=0.1，網(wǎng)絡(luò)中分發(fā)數(shù)據(jù)平均大小與最大傳輸數(shù)據(jù)塊的比值K=25。用戶采用發(fā)送興趣包的方法：當用戶發(fā)出一個興趣包后進入等待狀態(tài)，在網(wǎng)絡(luò)返回相應(yīng)的數(shù)據(jù)包之前，用戶不再繼續(xù)發(fā)送興趣包；當網(wǎng)絡(luò)返回相應(yīng)的數(shù)據(jù)包后，用戶立即發(fā)送下一個興趣包。

2.2 實驗結(jié)果

2.2.1性能對比

首先來考察使用最優(yōu)路徑算法和RFS算法(包括RFS*算法)的性能對比。在前面的理論分析中已說明修正條件并不會影響RFS算法的性能，因此本節(jié)并不額外對比RFS*算法的結(jié)果。

定義興趣包滿足數(shù)NSI(Number of Satisfied Interest)代表用戶每秒鐘發(fā)送出去的興趣包數(shù)量。顯然，NSI越高，算法的性能越好。利用NSI可以計算得到實驗條件下的路徑長度比率ηex：

(18)

首先，通過實驗得到不同算法下NSI隨時間變化的曲線，如圖2所示?？梢钥吹剑谑褂肦FS算法后，NSI的值有了明顯的提升，基本穩(wěn)定在1 300左右的范圍內(nèi)；而僅僅使用Best-route算法，NSI值基本在400左右。基于這兩條NSI曲線，得到了路徑長度比率ηex隨時間變化的曲線，如圖3所示。可以看到，ηex基本保持在0.30左右，平均值為0.29，基本與理論值0.269保持吻合。由式(18)可知，1-ηex=1-0.29=0.71表示使用RFS算法帶來的性能平均提升比率。

圖2 興趣包滿足數(shù)NSI對比

圖3 路徑長度比率ηex

實驗結(jié)果表明：在當前實驗條件下，使用RFS算法后網(wǎng)絡(luò)性能平均提升(網(wǎng)絡(luò)時延降低)了71%。

2.2.2開銷對比

本節(jié)考察最優(yōu)路徑算法、RFS算法和RFS*算法三者的開銷對比。通過定義平均單興趣包網(wǎng)絡(luò)流量(Average Traffic per satisfied Interest packet,AT)來代表每一被滿足的興趣包所需占用的網(wǎng)絡(luò)總流量。利用AT可以計算得到實驗條件下的網(wǎng)絡(luò)流量比率ξex：

(19)

首先通過實驗考察三種算法的值隨時間變化的曲線。如圖4所示，使用最優(yōu)路徑算法后平均單興趣包網(wǎng)絡(luò)流量AT在區(qū)間[1.032,1.066]內(nèi)，均值為1.044，均方差為0.009;使用RFS算法后AT在區(qū)間[1.133,1.249]內(nèi)，均值為1.156，均方差為0.029；而使用RFS*算法AT在區(qū)間[0.992,1.141]內(nèi)，均值為1.059，均方差為0.030?？梢姡褂昧薘FS算法和RFS*算法后，由于獲取數(shù)據(jù)位置的不確定性，AT變化相對于最優(yōu)路徑算法的AT變化要大得多。

圖4 平均單興趣包網(wǎng)絡(luò)流量AT對比

基于AT隨時間變化的曲線得到如圖5所示的流量比率ξ隨時間變化的曲線。可以看到，使用RFS算法流量比率ξ在區(qū)間[1.061,1.162]內(nèi)，均值為1.107(理論值為1.094)；而使用RFS*算法流量比率ξ在區(qū)間[0.949,1.070]內(nèi)，均值為1.006(理論值為1.003)。實驗結(jié)果與理論結(jié)果基本吻合。

圖5 流量比率ξ對比

根據(jù)實驗結(jié)果，由圖4中前20秒AT的均值數(shù)據(jù)可以算出使用RFS和RFS*算法帶來的網(wǎng)絡(luò)開銷的增量?？傻靡韵陆Y(jié)論：在當前實驗條件下，使用RFS算法后網(wǎng)絡(luò)開銷(網(wǎng)絡(luò)總流量)平均增加了10.7%；而使用RFS*算法后網(wǎng)絡(luò)開銷(網(wǎng)絡(luò)總流量)平均僅增加了0.6%。

3 結(jié) 語

本文提出了新型的RFS算法，較好地解決了CCN網(wǎng)絡(luò)轉(zhuǎn)發(fā)層節(jié)點緩存副本無法獲取的問題。提出的RFS*算法能夠在幾乎不帶來額外開銷的條件下，大幅提升網(wǎng)絡(luò)性能。結(jié)合理論分析和實驗驗證，證明了RFS*算法對解決目前CCN網(wǎng)絡(luò)轉(zhuǎn)發(fā)層問題的有效性。下一步，將把RFS*算法應(yīng)用于復(fù)雜的CCN網(wǎng)絡(luò)中并對其進行驗證。