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

（重慶郵電大學(xué) 光纖通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶400065）

0 引 言

CCN［1］中基本的路由機(jī)制是洪泛路由［2］（flooding routing，F(xiàn)R）和最優(yōu)路由［3］（best routing，BR）?；谙伻簝?yōu)化［4］（ant colony optimization，ACO）的分布式路由策略和貪婪路由算法［5］是基于BR 提出的，容易導(dǎo)致網(wǎng)絡(luò)中鏈路帶寬資源的浪費(fèi)并加重最優(yōu)路徑和相應(yīng)服務(wù)器的負(fù)載。CCN本身具有多路徑路由的特點(diǎn)，文獻(xiàn)［6］提出實(shí)現(xiàn)CCN多路徑傳輸?shù)膿砣刂茩C(jī)制，基于窗口的興趣包控制機(jī)制［7，8］來(lái)調(diào)控接收端請(qǐng)求包的速率，減少鏈路中的擁塞的發(fā)生。為了減少數(shù)據(jù)冗余［9］，根據(jù)不同參數(shù)提出基于層次分析法［10］的CCN 多路徑興趣包路由機(jī)制?；谂d趣包窗口的擁塞控制機(jī)制僅通過(guò)反饋的擁塞信息調(diào)節(jié)請(qǐng)求速率，不能及時(shí)減緩擁塞的發(fā)生，因此，本文提出一種MRSAB 算法。該算法依據(jù)鏈路帶寬占用情況及時(shí)選擇鏈路轉(zhuǎn)發(fā)興趣包，減少網(wǎng)絡(luò)中鏈路擁塞的發(fā)生。

1 CCN 的基本描述

1.1 CCN 的基本模型

CCN 采用七層結(jié)構(gòu)，保持了TCP／IP 體系結(jié)構(gòu)的沙漏模型［2］，在中間層采用命名數(shù)據(jù)取代IP。CCN 是一個(gè)由接收者驅(qū)動(dòng)的通信模型，在CCN 的通信過(guò)程中存在兩種類型的包：興趣包和數(shù)據(jù)包，請(qǐng)求者發(fā)送的興趣包由名字唯一的標(biāo)識(shí)，興趣包通過(guò)CCN 的節(jié)點(diǎn)轉(zhuǎn)發(fā)給能夠提供請(qǐng)求內(nèi)容的鄰近節(jié)點(diǎn)，與之相匹配的數(shù)據(jù)包沿著興趣包的反向路徑傳送給請(qǐng)求者，完成信息的傳輸過(guò)程。CCN 節(jié)點(diǎn)主要包括3部分：內(nèi)容存儲(chǔ)庫(kù) （content store，CS），未決請(qǐng)求表（pending interest table，PIT）和 轉(zhuǎn) 發(fā) 信 息 庫(kù) （forwarding information base，F(xiàn)IB）。CS通常采用LRU 或LFU 替換策略存儲(chǔ)數(shù)據(jù)包，PIT 被用來(lái)記錄未被滿足興趣包的進(jìn)入接口，以便請(qǐng)求的內(nèi)容順利地傳回請(qǐng)求節(jié)點(diǎn)，F(xiàn)IB 的處理機(jī)制類似于TCP／IP結(jié)構(gòu)中的路由轉(zhuǎn)發(fā)表，但FIB 支持向多個(gè)接口轉(zhuǎn)發(fā)請(qǐng)求。

在CCN 轉(zhuǎn)發(fā)模型中，請(qǐng)求者發(fā)出興趣包請(qǐng)求相匹配的數(shù)據(jù)，包的轉(zhuǎn)發(fā)過(guò)程如圖1 所示。當(dāng)興趣包到達(dá)節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)根據(jù)該興趣包中包含的內(nèi)容名依次在CS，PIT，F(xiàn)IB中利用最長(zhǎng)前綴匹配進(jìn)行查找。首先查找CS，如果CS中包含該興趣包匹配的數(shù)據(jù)包，節(jié)點(diǎn)將數(shù)據(jù)包按照請(qǐng)求接口發(fā)送到請(qǐng)求者；如果CS中未存儲(chǔ)匹配的數(shù)據(jù)，則在PIT 中繼續(xù)查找，如果PIT 中包含該興趣包的內(nèi)容條目，則將請(qǐng)求接口添加到PIT 的請(qǐng)求接口列表中，否則將在FIB 中繼續(xù)查找；如果FIB 中包含與該興趣包內(nèi)容名相關(guān)的條目，則按照FIB中記錄的信息將興趣包轉(zhuǎn)發(fā)到下一跳節(jié)點(diǎn)，同時(shí)將請(qǐng)求信息添加到PIT 條目中。如果以上3種情況都不符合，說(shuō)明不存在相關(guān)的匹配路由，則丟棄該興趣包。

圖1 CCN 中包的轉(zhuǎn)發(fā)過(guò)程

當(dāng)節(jié)點(diǎn)收到返回的數(shù)據(jù)包時(shí)，節(jié)點(diǎn)根據(jù)數(shù)據(jù)包中包含的內(nèi)容名查找PIT 條目，將該數(shù)據(jù)通過(guò)與內(nèi)容名相匹配的接口轉(zhuǎn)發(fā)，CCN 節(jié)點(diǎn)采用緩存策略將數(shù)據(jù)包存儲(chǔ)到CS中，同時(shí)刪除相應(yīng)的PIT 條目。如果查找不到相應(yīng)的PIT 條目則丟棄該數(shù)據(jù)。

1.2 兩種對(duì)比路由算法介紹

本文的對(duì)比算法采用CCN 中常用的兩種路由機(jī)制，F(xiàn)R 將興趣包轉(zhuǎn)發(fā)到節(jié)點(diǎn)的各個(gè)接口請(qǐng)求相應(yīng)數(shù)據(jù)，即將節(jié)點(diǎn)上興趣包的副本以廣播的形式轉(zhuǎn)發(fā)到下一跳節(jié)點(diǎn)，興趣包通過(guò)洪泛方式請(qǐng)求數(shù)據(jù)會(huì)提高緩存命中率，但是每個(gè)興趣包僅返回一個(gè)數(shù)據(jù)包，這樣將造成網(wǎng)絡(luò)資源浪費(fèi)，增加路由開銷。BR 從FIB的多個(gè)接口中選擇一個(gè)能獲得相匹配數(shù)據(jù)的最優(yōu)接口，使得該接口到服務(wù)器的性能最好 （如跳數(shù)最少或整體負(fù)載最低等），然后將節(jié)點(diǎn)上到達(dá)的興趣包通過(guò)該條最優(yōu)路徑進(jìn)行轉(zhuǎn)發(fā)。由于BR 將大部分興趣包通過(guò)一條路徑轉(zhuǎn)發(fā)，過(guò)多的興趣包請(qǐng)求將造成該鏈路擁塞的發(fā)生，而且會(huì)造成鏈路負(fù)載不均衡問(wèn)題。

FR 和BR 的路由轉(zhuǎn)發(fā)過(guò)程如圖2所示。圖中虛線表示興趣包請(qǐng)求的最優(yōu)路徑，最優(yōu)路徑根據(jù)該路由算法中選取的參數(shù)確定。洪泛將請(qǐng)求者發(fā)出的興趣包按照?qǐng)D中黑色箭頭向下游節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。由于CCN 網(wǎng)絡(luò)中過(guò)多的興趣包請(qǐng)求會(huì)導(dǎo)致網(wǎng)絡(luò)中鏈路擁塞的發(fā)生，F(xiàn)R 和BR 路由算法不能有效地減少鏈路擁塞的發(fā)生，從而增加請(qǐng)求數(shù)據(jù)的時(shí)延，BR 路由算法也造成網(wǎng)絡(luò)中鏈路負(fù)載不均衡問(wèn)題。為了將興趣包通過(guò)合理的接口轉(zhuǎn)發(fā)，本文在BR 算法的基礎(chǔ)上提出了MRSAB算法。

圖2 FR 和BR 轉(zhuǎn)發(fā)過(guò)程

2 MRSAB算法

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

2.1 三顏色標(biāo)識(shí)機(jī)制

CCN 中的FIB不同于IP中的FIB，IP的FIB中通常僅記錄最優(yōu)下一跳信息，NDN 的FIB 中包含排列的多個(gè)接口，用來(lái)記錄路由過(guò)程的信息并且提供一定的路由轉(zhuǎn)發(fā)策略，CCN 中FIB包含的信息如圖3所示。CCN 中的FIB條目為每個(gè)接口記錄一個(gè)檢索數(shù)據(jù)的狀態(tài)，本文使用三顏色機(jī)制［11］來(lái)標(biāo)識(shí)各個(gè)接口的狀態(tài)：綠色表示接口處于可用狀態(tài)；黃色表示接口處于可用或不可用狀態(tài)；紅色表示接口處于不可用狀態(tài)。當(dāng)節(jié)點(diǎn)創(chuàng)建一個(gè)新的FIB 條目時(shí)，該條目對(duì)應(yīng)接口的狀態(tài)被標(biāo)記為黃色，當(dāng)有相應(yīng)的數(shù)據(jù)包從該接口返回時(shí)則標(biāo)記該接口狀態(tài)為綠色，當(dāng)該接口的待發(fā)興趣包超時(shí)或者一段時(shí)間后未被使用，其狀態(tài)被標(biāo)記成黃色，如果一個(gè)接口失效或從上游接收到NACK 則該接口狀態(tài)被標(biāo)記為紅色。

圖3 CCN 中的FIB信息

2.2 數(shù)學(xué)模型描述

在CCN 網(wǎng)絡(luò)鏈路上，數(shù)據(jù)包占用大部分的鏈路帶寬，興趣包占用的帶寬可以忽略不計(jì)，因此本文利用數(shù)據(jù)包個(gè)數(shù)反映鏈路帶寬占用情況，節(jié)點(diǎn)上到達(dá)的興趣包根據(jù)預(yù)測(cè)的鏈路帶寬占用情況選擇接口進(jìn)行轉(zhuǎn)發(fā)。

在一個(gè)短時(shí)間段Δt內(nèi)鏈路上轉(zhuǎn)發(fā)的數(shù)據(jù)包個(gè)數(shù)變化很小，因此可以利用時(shí)間t前面時(shí)間段內(nèi)數(shù)據(jù)包個(gè)數(shù)的測(cè)量值來(lái)預(yù)t～t＋Δt內(nèi)數(shù)據(jù)包個(gè)數(shù)的估計(jì)值，根據(jù)該估計(jì)值評(píng)估t～t＋Δt內(nèi)每條可用接口鏈路帶寬占用情況。EWMA［12］數(shù)學(xué)模型根據(jù)實(shí)際的測(cè)量值cij（t）預(yù)測(cè)下一個(gè)時(shí)刻的估計(jì)值EWMA（t＋Δt），λ表示對(duì)測(cè)量值的權(quán)重系數(shù)，其公式如式 （1）所示

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

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

2.3 MRSAB具體描述

MRSAB首先通過(guò)三顏色路由機(jī)制為節(jié)點(diǎn)判斷可用接口，然后為可用接口對(duì)應(yīng)鏈路預(yù)測(cè)t～t＋Δt內(nèi)的估計(jì)值Bt＋1，從而判斷每個(gè)接口對(duì)應(yīng)鏈路的帶寬占用情況，最后對(duì)可用接口對(duì)應(yīng)鏈路的可用帶寬進(jìn)行比較排序，選取可用帶寬大的接口進(jìn)行興趣包的轉(zhuǎn)發(fā)。文中MRSAB 算法具體步驟如下：

步驟1 設(shè)網(wǎng)絡(luò)拓?fù)渲忻織l鏈路的負(fù)載容量為Rij，Bij表示一條鏈路上當(dāng)前時(shí)刻帶寬占用情況。

步驟2 節(jié)點(diǎn)收到興趣包后按照CCN 的基本轉(zhuǎn)發(fā)過(guò)程查找，需要在FIB中查找下一跳節(jié)點(diǎn)時(shí)根據(jù)該興趣包名進(jìn)行最長(zhǎng)前綴匹配查找，找出節(jié)點(diǎn)上標(biāo)記為綠色的可用狀態(tài)接口。

步驟3 判斷可用狀態(tài)接口對(duì)應(yīng)鏈路上占用帶寬是否超過(guò)該鏈路的負(fù)載容量Rij，如果所有可用鏈路上帶寬占用都超過(guò)總的負(fù)載容量，即都處于鏈路擁塞狀態(tài)則執(zhí)行步驟4，否則執(zhí)行步驟5。

步驟4 丟棄該興趣包，在一定程度上減少網(wǎng)絡(luò)拓?fù)渲信d趣包的數(shù)量，并標(biāo)記該接口為黃色。

步驟5 利用WMA 模型預(yù)測(cè)可用鏈路上數(shù)據(jù)包的估計(jì)值，從而計(jì)算鏈路上帶寬占用情況。

步驟6 比較可用鏈路中數(shù)據(jù)包的估計(jì)值，選擇兩條可用帶寬較大的鏈路，使用可用帶寬最大的鏈路轉(zhuǎn)發(fā)興趣包，另一條作為備選鏈路從而保證數(shù)據(jù)請(qǐng)求的可靠性。

本文提出的MRSAB 算法根據(jù)鏈路帶寬占用情況選擇轉(zhuǎn)發(fā)接口，這樣可以充分利用網(wǎng)絡(luò)中帶寬資源，通過(guò)一定的鏈路限制減少該機(jī)制中鏈路擁塞的發(fā)生，減少請(qǐng)求數(shù)據(jù)的時(shí)延。三顏色機(jī)制標(biāo)識(shí)可用接口使興趣包向具有匹配數(shù)據(jù)的鏈路轉(zhuǎn)發(fā)，增加緩存的命中率，減少服務(wù)器的負(fù)載，該機(jī)制最大的優(yōu)點(diǎn)是多接口路由的引入使CCN 網(wǎng)絡(luò)中鏈路到達(dá)更好的負(fù)載均衡。

3 仿真分析

本文在Linux環(huán)境下采用基于NS3 的ndnSim 仿真平臺(tái)。本文的數(shù)據(jù)請(qǐng)求服從Zipf分布，仿真結(jié)果與CCN 中常用的FR 和BR 進(jìn)行比較。本實(shí)驗(yàn)采用LCE 緩存策略和LRU 替換策略，仿真時(shí)間200s。

3.1 緩存命中率

MRSAB與FR 和BR 在緩存命中率的比較如圖4所示。由圖可知隨著參數(shù)α的增加，緩存命中率逐漸增加，因?yàn)棣猎酱缶彺嬷写鎯?chǔ)的內(nèi)容越集中，緩存命中的概率越大。相對(duì)于FR 和BR，MRSAB 在α＞0.6 時(shí)緩存命中率相對(duì)較高，F(xiàn)R 的緩存命中率越來(lái)越低是因?yàn)榫彺嬷写鎯?chǔ)的內(nèi)容越來(lái)越集中，通過(guò)廣播興趣包副本請(qǐng)求數(shù)據(jù)使網(wǎng)絡(luò)中興趣包增多，而每個(gè)興趣包僅返回一個(gè)數(shù)據(jù)包。MRSAB 在α＜0.6時(shí)緩存命中率低于FR 是因?yàn)榫彺嬷写鎯?chǔ)的內(nèi)容不太集中，F(xiàn)R 通過(guò)多條路徑請(qǐng)求數(shù)據(jù)能夠提高命中數(shù)據(jù)的可能性。

圖4 緩存命率的比較

3.2 平均時(shí)延

MRSAB與FR 和BR 在平均時(shí)延上的比較如圖5所示。由圖可知MRSAB的平均時(shí)延相對(duì)較低，隨著參數(shù)α的增加平均時(shí)延越來(lái)越低，因?yàn)棣猎酱?，?duì)存儲(chǔ)比較集中的內(nèi)容請(qǐng)求所需要的時(shí)延較小。

圖5 平均時(shí)延的比較

3.3 負(fù)載均衡

本文選取一個(gè)度數(shù)最大且具有3個(gè)輸入數(shù)據(jù)接口和一個(gè)輸出數(shù)據(jù)接口的節(jié)點(diǎn)進(jìn)行負(fù)載均衡的測(cè)量，MRSAB 與FR 和BR 負(fù)載均衡的比較如圖6所示。由圖可知MRSAB的負(fù)載均衡明顯優(yōu)于FR 和BR。圖中BR 的負(fù)載均衡最差是因?yàn)樵摍C(jī)制僅選取一個(gè)最優(yōu)路徑進(jìn)行興趣包的轉(zhuǎn)發(fā)，這樣容易造成該鏈路負(fù)載過(guò)大，從而使網(wǎng)絡(luò)中整體的負(fù)載均衡較差。FR的負(fù)載均衡不穩(wěn)定是因?yàn)橄蛞粋€(gè)節(jié)點(diǎn)的所有接口轉(zhuǎn)發(fā)興趣包的副本，而并非所有接口都是可用狀態(tài)，所以其負(fù)載均衡隨著路徑上興趣包請(qǐng)求速率的增加有較大的波動(dòng)。度數(shù)為n的節(jié)點(diǎn)負(fù)載均衡度Ln的計(jì)算公式如式（3）所示

式中：L——一個(gè)節(jié)點(diǎn)上返回?cái)?shù)據(jù)包接口的個(gè)數(shù)，αk——L個(gè)接口對(duì)應(yīng)每條鏈路上帶寬占用情況。

圖6 負(fù)載均衡的比較

3.4 服務(wù)器負(fù)載

3種路由機(jī)制服務(wù)器負(fù)載 （服務(wù)器中數(shù)據(jù)包請(qǐng)求次數(shù)）的比較如圖7所示。由圖可知MRSAB的服務(wù)器負(fù)載低于其它兩種路由機(jī)制，F(xiàn)R 向節(jié)點(diǎn)的各個(gè)接口轉(zhuǎn)發(fā)興趣包，當(dāng)相應(yīng)鏈路的中間節(jié)點(diǎn)沒有相匹配的數(shù)據(jù)時(shí)，興趣包被轉(zhuǎn)發(fā)到服務(wù)器進(jìn)行數(shù)據(jù)包的請(qǐng)求，因此使服務(wù)器的負(fù)載明顯增加。

圖7 服務(wù)器負(fù)載的比較

4 結(jié)束語(yǔ)

針對(duì)CCN路由過(guò)程中鏈路擁塞和負(fù)載不均衡等問(wèn)題，本文提出了一種MRSAB算法，該算法在WMA數(shù)學(xué)模型下利用t－Δt～t、t－2Δt～t－Δt、t－3Δt～t－2Δt內(nèi)數(shù)據(jù)包個(gè)數(shù)的測(cè)量值預(yù)測(cè)t～t＋Δt內(nèi)數(shù)據(jù)包個(gè)數(shù)的估計(jì)值，從而評(píng)估鏈路帶寬的占用情況，通過(guò)比較節(jié)點(diǎn)可用鏈路帶寬占用情況選擇t～t＋Δt內(nèi)興趣包的轉(zhuǎn)發(fā)接口。仿真結(jié)果表明，本文提出算法充分利用網(wǎng)絡(luò)中的帶寬資源，在α＞0.6的條件下提高緩存命中率，在整個(gè)α的變化范圍內(nèi)減少平均請(qǐng)求時(shí)延，該算法最明顯的優(yōu)點(diǎn)是提高鏈路的負(fù)載均衡，減少服務(wù)器的負(fù)載。

［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.