RIDSI:一種融合SDN和興趣域劃分的ICN路由機(jī)制

王海月,王興偉,張 爽,黃 敏

1(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,沈陽 110169)2(東北大學(xué) 軟件學(xué)院,沈陽 110169)3(東北大學(xué) 信息科學(xué)與工程學(xué)院,沈陽 110819)

1 引 言

在當(dāng)前的網(wǎng)絡(luò)中,雖然用戶對(duì)內(nèi)容的興趣度更高,但今天的信息傳輸仍然基于內(nèi)容的位置.以信息為中心的網(wǎng)絡(luò)(ICN)[1,2]是一種新的范式,ICN根據(jù)內(nèi)容的名字對(duì)數(shù)據(jù)進(jìn)行路由取代了根據(jù)IP地址進(jìn)行路由,可以為內(nèi)容分發(fā)提供潛在的改進(jìn).在ICN中,每個(gè)路由器都可以緩存大量的內(nèi)容,但是路由器很難掌握其它路由器緩存的具體內(nèi)容并且缺少提高緩存空間利用率的機(jī)制,同時(shí)路由器也難以收集全局的數(shù)據(jù)請(qǐng)求信息并制定出最優(yōu)的路由方法.現(xiàn)有的ICN路由方法雖然能通過結(jié)合SDN[3,4]較好地解決集中控制的問題,但是當(dāng)網(wǎng)絡(luò)中流量增大時(shí),FIB的轉(zhuǎn)發(fā)條目會(huì)急劇膨脹,由于路由算法迭代次數(shù)過多會(huì)嚴(yán)重影響路由的性能,導(dǎo)致尋路時(shí)間過長,同時(shí)對(duì)路由器空間的不合理分配會(huì)導(dǎo)致路由器負(fù)載不均衡.針對(duì)上述問題,根據(jù)興趣域?qū)β酚善鬟M(jìn)行邏輯上的劃分并且通過SDN的集中控制和全局視圖功能對(duì)路由算法進(jìn)行優(yōu)化是提高存儲(chǔ)空間利用率和路由效率的一個(gè)很好的解決辦法.但是如何實(shí)現(xiàn)負(fù)載均衡的內(nèi)容分配以及如何制定一條滿足用戶QoS請(qǐng)求的路徑是必須要解決的問題.

本文的貢獻(xiàn)如下:建立了SD-ICN網(wǎng)絡(luò)模型;基于Logistic函數(shù)設(shè)計(jì)了鏈路QoS評(píng)價(jià)模型和路徑QoS評(píng)價(jià)模型;提出基于蜂群算法的興趣域劃分機(jī)制;設(shè)計(jì)了基于改進(jìn)的QDMR算法的啟發(fā)式路由機(jī)制.

2 相關(guān)工作

文獻(xiàn)[5]中提出了一種集成ICN和SDN的體系結(jié)構(gòu),為內(nèi)容交付提供透明的網(wǎng)絡(luò)內(nèi)緩存.ContentSDN的內(nèi)容緩存通過數(shù)據(jù)進(jìn)行驅(qū)動(dòng),可根據(jù)業(yè)務(wù)需求進(jìn)行調(diào)整,擴(kuò)展了SDN的功能.文獻(xiàn)[6]提出了一種自適應(yīng)流的QoS路由方法,它允許SDN控制器根據(jù)整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),通過考慮分段的比特率來評(píng)估所有可通過的路徑,進(jìn)而實(shí)現(xiàn)高質(zhì)量傳輸.文獻(xiàn)[7]提出了一個(gè)分層的網(wǎng)絡(luò)結(jié)構(gòu)以及帶有QoS的域間路由方法.它將控制器進(jìn)行分層,將主控制器作為代理以獲得全局網(wǎng)絡(luò)狀態(tài)和視圖.

文獻(xiàn)[8]介紹了幾個(gè)重要的ICN架構(gòu),介紹它們之間在核心功能方面的異同,并且指出ICN存在的不足,最后概述ICN有哪些未解決的挑戰(zhàn).文獻(xiàn)[9]解決了ICN中網(wǎng)絡(luò)內(nèi)緩存和多路徑轉(zhuǎn)發(fā)存在的一些問題,并提出了一種計(jì)算局部內(nèi)容流行度的方法,使每個(gè)路由器能夠獲取該內(nèi)容局部范圍內(nèi)的流行度.文獻(xiàn)[10]提出了基于QoS的自適應(yīng)路由策略,在路由器中添加服務(wù)質(zhì)量監(jiān)測模塊,在進(jìn)行興趣包的轉(zhuǎn)發(fā)時(shí)提供監(jiān)測到的QoS參數(shù),通過對(duì)接口的輸入和輸出數(shù)據(jù)進(jìn)行實(shí)時(shí)地監(jiān)測來預(yù)測接口的QoS性能.以上幾個(gè)ICN路由方案中,路由器難以收集全局?jǐn)?shù)據(jù)請(qǐng)求所以無法制定出最優(yōu)的路由方法,因此需要引入一種集中控制的架構(gòu)—SDN,用它來解決ICN在路由和緩存方面存在的問題.

近幾年,有些研究工作開始嘗試將ICN與SDN進(jìn)行融合以期解決ICN存在的問題.文獻(xiàn)[11]分析了將ICN和SDN進(jìn)行融合的優(yōu)勢,并且討論了如何利用SDN的優(yōu)勢部署ICN架構(gòu),最后強(qiáng)調(diào)了一些未解決的問題和未來趨勢.文獻(xiàn)[12]提出了在無線網(wǎng)狀網(wǎng)絡(luò)中通過部署SDN來提高ICN內(nèi)容管理效率的機(jī)制,以確保向移動(dòng)用戶快速有效地傳播內(nèi)容.文獻(xiàn)[13]提出了一種可以準(zhǔn)確、及時(shí)地定位緩存內(nèi)容的ICN緩存內(nèi)容定位機(jī)制,它通過使用布隆過濾器和壓縮感知來有效地表示緩存的內(nèi)容,并利用SDN的集中控制功能使緩存信息在SDN控制器中保持一致.

雖然上述幾篇文章通過將SDN引入到ICN,解決了ICN路由器無法進(jìn)行集中控制的問題,但是當(dāng)網(wǎng)絡(luò)流量過大時(shí),ICN的路由延遲有時(shí)還是不能很好地滿足用戶的需求.本文提出基于興趣域進(jìn)行類別劃分,將類別相同的內(nèi)容緩存到一組路由器中,可以提高緩存命中率并降低收到PacketIn消息的次數(shù)以及開銷,SDN可以有效地獲取網(wǎng)絡(luò)拓?fù)?通過運(yùn)行路由算法來提升網(wǎng)絡(luò)性能,可以保證控制開銷在可接受的范圍內(nèi).

3 系統(tǒng)架構(gòu)

SD-ICN網(wǎng)絡(luò)模型如圖1所示.控制平面的控制器通過控制指令對(duì)轉(zhuǎn)發(fā)平面進(jìn)行控制,轉(zhuǎn)發(fā)平面由ICN路由器組成,轉(zhuǎn)發(fā)平面的路由器可以負(fù)責(zé)數(shù)據(jù)的傳輸,對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)和存儲(chǔ).控制平面的控制器則負(fù)責(zé)收集全局的興趣請(qǐng)求信息和鏈路狀態(tài)信息用來制定緩存和路由策略.

圖1 SD-ICN網(wǎng)絡(luò)模型Fig.1 SD-ICN network model

興趣包轉(zhuǎn)發(fā)過程如圖2所示,用戶通過發(fā)送興趣包獲取感興趣的內(nèi)容,興趣包到達(dá)路由節(jié)點(diǎn)后,首先查找CS,如果在CS中找到對(duì)應(yīng)的內(nèi)容,則包含內(nèi)容的數(shù)據(jù)包按原路返回,用戶的請(qǐng)求得到滿足;否則查找PIT,如果有相應(yīng)的PIT條目,添加輸入接口到相應(yīng)條目;否則,查找FIB,如果找到轉(zhuǎn)發(fā)接口,則按照轉(zhuǎn)發(fā)接口進(jìn)行轉(zhuǎn)發(fā);否則,查找IGT,如果沒有找到興趣包的興趣類別,將興趣包轉(zhuǎn)發(fā)到控制器;否則,將興趣包回溯或者丟棄.

圖2 興趣包轉(zhuǎn)發(fā)過程Fig.2 Interest packet forwarding process

當(dāng)路由器將興趣包的信息發(fā)送到控制器時(shí),控制器根據(jù)收集到的PacketIn消息和全局網(wǎng)絡(luò)信息,通過改進(jìn)的QDMR算法計(jì)算興趣包的轉(zhuǎn)發(fā)規(guī)則,并通過FlowMod消息將轉(zhuǎn)發(fā)規(guī)則下發(fā)到路由器,過程如圖3所示.數(shù)據(jù)包在返回時(shí)首先匹配PIT條目,如果成功,則轉(zhuǎn)發(fā)數(shù)據(jù)包,否則丟棄.同時(shí)可以對(duì)數(shù)據(jù)包進(jìn)行緩存,當(dāng)收到同樣的請(qǐng)求時(shí),可直接將該內(nèi)容返回給用戶.

圖3 控制器處理過程Fig.3 Controller processing

4 系統(tǒng)模型

4.1 網(wǎng)絡(luò)模型

SD-ICN網(wǎng)絡(luò)模型可以抽象為連通的無向圖G(V,E),其中V是具有存儲(chǔ)轉(zhuǎn)發(fā)能力的路由器節(jié)點(diǎn)集合;E是鏈路的集合.

4.2 鏈路QoS評(píng)價(jià)模型和路徑QoS評(píng)價(jià)模型

4.2.1 鏈路QoS評(píng)價(jià)模型

(1)

(2)

(3)

其中,公式(1)、公式(2)和公式(3)中的bw、del、jt分別代表三個(gè)QoS參數(shù)值.bwL、bwH、delL、delH、jtL、jtH分別代表用戶對(duì)這三個(gè)參數(shù)的最小需求和最大需求.

公式(1)中,0<α≤1,ε>0且ε是一個(gè)很小的正數(shù).當(dāng)bw

公式(2)中,當(dāng)del>delH時(shí),鏈路無法滿足QoS參數(shù)需求,此時(shí)值為0;當(dāng)del=delH時(shí),鏈路能夠滿足最基本的需求,此時(shí)值為ε;當(dāng)delL

公式(3)與公式(2)類似,這里不再對(duì)鏈路延遲抖動(dòng)評(píng)價(jià)函數(shù)進(jìn)行分析.

(4)

其中,λ1、λ2、λ3分別為以上三個(gè)參數(shù)的權(quán)重,且它們的約束條件如下:0<λi<1,i=1,2,3,λ1+λ2+λ3=1.

4.2.2 路徑QoS評(píng)價(jià)模型

(5)

(6)

(7)

本文將三個(gè)參數(shù)的評(píng)價(jià)函數(shù)進(jìn)行加權(quán)求和,得到路徑P的綜合QoS評(píng)價(jià)函數(shù),定義如下:

(8)

其中,μ1、μ2、μ3分別為路徑上三個(gè)參數(shù)的權(quán)重,且它們的約束條件如下:0<μi<1,i=1,2,3,μ1+μ2+μ3=1.

5 基于蜂群算法的興趣域劃分

根據(jù)第四部分構(gòu)建的系統(tǒng)模型,第五部分研究基于蜂群算法的興趣域劃分機(jī)制,即根據(jù)用戶的興趣請(qǐng)求對(duì)路由器進(jìn)行邏輯上的劃分,判斷哪些路由器屬于同一個(gè)興趣域并緩存相同類別的內(nèi)容;第六部分研究基于興趣域劃分的路由機(jī)制,通過建立Steiner樹提前聚集請(qǐng)求相同內(nèi)容的興趣包,降低平均路由延遲,提高PIT命中率.

5.1 問題定義

本文中定義的興趣域是由一組路由器組成的邏輯區(qū)域,同一個(gè)興趣域的路由器在物理位置上可以相鄰也可以不相鄰,這些路由器存儲(chǔ)的內(nèi)容是用戶感興趣的同一類別的內(nèi)容.

5.1.1 用戶興趣的分類

在本文中用戶請(qǐng)求的內(nèi)容是通過興趣標(biāo)簽標(biāo)識(shí)的,通過關(guān)鍵字將內(nèi)容分為體育、歷史、軍事、科學(xué)、數(shù)碼、美食、攝影等20個(gè)類別.同一個(gè)內(nèi)容最多屬于一個(gè)類別,一個(gè)類別可以包含多個(gè)不同的內(nèi)容,例如美食類別的內(nèi)容可以包括東方美食和西方美食.

5.1.2 用戶興趣的計(jì)算

用戶通過向網(wǎng)絡(luò)發(fā)送興趣包來獲得想要的內(nèi)容,興趣包包含興趣標(biāo)簽字段,通過分析該字段的關(guān)鍵字就可以判斷用戶感興趣的內(nèi)容,并在網(wǎng)絡(luò)中盡可能多地存儲(chǔ)用戶感興趣的內(nèi)容.興趣類別表示對(duì)某一內(nèi)容類別感興趣.為了更準(zhǔn)確地劃分用戶興趣,用戶請(qǐng)求持續(xù)發(fā)出的時(shí)間被劃分為若干個(gè)時(shí)間段,劃分的標(biāo)準(zhǔn)根據(jù)網(wǎng)絡(luò)流量的大小進(jìn)行調(diào)整,這樣不僅可以提高存儲(chǔ)空間利用率,而且能提高用戶的滿意度.

(9)

與前一段時(shí)間相比,用戶關(guān)于內(nèi)容類別w請(qǐng)求比例的變化為:

(10)

本文引入滑動(dòng)窗口機(jī)制.設(shè)滑動(dòng)窗口的大小為N,則用戶對(duì)內(nèi)容類別w的興趣度定義為:

(11)

其中,0<α1,α2,…,αN<1,且服從冪率分布,網(wǎng)絡(luò)用戶對(duì)該類型的內(nèi)容越感興趣,則該內(nèi)容的興趣度就越高.

5.1.3 興趣域的劃分

用戶更感興趣的內(nèi)容類別應(yīng)該分配更多的緩存空間.因此需要解決在哪些路由器上分配多少緩存空間給哪些興趣類別以實(shí)現(xiàn)負(fù)載均衡的問題.如果興趣類別相同的內(nèi)容全部緩存到網(wǎng)絡(luò)中某幾個(gè)路由器中,會(huì)導(dǎo)致這幾個(gè)節(jié)點(diǎn)的負(fù)載變大,負(fù)載不均衡.

在本文中衡量路由器的緩存容量用塊表示.設(shè)置塊的基本大小為C,路由器i的緩存空間表示為Si,則路由器i的緩存空間塊數(shù)表示為Bi:

(12)

設(shè)興趣域w的興趣度為Iw,網(wǎng)絡(luò)中興趣域的個(gè)數(shù)為N,網(wǎng)絡(luò)中路由器的數(shù)量為M,則該興趣域分配的緩存空間Cw的計(jì)算公式如下:

(13)

設(shè)興趣域w在路由器i上被分配的存儲(chǔ)空間為xwi,路由器i的負(fù)載計(jì)算公式如下:

(14)

將興趣類別相同的內(nèi)容分布式的緩存到網(wǎng)絡(luò)中的路由器中,力求找到最優(yōu)的分配方式,在下文中提出興趣域劃分問題的優(yōu)化目標(biāo).

5.1.4 優(yōu)化目標(biāo)

基于蜂群算法的興趣域劃分算法的優(yōu)化目標(biāo)的數(shù)學(xué)描述如下:

(15)

s.t.

(16)

(17)

xwi=0,1,…,Bi;w=1,2,…,N;i=1,2,…,M

5.1.5 解的表達(dá)

上述問題的解用向量進(jìn)行表示,興趣域在每個(gè)路由器上分配的塊數(shù)作為向量元素,解的具體表示形式為:

x=(x1,x2,…,xN)

(18)

xw=(xw1,xw2,…,xwM)

(19)

其中,xwi表示興趣域w在路由器i上分配的存儲(chǔ)空間,M表示網(wǎng)絡(luò)中路由器的個(gè)數(shù),N表示網(wǎng)絡(luò)中興趣域的個(gè)數(shù).

解的形式用矩陣表示為:

(20)

5.2 基于蜂群算法的興趣域劃分

5.2.1 基于蜂群算法的興趣域劃分

本文采用蜂群算法解決如何對(duì)網(wǎng)絡(luò)的存儲(chǔ)空間進(jìn)行分配的問題,在蜂群算法中種群適應(yīng)度由高到低依次是蜂王、雄蜂和工蜂,每個(gè)蜜蜂都是一個(gè)初始解.在執(zhí)行蜂群算法之前,需要對(duì)三種角色的蜜蜂進(jìn)行初始化,即生成初始解.本文隨機(jī)選擇一個(gè)路由器將一個(gè)基本塊分配給一個(gè)興趣域,興趣域劃分算法具體步驟如下:

算法1.興趣域劃分算法

輸入:所有興趣域w需要的空間為Cw,該興趣域已經(jīng)劃分的空間為Gw;任意一個(gè)路由器i中緩存容量為Bi,CS占用量為Ei.

輸出:對(duì)存儲(chǔ)空間分配的初始解矩陣x

1. 初始化解矩陣為零矩陣,每個(gè)興趣域在路由器的CS已占用塊數(shù)被設(shè)置為0.

2. WHILEw存在 DO

3. IFGw

4. 隨機(jī)選擇路由器i,它的緩存空間容量

5. 為Bi,CS占用量為Ei

6. IFEi

7. 路由器i中為興趣域w分配一塊基本塊

8.Gw=Gw+1

9.Ei=Ei+1

10.xwi=xwi+1

11. END IF

12. ELSE

13. 從待選集合中刪除路由器i

14. END ELSE

15. END IF

16. ELSE

17. 將興趣域w從待選集合中刪除

18. END ELSE

19. END WHILE

20. RETURN x

算法2.蜂王、雄蜂和工蜂選擇算法

輸入:對(duì)存儲(chǔ)空間分配的初始解矩陣x

輸出:候選解蜂王,雄蜂,工蜂

1. 解矩陣初始化為零矩陣,每個(gè)興趣域在路由器已占用塊數(shù)被設(shè)置為0.

2. 生成Q個(gè)初始解

3. 從高到低初始解的種群適應(yīng)度進(jìn)行排列

4. 種群適應(yīng)度最大的解為蜂王,第2～D+1個(gè)初始解為雄蜂,剩余的W個(gè)為工蜂

5. RETURN 候選解蜂王,雄蜂,工蜂

5.2.2 種群適應(yīng)度

種群適應(yīng)度用來衡量蜂群算法解決該問題的好壞,網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)載情況用來衡量興趣域劃分方法的好壞.將網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)載情況作為種群適應(yīng)度fitness(x),具體表示如下:

(21)

R=Max{Wi,i=1,2,…,M}

(22)

其中,R表示路由器的最大負(fù)載,網(wǎng)絡(luò)負(fù)載和種群適應(yīng)度成反比,種群適應(yīng)度越大,得到的解越優(yōu).

5.2.3 停止條件

蜂群算法以蜂王作為最優(yōu)可行解,當(dāng)蜂王的種群適應(yīng)度地在最大迭代次數(shù)范圍內(nèi),最大適應(yīng)度平均值變化不大且趨于穩(wěn)定,算法達(dá)到停止條件,即可停止運(yùn)行.

5.2.4 運(yùn)算規(guī)則

蜂群算法主要包括交叉階段、變異階段和招募階段.

交叉階段:交叉行為是指蜂王隨機(jī)的從D個(gè)雄蜂中選擇一個(gè)進(jìn)行交配,產(chǎn)生兩個(gè)新的幼蜂.在本階段,蜂群算法重復(fù)地執(zhí)行交叉行為,生成Q個(gè)幼蜂.在本文中,交叉行為是蜂王與雄蜂按照交叉概率pc交換解矩陣的行向量.

變異階段:依次對(duì)交叉階段產(chǎn)生的Q個(gè)幼蜂根據(jù)變異概率pm執(zhí)行變異操作.在本文中,變異操作是幼蜂根據(jù)變異概率pm將解矩陣的行同時(shí)加上或減去一個(gè)常數(shù).

招募階段:每只工蜂在各自的區(qū)域中可以招募附近的B只蜜蜂一起尋找食物.在本文中,工蜂的招募行為是隨機(jī)生成對(duì)某個(gè)興趣域的分配方案,而其他興趣域分配方案不變.

6 基于QoS依賴多播算法的啟發(fā)式路由

6.1 QoS依賴多播算法

QoS依賴多播算法(QoS Dependent Multicast Routing,QDMR)算法以源節(jié)點(diǎn)到目的節(jié)點(diǎn)的延遲與延遲約束的比值為啟發(fā)式信息,找到代價(jià)最小的多播樹.改進(jìn)的QDMR算法主要包含兩個(gè)階段:第一階段為Steiner樹構(gòu)造階段,第二階段為合并階段.在多播樹構(gòu)造階段,改進(jìn)的QDMR算法對(duì)多播樹進(jìn)行拓展,源節(jié)點(diǎn)到目的節(jié)點(diǎn)的延遲越小的節(jié)點(diǎn)越有可能作為一個(gè)新的“源點(diǎn)”連接其它的目的節(jié)點(diǎn).

6.2 問題定義

本文設(shè)計(jì)的改進(jìn)的QDMR路由算法對(duì)內(nèi)容名稱相同的多個(gè)興趣包進(jìn)行聚集,形成一棵樹形轉(zhuǎn)發(fā)路徑,根節(jié)點(diǎn)為可以滿足該興趣請(qǐng)求的節(jié)點(diǎn).為了構(gòu)建一棵滿足用戶QoS需求的樹形轉(zhuǎn)發(fā)路徑,需要解決如何保證興趣包成功的在分支節(jié)點(diǎn)進(jìn)行PIT匹配,以及如何生成將請(qǐng)求節(jié)點(diǎn)和內(nèi)容節(jié)點(diǎn)連接起來的樹形轉(zhuǎn)發(fā)路徑這兩個(gè)問題.

(23)

s.t.

(24)

(25)

Ti(v)≤Td(v)，v∈T

(26)

6.3 改進(jìn)的QoS依賴多播算法

QDMR算法解決了在哪些節(jié)點(diǎn)聚集的問題,但是并沒有解決在什么時(shí)間聚集的問題.多個(gè)興趣包在某節(jié)點(diǎn)進(jìn)行PIT匹配時(shí)應(yīng)該滿足興趣包在數(shù)據(jù)包返回之前進(jìn)行匹配.否則,如果興趣包轉(zhuǎn)發(fā)到下一節(jié)點(diǎn),雖然按照樹形轉(zhuǎn)發(fā)路徑進(jìn)行轉(zhuǎn)發(fā),但是不能提高PIT匹配率.為了解決上述問題,需要對(duì)QDMR算法進(jìn)行改進(jìn),保證在有效的時(shí)間內(nèi)進(jìn)行匹配.改進(jìn)后的算法偽代碼如下:

算法3.改進(jìn)的QDMR算法

輸入:請(qǐng)求節(jié)點(diǎn)集合R,內(nèi)容節(jié)點(diǎn)s,延遲約束Δ

輸出:滿足延遲和時(shí)間約束的樹T

1. Dijkstra算法計(jì)算s到R中節(jié)點(diǎn)的最小延遲del

2. IFdel<Δ

3. RETURN Φ

4. END IF

5. 初始化s到其余節(jié)點(diǎn)u的代價(jià)和延遲

6.Cost[s]=0Delay[s]=0Cost[u]=∞D(zhuǎn)elay[u]=∞

7. 初始化T=Φ,Q?T,Q=V

8. WHILEQ≠Φ andR-T≠Φ DO

/*初始化Steiner樹階段*/

9. 從Q中找到代價(jià)最小的節(jié)點(diǎn)u

10.T=T∪{u},Q=Q-{u}

11. FORu的每個(gè)鄰接點(diǎn)vDO

12. IFDelay[u]+D(u,v)<Δ andv?T

/*D(u,v)表示u到v的延遲*/

/*C(u,v)表示u到v的代價(jià)*/

/*ID(u)表示u到其他節(jié)點(diǎn)的延遲約束*/

13. IFCost[v]>ID(u)Cost[u]+C(u,v)

14.Cost[v]=ID(u)Cost[u]+C(u,v)

15.π[v]=u,Delay[v]=Delay[u]+D(u,v)

/*π[v]表示v的父節(jié)點(diǎn)*/

16. END IF

17. END IF

18. END FOR

19. END WHILE

20. FORu∈Randu∈T

21.p=π[u]

22. WHILEp存在 DO

23. 計(jì)算興趣包到達(dá)時(shí)間Ti(p)

24. 計(jì)算數(shù)據(jù)包的返回時(shí)間Td(p)

25.p=π[p]

26. END WHILE

27. END FOR

28. FORu∈TDO

29. IFTi(u)>Td(u)

30. 刪除節(jié)點(diǎn)u的分支

31. END IF

32. END FOR

33. IFR-T≠Φ /*合并階段,將剩余節(jié)點(diǎn)加到T*/

34. FORu?TDO

35. 迪杰斯特拉算法算u到其余節(jié)點(diǎn)最短路徑

36. WHILEu到每個(gè)節(jié)點(diǎn)v的最短路徑 DO

37. IFDelay[v]+D(u,v)<Δ andTi(v)

38. 將u到v的路徑添加到T

39. END IF

40. END WHILE

41. END FOR

42. END IF

43. RETURNT

Ti(v)和Td(v)分別記錄興趣包的最早到達(dá)時(shí)間和數(shù)據(jù)包的返回時(shí)間.興趣包和數(shù)據(jù)包未到達(dá)時(shí),這兩個(gè)值默認(rèn)為正無窮.當(dāng)有多個(gè)興趣包到達(dá)時(shí),Ti(v)的值為最小的到達(dá)時(shí)間.Td(v)的值為下一跳節(jié)點(diǎn)返回?cái)?shù)據(jù)包的時(shí)間與這兩個(gè)節(jié)點(diǎn)間的延遲之和.如果Ti(v)的值發(fā)生改變,那么需要更改分支上每個(gè)節(jié)點(diǎn)的Ti(v)和Td(v),該算法的時(shí)間復(fù)雜度為Ο(|E|logn).

7 性能評(píng)價(jià)

7.1 仿真實(shí)現(xiàn)

本文在實(shí)驗(yàn)室PC機(jī)上通過Eclipse平臺(tái)對(duì)提出的在SD-ICN網(wǎng)絡(luò)模型中設(shè)計(jì)的基于興趣域劃分的路由機(jī)制(Routing mechanism based on Interest Domain in Sd-Icn,RIDSI)進(jìn)行仿真實(shí)現(xiàn).本文選取文獻(xiàn)[14]中基于SDN和社區(qū)劃分的路由機(jī)制(RISC)和文獻(xiàn)[15]中基于OSPF的路由機(jī)制(OSPFN)作為基準(zhǔn)機(jī)制進(jìn)行對(duì)比分析.在實(shí)驗(yàn)時(shí)使用了NSFNET和Deltacom兩種拓?fù)?拓?fù)涞南嚓P(guān)信息如表1所示.在這兩種拓?fù)湎?用戶通過隨機(jī)選擇源節(jié)點(diǎn),每組實(shí)驗(yàn)在同樣的配置下分別隨機(jī)產(chǎn)生100、200、300、400、500、600個(gè)興趣請(qǐng)求,通過運(yùn)行興趣域劃分算法解決每個(gè)興趣類別應(yīng)該分配多少緩存空間以及在哪些路由器分配緩存空間的問題,然后在尋路過程通過改進(jìn)的QDMR算法為興趣包請(qǐng)求計(jì)算出滿足帶寬、延遲和延遲抖動(dòng)需求的路徑,在運(yùn)行過程中,選取了四個(gè)有代表性的參數(shù)對(duì)本文提出的算法進(jìn)行評(píng)估,分別是路由成功率、平均路由延遲、負(fù)載均衡度和PIT命中率,其具體定義將在下文中進(jìn)行介紹,將程序運(yùn)行的結(jié)果進(jìn)行記錄并與RISC和OSPEN算法進(jìn)行比較.

表1 拓?fù)湫畔⒈?br/>Table 1 Topology information table

節(jié)點(diǎn)個(gè)數(shù)鏈路平均節(jié)點(diǎn)度數(shù)NSFNET14213Deltacom1131612.85

7.2 對(duì)比分析

7.2.1 路由成功率

路由成功率表示轉(zhuǎn)發(fā)成功的興趣包個(gè)數(shù)與用戶發(fā)送的興趣包的數(shù)量總數(shù)的比值.如圖4所示,在NSFNET拓?fù)湎翿IDSI、RISC、OSPFN的平均路由成功率分別為0.975、0.967、0.938;在Deltacom拓?fù)湎翿IDSI、RISC、OSPFN的平均路由成功率分別為0.966、0.957、0.936.可見RIDSI的路由成功率高于RISC和OSPFN.雖然RIDSI機(jī)制和對(duì)比機(jī)制RISC機(jī)制都實(shí)現(xiàn)了數(shù)據(jù)平面和轉(zhuǎn)發(fā)平面相分離,控制器根據(jù)全局信息制定出全局最優(yōu)的轉(zhuǎn)發(fā)路徑,但是RIDSI機(jī)制將相同請(qǐng)求的興趣包提前聚合,增加了PIT條目的命中次數(shù),間接地減少了FIB的條目,因此路由成功率相對(duì)RISC機(jī)制較高.

圖4 NSFNET拓?fù)浜虳eltacom拓?fù)湎侣酚沙晒β蔉ig.4 Routing success rate in NSFNET topology and Deltacom topology

7.2.2 平均路由延遲

平均路由延遲表示用戶發(fā)出請(qǐng)求到獲得響應(yīng)或者路由失敗的平均時(shí)間.從圖5可以得出,當(dāng)興趣包數(shù)量較少時(shí),RIDSI和RISC的路由延遲較高,這是因?yàn)榕d趣包在FIB中沒有找到對(duì)應(yīng)的轉(zhuǎn)發(fā)條目時(shí),路由器需要通過PacketIn消息將興趣包的信息轉(zhuǎn)發(fā)到控制器,控制器根據(jù)收到的消息制定相應(yīng)的轉(zhuǎn)發(fā)規(guī)則,這個(gè)過程會(huì)產(chǎn)生一些延遲,如果興趣包的數(shù)量較少,該延遲就不能被忽略.當(dāng)興趣包數(shù)量增多時(shí),RIDSI路由機(jī)制的優(yōu)勢就會(huì)被體現(xiàn)出來.RIDSI機(jī)制考慮興趣包QoS需求,選擇延遲最小的轉(zhuǎn)發(fā)路徑作為最優(yōu)路徑,此外,RIDSI能夠?qū)Χ鄠€(gè)興趣包進(jìn)行聚集,興趣包不需要全部轉(zhuǎn)發(fā)到內(nèi)容節(jié)點(diǎn)就能獲得需要的內(nèi)容,又能在一定程度上降低平均路由延遲.

圖5 NSFNET拓?fù)浜虳eltacom拓?fù)湎缕骄酚裳舆tFig.5 Average routing delay in the NSFNET topology and Deltacom topology

7.2.3 負(fù)載均衡度

平均負(fù)載均衡度表示網(wǎng)絡(luò)元素負(fù)載的差異程度.從圖6可以得出,在NSFNET拓?fù)湎翿IDSI、RISC、OSPFN的平均負(fù)載均衡度分別為0.309、0.317、0.420;在Deltacom拓?fù)湎翿IDSI、RISC、OSPFN的平均負(fù)載均衡度分別為0.306、0.315、0.419,可見RIDSI的網(wǎng)絡(luò)負(fù)載好于RISC和OSPFN.OSPFN將內(nèi)容在網(wǎng)絡(luò)中隨機(jī)地進(jìn)行存儲(chǔ),沒有對(duì)區(qū)域進(jìn)行劃分,這就容易產(chǎn)生某些路由器訪問頻率過高或者過低的問題,

圖6 NSFNET拓?fù)浜虳eltacom拓?fù)湎仑?fù)載均衡度Fig.6 Load balancing degree in the NSFNET topology and Deltacom topology

導(dǎo)致網(wǎng)絡(luò)負(fù)載不均衡.RIDSI和RISC對(duì)內(nèi)容進(jìn)行整合,對(duì)區(qū)域進(jìn)行劃分,將訪問頻率高低不同的內(nèi)容類別存儲(chǔ)同一個(gè)域中以實(shí)現(xiàn)不同區(qū)域的負(fù)載均衡.RIDSI劃分的興趣域是邏輯的區(qū)域,相同興趣域內(nèi)的路由器在物理位置上既可以相鄰也可以不相鄰.RISC根據(jù)物理位置對(duì)節(jié)點(diǎn)進(jìn)行劃分,同一個(gè)區(qū)域內(nèi)的路由器在物理位置上是相鄰的.因此,RIDSI的負(fù)載均衡能力要好于RISC.

7.2.4 PIT命中率

PIT命中率表示PIT條目匹配次數(shù)與興趣請(qǐng)求數(shù)量的比值,代表對(duì)相同興趣包的聚集能力.從圖7可以得出,PIT命中率由高到低分別是RIDSI、RISC、OSPFN.RIDSI機(jī)制將對(duì)同一個(gè)內(nèi)容名稱的興趣請(qǐng)求進(jìn)行聚集,并且制定一組樹形轉(zhuǎn)發(fā)路徑,下發(fā)至路由器.興趣包根據(jù)下發(fā)的路徑進(jìn)行轉(zhuǎn)發(fā)時(shí),首先查看PIT條目,如果沒有找到就添加對(duì)應(yīng)的條目.由于RIDSI機(jī)制基于改進(jìn)的QDMR算法對(duì)興趣包進(jìn)行PIT匹配,因此RIDSI的PIT命中率較高.RISC與RIDSI都實(shí)現(xiàn)了數(shù)據(jù)平面與控制平面分離,但是RISC沒有對(duì)相同的請(qǐng)求進(jìn)行聚集,因此RISC與OSPFN的PIT命中率相差不大.由于興趣包與所有興趣請(qǐng)求的比值是趨于穩(wěn)定的,因此RIDSI的PIT命中率基本保持不變.

圖7 NSFNET拓?fù)浜虳eltacom拓?fù)湎翽IT命中率Fig.7 PIT hit rate in the NSFNET topology and Deltacom topology

8 總 結(jié)

本文通過分析ICN和SDN的特點(diǎn),設(shè)計(jì)了基于SDN和興趣域劃分的ICN路由機(jī)制,建立了SD-ICN網(wǎng)絡(luò)模型;設(shè)計(jì)了鏈路和路徑的QoS評(píng)價(jià)模型;提出了興趣域的概念和用戶興趣的分類方法;設(shè)計(jì)了基于改進(jìn)的QDMR算法的啟發(fā)式路由機(jī)制;從仿真實(shí)現(xiàn)的結(jié)果可以看出本文設(shè)計(jì)的路由機(jī)制在負(fù)載均衡度、平均路由延遲等方面都具有一定的優(yōu)勢.

本文提出了一種新型路由機(jī)制RIDSI,但是由于其中的一些想法可能并不成熟,仍然有一些問題沒有解決,希望之后在提升算法性能、路由失效時(shí)進(jìn)行重路由以及拓展控制器的個(gè)數(shù)以適應(yīng)大規(guī)模的軟件定義信息中心網(wǎng)絡(luò)等方面進(jìn)行深入的研究.