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

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

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

1 引 言

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

本文的貢獻如下:建立了SD-ICN網絡模型;基于Logistic函數設計了鏈路QoS評價模型和路徑QoS評價模型;提出基于蜂群算法的興趣域劃分機制;設計了基于改進的QDMR算法的啟發式路由機制.

2 相關工作

文獻[5]中提出了一種集成ICN和SDN的體系結構,為內容交付提供透明的網絡內緩存.ContentSDN的內容緩存通過數據進行驅動,可根據業務需求進行調整,擴展了SDN的功能.文獻[6]提出了一種自適應流的QoS路由方法,它允許SDN控制器根據整個網絡拓撲結構,通過考慮分段的比特率來評估所有可通過的路徑,進而實現高質量傳輸.文獻[7]提出了一個分層的網絡結構以及帶有QoS的域間路由方法.它將控制器進行分層,將主控制器作為代理以獲得全局網絡狀態和視圖.

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

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

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

3 系統架構

SD-ICN網絡模型如圖1所示.控制平面的控制器通過控制指令對轉發平面進行控制,轉發平面由ICN路由器組成,轉發平面的路由器可以負責數據的傳輸,對數據進行轉發和存儲.控制平面的控制器則負責收集全局的興趣請求信息和鏈路狀態信息用來制定緩存和路由策略.

圖1 SD-ICN網絡模型Fig.1 SD-ICN network model

興趣包轉發過程如圖2所示,用戶通過發送興趣包獲取感興趣的內容,興趣包到達路由節點后,首先查找CS,如果在CS中找到對應的內容,則包含內容的數據包按原路返回,用戶的請求得到滿足;否則查找PIT,如果有相應的PIT條目,添加輸入接口到相應條目;否則,查找FIB,如果找到轉發接口,則按照轉發接口進行轉發;否則,查找IGT,如果沒有找到興趣包的興趣類別,將興趣包轉發到控制器;否則,將興趣包回溯或者丟棄.

圖2 興趣包轉發過程Fig.2 Interest packet forwarding process

當路由器將興趣包的信息發送到控制器時,控制器根據收集到的PacketIn消息和全局網絡信息,通過改進的QDMR算法計算興趣包的轉發規則,并通過FlowMod消息將轉發規則下發到路由器,過程如圖3所示.數據包在返回時首先匹配PIT條目,如果成功,則轉發數據包,否則丟棄.同時可以對數據包進行緩存,當收到同樣的請求時,可直接將該內容返回給用戶.

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

4 系統模型

4.1 網絡模型

SD-ICN網絡模型可以抽象為連通的無向圖G(V,E),其中V是具有存儲轉發能力的路由器節點集合;E是鏈路的集合.

4.2 鏈路QoS評價模型和路徑QoS評價模型

4.2.1 鏈路QoS評價模型

(1)

(2)

(3)

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

公式(1)中,0<α≤1,ε>0且ε是一個很小的正數.當bw

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

公式(3)與公式(2)類似,這里不再對鏈路延遲抖動評價函數進行分析.

(4)

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

4.2.2 路徑QoS評價模型

(5)

(6)

(7)

本文將三個參數的評價函數進行加權求和,得到路徑P的綜合QoS評價函數,定義如下:

(8)

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

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

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

5.1 問題定義

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

5.1.1 用戶興趣的分類

在本文中用戶請求的內容是通過興趣標簽標識的,通過關鍵字將內容分為體育、歷史、軍事、科學、數碼、美食、攝影等20個類別.同一個內容最多屬于一個類別,一個類別可以包含多個不同的內容,例如美食類別的內容可以包括東方美食和西方美食.

5.1.2 用戶興趣的計算

用戶通過向網絡發送興趣包來獲得想要的內容,興趣包包含興趣標簽字段,通過分析該字段的關鍵字就可以判斷用戶感興趣的內容,并在網絡中盡可能多地存儲用戶感興趣的內容.興趣類別表示對某一內容類別感興趣.為了更準確地劃分用戶興趣,用戶請求持續發出的時間被劃分為若干個時間段,劃分的標準根據網絡流量的大小進行調整,這樣不僅可以提高存儲空間利用率,而且能提高用戶的滿意度.

(9)

與前一段時間相比,用戶關于內容類別w請求比例的變化為:

(10)

本文引入滑動窗口機制.設滑動窗口的大小為N,則用戶對內容類別w的興趣度定義為:

(11)

其中,0<α1,α2,…,αN<1,且服從冪率分布,網絡用戶對該類型的內容越感興趣,則該內容的興趣度就越高.

5.1.3 興趣域的劃分

用戶更感興趣的內容類別應該分配更多的緩存空間.因此需要解決在哪些路由器上分配多少緩存空間給哪些興趣類別以實現負載均衡的問題.如果興趣類別相同的內容全部緩存到網絡中某幾個路由器中,會導致這幾個節點的負載變大,負載不均衡.

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

(12)

設興趣域w的興趣度為Iw,網絡中興趣域的個數為N,網絡中路由器的數量為M,則該興趣域分配的緩存空間Cw的計算公式如下:

(13)

設興趣域w在路由器i上被分配的存儲空間為xwi,路由器i的負載計算公式如下:

(14)

將興趣類別相同的內容分布式的緩存到網絡中的路由器中,力求找到最優的分配方式,在下文中提出興趣域劃分問題的優化目標.

5.1.4 優化目標

基于蜂群算法的興趣域劃分算法的優化目標的數學描述如下:

(15)

s.t.

(16)

(17)

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

5.1.5 解的表達

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

x=(x1,x2,…,xN)

(18)

xw=(xw1,xw2,…,xwM)

(19)

其中,xwi表示興趣域w在路由器i上分配的存儲空間,M表示網絡中路由器的個數,N表示網絡中興趣域的個數.

解的形式用矩陣表示為:

(20)

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

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

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

算法1.興趣域劃分算法

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

輸出:對存儲空間分配的初始解矩陣x

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

2. WHILEw存在 DO

3. IFGw

4. 隨機選擇路由器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.蜂王、雄蜂和工蜂選擇算法

輸入:對存儲空間分配的初始解矩陣x

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

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

2. 生成Q個初始解

3. 從高到低初始解的種群適應度進行排列

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

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

5.2.2 種群適應度

種群適應度用來衡量蜂群算法解決該問題的好壞,網絡節點的負載情況用來衡量興趣域劃分方法的好壞.將網絡節點的負載情況作為種群適應度fitness(x),具體表示如下:

(21)

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

(22)

其中,R表示路由器的最大負載,網絡負載和種群適應度成反比,種群適應度越大,得到的解越優.

5.2.3 停止條件

蜂群算法以蜂王作為最優可行解,當蜂王的種群適應度地在最大迭代次數范圍內,最大適應度平均值變化不大且趨于穩定,算法達到停止條件,即可停止運行.

5.2.4 運算規則

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

交叉階段:交叉行為是指蜂王隨機的從D個雄蜂中選擇一個進行交配,產生兩個新的幼蜂.在本階段,蜂群算法重復地執行交叉行為,生成Q個幼蜂.在本文中,交叉行為是蜂王與雄蜂按照交叉概率pc交換解矩陣的行向量.

變異階段:依次對交叉階段產生的Q個幼蜂根據變異概率pm執行變異操作.在本文中,變異操作是幼蜂根據變異概率pm將解矩陣的行同時加上或減去一個常數.

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

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

6.1 QoS依賴多播算法

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

6.2 問題定義

本文設計的改進的QDMR路由算法對內容名稱相同的多個興趣包進行聚集,形成一棵樹形轉發路徑,根節點為可以滿足該興趣請求的節點.為了構建一棵滿足用戶QoS需求的樹形轉發路徑,需要解決如何保證興趣包成功的在分支節點進行PIT匹配,以及如何生成將請求節點和內容節點連接起來的樹形轉發路徑這兩個問題.

(23)

s.t.

(24)

(25)

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

(26)

6.3 改進的QoS依賴多播算法

QDMR算法解決了在哪些節點聚集的問題,但是并沒有解決在什么時間聚集的問題.多個興趣包在某節點進行PIT匹配時應該滿足興趣包在數據包返回之前進行匹配.否則,如果興趣包轉發到下一節點,雖然按照樹形轉發路徑進行轉發,但是不能提高PIT匹配率.為了解決上述問題,需要對QDMR算法進行改進,保證在有效的時間內進行匹配.改進后的算法偽代碼如下:

算法3.改進的QDMR算法

輸入:請求節點集合R,內容節點s,延遲約束Δ

輸出:滿足延遲和時間約束的樹T

1. Dijkstra算法計算s到R中節點的最小延遲del

2. IFdel<Δ

3. RETURN Φ

4. END IF

5. 初始化s到其余節點u的代價和延遲

6.Cost[s]=0Delay[s]=0Cost[u]=∞Delay[u]=∞

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

8. WHILEQ≠Φ andR-T≠Φ DO

/*初始化Steiner樹階段*/

9. 從Q中找到代價最小的節點u

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

11. FORu的每個鄰接點vDO

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

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

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

/*ID(u)表示u到其他節點的延遲約束*/

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的父節點*/

16. END IF

17. END IF

18. END FOR

19. END WHILE

20. FORu∈Randu∈T

21.p=π[u]

22. WHILEp存在 DO

23. 計算興趣包到達時間Ti(p)

24. 計算數據包的返回時間Td(p)

25.p=π[p]

26. END WHILE

27. END FOR

28. FORu∈TDO

29. IFTi(u)>Td(u)

30. 刪除節點u的分支

31. END IF

32. END FOR

33. IFR-T≠Φ /*合并階段,將剩余節點加到T*/

34. FORu?TDO

35. 迪杰斯特拉算法算u到其余節點最短路徑

36. WHILEu到每個節點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)分別記錄興趣包的最早到達時間和數據包的返回時間.興趣包和數據包未到達時,這兩個值默認為正無窮.當有多個興趣包到達時,Ti(v)的值為最小的到達時間.Td(v)的值為下一跳節點返回數據包的時間與這兩個節點間的延遲之和.如果Ti(v)的值發生改變,那么需要更改分支上每個節點的Ti(v)和Td(v),該算法的時間復雜度為Ο(|E|logn).

7 性能評價

7.1 仿真實現

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

表1 拓撲信息表
Table 1 Topology information table

節點個數鏈路平均節點度數NSFNET14213Deltacom1131612.85

7.2 對比分析

7.2.1 路由成功率

路由成功率表示轉發成功的興趣包個數與用戶發送的興趣包的數量總數的比值.如圖4所示,在NSFNET拓撲下RIDSI、RISC、OSPFN的平均路由成功率分別為0.975、0.967、0.938;在Deltacom拓撲下RIDSI、RISC、OSPFN的平均路由成功率分別為0.966、0.957、0.936.可見RIDSI的路由成功率高于RISC和OSPFN.雖然RIDSI機制和對比機制RISC機制都實現了數據平面和轉發平面相分離,控制器根據全局信息制定出全局最優的轉發路徑,但是RIDSI機制將相同請求的興趣包提前聚合,增加了PIT條目的命中次數,間接地減少了FIB的條目,因此路由成功率相對RISC機制較高.

圖4 NSFNET拓撲和Deltacom拓撲下路由成功率Fig.4 Routing success rate in NSFNET topology and Deltacom topology

7.2.2 平均路由延遲

平均路由延遲表示用戶發出請求到獲得響應或者路由失敗的平均時間.從圖5可以得出,當興趣包數量較少時,RIDSI和RISC的路由延遲較高,這是因為興趣包在FIB中沒有找到對應的轉發條目時,路由器需要通過PacketIn消息將興趣包的信息轉發到控制器,控制器根據收到的消息制定相應的轉發規則,這個過程會產生一些延遲,如果興趣包的數量較少,該延遲就不能被忽略.當興趣包數量增多時,RIDSI路由機制的優勢就會被體現出來.RIDSI機制考慮興趣包QoS需求,選擇延遲最小的轉發路徑作為最優路徑,此外,RIDSI能夠對多個興趣包進行聚集,興趣包不需要全部轉發到內容節點就能獲得需要的內容,又能在一定程度上降低平均路由延遲.

圖5 NSFNET拓撲和Deltacom拓撲下平均路由延遲Fig.5 Average routing delay in the NSFNET topology and Deltacom topology

7.2.3 負載均衡度

平均負載均衡度表示網絡元素負載的差異程度.從圖6可以得出,在NSFNET拓撲下RIDSI、RISC、OSPFN的平均負載均衡度分別為0.309、0.317、0.420;在Deltacom拓撲下RIDSI、RISC、OSPFN的平均負載均衡度分別為0.306、0.315、0.419,可見RIDSI的網絡負載好于RISC和OSPFN.OSPFN將內容在網絡中隨機地進行存儲,沒有對區域進行劃分,這就容易產生某些路由器訪問頻率過高或者過低的問題,

圖6 NSFNET拓撲和Deltacom拓撲下負載均衡度Fig.6 Load balancing degree in the NSFNET topology and Deltacom topology

導致網絡負載不均衡.RIDSI和RISC對內容進行整合,對區域進行劃分,將訪問頻率高低不同的內容類別存儲同一個域中以實現不同區域的負載均衡.RIDSI劃分的興趣域是邏輯的區域,相同興趣域內的路由器在物理位置上既可以相鄰也可以不相鄰.RISC根據物理位置對節點進行劃分,同一個區域內的路由器在物理位置上是相鄰的.因此,RIDSI的負載均衡能力要好于RISC.

7.2.4 PIT命中率

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

圖7 NSFNET拓撲和Deltacom拓撲下PIT命中率Fig.7 PIT hit rate in the NSFNET topology and Deltacom topology

8 總 結

本文通過分析ICN和SDN的特點,設計了基于SDN和興趣域劃分的ICN路由機制,建立了SD-ICN網絡模型;設計了鏈路和路徑的QoS評價模型;提出了興趣域的概念和用戶興趣的分類方法;設計了基于改進的QDMR算法的啟發式路由機制;從仿真實現的結果可以看出本文設計的路由機制在負載均衡度、平均路由延遲等方面都具有一定的優勢.

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