基于蟻群優(yōu)化的命名數(shù)據(jù)網(wǎng)絡(luò)QoS路由研究

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

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

命名數(shù)據(jù)網(wǎng)絡(luò)NDN是一種在尋址方式上不同于傳統(tǒng)IP網(wǎng)絡(luò)的新型網(wǎng)絡(luò)結(jié)構(gòu)，傳統(tǒng)IP網(wǎng)絡(luò)的IP數(shù)據(jù)報格式以IP地址(目的地址和源地址)作為標(biāo)識，而NDN則以URL分級結(jié)構(gòu)的包名信息作為路由標(biāo)識.

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

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

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

1 ACO_QoS路由策略

1.1 路由轉(zhuǎn)發(fā)機制

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

圖1 PT及其對應(yīng)的轉(zhuǎn)發(fā)接口Fig.1 PT and the forward interface

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

圖2 NDN節(jié)點轉(zhuǎn)發(fā)模型Fig.2 Forward model in NDN nodes

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

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

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

(4) 興趣包探尋結(jié)束.

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

1.2 QoS要求及信息素更新

1.2.1 QoS要求

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

(1)

(2)

(3)

(4)

1.2.2 狀態(tài)轉(zhuǎn)移規(guī)則

(5)

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

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

(6)

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

1.2.3 信息素更新規(guī)則

(7)

(8)

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

算法運行機制如下：

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

(2) 初始化網(wǎng)絡(luò)拓?fù)渲懈鬟叺南鄳?yīng)信息素；

(3) 數(shù)據(jù)請求節(jié)點發(fā)送興趣包探尋數(shù)據(jù)源，網(wǎng)絡(luò)中的每個節(jié)點接收到興趣包后根據(jù)公式(5)從PT表中選擇接口u，將u添加到FIB中并將興趣包從此接口轉(zhuǎn)發(fā)；

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

(5) 重復(fù)步驟(3)和(4)，直到網(wǎng)絡(luò)運行結(jié)束.

2 仿真算例

圖3為實驗所用的網(wǎng)絡(luò)拓?fù)洌瑘D中每個節(jié)點的值表示的是包丟失率和時延抖動，每條邊上的值表示的是費用和帶寬.

圖3 網(wǎng)絡(luò)拓?fù)浼捌鋮?shù)Fig.3 Network topology and the parameters

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

(9)

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

假定節(jié)點1處與用戶直接相連，節(jié)點7、節(jié)點10分別與兩個內(nèi)容服務(wù)器相連，節(jié)點1處的用戶需要獲取節(jié)點7和節(jié)點10處的內(nèi)容服務(wù)器中的內(nèi)容.它們的QoS要求是：Lmax=10-5，DJmin=3，Bmin=80，簡化后的網(wǎng)絡(luò)拓?fù)淙鐖D4所示.

圖4 簡化后的網(wǎng)絡(luò)拓?fù)銯ig.4 The simplified network topology

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

表1 ACO_QoS路由結(jié)果

圖5 ACO_QoS轉(zhuǎn)發(fā)與隨機轉(zhuǎn)發(fā)投遞成功率比較Fig.5 The comparison of Success_Delivery_Rate between ACO_QoS and random forwarding

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

3 結(jié)語

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

參 考 文 獻

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

[2] 林 嘯.以內(nèi)容為中心的新一代互聯(lián)網(wǎng)體系架構(gòu)研究[J].電信科學(xué),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] 林 闖,王元卓,任豐原.新一代網(wǎng)絡(luò)QoS 研究[J].計算機學(xué)報,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] 葉潤生, 徐明偉. 命名數(shù)據(jù)網(wǎng)絡(luò)中的鄰居緩存路由策略[J]. 計算機科學(xué)與探索, 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.