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

(中南民族大學(xué) 計(jì)算機(jī)科學(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ù)報(bào)格式以IP地址(目的地址和源地址)作為標(biāo)識(shí)，而NDN則以URL分級(jí)結(jié)構(gòu)的包名信息作為路由標(biāo)識(shí).

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

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

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

1 ACO_QoS路由策略

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

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

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

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

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

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

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

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

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

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

1.2 QoS要求及信息素更新

1.2.1 QoS要求

本文將NDN網(wǎng)絡(luò)模型表示為一個(gè)有向圖G=(V，E),E表示NDN中的節(jié)點(diǎn)集合，E表示相鄰節(jié)點(diǎn)所對(duì)應(yīng)的邊的集合.對(duì)于任意一個(gè)節(jié)點(diǎn)n∈V,包含兩個(gè)QoS指標(biāo)：節(jié)點(diǎn)丟失率Lost(n)、節(jié)點(diǎn)時(shí)延抖動(dòng)Delay_Jitter(n)；對(duì)于任意一個(gè)邊e∈E，也包含兩個(gè)QoS指標(biāo)：可用帶寬Bandwidth(e)、鏈路費(fèi)用Cost(e).對(duì)于一個(gè)包含QoS要求的興趣包Interest(QoS)，其中QoS=(Lmax,DJmin,Bmin)分別表示最大丟失率、最小時(shí)延抖動(dòng)以及最小帶寬限制，QoS路由算法的目的就是能夠找到一條費(fèi)用(Interest(cost))最小并且滿足QoS要求的路徑L(V′,E′)，其中V′?V表示Interest(QoS)所經(jīng)過的節(jié)點(diǎn)集合，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é)點(diǎn)選擇下一個(gè)接口的期望程度，β、γ、δ為期望啟發(fā)因子；q服從的0～1均勻分布，q0∈[0,1]是一個(gè)特定的參數(shù)，可以調(diào)節(jié)興趣包隨機(jī)選路的比率.

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

(7)

(8)

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

算法運(yùn)行機(jī)制如下：

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

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

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

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

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

2 仿真算例

圖3為實(shí)驗(yàn)所用的網(wǎng)絡(luò)拓?fù)?，圖中每個(gè)節(jié)點(diǎn)的值表示的是包丟失率和時(shí)延抖動(dòng)，每條邊上的值表示的是費(fèi)用和帶寬.

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

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

(9)

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

假定節(jié)點(diǎn)1處與用戶直接相連，節(jié)點(diǎn)7、節(jié)點(diǎn)10分別與兩個(gè)內(nèi)容服務(wù)器相連，節(jié)點(diǎn)1處的用戶需要獲取節(jié)點(diǎn)7和節(jié)點(diǎn)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所示，在對(duì)內(nèi)容服務(wù)器7請(qǐng)求數(shù)據(jù)時(shí)，存在路由1→4→7，該條路由的費(fèi)用只有3，但是其包丟失率達(dá)到了10-3，因此沒有選擇該路由.圖5是本文所采用的ACO_QoS轉(zhuǎn)發(fā)和NDN中另一種隨機(jī)轉(zhuǎn)發(fā)的投遞成功率的對(duì)比，從圖中可以得到，ACO_QoS轉(zhuǎn)發(fā)隨著迭代次數(shù)的增加投遞成功率越來越高，這是因?yàn)楹髞淼呐d趣包根據(jù)先驗(yàn)經(jīng)驗(yàn)選擇符合QoS要求的路線的概率增大了；而隨機(jī)轉(zhuǎn)發(fā)的投遞成功率基本維持在50%左右，大大影響了網(wǎng)絡(luò)的性能.圖6是對(duì)于內(nèi)容服務(wù)器7和內(nèi)容服務(wù)器10的請(qǐng)求的費(fèi)用收斂曲線，從圖中可以看出，對(duì)于內(nèi)容服務(wù)器7的請(qǐng)求的費(fèi)用收斂的較快，這是因?yàn)槠渥罴崖窂降馁M(fèi)用相對(duì)于其它路徑的費(fèi)用要小的多，從而能夠很快地尋找到最佳路線；而對(duì)于內(nèi)容服務(wù)器10的請(qǐng)求，由于多條路徑所需的費(fèi)用的差距很小，因此在探尋最佳路線時(shí)要花費(fèi)更長的時(shí)間.

表1 ACO_QoS路由結(jié)果

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

圖6 費(fèi)用收斂曲線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ò)中的路由是研究的一大熱點(diǎn).本文利用蟻群算法實(shí)現(xiàn)了命名數(shù)據(jù)網(wǎng)絡(luò)中基于QoS機(jī)制的路由選擇問題，能夠選擇出一條滿足QoS的路由以提高數(shù)據(jù)包的投遞成功率，并且使路徑的費(fèi)用和時(shí)延能夠快速的收斂到較低的水平.

參 考 文 獻(xiàn)

[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].計(jì)算機(jī)學(xué)報(bào),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]. 計(jì)算機(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.