命名數(shù)據(jù)網(wǎng)絡(luò)中VIP轉(zhuǎn)發(fā)方案的性能優(yōu)化

金 洋，呂金陽，譚小彬

(中國科學(xué)技術(shù)大學(xué) 未來網(wǎng)絡(luò)實(shí)驗(yàn)室，合肥 230027)

0 引 言

網(wǎng)絡(luò)架構(gòu)需要與用戶需求相匹配。當(dāng)前互聯(lián)網(wǎng)用戶的主要需求已從主機(jī)間的通信轉(zhuǎn)變?yōu)閷W(wǎng)絡(luò)內(nèi)容的重復(fù)訪問，傳統(tǒng)的TCP/IP協(xié)議架構(gòu)在拓展性、移動性、安全性等方面顯示出諸多不適應(yīng)性。信息中心網(wǎng)絡(luò)試圖從根本上解決這些問題[1]。命名數(shù)據(jù)網(wǎng)絡(luò)作為信息中心網(wǎng)絡(luò)的實(shí)例之一[2]，憑借先進(jìn)的理念、方案的可行性和諸多實(shí)質(zhì)性進(jìn)展，目前已經(jīng)成為信息中心網(wǎng)絡(luò)的主流方案。

NDN不同于IP網(wǎng)絡(luò)的會話模型，而是采用一種用戶驅(qū)動、名字尋址的通信方式，實(shí)現(xiàn)了從“Where”到“What”，“Push”到“Pull”的轉(zhuǎn)化，更符合用戶關(guān)注內(nèi)容本身的需求。NDN每個節(jié)點(diǎn)配有內(nèi)容緩存表(content store，CS)、待定興趣表(pending interest table，PIT)、轉(zhuǎn)發(fā)表(forwarding information base，F(xiàn)IB)3種數(shù)據(jù)結(jié)構(gòu)，通過傳輸興趣分組(interest packet)、數(shù)據(jù)分組(data packet)完成內(nèi)容請求和獲取。分組的分裝方式、尋址方式相對TCP/IP網(wǎng)絡(luò)有了根本的不同。緩存的存在減少了相同數(shù)據(jù)的重復(fù)傳輸，提高了網(wǎng)絡(luò)傳輸性能。NDN在網(wǎng)絡(luò)可拓展性、移動性、安全性、多路傳輸上有很大優(yōu)勢。

路由和轉(zhuǎn)發(fā)是網(wǎng)絡(luò)協(xié)議的核心部分，優(yōu)秀的路由、轉(zhuǎn)發(fā)算法有利于提高網(wǎng)絡(luò)的傳輸性能。TCP/IP網(wǎng)絡(luò)的轉(zhuǎn)發(fā)平面僅根據(jù)轉(zhuǎn)發(fā)表作出轉(zhuǎn)發(fā)決策，不支持多路傳輸，適應(yīng)性較差。NDN的轉(zhuǎn)發(fā)表中，一個信息名稱可以對應(yīng)著多個輸出端口，這為多播傳輸提供了直接支持，若選擇從所有的端口進(jìn)行轉(zhuǎn)發(fā)，無疑增加了冗余數(shù)據(jù)的傳輸，容易造成網(wǎng)絡(luò)擁塞。因此，若轉(zhuǎn)發(fā)算法能根據(jù)網(wǎng)絡(luò)狀態(tài)的變化調(diào)整轉(zhuǎn)發(fā)端口，使得轉(zhuǎn)發(fā)平面具有自適應(yīng)性，這將對網(wǎng)絡(luò)性能的提高有重要作用[3]。

在NDN的轉(zhuǎn)發(fā)算法研究中，VIP架構(gòu)是一種聯(lián)合動態(tài)轉(zhuǎn)發(fā)與緩存的網(wǎng)絡(luò)架構(gòu)[4]，轉(zhuǎn)發(fā)平面能根據(jù)網(wǎng)絡(luò)狀態(tài)的變化調(diào)整轉(zhuǎn)發(fā)端口選擇、緩存內(nèi)容的替換，實(shí)現(xiàn)了網(wǎng)絡(luò)吞吐量的最大化。但是當(dāng)網(wǎng)絡(luò)處于輕負(fù)載狀態(tài)時(shí)，該架構(gòu)將造成很大的傳輸時(shí)延，針對該問題，本文給出了一種解決方案。本文主要關(guān)注VIP架構(gòu)的轉(zhuǎn)發(fā)方案。

1 相關(guān)工作

隨著NDN 項(xiàng)目的進(jìn)行，NDN 轉(zhuǎn)發(fā)算法的研究已取得一定成果。根據(jù)當(dāng)前轉(zhuǎn)發(fā)策略所感知的信息類別，其大致可劃分為以下三類：①基于網(wǎng)絡(luò)端口狀況感知的轉(zhuǎn)發(fā)算法；②基于網(wǎng)絡(luò)內(nèi)容分布感知的轉(zhuǎn)發(fā)算法；③基于網(wǎng)絡(luò)端口狀況和內(nèi)容分布共同感知的轉(zhuǎn)發(fā)算法。

1.1 基于網(wǎng)絡(luò)端口狀況感知的轉(zhuǎn)發(fā)算法

依據(jù)NDN轉(zhuǎn)發(fā)平面所帶來的網(wǎng)絡(luò)狀態(tài)信息，文獻(xiàn)[3]提出一種基于端口著色的轉(zhuǎn)發(fā)策略。在該策略中，紅、黃、綠三色之一被標(biāo)記在網(wǎng)絡(luò)各個端口中，它們分別代表了3種不同的工作狀態(tài)。在實(shí)際的轉(zhuǎn)發(fā)過程中，端口顏色依據(jù)不同事件的發(fā)生而相互轉(zhuǎn)換。在其轉(zhuǎn)發(fā)決策中，綠色端口優(yōu)先被選擇，黃色端口只有在沒有綠色端口的情況下才被用于轉(zhuǎn)發(fā)，紅色端口不能轉(zhuǎn)發(fā)數(shù)據(jù)。通過對該策略分析容易發(fā)現(xiàn)：當(dāng)有兩份相同內(nèi)容被緩存在網(wǎng)絡(luò)節(jié)點(diǎn)中，一份離用戶很近，另一份離用戶很遠(yuǎn)，根據(jù)當(dāng)前的轉(zhuǎn)發(fā)策略，用戶可能會從較遠(yuǎn)的源節(jié)點(diǎn)獲取數(shù)據(jù)。換言之，該轉(zhuǎn)發(fā)策略不具有網(wǎng)絡(luò)內(nèi)容分布感知能力。

Posch等[5]提出一種隨機(jī)自適應(yīng)的轉(zhuǎn)發(fā)策略。該策略通過模仿水管系統(tǒng)自調(diào)節(jié)方法，智能指導(dǎo)和分發(fā)興趣分組，以繞過由鏈路故障、擁塞等導(dǎo)致的瓶頸節(jié)點(diǎn)。通過設(shè)置信任閾值，網(wǎng)絡(luò)所有轉(zhuǎn)發(fā)端口被分為信任端口與不信任端口。在實(shí)際轉(zhuǎn)發(fā)過程中，每過一段時(shí)間，各個端口都會被評定一次。信任端口的轉(zhuǎn)發(fā)概率大于不信任端口的轉(zhuǎn)發(fā)概率。通過對該轉(zhuǎn)發(fā)策略的工作原理分析，我們發(fā)現(xiàn)該轉(zhuǎn)發(fā)策略只適合于高度擁塞的場景，對于普通的場景，由于丟包率不大，很難得到一個很好的轉(zhuǎn)發(fā)效果。與此同時(shí)，該策略也不具有網(wǎng)絡(luò)內(nèi)容分布的感知能力。

1.2 基于網(wǎng)絡(luò)內(nèi)容分布感知的轉(zhuǎn)發(fā)策略

Yeh等[4]在原有命名數(shù)據(jù)網(wǎng)絡(luò)的基礎(chǔ)上，提出一種聯(lián)合動態(tài)轉(zhuǎn)發(fā)與緩存的網(wǎng)絡(luò)架構(gòu)。在該網(wǎng)絡(luò)架構(gòu)中，數(shù)據(jù)的轉(zhuǎn)發(fā)被分為2個層面來進(jìn)行，即虛擬的控制平面和實(shí)際的轉(zhuǎn)發(fā)平面。在虛擬控制平面中，基于用戶需求度量的虛擬興趣包被轉(zhuǎn)發(fā)。而實(shí)際平面中，實(shí)際的興趣包和數(shù)據(jù)包被處理。為了實(shí)現(xiàn)期望的目標(biāo)，虛擬控制平面通過分布式算法操作虛擬興趣包，而產(chǎn)生流率和隊(duì)列長度被用于指導(dǎo)現(xiàn)實(shí)平面中興趣包的轉(zhuǎn)發(fā)以及數(shù)據(jù)包的緩存。

Rossini等認(rèn)為NDN 緩存與轉(zhuǎn)發(fā)之間存在一種緊密的耦合性，并提出一種最近鄰轉(zhuǎn)發(fā)策略[6]。該策略在其實(shí)現(xiàn)過程中融入一種集中控制思想，具體部署如下：每個路由節(jié)點(diǎn)都能獲取完整的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及所有路由節(jié)點(diǎn)的緩存信息，然后通過一種擴(kuò)散的方式找到最近的緩存源，最后再向該源節(jié)點(diǎn)轉(zhuǎn)發(fā)。該轉(zhuǎn)發(fā)策略并沒有對網(wǎng)絡(luò)的實(shí)時(shí)狀態(tài)進(jìn)行感知，同時(shí)該策略隨著網(wǎng)絡(luò)拓?fù)渥兇蠛途W(wǎng)絡(luò)中轉(zhuǎn)發(fā)數(shù)據(jù)量的增加而變得難以實(shí)現(xiàn)。此外，文獻(xiàn)[7]實(shí)現(xiàn)了一種基于勢能的轉(zhuǎn)發(fā)策略，文獻(xiàn)[8]介紹了一種基于熱度的擁塞控制策略，文獻(xiàn)[9]提出一種通過區(qū)分不同服務(wù)的生命時(shí)間來提高QoS的策略。

1.3 基于網(wǎng)絡(luò)端口狀況和內(nèi)容分布共同感知的轉(zhuǎn)發(fā)策略

文獻(xiàn)[10]實(shí)現(xiàn)了一種按需分配的多路徑轉(zhuǎn)發(fā)策略。在轉(zhuǎn)發(fā)處理流程中，端口時(shí)延大小不僅被作為該端口狀況的衡量標(biāo)準(zhǔn)，以用于端口的概率計(jì)算，而且以一種平滑的方式被實(shí)時(shí)更新。盡管該策略通過不同端口下具體內(nèi)容延遲度量的方式實(shí)現(xiàn)了一種網(wǎng)絡(luò)端口狀況和內(nèi)容分布的共同感知，但其實(shí)際的感知效果較差，究其根本，該策略感知的對象是具體內(nèi)容前綴，其層次太低。盡管在文獻(xiàn)[11]中，Cao等針對以上問題提出一種改善方案，即提高網(wǎng)絡(luò)狀態(tài)的實(shí)時(shí)性，但這種方案并沒有從根本上解決上述問題。

2 VIP轉(zhuǎn)發(fā)方案和分析

VIP是虛擬興趣分組(virtual interest packet)的縮寫。VIP架構(gòu)是一種基于NDN的分布式動態(tài)轉(zhuǎn)發(fā)和動態(tài)緩存的架構(gòu)。VIP計(jì)數(shù)器記錄了局部區(qū)域內(nèi)對每個數(shù)據(jù)對象的需求度。如圖1，該架構(gòu)在實(shí)際的轉(zhuǎn)發(fā)平面以外構(gòu)造了一個虛擬平面(該平面上并不轉(zhuǎn)發(fā)實(shí)際的興趣分組和數(shù)據(jù)分組，只轉(zhuǎn)發(fā)VIP)。通過虛擬平面計(jì)算出的轉(zhuǎn)發(fā)端口、傳輸速率來指導(dǎo)實(shí)際平面進(jìn)行轉(zhuǎn)發(fā)，VIP架構(gòu)實(shí)現(xiàn)了網(wǎng)絡(luò)吞吐量的最大化，且設(shè)計(jì)了高效的內(nèi)容緩存方案。

2.1 VIP架構(gòu)的關(guān)鍵組成部分及變量

2.1.1 虛擬興趣分組

VIP架構(gòu)構(gòu)造了一種特殊的分組——虛擬興趣分組，用戶一旦請求某個數(shù)據(jù)對象 ，一個對應(yīng)的VIP便產(chǎn)生了。虛擬平面上虛擬興趣分組的轉(zhuǎn)發(fā)與實(shí)際平面上的興趣分組的轉(zhuǎn)發(fā)存在以下2點(diǎn)不同。

1)粒度。如圖1，VIP對應(yīng)的是一個Data Object，相比Interest Packet對應(yīng)的Data Packet，粒度更大。但由于VIP和Interest Packet內(nèi)主要包含所請求對象/塊的名稱，兩者的大小幾乎相同。VIP的這種設(shè)計(jì)可以使得虛擬平面上的算法復(fù)雜度大大降低。

2)轉(zhuǎn)發(fā)機(jī)制。虛擬平面上不設(shè)置PIT，因此，VIP被轉(zhuǎn)發(fā)后只有在到達(dá)請求數(shù)據(jù)對象的緩存路由器或內(nèi)容源時(shí)，才會停止轉(zhuǎn)發(fā)，到達(dá)這些地方后，VIP被丟棄。在實(shí)際轉(zhuǎn)發(fā)平面上，一個Interest Packet到達(dá)一個路由器節(jié)點(diǎn)，若PIT中已存有對相同數(shù)據(jù)分組的表項(xiàng)，Interest Packet便停止轉(zhuǎn)發(fā)。

圖1 VIP架構(gòu)(IP代表Interest Packets，DP代表Data Packets)Fig.1 VIP framework (IP stands for Interest Packets，DP stands for Data Packets)

2.1.2 VIP計(jì)數(shù)器

在內(nèi)容k的緩存路由器中，VIP計(jì)數(shù)器值較小。到達(dá)內(nèi)容源src(k)處，計(jì)數(shù)器值為0，“水往低處流”是該模型一個很直觀的比喻。因此，一個自然的思路便是，內(nèi)容k的虛擬興趣分組應(yīng)轉(zhuǎn)發(fā)至內(nèi)容k的VIP計(jì)數(shù)器值越低的節(jié)點(diǎn)。結(jié)合文獻(xiàn)[4]，容易得到VIP計(jì)數(shù)器的狀態(tài)轉(zhuǎn)移方程。

2.1.3 虛擬平面

虛擬平面通過VIP的轉(zhuǎn)發(fā)計(jì)算出轉(zhuǎn)發(fā)端口、傳輸速率來指導(dǎo)實(shí)際平面進(jìn)行轉(zhuǎn)發(fā)。由于VIP架構(gòu)是分布式、動態(tài)的，它需要與相鄰節(jié)點(diǎn)交換參數(shù)，這一部分占用了實(shí)際帶寬，但由于虛擬平面的操作都在object層面，這將導(dǎo)致要傳輸?shù)膮?shù)大大減少(相比于chunk)。相鄰節(jié)點(diǎn)在實(shí)際傳輸參數(shù)時(shí)可以把多個參數(shù)的信息放進(jìn)一個傳輸分組中。所以交換參數(shù)所占用的帶寬并不會太大。

2.2 VIP轉(zhuǎn)發(fā)方案

VIP架構(gòu)的虛平面上的轉(zhuǎn)發(fā)方案采用了背壓算法[12]。背壓算法根據(jù)相鄰兩點(diǎn)的積壓差(在本文中即為相鄰節(jié)點(diǎn)同一內(nèi)容VIP計(jì)數(shù)器值的差)來決定調(diào)度策略[13]，當(dāng)有多個傳輸對象要通過一個信道時(shí)，背壓算法優(yōu)先讓積壓差大的內(nèi)容進(jìn)行傳輸。積壓差越大，算法判斷下一跳節(jié)點(diǎn)對該內(nèi)容的傳輸能力更強(qiáng)，應(yīng)優(yōu)先向其傳輸該內(nèi)容；積壓差越小，算法判斷出下一跳節(jié)點(diǎn)的傳輸能力較弱，應(yīng)減少向其傳輸內(nèi)容，或?qū)ふ移渌溌贰?/p>

實(shí)際轉(zhuǎn)發(fā)平面上我們引入一個時(shí)間窗口T，用于計(jì)算過去T時(shí)間內(nèi)鏈路對虛擬興趣分組的平均轉(zhuǎn)發(fā)速率。當(dāng)興趣分組到達(dá)節(jié)點(diǎn)時(shí)，選擇對該內(nèi)容平均轉(zhuǎn)發(fā)速率最大的鏈路進(jìn)行轉(zhuǎn)發(fā)。

2.3 VIP轉(zhuǎn)發(fā)方案不足分析

VIP轉(zhuǎn)發(fā)方案采用的背壓算法能實(shí)現(xiàn)網(wǎng)絡(luò)吞吐量最大化，但背壓算法在網(wǎng)絡(luò)處于輕負(fù)載狀態(tài)時(shí)存在時(shí)延大的缺點(diǎn)。

圖2 網(wǎng)絡(luò)輕載狀態(tài)下節(jié)點(diǎn)VIP計(jì)數(shù)器Fig.2 VIP counts of nodes when the network is lightly loaded

以圖2為例，有節(jié)點(diǎn)a,b,c,x,y,z，假設(shè)此網(wǎng)絡(luò)中傳輸?shù)膬?nèi)容只有一種——k，c為內(nèi)容k的存儲源節(jié)點(diǎn)。節(jié)點(diǎn)a正在請求內(nèi)容k，圓內(nèi)的數(shù)字為當(dāng)前各節(jié)點(diǎn)對內(nèi)容k的VIP計(jì)數(shù)器值。采用虛擬平面上轉(zhuǎn)發(fā)方案，那么和a相連的任一條鏈路上的積壓差均為0，無法給實(shí)際平面提供有效的指導(dǎo)。最終實(shí)際平面上a的路由器將隨機(jī)選擇鏈路用于傳輸k的興趣分組。

因此，在網(wǎng)絡(luò)處于輕負(fù)載狀態(tài)時(shí)，各點(diǎn)中的VIP計(jì)數(shù)器值小且節(jié)點(diǎn)間較為接近，甚至為零，沒有明顯的積壓差，背壓算法效果差甚至失效，當(dāng)實(shí)際的網(wǎng)絡(luò)規(guī)模很大時(shí)，易造成較大的轉(zhuǎn)發(fā)時(shí)延，降低轉(zhuǎn)發(fā)性能。

3 網(wǎng)絡(luò)輕載時(shí)VIP轉(zhuǎn)發(fā)方案優(yōu)化

3.1 優(yōu)化思路

VIP轉(zhuǎn)發(fā)方案計(jì)算積壓差時(shí)，僅利用相鄰的節(jié)點(diǎn)VIP計(jì)數(shù)器值來計(jì)算，即一跳內(nèi)。圖2中，節(jié)點(diǎn)b的鄰居節(jié)點(diǎn)c即為內(nèi)容源，如果在計(jì)算積壓差時(shí)同時(shí)考慮一跳以外的節(jié)點(diǎn)信息[12，14]，使得朝向內(nèi)容源方向的積壓差更大，那么分組將會朝內(nèi)容源方向傳輸，以此改善原VIP架構(gòu)在網(wǎng)絡(luò)輕載時(shí)時(shí)延較大的現(xiàn)象。

為實(shí)現(xiàn)以上目的，可以嘗試對當(dāng)前節(jié)點(diǎn)VIP計(jì)數(shù)器值加上一個偏差量，用于增大朝向內(nèi)容源方向的積壓差。一般可把當(dāng)前節(jié)點(diǎn)距離內(nèi)容源的最小跳數(shù)作為偏差量。

仍以圖2為例，點(diǎn)a，b距離內(nèi)容源c的跳數(shù)分別為2，1；點(diǎn)x，y，z距離點(diǎn)c均為3跳，調(diào)整后的VIP計(jì)數(shù)器值為

再計(jì)算與a相連的各鏈路的積壓差，ab上達(dá)到最大(為1 ，其余均為-1)，因此，點(diǎn)a的請求將沿鏈路(a,b)上傳輸。

3.2 偏差函數(shù)

(1)

偏差函數(shù)的形式為

(2)

值得注意的是，文獻(xiàn)[15]中同樣采用了偏差函數(shù)來對原VIP架構(gòu)轉(zhuǎn)發(fā)方案作出改進(jìn)，本文與其在優(yōu)化的場景、偏差函數(shù)定義存在不同。

本文重點(diǎn)討論網(wǎng)絡(luò)輕負(fù)載場景。在此場景下，周圍節(jié)點(diǎn)VIP隊(duì)長小甚至為0，根據(jù)2.3節(jié)的分析，這將導(dǎo)致背壓算法效果差甚至失效，因此，偏差函數(shù)是基于節(jié)點(diǎn)到內(nèi)容源的最短路徑，而不是基于VIP隊(duì)長。文獻(xiàn)[15]考慮的是一般網(wǎng)絡(luò)場景，在原VIP架構(gòu)基礎(chǔ)上，其希望通過聯(lián)合動態(tài)轉(zhuǎn)發(fā)、緩存、擁塞控制機(jī)制進(jìn)一步提升時(shí)延性能。文獻(xiàn)[15]并不著重關(guān)注網(wǎng)絡(luò)輕負(fù)載，因此，不考慮周圍節(jié)點(diǎn)VIP隊(duì)長小甚至為0的情況，背壓算法仍能正常工作。在該場景中，節(jié)點(diǎn)n關(guān)于內(nèi)容k的偏差函數(shù)可基于周圍節(jié)點(diǎn)VIP隊(duì)長[16]，其中一種具體形式為

(3)

(3)式中，z為穩(wěn)定網(wǎng)絡(luò)的參數(shù)。但由于輕負(fù)載狀態(tài)中缺乏足夠的VIP隊(duì)長信息，此形式的偏差函數(shù)并不適用本文。

3.3 引入偏差函數(shù)后的轉(zhuǎn)發(fā)方案

引入偏差函數(shù)后需要對積壓差的計(jì)算做改變，即鏈路(a,b)上對內(nèi)容k的積壓差為

(4)

調(diào)整積壓差的計(jì)算后，虛平面上的轉(zhuǎn)發(fā)算法再按背壓算法進(jìn)行，再計(jì)算出VIP的最大傳輸速率和實(shí)際傳輸速率，即算法3.1(其中，N為節(jié)點(diǎn)集，K為內(nèi)容集，L為鏈路集，Lk為允許傳輸內(nèi)容k的鏈路集)。

3.4 工作流程

虛擬平面的工作流程如圖3所示，虛擬平面先按照算法3.1完成轉(zhuǎn)發(fā)速率的計(jì)算，再按照VIP狀態(tài)轉(zhuǎn)移方程更新VIP計(jì)數(shù)器值。

圖3 虛擬平面工作流程Fig.3 Flow chart of virtual control plane

算法3.1虛擬平面上的轉(zhuǎn)發(fā)算法。

Step 1: For each link (a,b) do

Step 2: For each k and each (a,b)∈Lkdo

Step 3: For eachkand each (a,b)∈Lkdo

實(shí)際轉(zhuǎn)發(fā)平面上，興趣分組、數(shù)據(jù)分組的轉(zhuǎn)發(fā)流程分別如圖4、圖5所示。傳輸興趣分組時(shí)，依次檢查當(dāng)前節(jié)點(diǎn)的CS，PIT，若命中則分別采取返回?cái)?shù)據(jù)分組、PIT增加接口的操作，并停止轉(zhuǎn)發(fā)Interest。當(dāng)檢查FIB時(shí)，采用虛擬平面計(jì)算的過去時(shí)間窗口內(nèi)平均轉(zhuǎn)發(fā)速率最高的鏈路進(jìn)行轉(zhuǎn)發(fā)。

圖4 實(shí)際平面興趣分組轉(zhuǎn)發(fā)流程Fig.4 Flow chart of Interest forwarding in actual forwarding plane

圖5 實(shí)際平面數(shù)據(jù)分組轉(zhuǎn)發(fā)流程Fig.5 Flow chart of data forwarding in actual forwarding plane

當(dāng)數(shù)據(jù)分組返回時(shí)，節(jié)點(diǎn)檢查PIT決定是否轉(zhuǎn)發(fā)，并依照緩存策略決定是否緩存和如何緩存。

3.5 算法復(fù)雜度對比

原VIP架構(gòu)轉(zhuǎn)發(fā)算法時(shí)間復(fù)雜度為O(|N|2|K|)，其中，|N|，|K|分別代表節(jié)點(diǎn)數(shù)目、內(nèi)容對象數(shù)目[4]。優(yōu)化后的轉(zhuǎn)發(fā)方案算法時(shí)間復(fù)雜度保持不變，理由如下。

針對①，需要計(jì)算每個內(nèi)容源節(jié)點(diǎn)與所有節(jié)點(diǎn)的最短路徑，可轉(zhuǎn)化為解決|K|次單源最短路徑問題，算法復(fù)雜度為O(|N|2|K|)。并且本文假設(shè)網(wǎng)絡(luò)拓?fù)洳蛔?，因此，最短距離可在初始時(shí)計(jì)算完畢，而不必在每次轉(zhuǎn)發(fā)時(shí)計(jì)算。

針對②，偏差函數(shù)值的計(jì)算、VIP計(jì)數(shù)器值的修改均在常數(shù)時(shí)間復(fù)雜度內(nèi)完成。

綜上，優(yōu)化后的轉(zhuǎn)發(fā)方案時(shí)間復(fù)雜度與原方案保持一致，均為O(|N|2|K|)。

4 仿真測試與分析

為對比原VIP架構(gòu)和優(yōu)化后的VIP架構(gòu)的轉(zhuǎn)發(fā)性能，我們設(shè)計(jì)了實(shí)驗(yàn)進(jìn)行仿真。仿真平臺為Microsoft Visual Studio Community 2015，使用C++語言。

實(shí)驗(yàn)采用了圖6所示的GEANT網(wǎng)絡(luò)拓?fù)?，設(shè)置22個節(jié)點(diǎn)，不同內(nèi)容數(shù)300種，并預(yù)先指定每個內(nèi)容的存儲位置，不同節(jié)點(diǎn)間最小距離跳數(shù)預(yù)先計(jì)算完畢。每個節(jié)點(diǎn)在每個時(shí)隙內(nèi)按設(shè)定的請求速率隨機(jī)發(fā)送興趣分組。不考慮PIT定時(shí)器超時(shí)、興趣分組重傳。改進(jìn)的轉(zhuǎn)發(fā)方案和原VIP轉(zhuǎn)發(fā)方案其余仿真參數(shù)保持一致，如表1所示，

圖6 GEANT網(wǎng)絡(luò)拓?fù)銯ig.6 GEANT network topology

表1 仿真參數(shù)Tab.1 Simulation parameter

我們定義時(shí)延為所有節(jié)點(diǎn)從發(fā)送一個興趣分組直到接收到對應(yīng)數(shù)據(jù)分組的歷時(shí)總和。以時(shí)延作為轉(zhuǎn)發(fā)性能指標(biāo)。仿真時(shí)間為100個時(shí)隙，實(shí)驗(yàn)中調(diào)整每個節(jié)點(diǎn)發(fā)送興趣分組的請求速率，記錄總時(shí)延，每個請求速率下進(jìn)行五次實(shí)驗(yàn)取平均值。

仿真結(jié)果如表2、圖7所示。在我們的仿真測試中，綜合6種請求速率，改進(jìn)后的轉(zhuǎn)發(fā)方案在時(shí)延上比原VIP轉(zhuǎn)發(fā)方案降低了24%，當(dāng)請求速率為50 pkt/time slot時(shí)，優(yōu)化效果最明顯，降低了11 980 time slots(降低40.4%)。

表2 仿真結(jié)果Tab.2 Simulation results

圖7 仿真時(shí)延對比圖Fig.7 Simulation comparison chart of time delay

在請求速率為20 pkt/time slot時(shí)，原VIP轉(zhuǎn)發(fā)方案比優(yōu)化后的轉(zhuǎn)發(fā)方案時(shí)延性能稍優(yōu)，以下是可能的解釋：GEANT網(wǎng)絡(luò)拓?fù)湓谝?guī)模上較小，每個節(jié)點(diǎn)的相鄰節(jié)點(diǎn)數(shù)為2—5，原背壓算法在輕負(fù)載狀態(tài)下雖然會隨機(jī)轉(zhuǎn)發(fā)，但仍有相當(dāng)概率轉(zhuǎn)發(fā)至更合適的鏈路——更快地到達(dá)內(nèi)容緩存節(jié)點(diǎn)，而不必花費(fèi)更長的時(shí)間轉(zhuǎn)發(fā)至內(nèi)容源節(jié)點(diǎn)。

實(shí)驗(yàn)結(jié)果表明，本文第3節(jié)優(yōu)化思路是正確的，引入偏差函數(shù)后的轉(zhuǎn)發(fā)方案可以達(dá)到時(shí)延性能優(yōu)化的效果。

5 結(jié)束語

NDN試圖解決TCP/IP網(wǎng)絡(luò)在當(dāng)前環(huán)境下的諸多不適應(yīng)性問題，但對于NDN本身，仍然在不少方面需要進(jìn)行性能優(yōu)化。VIP架構(gòu)具有良好的轉(zhuǎn)發(fā)性能和緩存性能。VIP架構(gòu)在轉(zhuǎn)發(fā)上使用了背壓算法，該算法在網(wǎng)絡(luò)處于輕負(fù)載狀態(tài)時(shí)，將導(dǎo)致傳輸時(shí)延較大。本文基于VIP架構(gòu)的轉(zhuǎn)發(fā)方案，引入偏差函數(shù)進(jìn)行優(yōu)化。仿真實(shí)驗(yàn)對優(yōu)化前后的轉(zhuǎn)發(fā)方案進(jìn)行了實(shí)驗(yàn)對比。實(shí)驗(yàn)結(jié)果顯示，優(yōu)化后的VIP架構(gòu)在時(shí)延上有一定降低。

在轉(zhuǎn)發(fā)問題上，仍然存在諸多難題：如何對不同的內(nèi)容實(shí)現(xiàn)不同的轉(zhuǎn)發(fā)策略？查找時(shí)查詢空間過大如何解決？網(wǎng)絡(luò)中存在擁塞時(shí)如何恢復(fù)？這些問題的解決對NDN轉(zhuǎn)發(fā)性能的提高有很大幫助。

除了使用軟件進(jìn)行實(shí)驗(yàn)仿真，文獻(xiàn)[17]提到了使用一種Banana Pi的實(shí)際實(shí)驗(yàn)平臺，使用Banana Pi進(jìn)行實(shí)驗(yàn)，其結(jié)果將更為真實(shí)，這也是我們下一步的努力方向。

[1] 吳超, 張堯?qū)W, 周悅芝,等. 信息中心網(wǎng)絡(luò)發(fā)展研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(3):455-471.

WU Chao,ZHANG Yaoxue,ZHOU Yuezhi,et al.A Survey for the Development of Information-Centric Networking[J].Chinese Journal of Computers,2015,38(3):455-471.

[2] ZHANG L, AFANASYEV A, BURKE J, et al. Named Data Networking[J]. Acm Sigcomm Computer Communication Review, 2014, 44(3):66-73.

[3] CUI Ying, AFANASYEV A, MOISEENKO I, et al. A Case for Stateful Forwarding Plane[J]. Computer Communications, 2013, 36(7):779-791.

[4] YEH E, HO T, CUI Ying, et al. VIP: A Framework for Joint Dynamic Forwarding and Caching in Named Data Networks[J]. Computer Science, 2014(28):117-126.

[5] POSCH D,RAINER B,HELLWAGNER H.SAF:Stochastic Adaptive Forwarding in Named Data Networking[J].IEEE/ACM Transactions on Networking,2015,PP(99):1-14.

[6] ROSSINI G, ROSSI D. Coupling caching and forwarding: Benefits, analysis, and implementation[C]//Proceedings of the 1st international conference on Information-centric networking. New York: ACM, 2014: 127-136.

[7] EUM S, NAKAUCHI K, MURATA M, et al. CATT:potential based routing with content caching for ICN[C]// Edition of the Icn Workshop on Information-Centric NETWORKING. Helsinki:ACM,2012:49-54.

[8] PARK H, JANG H, KWON T. Popularity-based congestion control in named data networking[C]// International Conf on Ubiquitous & Future Networks. Shanghai: IEEE, 2014:166-171.

[9] WU Tinyu, LEE W T, DUAN C Y, et al. Data Lifetime Enhancement for Improving QoS in NDN [J]. Procedia Computer Science, 2014(32):69-76.

[10] UDUGAMA A, ZHANG XINYI, KULADINITHI K, et al. An On-demand Multi-Path Interest Forwarding strategy for content retrievals in CCN[C]// NOMS 2014-2014 IEEE/IFIP Network Operations and Management Symposium. New York: IEEE, 2014:1-6.

[11] CAO Jianxun, PEI Dan, WU Zhelun, et al. Improving the freshness of NDN forwarding states[C]// Ifip NETWORKING Conference. Krakow, Vienna: IEEE Computer Society, 2016:189-197.

[12] NEELY M J, URGAONKAR R. Optimal Backpressure Routing for Wireless Networks with Multi-Receiver Diversity[C]∥Information Sciences and Systems, 2006, Conference on. Princeton: IEEE, 2007:18-25.

[13] YING Lei, SHAKKOTTAI S, REDDY A, et al. On Combining Shortest-Path and Back-Pressure Routing Over Multihop Wireless Networks[J]. IEEE/ACM Transactions on Networking, 2009, 19(3):841-854.

[14] NEELY M J. Dynamic Power Allocation and Routing for Satellite and Wireless Networks with Time Varying Channels[J]. Massachusetts Institute of Technology, 2003(31):231-241.

[15] CUI Ying, LAI Fan, YEH E, et al. Enhanced VIP Algorithms for Forwarding, Caching, and Congestion Control in Named Data Networks[C]//Global communications conference. CA, USA: IEEE, 2017:1-7.

[16] CUI Ying, YEH E, LIU Ran. Enhancing the delay performance of dynamic backpressure algorithms[C]// Signals, Systems and Computers, 2013 Asilomar Conference on. Pacific Grove: IEEE, 2013:27-31.

[17] RAINER B, POSCH D, LEIBETSEDER A, et al. A Low-Cost NDN Testbed on Banana Pi Routers[J]. IEEE Communications Magazine, 2016, 54(9):105-111.

(編輯：張 誠)