受限洪泛策略的內容中心網絡路由算法

吳文剛 王慶生

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

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

0 引 言

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

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

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

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

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

1) 降低復雜性。洪泛算法可以極大地降低協議復雜性并簡化協議設計。特別地，文獻[11]中指出，洪泛算法在某些不穩定的網絡環境中最適用。

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

3) 減小路由狀態。相對于最優路徑算法，洪泛算法在基于路由的內容發現機制方面，所需要維護的網絡狀態相對比較少。

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

本文針對CCN網絡轉發層存在的問題，結合洪泛算法和最優路徑算法，通過控制洪泛區域降低開銷的方法，提出了新型的RFS算法來解決網絡無法獲取鄰居節點緩存副本的問題。提出的RFS*算法在開銷幾乎不變的條件下，大幅降低分發數據獲取的網絡時延。

1 RFS算法與理論分析

1.1 RFS算法

1.1.1參數定義

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

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

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

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

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

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

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

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

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

如圖1所示，對于某一興趣包釆用域內洪泛算法，并定義mFTTL=3、NF=1。可以看到，圖中共有1條B-路徑、3條F-路徑、3臺B-路由器和5臺F-路由器。

圖1 RFS相關定義示意圖

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-路徑轉發

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。

② 根據路由表，沿B-路徑轉發該興趣包。

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

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

①FTTL增加1。

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

算法結束：用戶收到興趣包對應的數據包。

1.2 理論分析

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

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

顯然，洪泛覆蓋代表使用RFS算法產生的額外開銷，即網絡額外產生的興趣包數量。

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

證畢。

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

假設1假設網絡中所有的緩存命中概率相等。

p1=p2=…=pC=phit

(6)

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

(7)

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

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

(8)

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

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

(9)

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

(10)

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

(11)

(12)

證畢。

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

假設2假設網絡中所有興趣包大小Mint相等，所有數據包大小Mdata相等，且滿足：

Mdata=50Mint

(13)

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

(14)

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

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

(15)

因此，根據定義9，網絡的流量比率ξ為:

(16)

整理后即得式(14)。

證畢。

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

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

1.3 RFS算法觸發條件

1.3.1觸發條件

值得注意的是，針對某一興趣包，雖然網絡總流量增加并不多，但網絡的轉發壓力陡增。以命中率phit=0.01為例，本節選擇最優的方案(T,N)=(2,5)，盡管此時網絡的總流量比率ξ=1.263并不是特別高，即在可接受范圍內，但是對于某一興趣包，由于RFS算法引發的網絡中額外的興趣包數量(即洪泛覆蓋)為C=35，而不使用RFS算法時網絡中該興趣包數量為L=8，因此，網絡轉發壓力變為原來的437.5%。

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

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

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

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

1) 興趣包所請求的數據在網絡非轉發路徑的位置中有可能存在被緩存的副本。

2) 興趣包所請求的數據尚未使用過RFS算法進行轉發，否則只需要繼續沿著上次執行RFS算法找到的位置獲取數據即可。

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

1) 興趣包為新興趣包。

2) 所請求的數據為分發數據(即不是端到端數據)。

算法觸發條件的偽代碼如算法2所示。基于該觸發條件的RFS算法稱為修正條件下的RFS算法——RFS*算法。

算法2RFS觸發算法

RFSTrig(Interestinterest,intf_depth)

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

ifinterest.name.seq_number!=0

BestRoute(interest);

Return；

endif

//如果不是分發數據

ifinterest.type==END_TO_END

BestRoute(interest);

Return；

endif

//如果滿足觸發條件

RFS(interest,f_depth);

1.3.2理論分析

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

假設3假設網絡中分發數據平均為最大傳輸數據塊的K倍。

(17)

根據定理4，當K=25，取最優數據對(T,N)=(2,5)時，網絡參數如表2所示。可以看到，在修正條件下，網絡性能(獲取數據的平均跳數)提升明顯的同時，網絡的額外開銷(網絡總流量)幾乎控制在可以忽略不計的范圍內(1%)。

表2 RFS*算法相應的最優數據對(T,N)

2 仿真實驗

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

2.1 實驗設置

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

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

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

2.2 實驗結果

2.2.1性能對比

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

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

(18)

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

圖2 興趣包滿足數NSI對比

圖3 路徑長度比率ηex

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

2.2.2開銷對比

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

(19)

首先通過實驗考察三種算法的值隨時間變化的曲線。如圖4所示，使用最優路徑算法后平均單興趣包網絡流量AT在區間[1.032,1.066]內，均值為1.044，均方差為0.009;使用RFS算法后AT在區間[1.133,1.249]內，均值為1.156，均方差為0.029；而使用RFS*算法AT在區間[0.992,1.141]內，均值為1.059，均方差為0.030。可見，使用了RFS算法和RFS*算法后，由于獲取數據位置的不確定性，AT變化相對于最優路徑算法的AT變化要大得多。

圖4 平均單興趣包網絡流量AT對比

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

圖5 流量比率ξ對比

根據實驗結果，由圖4中前20秒AT的均值數據可以算出使用RFS和RFS*算法帶來的網絡開銷的增量。可得以下結論：在當前實驗條件下，使用RFS算法后網絡開銷(網絡總流量)平均增加了10.7%；而使用RFS*算法后網絡開銷(網絡總流量)平均僅增加了0.6%。

3 結 語

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