命名數據網絡中的轉發策略研究

楊若冰，馬嚴（. 北京郵電大學網絡技術研究院，北京 00876；. 北京郵電大學，北京 00876）

命名數據網絡中的轉發策略研究

楊若冰1，馬嚴2
（1. 北京郵電大學網絡技術研究院，北京 100876；2. 北京郵電大學，北京 100876）

以信息為中心的網絡（Information Centric Networking，ICN）架構是一個面向未來的互聯網體系結構，它提供了一個更加安全，高效和可擴展的服務。命名數據網絡（Named Data Networking，NDN）是ICN的幾種具體實現方式之一，路由和轉發機制是NDN網絡中的核心。本文對NDN中的幾種轉發策略進行了全方位的分析，通過不同的指標來評估轉發策略的性能，如網絡時延，報文命中距離，報文重傳次數等。實驗使用了ndnSIM進行模擬仿真。從仿真結果中得出，選擇一個單一的最優秀的轉發策略是很困難的，另外，不同的轉發策略的優勢和劣勢也受到網絡環境的較大影響，反之，不同的策略也影響了NDN架構所特有的分布式緩存機制的效果。最后，本文對不同的轉發策略適用的網絡情況進行了分析和總結。

計算機網絡；命名數據網絡；內容中心網絡；轉發策略

0　引言

從社交網絡服務增值到查看和分享數字內容，如視頻、照片、文檔等，因特網不再簡單的提供基本的連接性，而是變成了一個有著大量從內容提供者到內容消費者的內容流的巨大分發網絡。互聯網用戶如今需要的是更快，更高效，更安全的內容入口，而不再關心內容的位置。因此，未來的網絡需要從所關注的數據在哪兒（地址和主機）轉移到數據是什么（用戶和應用關心的內容）。

以內容為中心的網絡[1]是一個以唯一命名的數據為核心的互聯網基礎設施架構。數據獨立于位置、應用、存儲以及各種傳輸方式，并且使用了網絡內部的緩存功能。可以預期的是，這樣的架構會帶來效率的提升，關于信息與帶寬需求的更好的可擴展性，以及網絡在具有挑戰的通信情景中的更好的魯棒性。

目前的互聯網保障的是數據容器的安全，而NDN（Named Data Networking）[2]保障的則是內容的安全。這個設計決策將對數據的信任從對主機的信任解耦[3]，使得一些從根本上可擴展的通信機制成為可能，例如利用自動的緩存機制來優化帶寬消耗的方法。

作為NDN網絡的核心，路由和轉發平面的架構也與IP網絡有著根本上的不同，有狀態的轉發層使得NDN的轉發策略有了更強的可適應性[4]。

1　NDN基礎架構

沙漏體系結構是使最初的互聯網設計美觀大方并且功能強大的核心原則之一，中心是一個通用的網絡層（IP），這個“瘦腰”部分是推動互聯網爆炸式增長的關鍵。NDN保持相同的沙漏形結構，如圖1所示。和今天的IP架構類似，瘦腰部分也是NDN架構的中心。NDN用數據名字來發送數據而非IP地址，這個簡單的變化使得IP和NDN在數據發送的操作上有著巨大的差異。

NDN設計方案中采用了層次化的內容命名機制，類似于目前的URL命名方案。例如，一個由example.com網站發布的視頻的名字為“/example. com/videos/something.mpg”，“/”表示名字組件之間的分隔。而“/example.com”及“/example.com/videos”則可作為內容前綴（prefix）用于路由查找及轉發。這個層級結構用來表現不同的數據片之間的關聯，也保障了路由的可擴展性。

圖1　Internet和NDN的沙漏架構Fig. 1 Internet and NDN Hourglass Architectures

2　NDN的路由轉發

2.1NDN的路由轉發模型

NDN中有兩類數據報文，分別為請求報文（Interest Packet）和數據報文（Data Packet），如圖2。

圖2　NDN包結構Fig. 2 Packets In NDN Architecture

NDN轉發模型主要有三類數據結構，分別為 轉 發 信 息 庫（forwarding information base，FIB）、內容存儲庫（content store，CS）以及未決請求表（pending interest table，PIT），如圖3

所示。FIB保存了路由結點到達內容服務器的下一跳的接口，CS保存路由結點的緩存內容，PIT記錄未得到響應的Interest報文的名字及其到達接口等信息，以便Data報文沿途返回。

NDN的通信是由請求方驅動并主動取回的。內容請求方（Consumer）通過網絡發送一個Interest請求，Interest中含有內容的名字。通過一組路由器傳播Interest，直到找到相應的Data或Interest的生存時間結束。一個Interest數據包可取回最多一個Data數據包。Interest會在傳播路徑上留下狀態信息，Data數據包遵循反向路徑找到數據請求方。

路由轉發過程總結如下：Interest進入，被cache所滿足，直接匹配Content Store中的內容；Interest進入，沒有被cache所滿足，但已存在PIT表中，為抑制Interest在網絡中的重復出現，不進行轉發；Interest進入，沒有被cache所滿足，同時也不在PIT表中，因此在PIT表中增加一個記錄，同時在FIB中進行查詢，通過轉發策略轉發；返回Data數據包，和PIT表中內容匹配，消除表中相應行，存儲在Content Store中，遵循對應Interest的反向路徑轉發。

圖3　NDN路由節點Fig.3 NDN Node

2.2NDN的轉發策略

在NDN的數據層，PIT紀錄了所有未被滿足的Interests和各自進入的接口，當接收到匹配的數據或者發生超時后，相應的PIT項將從表中刪除。保存每一個數據報的狀態這一點和IP無狀態的數據層有著根本上的區別。這些狀態信息使NDN的數據層在處理網絡問題上有著可適應性，同時也能夠更加有效的利用網絡資源。

NDN和傳統的IP網絡不同，傳統的IP網絡的路由層負責各種功能，轉發層只需要根據FIB進行轉發。而NDN中路由層只需要建立最初的FIB表，并且負責網絡和拓撲的長期變化，確保路徑無環、擁塞控制等均由轉發層完成[5]。

NDN的轉發策略是路由器中的決策者，決定是否轉發，在什么時間轉發，以及向哪里轉發某個Interest。目前NDN中核心的兩種轉發策略為洪泛轉發策略（Flooding Strategy）和最優路徑轉發策略（Best Route Strategy），根據網絡的負載和取回數據的延遲之間的權衡選擇不同策略。本文的主要目的為通過兩種主要策略的性能優勢，找到不同策略的適用環境。

洪泛轉發策略中，接收一個Interest請求報文，路由器向FIB表中對應前綴的所有接口轉發該報文。FIB表中的多路徑選項由相應的路由策略在網絡初始建立和網絡拓撲發生變化時寫入[6-8]。

最優路徑轉發策略將Interest轉發給開銷最小的上游節點。之后，如果consumer重發這個Interest，或者相同的Interest從其他下游節點到達，如果在最小轉發間隔的時間內，則新的Interest不會被轉發，否則會被再次轉發。一個再次轉發的Interest被轉發給除了之前使用過的接口之外的開銷最小的下一跳節點。

圖4　GEANT拓撲Fig.4 GEANT Topology

3　實驗及分析

實驗使用ndnSIM[9-10]仿真環境對不同算法進行評估，ndnSIM是基于ns-3的NDN模擬器。我們在實驗中對洪泛，最優路徑策略進行比較，同時分析了網絡內緩存的影響。

拓撲結構采用GEANT（http://www.geant.net/）網絡，如圖4所示。拓撲結構有22個節點，36條鏈路，鏈路間的帶寬設為1Mbps，時延為10ms。為了增加網絡鏈路通信壓力，以體現轉發策略的優劣，實驗設置13個消費者節點，2個生產者節點。Interest的生存時間為2s，重傳時間為50ms。緩存的替換算法為LRU（Least Recently Used）。在模擬中，使用路由策略預先計算了路由路徑，并將結果設置在每一個router上。

實驗所評估的內容為：最優路徑轉發策略（Best Route），啟用網絡緩存的最優路徑轉發策略（Best Route with Caching），洪泛轉發策略（Flooding），啟用網絡緩存的洪泛轉發策略（Flooding with Caching）。

3.1理想狀態下的網絡

設置拓撲中每個consumer每秒發送固定的Interest數量，此時網絡中無擁塞。在不造成超時的情況下，第10s增加了Interest請求。由于沒有請求的超時和重發，consumer發送請求的行為在第10秒停止。

從圖5中可以看出，在網絡無擁塞的情況下，四種情況下的表現基本相同。緩存在此時并沒有明顯起到作用，因為所有的consumers都是同時對同一個數據進行請求的，所以一般情況下對應的數據都是直接從producers返回的。因此每個轉發策略在網絡中啟用緩存和不啟用緩存的性能相同。

圖5　理想狀態下的網絡性能Fig. 5 Network under Ideal Conditions

唯一的不同在于Best Route（ Best Route with Caching）在第10s的Interest發送速率增大之后，接收數據的速率低于Flooding（ Flooding with Caching），平均時延高于Flooding（ Flooding with Caching），這說明在網絡無擁塞的情況下，洪泛策略總能找到更好的路徑，這也在命中距離中有體現。因為每兩個鄰接的routers的鏈路開銷都一樣，在不考慮鏈路交通狀況的情況下，跳數就代表了所走路徑的總開銷。此時由于發送了大量數據包，跳數最短路徑不再是最快的路徑，此時洪泛策略能夠更快地找到跳數多但時延短的路徑。

3.2突發擁塞的網絡

設置拓撲中每個consumer節點在理想網絡狀態的基礎上，首先按照恒定速率發送Interest數據包，在第10s突然增大發送數量，此時網絡中發生了Interest的超時。

3.2.1發送Interest報文的數量

圖6　Consumers每秒發送Interests的總數量Fig. 6 Number of Transmitted Interests

由于Consumer每秒發送Interests的總數量中，包括那些因為超時而重發的Interest包，因此可以看到發送趨勢整體上是在第10s突然增大并且維持到第12s之后開始下降。從發送數量可以看出，Flooding with Caching首先結束Interest的發送，接下來是Flooding，Best Route with Caching，最后是Best Route。

3.2.2接收Data報文的數量

圖7　Consumers每秒接收Data packets的總數量Fig. 7 Number of Received Data Packets

從圖中可以看出，完成總共1000個Interest的發送和數據的接收，Consumer接收Data packets的結束順序與發送Interest的結束順序相同。并且對于同一個轉發策略而言，啟用緩存比不啟用緩存能夠在每秒接收到更多的數據。

3.2.3平均時延

圖8　平均時延Fig. 8 Average Time Delay

時延基本上呈線性增長趨勢，從理想狀態下的網絡中得出，相互之間應該為差異較小的狀態。

3.2.4平均命中距離

以時間為維度來比較每秒的平均命中距離的變化時，由于到后期網絡中每秒發送的Interest較少，樣本不足，因此平均命中距離有較大波動。因為在此例中選擇了計算總的平均命中距離。

通過比較所有Interest的平均命中距離，我們可以得出，網絡內緩存在此時有了很大的作用。Flooding with Caching和 Best Route with Caching都分別優于Flooding和Best Route。這說明有緩存的情況下，Interest可以在離自己更近的節點找到匹配的數據。而Best Route的平均命中距離又小于Flooding，這是因為Best Route總是優先選擇線路開銷最小的路徑，在實驗中即經過的跳數最少的路徑。

3.2.5超時Interest報文的數量

圖9　平均命中距離Fig. 9 Average Hit Distance

圖10　每秒超時Interests的總數量Fig. 10 Timeout Interests

由于洪泛策略會在網絡中創造更多的流量，因此在擁塞剛開始的時候，洪泛策略的擁塞狀況更為嚴重，超時數量遠遠高于最優路徑轉發策略。但由于突發擁塞非常短暫，洪泛策略的超時數量也迅速下降。基本和最優路徑轉發策略持平。而由于洪泛策略的數據可以通過所有可用路徑返回，從3.2.2可用看出，在最初的擁塞情況得到緩解后，能夠到達consumer的Data packet也更多。

同時，在網絡啟用緩存的情況下，超時的數量也相應下降，這是因為consumer可以從相對于producer而言，離自己更近的節點處獲得數據，進而降低了擁塞程度。

3.3連續擁塞的網絡

從3.1和3.2節中可以看出，洪泛策略在網絡負載不過重的情況下，性能都較好，為了對現實中可能發生的持續擁塞的網絡中不同策略的性能進行比較，在這個實驗中，設置拓撲中每個consumer在前兩節的基礎上，從第10s開始發送大量Interest請求并持續一段時間，結果如下。

3.3.1發送Interest報文的數量

從圖11中可以看到consumers從10s開始至12s連續發送500個Interest之后，最優路徑轉發策略的發送數量立刻下降，而洪泛策略由于嚴重的擁塞和超時，接下來仍然保持著較高的發送數量。Best Route首先結束Interest的發送，接下來是Best Route with Caching，Flooding with Caching，最后是Flooding。

圖11 Consumers每秒發送Interests的總數量Fig. 11 Number of Transmitted Interests

3.3.2接收Data報文的數量

在本次試驗中，首先完成所有包發送和接收的是Best Route，接下來是Best Route with Caching，Flooding with Caching，最后是Flooding，與3.3.1中的結束順序相同。從擁塞初始發生的時間點可以看出，Best Route和Best Route with Caching的成功接收數據數量最高，Flooding with Caching次之，Flooding最后。

圖12　Consumers每秒接收Data Packets的總數量Fig. 12 Number of Received Data Packets

Best Route和Best Route with Caching在連續擁塞的網絡中表現差異不大，一方面是由于緩存的過程造成了一定的資源消耗，再者是因為實驗中所有節點對相同數據的請求都是在按同樣順序發送的（除了超時重傳），在最優路徑上的緩存效果并不十分明顯。

3.3.3平均時延

平均時延仍然是近似線性增長，由于平均時延計算的是最終成功返回匹配數據的請求，并且是從第一次發送某Interest開始計時，最優路徑策略略高于洪泛策略。

圖13　平均時延Fig. 13 Average Time Delay

3.3.4平均命中距離

類似于3.2節中的結果，啟用網絡緩存時的平均命中距離均小于不啟用緩存時的對應數據。Flooding with Caching由于使用洪泛的方式發送請求，一個返回的數據可以緩存在多個節點上，因此優于Best Route with Caching。

而關于Flooding和 Best Route，通過實驗中的觀測，隨著實驗的進行，Flooding策略的平均命中距離變化并不明顯，而Best Route每秒的平均命中距離在不斷上升后保持了一個較高的平均跳數，這是由于原本在FIB中優先性高的路徑由于發生了超時而被標記為不可用的，而經過的跳數高因而優先級低的路徑被Best Route啟用并且保持使用。

圖14　平均命中距離Fig. 14 Average Hit Distance

3.3.5超時Interest報文的數量

每秒的超時數量印證了通過每秒發送Interest和接收Data的數量得出的結論。在連續的擁塞網絡中，洪泛策略會造成更加嚴重的請求超時。Flooding超時最為嚴重，Flooding with Caching次之，而Best Route和Best Route with Caching的請求超時數量類似。

圖15　每秒超時Interests的總數量Fig. 15 Timeout Interests

4　結論

在相同的網絡狀況下，洪泛策略總是能找到最優的路徑來取回數據，從實驗一也可以看出這一點，在網絡無壓力的情況下，洪泛策略的時延最小。但與此同時，洪泛策略在網絡中同時發出的多個Interest報文將導致網絡產生大量的冗余流量，當 NDN 網絡連接度較高時，這種冗余現象會更加明顯。

最優路徑轉發策略是由路由算法預先在FIB設置了多條路徑以及每條路徑對應的優先級。由于網絡狀況的變化，在一個Interest的轉發過程中，節點所選擇的FIB表中的最優路徑并不一定是此時網絡中的最優路徑，因而對于網絡變化會有一定的反應延遲。但與洪泛策略相比，最優路徑轉發策略大大的降低了網絡中的負載，對于擁塞的網絡，不會造成更大的網絡負擔。

在普遍啟用了網絡內緩存的情況下，最優路徑轉發策略雖然在一定程度上能夠減少網絡的冗余流量，但未考慮周圍節點可能存在的緩存內容，因此當周圍節點有對應的緩存內容時，最優路徑轉發策略也不一定是最好的。而洪泛策略總是能匹配到離請求節點最近的數據。

實驗表明一個單獨的固定協議并不適用于所有的網絡狀況。在網絡沒有擁塞，并且洪泛策略也不會產生擁塞的情況下，洪泛策略是最優的，它總能找到所有可用的路徑，并且從最優的路徑中返回數據給請求節點。而在有突發擁塞的網絡中，洪泛策略也能在擁塞程度迅速下降后，保持相對更高的收發數據速率。但在持續擁塞的網絡中，由于洪泛策略使擁塞的網絡更加擁塞，導致網絡負載急劇增長，更加容易造成網絡的癱瘓。而此時最優路徑策略的性能更優，因為最優路徑策略在一條路徑發生問題時，會自動的使用下一條可用路徑。在不造成網絡負擔的情況下，對網絡進行了自動的適應，這種由多路帶來的可適應性轉發的能力在嚴重擁塞的網絡情況下工作的更好。

實驗中，網絡內緩存的啟用也對算法性能有一定的影響，緩存功能一方面能夠提供更小的命中距離，更低的時延，另一方面也會造成資源的消耗。實驗中采取LRU算法對緩存內容進行更替，這就使得網絡節點需要對每一個接收到的Data packet進行保存和替換。但同時也要考慮到，網絡內緩存不僅可以在網絡擁塞的情況下起作用，對于其他一些應用場景也有著重要意義。根據小世界路由法則，一定范圍的節點在某在一段時間內可能會請求同樣的數據，而緩存能夠加速這一內容分發過程。

由于并沒有一個最優的轉發策略，因此，router也可以在不同的場景上應用不同的策略，例如某個Interest的第一次轉發只轉發給最優的路徑；而當發生重傳時，將Interest同步轉發給多個可用的接口；當接收到NACK時，將Interest轉發給除了接收到NACK的上游router以外的其他router，將數據流分散到其他可用的接口；同時，也可以定期的將Interest同時轉發給目前不可用的接口，對接口進行主動探測，得到接口對應的鏈路情況。

更進一步的想法是，NDN router可以對不同的前綴采用不同的轉發策略。例如在網絡負載較輕的情況下，對于一段時間內請求較多的前綴，采取洪泛策略，可以更多的在緩存中命中匹配的數據。此外，網絡中不同的節點也可能采用不同的轉發策略。例如根據網絡中節點的不同聯通度，節點周圍的緩存能力狀況，來制定相應的轉發策略。

關于轉發策略的實驗研究對于未來NDN路由轉發的研究方向，以及評估標準有著一定的指導意義。對于研究一個綜合洪泛策略和最優路徑轉發策略優勢的新的轉發策略，提供了一定的理論支持。例如更低的網絡負載，更高的緩存命中率等更加適用于NDN網絡的路由轉發策略。

[1] Ahlgren B，Dannewitz C，Imbrenda C，et al. A survey of information-centric networking[J]. Communications Magazine，IEEE，2012，50 （7）: 26-36.

[2] Zhang L，Afanasyev A，Burke J，et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review，2014，44（3）: 66-73.

[3] Wendlandt D，Avramopoulos I，Andersen D G，et al. Don’t secure routing protocols，secure data delivery[J]. Computer Science Department，CMU，2006，40（3）: 61-66.

[4] Yi C，Afanasyev A，Wang L，et al. Adaptive forwarding in named data networking[J]. ACM SIGCOMM computer communication review，2012，42（3）: 62-67.

[5] Yi C，Afanasyev A，Moiseenko I，et al. A case for stateful forwarding plane[J]. Computer Communications，2013，36（7）: 779-791.

[6] 屈鴻.一種基于神經網絡的最短路徑樹生成算法[J].新型工業化，2012，2（2）：62-66.

Qu Hong.A neural network method for the computing of the shortest path tree[J].The Journal of New Industrialization，2012，2（2）：62-66.

[7] 張燦，林昭文，馬嚴. OpenFlow網絡環境中的路由技術研究[J].新型工業化，2014，4（2）：57-61，66.

ZHANG Can，LIN Zhao-wen，MA Yan. Research On Routing Technology In Openflow Environment[J].The Journal of New Industrialization，2014，4（2）：57-61，66.

[8] Hoque A K M，Amin S O，Alyyan A，et al. Nlsr: Named-data link state routing protocol[C]//Proceedings of the 3rd ACM SIGCOMM Workshop on Information-centric Networking. ACM，2013: 15-20.

[9] S. Mastorakis，A. Afanasyev，I. Moiseenko，and L. Zhang. ndnSIM 2.0: A new version of the NDN simulator for NS-3[R]. NDN，Technical Report NDN-0028，2015.

[10] A. Afanasyev，I. Moiseenko，and L. Zhang. ndnSIM: NDN simulator for NS-3[R]. NDN，Technical Report NDN-0005，2012.

Research on Forwarding Strategies in Named Data Networking

YANG Ruo-bing1, MA Yan2
(1.Beijing University of Posts and Telecommunications Institute of Network Technology, Beijing 100876, China; 2. Beijing University of Posts and Telecommunications, Beijing 100876, China)

Information centric networks(ICN) architecture is an architecture for the future use of the Internet, it provides a more secure, efficient and scalable service. Naming data network(NDN) is one of several concrete implementations of ICN. Routing and forwarding mechanism is the core of NDN. In this paper, we focus on analyzing the performance of several forwarding strategies of NDN through different indicators, such as network delay, packet hit distance, and the number of packet retransmissions. A ns-3 based NDN simulator, namely ndnSIM simulator was used to evaluate the performance of considered algorithms. Simulation results show that there is not a single best strategy, every strategy has its pros and cons, and which is severely affected by the network environment. In turn, the strategies affect the effectiveness of the distributed caching mechanisms typically used in the NDN architecture. In the end, we summarize the network situation that suitable for each forwarding strategy.

Computer network; NDN; ICN; Forwarding strategies

10.3969/j.issn.2095-6649.2015.10.009

YANG Ruo-bing, MA Yan. Research on Forwarding Strategies in Named Data Networking[J]. The Journal of New Industrialization，2015，5（10）: 59-67.

楊若冰（1991-），女，碩士研究生，計算機網絡技術與應用

通信聯系人：馬嚴，教授，主要研究方向：下一代互聯網技術

本文引用格式：楊若冰，馬嚴.命名數據網絡中的轉發策略研究[J]. 新型工業化，2015，5（10）：59-67.