命名數(shù)據(jù)網(wǎng)絡(luò)中基于蟻群優(yōu)化的視頻業(yè)務(wù)路徑優(yōu)化

侯睿，鄭勇*，周爍，張成俊

(1 中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074；2 武漢紡織大學(xué) 機(jī)械工程與自動(dòng)化學(xué)院，武漢 430073)

目前的TCP/IP網(wǎng)絡(luò)體系存在地址數(shù)量有限、移動(dòng)性、安全性等局限而發(fā)展受限.作為下一代互聯(lián)網(wǎng)體系的典型解決方案之一,命名數(shù)據(jù)網(wǎng)絡(luò)[1](NDN，Named Data Networking)允許用戶(hù)根據(jù)所需數(shù)據(jù)信息對(duì)象的名稱(chēng)而非位置來(lái)請(qǐng)求和獲取數(shù)據(jù)，通過(guò)分層結(jié)構(gòu)化命名方式分離位置和標(biāo)識(shí)，使目前主機(jī)-主機(jī)通信方式轉(zhuǎn)變?yōu)檎?qǐng)求內(nèi)容-獲取內(nèi)容的通信方式，因此較TCP/IP體系在安全性、移動(dòng)性、數(shù)據(jù)重用性等方面具有更明顯的優(yōu)勢(shì).

同時(shí)，隨著多媒體業(yè)務(wù)的快速發(fā)展，視頻業(yè)務(wù)流量在因特網(wǎng)中的比重越來(lái)越大，據(jù)思科可視化網(wǎng)絡(luò)指數(shù)(VNI)報(bào)告預(yù)測(cè)，全球各業(yè)務(wù)總量逐年攀升，其中視頻業(yè)務(wù)流量占比最高，而視頻業(yè)務(wù)因其數(shù)據(jù)量較大、帶寬占用較高的特點(diǎn)，對(duì)網(wǎng)絡(luò)資源有較高的要求，如何保證視頻業(yè)務(wù)在NDN中的可靠傳輸就成為信息中心網(wǎng)絡(luò)(ICN，Information Centric Networking)研究領(lǐng)域的重要課題.

為了提升視頻業(yè)務(wù)在NDN中的傳輸可靠性并保證服務(wù)質(zhì)量QoS，文獻(xiàn)[2]提出一種QoE驅(qū)動(dòng)的動(dòng)態(tài)視頻流算法(fair-DAS，fair Dynamic Adaptive video Streaming)，該算法能對(duì)多客戶(hù)端的視頻流進(jìn)行動(dòng)態(tài)自適應(yīng)帶寬優(yōu)化分配，但在客戶(hù)端增多時(shí)仍可能出現(xiàn)因總帶寬不足產(chǎn)生的客戶(hù)端視頻體驗(yàn)不佳等問(wèn)題；文獻(xiàn)[3]提出一種基于網(wǎng)絡(luò)編碼的自適應(yīng)視頻流架構(gòu)，在一定程度上能提高視頻質(zhì)量，但是網(wǎng)絡(luò)編碼過(guò)程可能會(huì)導(dǎo)致編碼時(shí)間開(kāi)銷(xiāo)增大而影響路由；文獻(xiàn)[4]提出一種基于視頻請(qǐng)求比例不同來(lái)劃分視頻熱度的緩存替換算法(PCSD)，PCSD根據(jù)請(qǐng)求比例將視頻熱度高的視頻塊放到靠近視頻接收端的邊緣路由器中來(lái)減少路由跳數(shù)，增加視頻傳輸性能，但對(duì)于熱度較低的視頻數(shù)據(jù)不能達(dá)到相同效果；文獻(xiàn)[5]提出一種基于視頻分發(fā)的網(wǎng)絡(luò)編碼和速率分配算法，該算法測(cè)算出客戶(hù)端和中間節(jié)點(diǎn)發(fā)送數(shù)據(jù)包(Data Packet)的最優(yōu)速率，根據(jù)各data包流的速率分配提高各客戶(hù)端視頻平均質(zhì)量，但并不能根據(jù)各客戶(hù)端視頻業(yè)務(wù)的不同針對(duì)性地保證視頻質(zhì)量.文獻(xiàn)[6]提出基于路徑上緩存的多徑路由MRBRC，通過(guò)發(fā)送探路興趣包，根據(jù)緩存內(nèi)容的流行度與轉(zhuǎn)發(fā)端口的歷史信息來(lái)收集熱度信息，并通過(guò)周期性統(tǒng)計(jì)緩存流行內(nèi)容來(lái)更新路由表實(shí)現(xiàn)內(nèi)容與轉(zhuǎn)發(fā)接口的對(duì)應(yīng)，其路由表維護(hù)成本及內(nèi)容統(tǒng)計(jì)成本會(huì)隨著緩存信息的增大而急劇增大，極大降低了傳輸性能.

有別于以上僅以帶寬、緩存、熱度作為優(yōu)化對(duì)象的視頻業(yè)務(wù)優(yōu)化方法，本文從視頻業(yè)務(wù)數(shù)據(jù)量大、適宜多路徑傳輸?shù)奶攸c(diǎn)進(jìn)行考慮，提出了一種適用于NDN網(wǎng)絡(luò)中，基于改進(jìn)的蟻群優(yōu)化算法的視頻業(yè)務(wù)路徑優(yōu)化方法 (ACO-MpR，Ant Colony Optimization-based Multipath Routing).該方法通過(guò)NDN中信息轉(zhuǎn)發(fā)表 (FIB，F(xiàn)orwarding Information Base)能轉(zhuǎn)發(fā)興趣包(Interest Packet)到多個(gè)接口的特性，使用多條路徑[7]并行傳輸，并通過(guò)最優(yōu)化模型計(jì)算和分析得到針對(duì)不同視頻業(yè)務(wù)傳輸?shù)亩鄺l路徑,以達(dá)到增加網(wǎng)絡(luò)聚合帶寬、減少時(shí)延、增加吞吐量的目的.

1 ACO-MpR算法及多路徑模型

1.1 視頻業(yè)務(wù)分類(lèi)

NDN中訂閱者(Subscriber)發(fā)送帶有請(qǐng)求信息的interest包來(lái)獲取數(shù)據(jù)，返回的data包包含相應(yīng)的內(nèi)容，data包的傳輸方式會(huì)因視頻業(yè)務(wù)特性的不同而不同，從而給出相應(yīng)的傳輸方案.

視頻業(yè)務(wù)因具體路由要求不同，其QoS服務(wù)要求也不同，QoS要求分為：盡力而為型(BE，Best-effort)，快速轉(zhuǎn)發(fā)型(EF，Expedited Forwarding)及保證轉(zhuǎn)發(fā)型(AF，Assured Forwarding).視頻業(yè)務(wù)在業(yè)務(wù)需求上具有數(shù)據(jù)傳輸量較大、實(shí)時(shí)性要求高及所需帶寬較大等特點(diǎn)，本文針對(duì)視頻業(yè)務(wù)的特點(diǎn)從擁塞、帶寬及時(shí)延等方面進(jìn)行視頻業(yè)務(wù)分類(lèi)，根據(jù)不同視頻業(yè)務(wù)對(duì)應(yīng)的擁塞、帶寬及時(shí)延要求組成約束三元組進(jìn)行路由限制，通過(guò)約束三元組中約束條件重要性的不同進(jìn)行加權(quán)，以找到最能滿(mǎn)足其服務(wù)要求的路由.

本文將視頻業(yè)務(wù)通信類(lèi)型分為視頻傳輸及下載、視頻通話(huà)、視頻分發(fā)及群會(huì)議等幾個(gè)具有代表性的業(yè)務(wù)類(lèi)型，不同通信類(lèi)型根據(jù)其具體服務(wù)要求進(jìn)行細(xì)化，提供針對(duì)不同視頻業(yè)務(wù)的優(yōu)化傳輸方案，如表1所示，表1中視頻傳輸及下載業(yè)務(wù)對(duì)帶寬要求較高，對(duì)時(shí)延要求一般，屬于盡力傳輸型業(yè)務(wù)，因此帶寬要求占有更大的權(quán)重.

表1 視頻業(yè)務(wù)分類(lèi)

數(shù)據(jù)對(duì)象是根據(jù)Subscriber在網(wǎng)絡(luò)拓?fù)渲信c之通信的數(shù)據(jù)發(fā)布者(Publisher)的數(shù)量進(jìn)行劃分的，一般情況下，Subscriber只能與一個(gè)或多個(gè)Publisher進(jìn)行數(shù)據(jù)通信.圖1 是一個(gè)一對(duì)一雙向數(shù)據(jù)傳輸過(guò)程，為簡(jiǎn)化模型可看成兩個(gè)獨(dú)立的單向數(shù)據(jù)傳輸過(guò)程，同樣，一對(duì)多的通信過(guò)程也可以簡(jiǎn)化為多個(gè)一對(duì)一的多路徑通信過(guò)程.

圖1 數(shù)據(jù)生產(chǎn)消費(fèi)關(guān)系

1.2 多路徑設(shè)計(jì)原理

根據(jù)業(yè)務(wù)類(lèi)型來(lái)初始化包括滿(mǎn)足其相應(yīng) QoS的時(shí)延、帶寬及擁塞值在內(nèi)的所有參數(shù)，并在找到一條路徑后更新NHN (Next Hop Node)表，重復(fù)該過(guò)程直到找到滿(mǎn)足其約束條件的多條路徑，最后將得到的多條路徑通過(guò)最優(yōu)化模型篩選出最滿(mǎn)足 QoS 要求的多條路徑.

在ACO-MpR算法中加入NHN表記錄網(wǎng)絡(luò)拓?fù)渲忻總€(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn).對(duì)于一個(gè)通信過(guò)程，對(duì)同一業(yè)務(wù)數(shù)據(jù)而言，設(shè)置TSR(Travel Second Route)值用于記錄下一跳接口的轉(zhuǎn)發(fā)狀態(tài)，通過(guò)改變信息轉(zhuǎn)發(fā)表FIB中TSR值來(lái)避免鏈路段相交，從而達(dá)到同一業(yè)務(wù)的不同數(shù)據(jù)塊能在沒(méi)有重復(fù)鏈路段的路徑上傳輸?shù)哪康?

算法1：

while(not satisfy the feasibility test of route)

initialize all parameters and NHN table

while (not satisfy the end condition)

fori=1 to num_ant do

randomly choose an initial node

forj=1 to nodes do

choose next node

add path[i,j] into taboo table

end for

end for

for link inGdo

update the pheromone concentration

end for

print route

end while

update the NHN by the output route

end while

for route in routes do

filter routes by the optimization model

end for

算法1中，ACO-MpR設(shè)立路由可行性條件，并結(jié)合最優(yōu)化模型，引入NHN表以得出最滿(mǎn)足相應(yīng)視頻業(yè)務(wù)類(lèi)型QoS要求且鏈路不相交的多路徑.

幾條不同路徑存在重復(fù)鏈路段時(shí)會(huì)導(dǎo)致?lián)砣酚晒?jié)點(diǎn)重復(fù)則不會(huì)，因此對(duì)于不同路徑中某個(gè)相交路由節(jié)點(diǎn)，通過(guò)判斷其下一跳節(jié)點(diǎn)是否重復(fù)即可避免重復(fù)鏈路段的出現(xiàn)，因此避免路徑重復(fù)機(jī)制也是能順利得出多條無(wú)重復(fù)鏈路段路徑的必要條件，對(duì)于數(shù)據(jù)量較大的視頻業(yè)務(wù)而言，視頻業(yè)務(wù)的不同數(shù)據(jù)塊在不同路徑的相同鏈路段傳輸可能導(dǎo)致?lián)砣?，因此在ACO-MpR中根據(jù)鏈路不相交原則，通過(guò)在蟻群優(yōu)化算法中加入NHN表來(lái)解決這種擁塞問(wèn)題.

1.3 包格式設(shè)計(jì)

NDN中把data包粒度較高且數(shù)據(jù)量較大的數(shù)據(jù)對(duì)象以一定的比例分配在多條路徑中傳輸.如圖2所示，在包格式[8]的設(shè)計(jì)中加入separator，if_separate用于區(qū)分是否按照多路徑方式傳輸；separate section用以區(qū)分?jǐn)?shù)據(jù)塊中的不同data包在哪條路徑上傳輸.

圖2 包格式設(shè)計(jì)

1.4 避免路徑重復(fù)機(jī)制

圖3表示interest包轉(zhuǎn)發(fā)到下一接口的避免路徑重復(fù)過(guò)程.

圖3 避免路徑重復(fù)流程

通過(guò)在ACO-MpR中加入NHN表，對(duì)輸出的路由節(jié)點(diǎn)進(jìn)行判斷使TSR狀態(tài)發(fā)生變化，由此確保多條路徑?jīng)]有相同路由鏈路[9].ACO-MpR算法中NHN表用于記錄網(wǎng)絡(luò)拓?fù)渲忻總€(gè)路由節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，通過(guò)區(qū)分同一業(yè)務(wù)的不同數(shù)據(jù)塊決定不同傳輸路徑中該節(jié)點(diǎn)通往相鄰節(jié)點(diǎn)的接口的狀態(tài)，產(chǎn)生TSR狀態(tài)轉(zhuǎn)換，使得信息轉(zhuǎn)發(fā)表FIB禁止同一個(gè)視頻業(yè)務(wù)的不同數(shù)據(jù)塊在相交節(jié)點(diǎn)的同一個(gè)接口轉(zhuǎn)發(fā)，對(duì)于一個(gè)通信過(guò)程，設(shè)置TSR值用于記錄下一跳接口的轉(zhuǎn)發(fā)狀態(tài)，通過(guò)改變信息轉(zhuǎn)發(fā)表FIB中TSR值來(lái)避免鏈路相交.

路由轉(zhuǎn)發(fā)機(jī)制如圖4所示，TSR值為1表示對(duì)該interest包而言該接口為可轉(zhuǎn)發(fā)狀態(tài)，為0則表示不可轉(zhuǎn)發(fā)狀態(tài).若interest包block1從接口A轉(zhuǎn)發(fā)到路由節(jié)點(diǎn)A，則TSR值變?yōu)?，對(duì)于同一視頻業(yè)務(wù)的block2則只能從TSR值為1的接口轉(zhuǎn)發(fā).這種機(jī)制能有效避免路徑重復(fù)，且能解決返回的data包在相同鏈路中傳輸帶來(lái)的擁塞問(wèn)題.

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

1.5 最優(yōu)化模型

ACO-MpR算法將鏈路上三元組數(shù)據(jù)(Congestion,Delay,Bandwidth)作為約束條件，通過(guò)有約束非線(xiàn)性最優(yōu)化模型[10]進(jìn)行路徑篩選以滿(mǎn)足相應(yīng)視頻業(yè)務(wù)的QoS，將n條路徑篩選為m(n≥m≥1)條滿(mǎn)足相應(yīng)業(yè)務(wù)QoS的路徑進(jìn)行數(shù)據(jù)傳輸.

本文對(duì)三元組數(shù)據(jù)進(jìn)行無(wú)量綱化處理得到預(yù)處理數(shù)據(jù)(Conge,Delay,Band)，并做約束處理[11]，每段鏈路需滿(mǎn)足相應(yīng)視頻業(yè)務(wù)的QoS要求的帶寬、時(shí)延及擁塞值，如下式(1)、(2)、(3)分別表示第N條路徑滿(mǎn)足相應(yīng)視頻業(yè)務(wù)的盡力而為型、快速轉(zhuǎn)發(fā)型及保證轉(zhuǎn)發(fā)型的QoS要求,其中最優(yōu)化模型可行域中必須以式(1)、(2)、(3)這3個(gè)值與被篩選路徑相應(yīng)數(shù)據(jù)的比較關(guān)系來(lái)確定篩選條件.

(1)

(2)

(3)

最優(yōu)化模型通過(guò)對(duì)帶寬與時(shí)延擁塞積的商做平均化處理，表示當(dāng)Band,Delay，Conge滿(mǎn)足視頻業(yè)務(wù)相應(yīng)QoS要求時(shí)m條路徑的帶寬與時(shí)延擁塞積的商的平均數(shù)最大，當(dāng)再增加或者減少一條路徑時(shí)使得該商的平均數(shù)變小都不可取，以其最大值確定、篩選出m條路徑，將其作為最優(yōu)化模型中的目標(biāo)函數(shù)，如下：

(4)

如表2所示，基于IETF提出的區(qū)分服務(wù)模型[12]DiffServ(Differentiated Services)，對(duì)于不同業(yè)務(wù)類(lèi)型的QoS要求都有對(duì)應(yīng)于帶寬、時(shí)延以及擁塞值的系數(shù)α,β,λ,且α+β+λ=1.

設(shè)置Datam為最優(yōu)化模型的決策變量，它表示數(shù)據(jù)源節(jié)點(diǎn)到數(shù)據(jù)請(qǐng)求節(jié)點(diǎn)第m條路徑傳輸總量，再設(shè)置最優(yōu)化模型相應(yīng)的可行域.然后根據(jù)式(1)、(2)、(3)的篩選條件建立最優(yōu)化模型可行域約束條件[13]為：

(5)

2 仿真結(jié)果與分析

針對(duì)視頻業(yè)務(wù)數(shù)據(jù)量大、QoS要求較高的特點(diǎn)，當(dāng)前關(guān)于命名數(shù)據(jù)網(wǎng)絡(luò)中視頻業(yè)務(wù)優(yōu)化的研究多以帶寬、緩存及內(nèi)容熱度為研究方向，本文選取命名數(shù)據(jù)網(wǎng)絡(luò)中經(jīng)典的路由方式蟻群優(yōu)化算法ACOIR(ACO-inspired ICN Routing)[14]和多路徑路由方法MRBRC為對(duì)比對(duì)象.本文以蟻群優(yōu)化算法對(duì)路由選擇具有收斂快及魯棒性強(qiáng)的特點(diǎn)，結(jié)合命名數(shù)據(jù)網(wǎng)絡(luò)支持多網(wǎng)址的特征，做出針對(duì)視頻業(yè)務(wù)區(qū)分及多路徑傳輸?shù)母倪M(jìn)，在以蟻群優(yōu)化算法為主的傳統(tǒng)路由方法基礎(chǔ)上，針對(duì)不同視頻業(yè)務(wù)提出基于改進(jìn)蟻群優(yōu)化算法的多路徑傳輸方案.在實(shí)驗(yàn)階段，設(shè)置ACO-MpR及ACOIR的實(shí)驗(yàn)參數(shù)見(jiàn)表3.

表3 參數(shù)表

如圖5所示，本文基于改進(jìn)薩拉瑪算法[15]來(lái)隨機(jī)生成一個(gè)包含30個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)鋱D.在多路徑視頻數(shù)據(jù)傳輸過(guò)程中，路徑條數(shù)越多，算法時(shí)間復(fù)雜度越高，劃分以及組合數(shù)據(jù)塊的時(shí)間開(kāi)銷(xiāo)越大，當(dāng)路徑條數(shù)達(dá)到一定值時(shí)，ACO-MpR算法優(yōu)越性會(huì)達(dá)到最高，故本實(shí)驗(yàn)中路徑條數(shù)設(shè)為兩條來(lái)代表多路徑中的一種情況，進(jìn)行實(shí)驗(yàn)對(duì)比.

圖5 拓?fù)鋱D

ACO-MpR算法在找到多條路徑后，將視頻對(duì)象分配到各路徑傳輸，分配原則是使最終到達(dá)數(shù)據(jù)請(qǐng)求端的時(shí)間開(kāi)銷(xiāo)差最小.如圖6所示，實(shí)驗(yàn)表明：在包含30個(gè)結(jié)點(diǎn)的拓?fù)鋱D中約有54.7%的數(shù)據(jù)報(bào)文由第一條路徑傳輸，第二條路徑則傳輸了45.3%，這樣分配使得時(shí)間開(kāi)銷(xiāo)一致，即達(dá)到數(shù)據(jù)同時(shí)接收完畢的平衡狀態(tài)，使得數(shù)據(jù)的總傳輸時(shí)間降到最低.

圖6 多路徑數(shù)據(jù)分配圖

如圖7所示，ACO-MpR中聚合帶寬的優(yōu)勢(shì)使得數(shù)據(jù)對(duì)象并行發(fā)送，降低了傳輸時(shí)間，且對(duì)數(shù)據(jù)量較大的數(shù)據(jù)給出相應(yīng)約束條件，使得路由更能滿(mǎn)足其QoS，有效滿(mǎn)足EF及AF可靠性的視頻業(yè)務(wù)需求.而MRBRC由于需查詢(xún)數(shù)據(jù)包與端口的關(guān)系，導(dǎo)致傳輸時(shí)間受查詢(xún)結(jié)果影響.ACO-MpR和MRBRC由于節(jié)點(diǎn)緩存在每次路由后會(huì)趨向請(qǐng)求節(jié)點(diǎn)，因此平均傳輸時(shí)間都有一定程度的降低.

圖7 傳輸時(shí)間

如圖8所示，ACOIR與ACO-MpR的時(shí)延幾乎一致，而MRBRC中時(shí)延較高且時(shí)延抖動(dòng)較大，這是由于MRBRC中匹配數(shù)據(jù)包與端口存在不穩(wěn)定性以及周期性更新緩存內(nèi)容使得開(kāi)銷(xiāo)增大導(dǎo)致的，且拓?fù)鋱D中節(jié)點(diǎn)數(shù)量有限使得ACO-MpR算法產(chǎn)生后續(xù)的路徑時(shí)會(huì)增大時(shí)延，在實(shí)際路由中，時(shí)延會(huì)隨著拓?fù)涔?jié)點(diǎn)總數(shù)量的增多而降低.

圖8 各路徑總時(shí)延

圖9給出了網(wǎng)絡(luò)吞吐量情況，由于多路徑聚合并行帶寬更大，因此ACO-MpR算法能得到更大的數(shù)據(jù)吞吐量，有效保證數(shù)據(jù)的可靠性，使BE類(lèi)型業(yè)務(wù)傳輸時(shí)間降低，而MRBRC未考慮多路徑數(shù)據(jù)傳輸中的擁塞，使得路由受擁塞的影響比ACO-MpR大.

圖9 吞吐量

3 結(jié)論

本文針對(duì)視頻業(yè)務(wù)服務(wù)質(zhì)量?jī)?yōu)化問(wèn)題提出了視頻數(shù)據(jù)的多路徑傳輸方案，針對(duì)其不同的傳輸需求給出相應(yīng)的滿(mǎn)足其QoS的傳輸方式，仿真實(shí)驗(yàn)結(jié)果表明基于蟻群優(yōu)化的視頻業(yè)務(wù)路徑優(yōu)化方法能為視頻業(yè)務(wù)提供更好的服務(wù)質(zhì)量保障.該方法能通過(guò)更大的聚合帶寬，在不同數(shù)據(jù)傳輸場(chǎng)景中根據(jù)不同視頻業(yè)務(wù)類(lèi)型的特點(diǎn)對(duì)數(shù)據(jù)傳輸方式進(jìn)行優(yōu)化，尤其對(duì)于傳輸帶寬資源占用較大的視頻業(yè)務(wù)以及數(shù)據(jù)量較大的數(shù)據(jù)對(duì)象，ACO-MpR算法在網(wǎng)絡(luò)聚合帶寬、路由時(shí)間及數(shù)據(jù)吞吐量等方面有更好的表現(xiàn).