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

吳文剛 王慶生

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

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

0 引 言

隨著網(wǎng)絡(luò)日益扁平化和網(wǎng)絡(luò)連接資源的日趨豐富，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也變得愈加復(fù)雜，獲取網(wǎng)絡(luò)資源所需要的網(wǎng)絡(luò)跳數(shù)也愈來愈少[1]。面對(duì)網(wǎng)絡(luò)扁平化的趨勢，TCP/IP網(wǎng)絡(luò)提出了一系列的新型網(wǎng)絡(luò)協(xié)議[2-3]，例如：P2P協(xié)議提供對(duì)等網(wǎng)絡(luò)進(jìn)行去中心化的數(shù)據(jù)傳輸以進(jìn)行直接的共享資源與服務(wù);CDN協(xié)議則通過DNS重定向技術(shù)在網(wǎng)絡(luò)中部署節(jié)點(diǎn)服務(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é)點(diǎn)，以請(qǐng)求該內(nèi)容提供商數(shù)據(jù)的用戶為葉節(jié)點(diǎn)，那么網(wǎng)絡(luò)中所有針對(duì)該內(nèi)容提供商的數(shù)據(jù)請(qǐng)求路徑將構(gòu)成一顆請(qǐng)求樹。顯然，這樣的樹狀數(shù)據(jù)請(qǐng)求結(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ā)的策略上進(jìn)行改變和創(chuàng)新。當(dāng)前的CCN網(wǎng)絡(luò)層中，轉(zhuǎn)發(fā)一個(gè)興趣包時(shí)，主要有兩種轉(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ò)的特性，針對(duì)最優(yōu)路徑算法提出了一系列自適應(yīng)的、有狀態(tài)的轉(zhuǎn)發(fā)策略，使CCN轉(zhuǎn)發(fā)層相比于IP網(wǎng)絡(luò)的轉(zhuǎn)發(fā)層更加智能[6-9]。然而，最優(yōu)路徑算法目前仍然無法支持最近副本路由，這使得對(duì)于熱門數(shù)據(jù)，除非最優(yōu)轉(zhuǎn)發(fā)路徑的緩存中存在相應(yīng)的副本，否則大量的網(wǎng)絡(luò)緩存對(duì)于用戶來說全部是透明的，這極大程度地限制了網(wǎng)絡(luò)的性能[10-11]。

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

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

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

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

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

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

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

1 RFS算法與理論分析

1.1 RFS算法

1.1.1參數(shù)定義

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

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

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

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

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

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

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

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

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

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

//隨機(jī)選擇NF臺(tái)下一跳路由器進(jìn)行洪泛

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標(biāo)簽并進(jìn)行洪泛

f_interest=interest.getCopy();

f_interest.lable=F;

RamdomFlooding(f_interest,NF);

endif

endif

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

初始化：

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

算法開始：

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

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

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

③ 比較當(dāng)前興趣包的FTTL與mFTTL的大小。如果FTTL

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

①FTTL增加1。

② 比較當(dāng)前興趣包的FTTL與mFTTL的大小。如果FTTL

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

1.2 理論分析

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

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

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

證畢。

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

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

p1=p2=…=pC=phit

(6)

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

(7)

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

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

(8)

因此，在域內(nèi)洪泛中，至少有一個(gè)興趣包命中緩存的概率為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越小，但是在實(shí)際情況下，T越小通常也意味著洪泛覆蓋C越小，這樣EPRS和η都很難逼近理論下界。因此，如何最優(yōu)化T值需要結(jié)合式(3)和式(10)進(jìn)行仿真分析。

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

Mdata=50Mint

(13)

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

(14)

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

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

(15)

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

(16)

整理后即得式(14)。

證畢。

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

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

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

1.3.1觸發(fā)條件

值得注意的是，針對(duì)某一興趣包，雖然網(wǎng)絡(luò)總流量增加并不多，但網(wǎng)絡(luò)的轉(zhuǎn)發(fā)壓力陡增。以命中率phit=0.01為例，本節(jié)選擇最優(yōu)的方案(T,N)=(2,5)，盡管此時(shí)網(wǎng)絡(luò)的總流量比率ξ=1.263并不是特別高，即在可接受范圍內(nèi)，但是對(duì)于某一興趣包，由于RFS算法引發(fā)的網(wǎng)絡(luò)中額外的興趣包數(shù)量(即洪泛覆蓋)為C=35，而不使用RFS算法時(shí)網(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)，因此，當(dāng)用戶請(qǐng)求相對(duì)較大的數(shù)據(jù)時(shí)，需要發(fā)送多個(gè)興趣包才能將全部數(shù)據(jù)取回。這樣，用戶請(qǐng)求較大的數(shù)據(jù)所發(fā)出的興趣包可以分為以下兩種：

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

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

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

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

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

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

1) 興趣包為新興趣包。

2) 所請(qǐng)求的數(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ā)條件，對(duì)理論分析結(jié)果進(jìn)行一定修正。顯然，修正的結(jié)果并不影響η值，因此僅需要考慮ξ值。

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

(17)

根據(jù)定理4，當(dāng)K=25，取最優(yōu)數(shù)據(jù)對(duì)(T,N)=(2,5)時(shí)，網(wǎng)絡(luò)參數(shù)如表2所示。可以看到，在修正條件下，網(wǎng)絡(luò)性能(獲取數(shù)據(jù)的平均跳數(shù))提升明顯的同時(shí)，網(wǎng)絡(luò)的額外開銷(網(wǎng)絡(luò)總流量)幾乎控制在可以忽略不計(jì)的范圍內(nèi)(1%)。

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

2 仿真實(shí)驗(yàn)

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

2.1 實(shí)驗(yàn)設(shè)置

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

網(wǎng)絡(luò)拓?fù)洌核蟹抡鎸?shí)驗(yàn)中，并未使用復(fù)雜的真實(shí)網(wǎng)絡(luò)拓?fù)洌遣捎昧?5×15的網(wǎng)格拓?fù)浣Y(jié)構(gòu)。這225個(gè)節(jié)點(diǎn)中，四角的節(jié)點(diǎn)(0,0)、(0,14)、(14,0)和(14,14)作為網(wǎng)絡(luò)的內(nèi)容提供商，而其他221各節(jié)點(diǎn)中，隨機(jī)設(shè)置30%的節(jié)點(diǎn)作為用戶，70%的節(jié)點(diǎn)作為網(wǎng)絡(luò)路由器。其他網(wǎng)絡(luò)拓?fù)涞膮?shù)均設(shè)為理想狀態(tài)下的參數(shù)，確保網(wǎng)絡(luò)任何環(huán)節(jié)(如轉(zhuǎn)發(fā)能力、帶寬等)均無瓶頸。

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

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

2.2.1性能對(duì)比

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

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

(18)

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

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

圖3 路徑長度比率ηex

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

2.2.2開銷對(duì)比

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

(19)

首先通過實(shí)驗(yàn)考察三種算法的值隨時(shí)間變化的曲線。如圖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。可見，使用了RFS算法和RFS*算法后，由于獲取數(shù)據(jù)位置的不確定性，AT變化相對(duì)于最優(yōu)路徑算法的AT變化要大得多。

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

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

圖5 流量比率ξ對(duì)比

根據(jù)實(shí)驗(yàn)結(jié)果，由圖4中前20秒AT的均值數(shù)據(jù)可以算出使用RFS和RFS*算法帶來的網(wǎng)絡(luò)開銷的增量。可得以下結(jié)論：在當(dāng)前實(shí)驗(yàn)條件下，使用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é)點(diǎn)緩存副本無法獲取的問題。提出的RFS*算法能夠在幾乎不帶來額外開銷的條件下，大幅提升網(wǎng)絡(luò)性能。結(jié)合理論分析和實(shí)驗(yàn)驗(yàn)證，證明了RFS*算法對(duì)解決目前CCN網(wǎng)絡(luò)轉(zhuǎn)發(fā)層問題的有效性。下一步，將把RFS*算法應(yīng)用于復(fù)雜的CCN網(wǎng)絡(luò)中并對(duì)其進(jìn)行驗(yàn)證。