基于蟻群優化的命名數據網絡QoS路由研究

侯 睿，邵 瑞，鄭明明，張 晴

(中南民族大學 計算機科學學院，武漢 430074)

命名數據網絡NDN是一種在尋址方式上不同于傳統IP網絡的新型網絡結構，傳統IP網絡的IP數據報格式以IP地址(目的地址和源地址)作為標識，而NDN則以URL分級結構的包名信息作為路由標識.

興趣包和數據包是NDN中的兩種基本包格式，其中數據包是用戶想要獲取的資源，而興趣包的功能則是探尋數據包.為了獲取數據包，首先需要廣播相應的興趣包，以探尋數據包[1].例如，用戶想要從谷歌中獲取某一個圖片的數據，那么用戶就要發送名字為URL格式的興趣包來探尋數據包，若探尋到相同名字信息的數據包，便按照興趣包所走路徑的相反方向將數據包發送給用戶.

基本的NDN節點包含3個數據結構表：轉發信息表(FIB)，待定請求表(PIT)，內容存儲器(CS)[2].FIB中存儲的是路由節點到達內容服務器的下一跳的接口，PIT存儲的是已從節點轉發到下一節點的興趣包的名字信息，以使數據包能夠沿著原路徑返回，CS中存儲的是緩存的內容.當節點從一個接口收到一個興趣包時，將根據它所包含的內容名進行最大匹配查詢，而后根據查詢結果進行下一步的操作.查詢的優先級順序依次為CS、PIT、FIB.

NDN具有多樣的路由轉發策略，并獲取了豐富的研究成果，但目前的研究都還處于發展階段，因此路由策略有很大的研究空間.由于因特網的快速發展，多樣化的用戶需求，特別是實時多媒體的應用對QoS的需求越來越高[3]，如何實現QoS路由顯得尤為重要.QoS路由的任務就是對網絡中的資源進行優化配置以尋找一條向用戶提供端到端服務質量保證的路由.網絡的路由問題與蟻群尋路的問題有很大的相似性，都是尋找可以到達目的地的最優路線，而且模擬蟻群尋路的ACO算法在解決路由問題上具有分布式、正反饋、全局收局收斂等優點，因此，本文將利用ACO來實現NDN中的QoS路由.

1 ACO_QoS路由策略

1.1 路由轉發機制

對于節點的設計，依然采用文獻[7]中SoCCeR算法所采用的節點設計方法.在SoCCer算法中，節點新增了信息素濃度表(PT)，PT中包含了服務的名字、對應的接口信息、接口所對應的信息素濃度值以及根據信息素濃度所計算出來的每個接口相應的選擇概率.對于每一個服務請求，節點按照概率選擇某一個接口將其添加到FIB中，并沿著FIB中的接口轉發出去.PT對應的轉發接口如圖1所示，其中P0>P1>P2，P3>P1.

圖1 PT及其對應的轉發接口Fig.1 PT and the forward interface

在基于QoS服務的NDN中，為了獲取數據包，首先需要發送一個帶有QoS約束的興趣包，興趣包在各個節點通過NDN轉發機制轉發，當節點接收到興趣包時，將根據內容名進行最大匹配查詢，然后進行下一步操作.為了釋放探尋失敗的興趣包所占用的PIT空間，本文新增了興趣包探尋失敗的響應報文，該報文中只包含與興趣包相同的名字信息，如果探尋失敗，當前路由器便會產生一個響應報文沿著興趣包的反方向依次釋放路由節點PIT中的興趣包接口，這一點跟數據包的功能一樣.操作流程如圖2所示.

圖2 NDN節點轉發模型Fig.2 Forward model in NDN nodes

(1) 節點接收到興趣包后，首先查詢CS中是否包含興趣包所請求的內容，若包含，則將請求的內容反向發送給用戶，并沿途消耗對應的興趣包.否則，轉到⑵；

(2) 繼續查詢PIT中是否已經包含興趣包對應的接口信息，若包含，則表明已經有與之相同名字信息的興趣包在等待數據的相應，直接舍棄興趣包,并將接口信息添加到PIT中.否則，轉到⑶；

(3) 繼續查詢PT中是否包含與興趣包對應的接口信息，若包含，則按照概率轉移規則從PT中選擇某一接口將興趣包轉發出去，并在PIT中新增該接口信息.若不包含，則表明無法探尋下一跳的接口，直接丟棄興趣包，并在當前路由節點產生與興趣包名字信息相同的響應報文，沿著興趣包的反方向釋放興趣包所對應的接口信息；

(4) 興趣包探尋結束.

因此，知識可視化和網絡媒介素養教育的目的是一致的，都是為了知識的傳播和知識的創造。知識可視化是從知識呈現的形式上的視覺化來促進知識的傳播；網絡媒介素養教育是從技術手段上促進知識的傳播。如果把二者結合起來，快速傳播的網絡媒介技術承載著易懂的可視化的信息，人們既可以快速地獲取信息，又能快速地解讀信息，使得人們在信息時代中所面臨的更快、更多地掌握知識的難題得到了解決。

1.2 QoS要求及信息素更新

1.2.1 QoS要求

本文將NDN網絡模型表示為一個有向圖G=(V，E),E表示NDN中的節點集合，E表示相鄰節點所對應的邊的集合.對于任意一個節點n∈V,包含兩個QoS指標：節點丟失率Lost(n)、節點時延抖動Delay_Jitter(n)；對于任意一個邊e∈E，也包含兩個QoS指標：可用帶寬Bandwidth(e)、鏈路費用Cost(e).對于一個包含QoS要求的興趣包Interest(QoS)，其中QoS=(Lmax,DJmin,Bmin)分別表示最大丟失率、最小時延抖動以及最小帶寬限制，QoS路由算法的目的就是能夠找到一條費用(Interest(cost))最小并且滿足QoS要求的路徑L(V′,E′)，其中V′?V表示Interest(QoS)所經過的節點集合，E′?E表示Interest(QoS)所經過得邊的集合.QoS要求如下：

(1)

(2)

(3)

(4)

1.2.2 狀態轉移規則

(5)

ηnk(t)=[Lost(k)]β[DelayJitter(n)]γ·

[Bandwidth((n,k))]δ,

(6)

其中α為信息啟發因子，其值的大小反映了在選路過程中信息素的重要程度；公式(6)是啟發函數，表示興趣包從節點選擇下一個接口的期望程度，β、γ、δ為期望啟發因子；q服從的0～1均勻分布，q0∈[0,1]是一個特定的參數，可以調節興趣包隨機選路的比率.

1.2.3 信息素更新規則

(7)

(8)

Q表示信息素強度增加系數,costbest表示本輪迭代中最佳路由的費用的總和.

算法運行機制如下：

(1) 通過刪除帶寬小于需求帶寬的鏈路，把網絡過濾成一個新的簡單的網絡；

(2) 初始化網絡拓撲中各邊的相應信息素；

(3) 數據請求節點發送興趣包探尋數據源，網絡中的每個節點接收到興趣包后根據公式(5)從PT表中選擇接口u，將u添加到FIB中并將興趣包從此接口轉發；

(4) 一輪迭代結束后，對興趣包經過的路徑按公式(7)進行信息素的更新，并重新計算轉移概率；

(5) 重復步驟(3)和(4)，直到網絡運行結束.

2 仿真算例

圖3為實驗所用的網絡拓撲，圖中每個節點的值表示的是包丟失率和時延抖動，每條邊上的值表示的是費用和帶寬.

圖3 網絡拓撲及其參數Fig.3 Network topology and the parameters

為了與NDN中的隨機轉發模式比較興趣包探索數據包的成功率，本文定義投遞成功率(Success_Delivery_Ratek)如下：

(9)

其中Data_Countk表示第k次迭代過程中探尋到的數據包的數目，Interest_Countk表示第k次迭代過程中興趣包的數目.

假定節點1處與用戶直接相連，節點7、節點10分別與兩個內容服務器相連，節點1處的用戶需要獲取節點7和節點10處的內容服務器中的內容.它們的QoS要求是：Lmax=10-5，DJmin=3，Bmin=80，簡化后的網絡拓撲如圖4所示.

圖4 簡化后的網絡拓撲Fig.4 The simplified network topology

仿真獲得的全局優化路線如表格1所示，在對內容服務器7請求數據時，存在路由1→4→7，該條路由的費用只有3，但是其包丟失率達到了10-3，因此沒有選擇該路由.圖5是本文所采用的ACO_QoS轉發和NDN中另一種隨機轉發的投遞成功率的對比，從圖中可以得到，ACO_QoS轉發隨著迭代次數的增加投遞成功率越來越高，這是因為后來的興趣包根據先驗經驗選擇符合QoS要求的路線的概率增大了；而隨機轉發的投遞成功率基本維持在50%左右，大大影響了網絡的性能.圖6是對于內容服務器7和內容服務器10的請求的費用收斂曲線，從圖中可以看出，對于內容服務器7的請求的費用收斂的較快，這是因為其最佳路徑的費用相對于其它路徑的費用要小的多，從而能夠很快地尋找到最佳路線；而對于內容服務器10的請求，由于多條路徑所需的費用的差距很小，因此在探尋最佳路線時要花費更長的時間.

表1 ACO_QoS路由結果

圖5 ACO_QoS轉發與隨機轉發投遞成功率比較Fig.5 The comparison of Success_Delivery_Rate between ACO_QoS and random forwarding

圖6 費用收斂曲線Fig.6 Average cost of ACO_QoS routing

3 結語

為了克服傳統IP網絡的缺陷，以內容為中心的命名數據網絡成為一種新型的未來網絡體系結構，其中命名數據網絡中的路由是研究的一大熱點.本文利用蟻群算法實現了命名數據網絡中基于QoS機制的路由選擇問題，能夠選擇出一條滿足QoS的路由以提高數據包的投遞成功率，并且使路徑的費用和時延能夠快速的收斂到較低的水平.

參 考 文 獻

[1] Zhang L X,Estrin D, Burke J, et al. Named data networking (ndn) project[R]. California:PARC, 2010.

[2] 林 嘯.以內容為中心的新一代互聯網體系架構研究[J].電信科學,2010,5: 1-7.

[3] Zhang M W, Sun X M, Lv X Y. A QoS routing algorithm based on culture-ant colony algorithm[C]//IEEE.International Conference on Computer Application and System Modeling(ICCASM).Taiyuan: IEEE, 2010: 198-201.

[4] Ding G, Shi L, Wu X, et al. Improved ant colony algorithm with multi-strategies for QoS routing problems[C]//IEEE. International Conference on Natural Computation (ICNC).Chongqing:IEEE, 2012: 767-771.

[5] 林 闖,王元卓,任豐原.新一代網絡QoS 研究[J].計算機學報,2008, 31(9):1525-1535.

[6] Yuan H, Song T, Crowley P. Scalable NDN forwarding: Concepts, issues and principles[C]//IEEE.International Conference on Computer Communications and Networks (ICCCN).Munich: IEEE, 2012: 1-9.

[7] Shanbhag S, Schwan N, Rimac I, et al. SoCCeR: Services over content-centric routing[C]//ACM.Proceeding of the ACM SIGCOMM workshop on Information-Centric Networking (ICN).Toronto:ACM,2011:62-67.

[8] 葉潤生, 徐明偉. 命名數據網絡中的鄰居緩存路由策略[J]. 計算機科學與探索, 2012, 6(7): 593-601.

[9] Li Y, He Z. Improved ant colony algorithms with chaotic selection strategy for solving QoS routingproblems[J]. Energy Procedia, 2011, 13: 5890-5897.

[10] Sabrina F. A novel resource scheduling algorithm for QoS-aware services on the Internet[J]. Computers & Electrical Engineering, 2010, 36(4): 718-734.

[11] Triay J, Cervelló-Pastor C. An ant-based algorithm for distributed routing and wavelength assignment in dynamic optical networks[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(4): 542-552.