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

(1 中南民族大學 計算機科學學院，武漢 430074；2 武漢紡織大學 機械工程與自動化學院，武漢 430073)

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

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

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

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

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

1.1 視頻業(yè)務分類

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

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

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

表1 視頻業(yè)務分類

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

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

1.2 多路徑設計原理

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

在ACO-MpR算法中加入NHN表記錄網(wǎng)絡拓撲中每個節(jié)點的相鄰節(jié)點.對于一個通信過程，對同一業(yè)務數(shù)據(jù)而言，設置TSR(Travel Second Route)值用于記錄下一跳接口的轉(zhuǎn)發(fā)狀態(tài)，通過改變信息轉(zhuǎn)發(fā)表FIB中TSR值來避免鏈路段相交，從而達到同一業(yè)務的不同數(shù)據(jù)塊能在沒有重復鏈路段的路徑上傳輸?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設立路由可行性條件，并結(jié)合最優(yōu)化模型，引入NHN表以得出最滿足相應視頻業(yè)務類型QoS要求且鏈路不相交的多路徑.

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

1.3 包格式設計

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

圖2 包格式設計

1.4 避免路徑重復機制

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

圖3 避免路徑重復流程

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

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

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

1.5 最優(yōu)化模型

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

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

(1)

(2)

(3)

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

(4)

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

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

(5)

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

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

表3 參數(shù)表

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

圖5 拓撲圖

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

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

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

圖7 傳輸時間

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

圖8 各路徑總時延

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

圖9 吞吐量

3 結(jié)論

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