基于名稱分類的NDN路由可擴展性改進方案

張 進，江凌云

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

命名數據網絡(named data networking，NDN)[1]被認為是一個能夠較好地滿足用戶對信息傳遞需求的新型網絡體系結構。然而，它以數據名稱進行通信在路由可擴展性問題上帶來了相比于傳統TCP/IP網絡更加嚴峻的挑戰[2，3]：實際的網絡規模很大，人們對于信息的請求也很多，會出現數量較多的生產者和消費者，那么路由器節點將需要存儲很多的名稱條目。相比于固定長度的IP地址，NDN不定長度的層次化數據名稱會使得FIB的表項數目成倍地增長，從而造成節點的負載(例如，內存等指標)加大，存在崩潰的隱患。因此，NDN傳統的路由轉發方案并不可靠，需要對其進行修改，使得網絡可以承載更大的規模。然而，目前提出的路由可擴展性改進方案仍然存在著缺陷，例如基于映射的方案缺乏映射細節，基于跟蹤的方案集中點負載更大等等。針對以上缺陷，提出了一種基于名稱分類的路由可擴展性改進方案。

1 相關工作

針對NDN中路由可擴展性的種種難點，專家和學者們提出了一些改進方案，大致可以分為基于映射與封裝的路由可擴展性改進方案和基于跟蹤的路由可擴展性改進方案兩類。

1.1 基于映射與封裝的路由可擴展性改進方案

在傳統IP網絡中，雖然IP地址空間是有限的，但IP轉發(路由)可擴展性一直被認為是互聯網部署早期以來的主要挑戰之一。其中保持路由表大小受控的一個方案是引入一個間接層：通過將不在全局路由表上的地址映射到表上的地址，可以到達不在全局路由表上的地址。這是映射與封裝提案背后的主要思想。這種思想同樣也可以運用到NDN當中，具體如下：

Afanasyev等[4]提出SNAMP機制，它將全局路由前綴放入無默認區域(default free zone，DFZ)FIB中，不在DFZ FIB中的數據名稱可以通過其與全局路由前綴的關聯——鏈接來進行檢索，鏈接將要檢索的數據名稱委托給一個全局路由前綴。而這個前綴委托需要通過NDNS[5]的迭代查詢來獲得。然而，這些文獻并沒有交代映射的具體細節，同時僅依靠映射系統來提高路由可擴展性效果并不明顯。

雙曲線路由具有高可擴展性，因為節點無需維護路由表或FIB，而且除了學習鄰居節點的坐標外，沒有動態的路由更新，因此可以將其運用到NDN網絡中。Lehman等[6]在NDN網絡中采取了雙曲線路由的方式。Yang等[7]通過在分配雙曲坐標的同時綜合考慮節點之間的中心性和內容的流行程度，提出了一種基于內容的雙曲線路由，稱為Pop-Hyper，提高了網絡的路由性能。但是，雙曲線路由在NDN 中的可行性取決于基礎拓撲是否是雙曲線的，這是個尚未探索的問題；另外，作為域間路由，雙曲線路由如何支持路由策略是另一個等待探索的問題；此外，雙曲線路由中興趣包的轉發可能陷入局部最優的情況，限制了它的使用。

Ahmed等[8]提出了一種基于名稱的路由方案αRoute。該方案可擴展并提供內容查找保證。并且對于使用αRoute的Internet域間路由，提出了一種分布式覆蓋到底層映射方案，該方案通過保留覆蓋圖中的鄰接關系來實現底層(AS網絡)中的最短路徑路由。

1.2 基于跟蹤的路由可擴展性改進方案

NDN采用有狀態轉發平面，其保留興趣包所采用的路徑的跟蹤，使數據包跟隨這些“面包屑路徑”以逐跳方式返回數據請求者[9]。一些文獻利用NDN的這一優勢來提高網絡的路由可擴展性，具體如下：

Shi等[10]提出自學習路由方案，其使用有狀態轉發平面為生產者建立消費者發起的路徑跟蹤。在路由過程中，沒有匹配的FIB條目的情況下，興趣包可以以泛洪或隨機單播的方式來到達數據生產者。在數據包返回消費者的路上，沿著跟蹤的每個路由器為相應的數據前綴創建FIB條目，指向數據包的傳入接口。這樣，數據名稱前綴只出現在數據包經過的節點FIB表中，FIB表項數量會有所下降。然而，興趣包通過泛洪或隨機單播的方式傳播會增大網絡負擔，同時減小興趣包命中數據的速度。

Schmidt等[11]引入聚合點(NAC)，其包含所有的名稱前綴，可通過默認路由(最短路徑)到達，內容提供者需通過名稱公告消息(NAM)在NAC處注冊。興趣包也沿默認路由到達NAC，再在NAC中的完整FIB的指引下到達名稱提供者，如若沒有，則進行泛洪。中間節點的FIB表不完整，需要使用自適應管理(基于名稱流行度、附加時間戳等等)。然而，所有路由表項集中在聚合點(NAC)，雖然減小了其它節點的FIB路由表項，但在NAC處的FIB表項將成倍遞增，網絡規模過大時存在隱患。

Zhang等[12]提出一種名為KITE的基于跟蹤的生產者移動性解決方案，同時也可用于解決FIB表項過多的問題。KITE通過在FIB中設置從固定會合服務器(RV)到移動生產者的路徑，實現從移動生產者的數據檢索。具體來講，生產者首先向RV發出簽名的跟蹤興趣包(TI)。RV驗證TI并使用簽名的跟蹤數據包(TD)進行響應，然后返回給移動生產者。在接收TD時，中間路由器創建或更新指向TI輸入接口的數據名稱前綴的FIB條目。興趣包會先到RV查找想要的數據名稱，在RV處FIB表的指引下逐跳到達數據生產者。此時，數據名稱前綴僅出現在跟蹤的FIB中，從而減少了其它節點FIB表項數目。然而，此路由方案過于依賴固定會合服務器(RV)，RV中的路由表項數目遠高于其它節點，存在隱患。

總的來說，這兩類改進方案對網絡的路由可擴展性都有一定的改善，但也存在明顯的不足。基于映射與封裝的方案映射細節沒有給出、僅通過映射系統對FIB表項改進不明顯、映射開銷過大；基于跟蹤的方案將表項集中在某一聚合節點會使得此處的FIB表項數目過多、負載過大。

2 基于名稱分類的路由可擴展性改進方案

本節提出一種基于名稱分類的路由可擴展性改進方案，解決上一節中提到的兩類改進方案缺陷的同時，進一步提高網絡的路由可擴展性。

2.1 總體拓撲結構以及網絡的初始化過程

如圖1所示的網絡拓撲結構，我們假設網絡中存在7個中間路由器、5個生產者、2個名稱集中點，并且所有的網絡中的節點已知網絡拓撲結構，每個中間路由器都有自己本身的名稱前綴，如路由器1的名稱前綴為“/router/1”。全局名稱集中點、非全局名稱集中點是功能強大的存儲設備，其作用與路由器相似，但其存儲功能要優于中間路由器，可以存儲數量較大的名稱條目。接下來詳細介紹網絡的初始化過程。

圖1 總體拓撲結構

2.1.1 生產者主動發布內容公告包

所有生產者沿著到達全局名稱集中點的最短路徑發送內容公告包到全局名稱集中點，內容公告包中包含其可以提供的數據名稱，如圖2中5個生產者的內容公告所示。全局名稱集中點以及內容公告包路徑上的路由器節點根據內容公告包的傳入接口建立FIB表，如圖2中間路由器R2、R3的FIB中只包含生產者2、生產者3、生產者4的前綴條目，不包含生產者1、生產者5的前綴條目。而全局名稱集中點的FIB中包含所有5個生產者的下一跳信息。

圖2 生產者主動發布內容公告后網絡狀態

這一步驟首先在最初生產者主動發布自己可以提供的數據名稱的內容，不需要興趣包通過泛洪方式來尋找生產者，降低了網絡中的流量。其次，數據名稱只出現在內容公告包路徑上的路由器節點的FIB表中，降低了其它網絡中路由器節點的FIB表項數目以及負載。

2.1.2 不流行內容生產者發布不流行內容公告

隨著網絡規模的增大，網絡中生產者、消費者增多，中間路由器節點以及全局名稱集中點的負載和維護的FIB表項數目呈指數增長。這時，流行度較低(被請求頻率較低)的數據名稱的生產者主動發送不流行內容公告包(包括數據名稱以及路由器名稱)到全局內容名稱集中點。起初不流行內容公告包的“路由器名稱”字段是空的，當第一跳路由器節點收到不流行內容公告包時，將其路由器名稱添加到“路由器名稱”字段中。

之后的路由器節點收到此包后首先刪除FIB表中包中攜帶的不流行內容名稱的條目，然后檢索FIB表中有無不流行內容公告包中“路由器名稱”中存儲的路由器名稱的條目，如果有則不做操作，沒有則將包中的路由器名稱與不流行內容公告包到達接口的對應關系添加到FIB表中。全局名稱集中點收到此包后執行相同操作，并將此包轉發給非全局名稱集中點。非全局名稱集中點根據收到的不流行內容公告包，建立一張映射關系表，此表包括不流行數據名稱(非全局路由名稱)與路由器名稱(全局路由名稱)的一一對應關系。

例如，我們假設生產者2、生產者3、生產者4提供的數據內容是不流行的，這3個生產者發送不流行內容公告包到全局名稱集中點。出于簡單直觀的考慮，圖3中只畫出了生產者2、生產者3的不流行內容公告以及它們在網絡中的變化。實際上生產者4也具有不流行內容公告，同樣在網絡中變化，與生產者2、生產者3類似。起初不流行內容公告包的“路由器名稱”是空的，如圖3中生產者2、生產者3旁的不流行內容公告所示。當他們到達第一跳路由器R3時，將R3的路由器名稱“/router/3”添加到包中的“路由器名稱”字段中，并在FIB表中刪除包中的不流行內容名稱條目，再將修改過的不流行內容公告發送給R2，R2收到包后，在其FIB表中刪除這3個不流行內容名稱條目，并將R3的路由器名稱“/router/3”和包的到達接口“face3”添加到FIB表中，之后將此包發送給全局名稱集中點，全局名稱集中點收到此包后執行與R2相同的操作，之后將此包轉發給非全局名稱集中點，非全局名稱集中點根據此包建立映射關系表。

圖3 不流行內容生產者發布不流行內容公告后網絡狀態

這一步驟首先不流行的數據名稱被訪問較少，因此不必在中間路由器節點存儲這些數據名稱和接口的對應關系，特別是在網絡規模增大時。其次，上一步全局路由名稱節點需要維護所有生產者可提供的數據名稱與下一跳接口的對應關系，導致集中點的負載過大，存在隱患。而加入非全局路由名稱集中點可以緩解全局集中點的壓力，使得網絡可以承載更大的規模。

2.2 興趣包處理過程

基于名稱分類的路由可擴展性改進方案的興趣包處理過程也與傳統的興趣包處理過程不同，如圖4所示，具體如下：

圖4 興趣包處理過程

(1)興趣包到達某一路由器節點，首先檢查內容存儲(CS)中有無數據，有則返回數據，沒有則檢查待定興趣表(PIT)中有無興趣包中攜帶的名稱條目，有則添加來源接口，沒有則檢查轉發信息表(FIB)中有無興趣包中攜帶的名稱條目，有則從相應的接口轉發到下一跳節點；

(2)如果FIB表中沒有興趣包中攜帶的名稱條目，則將此興趣包轉發到全局名稱集中點。興趣包到達全局名稱集中點后，檢查全局名稱集中點的FIB表中有無興趣包中攜帶的名稱條目，有則從相應的接口轉發到下一跳節點，沒有則檢查興趣包中是否攜帶轉發提示；

(3)如果興趣包中攜帶轉發提示，則重新檢索FIB表，在其指引下將興趣包轉發到下一跳節點。如果興趣包中不攜帶轉發提示，則將興趣包轉發到非全局名稱集中點；

(4)興趣包到達非全局名稱集中點后，會檢索映射關系表中是否存在其攜帶的名稱條目，如果存在，則將其非全局路由名稱所對應的全局路由名稱作為轉發提示添加到興趣包中，修改過的興趣包重新回到全局名稱集中點，在其FIB表的指引下轉發到下一跳節點；如果不存在，則丟棄此興趣包。

2.3 興趣包處理場景

2.3.1 全局路由名稱興趣包處理

我們考慮兩個請求全局名稱的興趣包，它們分別請求“/tencent/movie”以及“/baidu/picture”數據，如圖5所示。

我們先來處理興趣包1，興趣包1到達中間路由器R4后，查詢CS、PIT、FIB后，都沒有其請求的數據名稱條目，那么中間路由器R4會將其轉發到距離全局名稱集中點最近的中間路由器R1。興趣包1到達中間路由器R1后，同樣檢查其CS、PIT、FIB。在其FIB中找到了其請求的“/tencent/movie”名稱前綴，則在其FIB指引下，從face5接口轉發到達生產者1，如圖5中實線箭頭所示。

圖5 全局路由名稱興趣包的處理

興趣包2同樣到達中間路由器R4后，查詢CS、PIT、FIB后，都沒有其請求的數據名稱條目，那么中間路由器R4會將其轉發到距離全局名稱集中點最近的中間路由器R1，R1的FIB中也沒有其請求的數據名稱條目，R1就將此興趣包轉發至全局名稱集中點，全局名稱集中點的FIB中存在其請求的數據名稱條目，則在其指引下到達R6，再在R6的FIB指引下到達R7，在R7的FIB指引下到達生產者5，如圖5中虛線箭頭所示。

從興趣包1、興趣包2的處理過程可以看到，生產者主動宣告自己可以提供的數據名稱的內容可以有效降低中間路由器的FIB表項數目和負載，同時興趣包找到生產者的時間相比之前通過洪泛等方式建立的網絡來講不會增加甚至更少。

2.3.2 非全局路由名稱興趣包處理

請求非全局路由名稱“/sina/news”的興趣包3到達R4后，查詢R4的CS、PIT、FIB中都無“/sina/news”前綴條目，則R4將其轉發給距離全局名稱集中點最近的R1，R1中同樣沒有此名稱前綴，R1將其轉發給全局名稱集中點，全局名稱集中點查詢后同樣沒有此名稱前綴，則將其轉發給非全局名稱集中點，在非全局名稱集中點的映射關系表中找到了此非全局名稱前綴所對應的全局名稱前綴“/router/3”，將其封裝到興趣包3中作為轉發提示，再將封裝后的興趣包3轉發給全局名稱集中點，全局名稱集中點檢索興趣包3中的轉發提示，找到了“/router/3”所對應的下一跳接口“face3”，通過此接口將興趣包轉發給R2，R2同樣檢索轉發提示通過接口“face3”將興趣包3轉發給R3，R3的FIB中存在其請求的數據名稱前綴“/sina/news”，通過接口“face3”轉發到達生產者3，如圖6中箭頭所示。

圖6 非全局路由名稱興趣包的處理

從興趣包3的處理過程可以看到，請求非全局路由名稱的興趣包相對于請求全局路由名稱的興趣包只是多了一步去非全局名稱集中點查詢的過程，對于興趣包找到生產者的時間幾乎沒有影響，但可以大大減少這中間的路由器以及全局名稱集中點的表項數目和負載，使得網絡可以承載更大的規模，網絡的路由可擴展性得到了改善。

3 實驗和結果

在本節中，我們將對所提出的路由可擴展性方案進行仿真實驗，實驗平臺為ndnSIM[13]，這是NDN團隊開發的針對NDN實驗的開源仿真平臺，它是ns-3的擴展。

3.1 實驗設置

為了得出我們提出的基于名稱分類的路由可擴展性改進方案相對于基于跟蹤的路由可擴展性改進方案[12](只有一個集中點，沒有所謂的非全局路由名稱集中點)在路由可擴展性上的優勢，我們設計了兩個簡易拓撲，如圖7、圖8 所示。每個拓撲都有4個消費者、2個生產者，網絡中的每個鏈路都具有1 Mbps帶寬和10 ms的RTT。在所有情況下，興趣包的大小為40字節，而數據包的大小為1024字節。在拓撲1中，選擇一個中間路由器作為名稱集中點。在拓撲2中，選擇兩個中間路由器，一個作為全局名稱集中點，另一個作為非全局名稱集中點。

圖7 拓撲1

圖8 拓撲2

同時，為了區分流行的內容生產者和不流行的內容生產者，我們規定Dst1為不流行內容生產者、Dst2為流行內容生產者。Src1為請求不流行內容的消費者，Src2、Src3、Src4為請求流行內容的消費者。4個消費者都是每秒發送100個興趣包，轉發策略采用最佳路由策略。由于我們專注于網絡的路由性能，因此我們在仿真實驗中不考慮緩存的影響。

3.2 實驗指標

我們根據ndnSIM仿真平臺可以實驗出來的數據指標，選擇以下3個指標進行仿真實驗。

(1)路由器處理的興趣包的數量：記錄隨著時間的推移，兩套方案的中間路由器處理的興趣包的數量的平均值。處理的興趣包的數量越多代表網絡可以承載更大規模的興趣包的請求，也就意味著網絡的路由可擴展性越強；

(2)時延：興趣包的處理所需要的時間。興趣包處理的越快，網絡就可以處理更多的興趣包，從某種意義上講也是路由可擴展性性能的提升；

(3)丟包率：路由器丟棄的興趣包數目與總的興趣包數目的比值。每個路由器不可能處理完所有的興趣包，一些處理不了的興趣包會將其丟棄，例如全局集中點與非全局集中點都沒有所請求的數據名稱條目。丟包率越低，代表網絡初始化的更加合理。

3.3 實驗結果

3.3.1 路由器處理的興趣包的數量

圖9顯示了我們的方案與基于跟蹤的方案隨著時間的推移路由器處理的興趣包數目的實驗結果。從圖中可以看出，起初兩種方案處理的興趣包數目都很少，在0.5 s-1 s中都急劇增加，后面大體處于穩定的趨勢。從二者的對比情況來看，我們的方案一直比基于跟蹤的方案處理的興趣包的數目更多。這是因為我們的方案將流行內容的興趣包與不流行內容的興趣包分開處理，與之前統一處理的方式相比路由器的負擔會減少，相應的處理的興趣包數量也會增多。

圖9 路由器處理的興趣包數隨時間的變化曲線

3.3.2 時延

在時延方面，ndnSIM可以仿真出消費者興趣包的兩種處理時延：LastDelay、FullDelay。其中，LastDelay表示最后發送的興趣包和接收到的數據包之間的延遲。FullDelay代表發送的第一個興趣包和接收到的數據包之間的延遲(即，包括興趣包重傳的時間)。在圖10中，我們仿真了FullDelay隨著時間的變化，可以看到，基于跟蹤的方案FullDelay隨著時間的增加呈現波動上升趨勢，而我們的方案FullDelay一直處在一個較低的值并保持平穩。在圖11中，我們仿真了LastDelay隨著時間的變化，可以看到，兩種方案的實驗值雖有波動但都保持平穩，我們的方案相對來講時延更低一些。綜上兩個圖可以得到，我們的方案的興趣包需要重傳的次數相對基于跟蹤的方案會少很多，才會導致LastDelay二者相差不大，FullDelay相差懸殊。由此可見，我們的方案更能很好地處理興趣包。

圖10 FullDelay隨時間的變化曲線

圖11 LastDelay隨時間的變化曲線

3.3.3 丟包率

圖12顯示了隨著時間的推移路由器的丟包率的變化趨勢。從圖12中可以看到，兩種方案都呈現上升后平穩的趨勢，在丟包率這一指標來講，二者差別不大，說明兩種方案網絡初始化都很合理，路由器丟包率處在一個正常水平。

圖12 丟包率隨時間的變化曲線

4 結束語

命名數據網絡中的路由可擴展性是一個急需解決的問題，它直接影響到此網絡結構能否運用到實際的大規模環境中。本文從基于映射與封裝的方案以及基于跟蹤的方案的基礎上，針對它們的缺點，提出了一種基于名稱分類的路由可擴展性改進方案。該方案首先讓生產者主動宣告自己可以提供的數據名稱內容到全局名稱集中點，相比于洪泛會降低網絡中興趣包的流量，同時減輕中間路由器的負載；其次引入非全局路由名稱集中點，分擔了全局名稱集中點的壓力，進一步降低其它路由器的負載。實驗結果表明，該方案相比基于跟蹤的方案在路由器可以處理的興趣包的數量、時延等指標上存在優化效果，驗證該方案相比基于跟蹤的方案進一步提升了路由可擴展性性能。下一步，準備從查表結構以及算法出發，提升查表速度，進一步提升網絡的路由可擴展性。