內容中心網絡中基于可用帶寬的多接口路由策略

黃 勝，張宏宇，吳 震，滕明埝，鄭丹玲

（重慶郵電大學 光纖通信技術重點實驗室，重慶400065）

0 引 言

CCN［1］中基本的路由機制是洪泛路由［2］（flooding routing，FR）和最優路由［3］（best routing，BR）。基于蟻群優化［4］（ant colony optimization，ACO）的分布式路由策略和貪婪路由算法［5］是基于BR 提出的，容易導致網絡中鏈路帶寬資源的浪費并加重最優路徑和相應服務器的負載。CCN本身具有多路徑路由的特點，文獻［6］提出實現CCN多路徑傳輸的擁塞控制機制，基于窗口的興趣包控制機制［7，8］來調控接收端請求包的速率，減少鏈路中的擁塞的發生。為了減少數據冗余［9］，根據不同參數提出基于層次分析法［10］的CCN 多路徑興趣包路由機制。基于興趣包窗口的擁塞控制機制僅通過反饋的擁塞信息調節請求速率，不能及時減緩擁塞的發生，因此，本文提出一種MRSAB 算法。該算法依據鏈路帶寬占用情況及時選擇鏈路轉發興趣包，減少網絡中鏈路擁塞的發生。

1 CCN 的基本描述

1.1 CCN 的基本模型

CCN 采用七層結構，保持了TCP／IP 體系結構的沙漏模型［2］，在中間層采用命名數據取代IP。CCN 是一個由接收者驅動的通信模型，在CCN 的通信過程中存在兩種類型的包：興趣包和數據包，請求者發送的興趣包由名字唯一的標識，興趣包通過CCN 的節點轉發給能夠提供請求內容的鄰近節點，與之相匹配的數據包沿著興趣包的反向路徑傳送給請求者，完成信息的傳輸過程。CCN 節點主要包括3部分：內容存儲庫 （content store，CS），未決請求表（pending interest table，PIT）和 轉 發 信 息 庫 （forwarding information base，FIB）。CS通常采用LRU 或LFU 替換策略存儲數據包，PIT 被用來記錄未被滿足興趣包的進入接口，以便請求的內容順利地傳回請求節點，FIB 的處理機制類似于TCP／IP結構中的路由轉發表，但FIB 支持向多個接口轉發請求。

在CCN 轉發模型中，請求者發出興趣包請求相匹配的數據，包的轉發過程如圖1 所示。當興趣包到達節點時，節點根據該興趣包中包含的內容名依次在CS，PIT，FIB中利用最長前綴匹配進行查找。首先查找CS，如果CS中包含該興趣包匹配的數據包，節點將數據包按照請求接口發送到請求者；如果CS中未存儲匹配的數據，則在PIT 中繼續查找，如果PIT 中包含該興趣包的內容條目，則將請求接口添加到PIT 的請求接口列表中，否則將在FIB 中繼續查找；如果FIB 中包含與該興趣包內容名相關的條目，則按照FIB中記錄的信息將興趣包轉發到下一跳節點，同時將請求信息添加到PIT 條目中。如果以上3種情況都不符合，說明不存在相關的匹配路由，則丟棄該興趣包。

圖1 CCN 中包的轉發過程

當節點收到返回的數據包時，節點根據數據包中包含的內容名查找PIT 條目，將該數據通過與內容名相匹配的接口轉發，CCN 節點采用緩存策略將數據包存儲到CS中，同時刪除相應的PIT 條目。如果查找不到相應的PIT 條目則丟棄該數據。

1.2 兩種對比路由算法介紹

本文的對比算法采用CCN 中常用的兩種路由機制，FR 將興趣包轉發到節點的各個接口請求相應數據，即將節點上興趣包的副本以廣播的形式轉發到下一跳節點，興趣包通過洪泛方式請求數據會提高緩存命中率，但是每個興趣包僅返回一個數據包，這樣將造成網絡資源浪費，增加路由開銷。BR 從FIB的多個接口中選擇一個能獲得相匹配數據的最優接口，使得該接口到服務器的性能最好 （如跳數最少或整體負載最低等），然后將節點上到達的興趣包通過該條最優路徑進行轉發。由于BR 將大部分興趣包通過一條路徑轉發，過多的興趣包請求將造成該鏈路擁塞的發生，而且會造成鏈路負載不均衡問題。

FR 和BR 的路由轉發過程如圖2所示。圖中虛線表示興趣包請求的最優路徑，最優路徑根據該路由算法中選取的參數確定。洪泛將請求者發出的興趣包按照圖中黑色箭頭向下游節點進行轉發。由于CCN 網絡中過多的興趣包請求會導致網絡中鏈路擁塞的發生，FR 和BR 路由算法不能有效地減少鏈路擁塞的發生，從而增加請求數據的時延，BR 路由算法也造成網絡中鏈路負載不均衡問題。為了將興趣包通過合理的接口轉發，本文在BR 算法的基礎上提出了MRSAB算法。

圖2 FR 和BR 轉發過程

2 MRSAB算法

目前大部分的設備都具有多路徑傳輸的能力，研究結果表明TCP／IP網絡中多路徑路由可以獲得負載均衡，減少擁塞，低功率消耗和較高吞吐量等好的性能。CCN 本身具有支持多路徑傳輸的能力，因此，CCN 的多路徑路由采取一定的路由機制合理地分配興趣包到多條路徑上請求數據，可以充分利用網絡帶寬資源，并且使CCN 網絡獲得較好的性能。

2.1 三顏色標識機制

CCN 中的FIB不同于IP中的FIB，IP的FIB中通常僅記錄最優下一跳信息，NDN 的FIB 中包含排列的多個接口，用來記錄路由過程的信息并且提供一定的路由轉發策略，CCN 中FIB包含的信息如圖3所示。CCN 中的FIB條目為每個接口記錄一個檢索數據的狀態，本文使用三顏色機制［11］來標識各個接口的狀態：綠色表示接口處于可用狀態；黃色表示接口處于可用或不可用狀態；紅色表示接口處于不可用狀態。當節點創建一個新的FIB 條目時，該條目對應接口的狀態被標記為黃色，當有相應的數據包從該接口返回時則標記該接口狀態為綠色，當該接口的待發興趣包超時或者一段時間后未被使用，其狀態被標記成黃色，如果一個接口失效或從上游接收到NACK 則該接口狀態被標記為紅色。

圖3 CCN 中的FIB信息

2.2 數學模型描述

在CCN 網絡鏈路上，數據包占用大部分的鏈路帶寬，興趣包占用的帶寬可以忽略不計，因此本文利用數據包個數反映鏈路帶寬占用情況，節點上到達的興趣包根據預測的鏈路帶寬占用情況選擇接口進行轉發。

在一個短時間段Δt內鏈路上轉發的數據包個數變化很小，因此可以利用時間t前面時間段內數據包個數的測量值來預t～t＋Δt內數據包個數的估計值，根據該估計值評估t～t＋Δt內每條可用接口鏈路帶寬占用情況。EWMA［12］數學模型根據實際的測量值cij（t）預測下一個時刻的估計值EWMA（t＋Δt），λ表示對測量值的權重系數，其公式如式 （1）所示

由于EWMA 模型對估計值進行預測的精確度不高，為了提高預測精確度將其變形為WMA 數學模型來預測t～t＋Δt內數據包的個數，WMA 模型根據不同時間段內測量值對估計值的影響程度給予不同的權值。由于每個匹配興趣包的數據包大小相同，且占用帶寬相同，因此一個時間段內數據包的個數可以反映鏈路帶寬占用情況。利用WMA 模型預測t～t＋Δt時間段內數據包個數的估計值，需要利用t－Δt～t、t－2Δt～t－Δt、t－3Δt～t－2Δt這3個時間段內數據包個數的測量值對其進行預測。例如預測t～t＋Δt內數據包個數Bt＋1，則需要記錄之前3個時間段內對應數據包個數的測量值Bt、Bt－1、Bt－2，每個時間段之間的間隔為Δt＜＜T（T 表示仿真時間）。WMA 模型預測Bt＋1的公式如式 （2）所示

其中，參數α、β、γ 分別對應t－Δt～t、t－2Δt～t－Δt、t－3Δt～t－2Δt這3個時間段內數據包個數測量值的權值，α＋β＋γ＝1。在該模型中，越是接近需要預測的時間段，測量值對估計值的影響越大，即Bt對Bt＋1的預測影響最大，因此α的設置應該明顯大于其它兩個參數 （本文α取0.7，β取0.2，γ取0.1）。

2.3 MRSAB具體描述

MRSAB首先通過三顏色路由機制為節點判斷可用接口，然后為可用接口對應鏈路預測t～t＋Δt內的估計值Bt＋1，從而判斷每個接口對應鏈路的帶寬占用情況，最后對可用接口對應鏈路的可用帶寬進行比較排序，選取可用帶寬大的接口進行興趣包的轉發。文中MRSAB 算法具體步驟如下：

步驟1 設網絡拓撲中每條鏈路的負載容量為Rij，Bij表示一條鏈路上當前時刻帶寬占用情況。

步驟2 節點收到興趣包后按照CCN 的基本轉發過程查找，需要在FIB中查找下一跳節點時根據該興趣包名進行最長前綴匹配查找，找出節點上標記為綠色的可用狀態接口。

步驟3 判斷可用狀態接口對應鏈路上占用帶寬是否超過該鏈路的負載容量Rij，如果所有可用鏈路上帶寬占用都超過總的負載容量，即都處于鏈路擁塞狀態則執行步驟4，否則執行步驟5。

步驟4 丟棄該興趣包，在一定程度上減少網絡拓撲中興趣包的數量，并標記該接口為黃色。

步驟5 利用WMA 模型預測可用鏈路上數據包的估計值，從而計算鏈路上帶寬占用情況。

步驟6 比較可用鏈路中數據包的估計值，選擇兩條可用帶寬較大的鏈路，使用可用帶寬最大的鏈路轉發興趣包，另一條作為備選鏈路從而保證數據請求的可靠性。

本文提出的MRSAB 算法根據鏈路帶寬占用情況選擇轉發接口，這樣可以充分利用網絡中帶寬資源，通過一定的鏈路限制減少該機制中鏈路擁塞的發生，減少請求數據的時延。三顏色機制標識可用接口使興趣包向具有匹配數據的鏈路轉發，增加緩存的命中率，減少服務器的負載，該機制最大的優點是多接口路由的引入使CCN 網絡中鏈路到達更好的負載均衡。

3 仿真分析

本文在Linux環境下采用基于NS3 的ndnSim 仿真平臺。本文的數據請求服從Zipf分布，仿真結果與CCN 中常用的FR 和BR 進行比較。本實驗采用LCE 緩存策略和LRU 替換策略，仿真時間200s。

3.1 緩存命中率

MRSAB與FR 和BR 在緩存命中率的比較如圖4所示。由圖可知隨著參數α的增加，緩存命中率逐漸增加，因為α越大緩存中存儲的內容越集中，緩存命中的概率越大。相對于FR 和BR，MRSAB 在α＞0.6 時緩存命中率相對較高，FR 的緩存命中率越來越低是因為緩存中存儲的內容越來越集中，通過廣播興趣包副本請求數據使網絡中興趣包增多，而每個興趣包僅返回一個數據包。MRSAB 在α＜0.6時緩存命中率低于FR 是因為緩存中存儲的內容不太集中，FR 通過多條路徑請求數據能夠提高命中數據的可能性。

圖4 緩存命率的比較

3.2 平均時延

MRSAB與FR 和BR 在平均時延上的比較如圖5所示。由圖可知MRSAB的平均時延相對較低，隨著參數α的增加平均時延越來越低，因為α越大，對存儲比較集中的內容請求所需要的時延較小。

圖5 平均時延的比較

3.3 負載均衡

本文選取一個度數最大且具有3個輸入數據接口和一個輸出數據接口的節點進行負載均衡的測量，MRSAB 與FR 和BR 負載均衡的比較如圖6所示。由圖可知MRSAB的負載均衡明顯優于FR 和BR。圖中BR 的負載均衡最差是因為該機制僅選取一個最優路徑進行興趣包的轉發，這樣容易造成該鏈路負載過大，從而使網絡中整體的負載均衡較差。FR的負載均衡不穩定是因為向一個節點的所有接口轉發興趣包的副本，而并非所有接口都是可用狀態，所以其負載均衡隨著路徑上興趣包請求速率的增加有較大的波動。度數為n的節點負載均衡度Ln的計算公式如式（3）所示

式中：L——一個節點上返回數據包接口的個數，αk——L個接口對應每條鏈路上帶寬占用情況。

圖6 負載均衡的比較

3.4 服務器負載

3種路由機制服務器負載 （服務器中數據包請求次數）的比較如圖7所示。由圖可知MRSAB的服務器負載低于其它兩種路由機制，FR 向節點的各個接口轉發興趣包，當相應鏈路的中間節點沒有相匹配的數據時，興趣包被轉發到服務器進行數據包的請求，因此使服務器的負載明顯增加。

圖7 服務器負載的比較

4 結束語

針對CCN路由過程中鏈路擁塞和負載不均衡等問題，本文提出了一種MRSAB算法，該算法在WMA數學模型下利用t－Δt～t、t－2Δt～t－Δt、t－3Δt～t－2Δt內數據包個數的測量值預測t～t＋Δt內數據包個數的估計值，從而評估鏈路帶寬的占用情況，通過比較節點可用鏈路帶寬占用情況選擇t～t＋Δt內興趣包的轉發接口。仿真結果表明，本文提出算法充分利用網絡中的帶寬資源，在α＞0.6的條件下提高緩存命中率，在整個α的變化范圍內減少平均請求時延，該算法最明顯的優點是提高鏈路的負載均衡，減少服務器的負載。

［1］Jacobson V，Smetters DK，Thornton JD，et al.Networking named content［C］／／Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies.ACM，2009：1－12.

［2］Zhang L，Estrin D，Burke J，et al.Named data networking（ndn）project［R］.Relatório Técnico NDN－0001，Xerox Palo Alto Research Center－PARC，2010：1－24.

［3］Detti A，Blefari－Melazzi N.Network layer solutions for a content－centric internet ［M］／／Trustworthy Internet.Springer Milan，2011：359－369.

［4］Shanbhag S，Schwan N，Rimac I，et al.SoCCeR：Services over content－centric routing ［C］／／Proceedings of the ACM SIGCOMM Workshop on Information－Centric Networking.ACM，2011：62－67.

［5］Wang L，Waltari O，Kangasharju J.MobiCCN Mobility support with greedy routing in content－centric networks ［C］／／GLOBECOM IEEE Global Communications Conference：NGNNext Generation Network，2013.

［6］Carofiglio G，Gallo M，Muscariello L，et al.Multipath congestion control in content－centric networks ［J］.IEEE NOMEN，2013，13：1－6.

［7］Carofiglio G，Gallo M， Muscariello L.ICP：Design and evaluation of an interest control protocol for content－centric networking ［C］／／IEEE Conference on Computer Communications Workshops.IEEE，2012：304－309.

［8］Fu T，Li Y，Lin T，et al.An effective congestion control scheme in content－centric networking ［C］／／13th International Conference on Parallel and Distributed Computing，Applications and Technologies.IEEE，2012：245－248.

［9］Rossini G，Rossi D.Evaluating CCN multi－path interest forwarding strategies［J］.Computer Communications，2013，36（7）：771－778.

［10］Zhang Y，Liu J，Huang T，et al.Multi－path interests routing scheme for multi－path data transfer in content centric networking ［C］／／National Doctoral Academic Forum on Information and Communications Technology，2013：1－6.

［11］Yi C，Afanasyev A，Wang L，et al.Adaptive forwarding in named data networking ［J］.ACM SIGCOMM Computer Communication Review，2012，42 （3）：62－67.

［12］Qian H，Ravindran R，Wang GQ，et al.Probability－based adaptive forwarding strategy in named data networking ［C］／／IFIP／IEEE International Symposium on Integrated Network Management.IEEE，2013：1094－1101.