NDN 中名稱查找方法對比

周炳晟，苗 笛，楊俊杰，王優(yōu)祎康

（天津職業(yè)技術師范大學電子工程學院，天津 300222）

目前，互聯網上大量的多媒體內容被廣泛傳輸，并且移動應用的使用也變得越來越流行，因此高速數據傳輸的互聯網流量正在飛速增長。在基于傳統(tǒng)的IP網絡中，IP 地址用來路由、尋址和傳遞數據包。用戶如想訪問互聯網中的信息，應該基于內容提供商和信息請求者的IP 地址，在他們之間建立主機到主機的通信鏈路。如果多個用戶向單個主機頻繁請求相同的內容，則會出現傳輸瓶頸。為了解決這一問題，命名數據網絡（name data networking，NDN）被認為是一個有前途的未來互聯網技術。NDN 是一種互聯網架構，用于將內容請求分發(fā)到網絡中以前集中在內容源上的不同節(jié)點，其采用內容名稱作為網絡地址，使用前綴名稱處理尋址、路由和傳遞的內容問題。NDN 的節(jié)點具有緩存能力，可以臨時存儲通過其路由的內容。如果NDN 節(jié)點接收到已經緩存在其緩存空間中的內容請求，其將立即向相應的用戶提供所請求的內容。NDN 體系結構通過將內容存儲在路由器等網絡節(jié)點中，并重復提供不同用戶請求的內容，有效地減少了網絡流量。NDN 的提出有效地解決網絡擁塞以及網絡安全性不足等諸多問題。

本文分析NDN 內容名稱的命名特點，以及現有NDN 名稱查找策略的發(fā)展過程及其優(yōu)缺點，對不同的查找策略進行綜合對比，并提出NDN 名稱查找策略下一步的研究方向。

1 NDN 的結構及名稱查找

NDN[1]路由器的組件包括：①內容緩存（content store，CS），用于存儲數據以響應新請求者即將到來的興趣；②待定興趣表（pending interest table ，PIT），它是一個用于臨時存儲興趣包直至被滿足的表；③轉發(fā)興趣表（forwarding information database，FIB），通過最長前綴匹配（LPM）將興趣包轉發(fā)給下一個路由器。

NDN 使用2 種類型的包，分別為興趣包和數據包。NDN 通信由消費者驅動，消費者發(fā)送興趣包以請求內容，內容提供商將數據包作為對興趣包的響應轉發(fā)給消費者，如果從消費者到內容提供商的路徑上的任何中間節(jié)點具有滿足興趣包的數據包，則該節(jié)點可以提供該數據包。在通信時，數據包與興趣包沒有任何接口或主機地址[2]。興趣包由消費者發(fā)送，而數據包由興趣包建立的信息傳遞回來。

在傳統(tǒng)IP 網絡的傳輸架構下，隨著數據的大量增加，數據傳輸效率變得低效。而NDN 的結構區(qū)別于傳統(tǒng)的IP 結構，它把內容作為網絡處理的基本對象，用名稱作為數據查找的依據，為數據的高質量傳輸提供了更多的可能性。

NDN 的每個數據包的名稱都是獨一無二的，每個NDN 名稱由多個可變長度的名稱組成。NDN 名稱采用分層的方式來組合構成，如名稱為/a/b/c/有3 個a/、b/、c/，名稱組件被“/”分隔開；其名稱前綴為/a/、/a/b/、和/a/b/c/。采用分層結構能夠聚合名稱，降低規(guī)范命名的工作量，減輕路由的壓力并在一定程度上加快名稱的查找速度。由于網絡內容的龐大，路由會承受越來越大的壓力，造成工作效率的降低，所以名稱的結構也會影響名稱的查找。

盡管NDN 重新構建了以數據為核心的網絡架構，但其轉發(fā)機制與傳統(tǒng)網絡類似，并且名稱前綴依賴于最長前綴匹配（LPM），所以還不足以實現高質量快速查找。使用高速數據包轉發(fā)，NDN 的名稱查找面臨以下挑戰(zhàn)：①長度不固定的名稱。與固定長度的IP地址不同，NDN 名稱類似于統(tǒng)一資源定位符（URL）[3]，它有一個分層結構，由一系列帶任何類型字符的分隔組件組成。另外，名稱的長度不固定，理論上沒有上限。因此，傳統(tǒng)網絡中的查找算法很難延續(xù)到NDN。②大型轉發(fā)表。在NDN 中每個傳入的名稱都會搜索一個帶有一組名稱前綴的前綴數據庫。從這個意義上說，大規(guī)模的名稱前綴數據庫會極大降低性能。事實上，NDN 命名前綴數據庫的規(guī)模至少比傳統(tǒng)網絡大一個數量級。因此，迫切需要專用的名稱查找算法來實現高吞吐量。③頻繁更新。隨著物聯網、云計算和網絡功能虛擬化的發(fā)展，網絡應用必須在極短的時間內響應不同的用戶需求，所請求的數據、拓撲和策略將頻繁改變，使得數萬個新的名稱前綴被動態(tài)地插入名稱前綴數據庫，并且許多舊的名稱前綴將同時被刪除。因此，快速前綴更新是NDN 的一大挑戰(zhàn)。

2 NDN 名稱查找策略

2.1 名稱查找分類

近年來，國內外眾多科研小組圍繞NDN 名稱查找策略開展了系統(tǒng)的研究，研究方向大致分為FIB 名稱查找、PIT 名稱查找以及NDN 路由器的通用解決方案3 類。每個方案中的名稱查找技術大致分為3 種：①基于前綴樹查找方法。前綴樹是一種有序的樹形結構，已廣泛應用于IP 地址查找[4-5]，在IP 領域是一種較為成熟的查找方法。在NDN 領域中前綴樹將NDN 名稱排成樹形結構，從樹根開始依次分叉開到樹葉，然后根據要查找的名稱，從低級別向高級別搜索，直到完全匹配。根據其結構特性的優(yōu)勢，前綴樹可以通過聚合名稱中的前綴冗余減少內存消耗，但前綴樹的查找效率相對較差。②基于哈希表查找方法。哈希表也叫散列表，原理是將關鍵碼值映射到表中的一個位置，以此來加快搜索速度。哈希表查找方法比其他方法要消耗更多內存，這是因為其需要存儲整個名稱字符串來處理哈希沖突并確保正確轉發(fā)，還會造成假陰性的弊端。③基于布隆過濾器查找方法。布隆過濾器可以檢測一個名稱組件是否在一個集合當中。該方法是一種高效查找方法并且內存消耗較低，布隆過濾器從不生成假陰性，但可能會因哈希沖突而生成假陽性。據調查，目前并沒有關于CS 名稱查找方面的研究文獻，因為CS 原理與FIB 相同。命名數據網絡查找方案分類如表1 所示。

表1 命名數據網絡查找方案分類

2.2 當前解決方案

2.2.1 FIB查找方法

FIB 也稱轉發(fā)信息庫，維護NDN 路由轉發(fā)表的轉發(fā)信息。目前，在FIB 方向基于前綴樹的NDN 名稱查找的相關工作有很多，代表性的有：2014 年，湖南大學Li 等[6]研究了基于FPGA 的加速名稱查找方法（hierarchical aligned transition array，HATA） 來 代 替GPU 名稱查找方法（multi-ATA，MATA）。雖然多對齊轉換數組MATA 有效地提高了查找速度，并且在一定程度上壓縮了儲存空間，但其查找延遲較嚴重。為了解決這一問題，該研究組提出分層對齊過渡數組HATA 來表示名稱樹，在FPGA 平臺上實現了流水線加速NDN 名稱查找。實驗結果表明，內存占比為63.45%，與現有的GPU 解決方案相比，該方法的內存成本降低了90%以上，延遲降低了3 個數量級，吞吐量達到125 MLPS。2016 年，Lee 等[7]提出了一種名為路徑壓縮名稱前綴樹（path-compressed name prefix tree，PC-NPT）來降低內存需求，提高搜索性能。這種新的用于FIB 表查找的結構將路徑壓縮應用于名稱前綴樹中，進行單個子空節(jié)點的壓縮。仿真結果表明，空節(jié)點數減少了97%以上。2016 年，Li 等[8]提出了一種基于多對齊轉換數組（MATA）的P-tire 結構，該結構可以加快名稱查找過程并且解決了轉發(fā)的可擴展性問題。Ptire 結構的LPM 算法能夠提前獲取結束端口，且在不匹配時立刻返回端口。實驗結果表明，P-tire 結構的吞吐量是MATA 的3 倍。

同樣也有一部分FIB 方向基于哈希表的NDN 名稱查找方法，如2014 年，Wang 等[9]提出了一種自適應貪婪策略來搜索最長的匹配前綴（greedy-SPHT）。其優(yōu)點是通過動態(tài)調整搜索路徑來進行應變。該方法不僅可以加快名稱查找速度，還能夠防御名稱的攻擊。該團隊還開發(fā)出一種新型哈希表數據結構，將許多小的稀疏完美哈希表組合成一個更大哈希表，提高了查找速度并且減少了內存的壓力。實驗表明，在3 M 與10 M 條目下greedy-SPHT 的吞吐量達到57.14 MLPS，并且分別將內存消耗顯著降低到72.95 MB 和247.20 MB，內存占比為45.11%。

2013 年，Wang 等[10]提出了單獨使用基于布隆過濾器的FIB 查找方法，該查找方法分為2 個階段。在第一階段，將名稱前綴的長度發(fā)送到布隆過濾器中，并且通過查詢布隆過濾器來確定名稱的最長前綴。在第二階段，根據第一階段的結果，在多個布隆過濾器的簡化組中查找名稱。在本文中使用布隆過濾器進行查找，可以有效減少內存消耗，加速名稱查找。實驗結果表明，NameFilter 在僅使用了237.27 MB 內存的情況下，實現了37 MLPS 的吞吐量，比經典的字符前綴樹查找法快約12 倍，節(jié)省了4 倍內存，內存占比為30.1%。NameFilter 在平均工作負載和繁重工作負載下分別達到37 MSPS 和32.59 MSPS。與其他方法相比，內存消耗占比提高不大，并且NameFilter 的性能取決于前綴長度和路由器接口的數量，只能在特定環(huán)境發(fā)揮優(yōu)勢。

也有很多混合方法，將各個查找方法相融合，取其所長，代表性的有：2015 年，Tan 等[11]為解決內存效率問題，提出了一種名為名稱分裂字符樹法（split name character tree，SNT）。該方法首先將名稱分解成多個組件，然后對這些組件分別進行哈希運算后構建成一個前綴樹，再將該前綴樹分成2 部分，分別對這2部分進行查找。實驗結果表明，SNT 通過哈希計算可以減少約30%的內存開銷，通過分解前綴樹可以進一步減少約30%內存消耗。雖然維護哈希表需要額外的內存成本，但該方法仍將內存效率提高了23%～49%。2015 年，華盛頓大學的Yuan 等[12]提出了一種基于哈希表與二分搜索法的最長名稱前綴匹配（longest name prefix matching，LNPM）設計。在每個節(jié)點，如果在相應的哈希表中找到匹配的前綴，則前進到右子樹來搜索更長的匹配前綴；如果沒有搜索到，那么最長的匹配前綴必須在左子樹中。當到達葉FIB 條目時，則查找過程結束。實驗結果表明，在7 個組件名稱表中使用10 億個最長名稱前綴可以達到6 MLPS 的吞吐量。2017 年，He 等[13]對二分搜索法進行了深入的研究，團隊提出了一種新的算法以確?？焖偎阉髀窂?，并且無需額外的回溯代價和多余的內存消耗。該算法是一種布隆過濾器輔助的二分搜索法（BBS）算法，二分搜索法的散列查找次數比LNPM 少得多，但是在NDN 直接應用可能會占據大量內存，因此BBS 使用布隆過濾器在保持快速查找的同時，還可以減少內存消耗。實驗表明，在查找速度方面，隨著名稱前綴數量的增加，BBS 的速度會比LNPM 的速度有較慢的衰減，BBS 僅比LNPM 增加了4%的內存消耗。2019 年，Wu 等[14]提出名為SNBS（split the name into basis and suffix）的名稱查找方法，將名稱拆分為2 部分，前半部分的組件存儲在計數布隆過濾器CBF 中進行并行查找，降低假陽性發(fā)生的概率，后半部分使用樹形圖來減少樹的長度，這樣隨著前綴名稱數量的增加，其也可以保持相對穩(wěn)定高效的查找性能。實驗表明，SNBS 的吞吐量可以達到10 MLPS。2019 年，Byun 等[15]提出了一種用于FIB 查找的階級優(yōu)先樹算法（LPT）和實現LPT 的2 階段布隆過濾器結構。當搜索LPT 時，如果遇到普通節(jié)點，則記住該級別，然后搜索下一個級別；當沒有后續(xù)節(jié)點時，訪問最后一個匹配級別的哈希表。如果哈希表所返回級別的名稱前綴與輸入的匹配，則可以完成對給定輸入的搜索。2 階段布隆過濾器的前半部分為級別布隆過濾器I-BF 和端口布隆過濾器p-BF。儲存在LPT 的級別信息被編程為I-BF，儲存在FIB 的輸出信息被編程為p-BF。由于所提出的架構足夠小，可以存儲在片內存儲器中，因此僅通過查詢片內布隆過濾器而不訪問片外散列表，FIB 查找性能得到了極大的提高。2020 年，Lee 等[16]提出了一種新的布隆過濾器，名為雙負載布隆過濾器（DLBF），其能夠在單個布隆過濾器中保存成員信息與返回值。本文將PC-NPT 存儲在DLBF 中，用來加速名稱的查找。DLBF 在FIB 的片內，PC-NPT 在片外。且PC-NPT 的每個節(jié)點都被編程到片內DLBF 并存儲在片外FIB 中。仿真結果表明，在使用內存更少的情況下，吞吐量為48.5 MLPS。2020年，Kim 等[17]提出一種方法，該方法將分層哈希表與帕特里夏前綴樹相結合，在每個組件上分層構建多個哈希表，每個哈希表可以動態(tài)變化。在產生哈希沖突時，可以使用帕特里夏前綴樹解決。實驗結果表明，該方法吞吐量可達到14.2 MLPS。

2.2.2 PIT查找方法

PIT 也稱待定信息表，通過上游接受興趣信息與下游接受數據信息的方式參與轉發(fā)過程。在PIT 中，基于前綴樹的查找方法最典型的是在2016 年Saxena等[18]提出的Radient。其將所有傳入的名稱請求分為多個組件，給每個組件分配一個令牌，使所有相同的組件都接受相同的令牌。當名稱的所有組成部分都分配到令牌后，編碼的名稱就存儲到前綴樹中，以便更加快速查找。實驗結果表明，在2 900×104個真實數據中編碼的存儲名稱比不編碼存儲名稱減少了87.63%的內存消耗，比ENPT 方案減少了35.45%的內存消耗，吞吐量為0.051 MLPS。雖然該方法比其他方法減少了更多的內存消耗，但在查找速率以及數據傳輸穩(wěn)定性方面略有不足。

2013 年，So 等[19]提出了基于哈希表的PIT 查找方法SipHash，解決了惡意生成興趣包導致哈希沖突的問題，并發(fā)揮了更好的性能。在FIB 的名稱查找，使用了2 階段LPM 算法。結果表明，在20 GbpsNDN 流量的吞吐量為8.8 MLPS。然而該方法使用哈希表導致了較高的內存成本，內存開銷占比過高。2014 年，Yuan等[20]提出了一種新型PIT，將網絡路由器分為核心路由器與邊緣路由器。核心路由器存儲16 bit 的指紋而不是名稱字符串，邊緣過濾器用來過濾。興趣聚合功能解放了核心路由器，因此即使在指紋沖突發(fā)生時，也能保證數據包得到傳遞。實驗結果表明，該吞吐量為0.83 MLPS，內存消耗為64.49 MB。

同樣有一部分基于布隆過濾器的PIT 查找方法。如在2015 年，Carofiglio 等[21]提出了一種新的實現PIT的方法，該方法開發(fā)了一個PIT 動力學作為相關系統(tǒng)參數函數的分析模型，構建了高速內容路由器實現的實驗平臺研究PIT 動態(tài)，并確認分析結果的準確性，提供最優(yōu)PIT 尺寸的指導方針，并分析具有跟蹤驅動數據包延遲分布的ISP 聚合網絡的情況。實驗結果表明，該方法的內存消耗為70.35 MB，實現了更高的吞吐量。2014 年，Li 等[22]提出了PIT 的增強版MaPIT，提出一種新的數據結構MappingBloomfilter（MBF）來滿足PIT 縮減其大小和快速操作的需求，在MBF 的基礎上提出了MaPIT。實驗結果表明，在片內存儲中減少了99.34%的內存消耗。

2.2.3 NDN路由器查找方法

目前，NDN 路由器的查找方法一般為哈希查找以及布隆過濾器查找。2015 年，Feng 等[23]提出了一種新的編碼機制，將NDN 名稱用拆分運算符分層，在每一層使用哈希增量函數獲得哈希序列，并且通過狀態(tài)轉移數組將哈希函數簡化并且更新，使對名稱的搜索、修改、刪除更加快速。但是，該方法容易使NDN 路由器背負相當大的負載壓力。同樣在2015 年，Dai 等[24]提出一種名為BFAST 的數據索引結構，該結構采用計數布隆過濾器平衡哈希表之間的負載，使每個非空哈希表的前綴數量接近1，這樣減少了查找時間并且提高了查找性能。實驗結果表明，BFAST 的吞吐量可以達到36.41 MLPS，速度分別是NameFilter、NCE 和CCNx的1.27 倍、4.49 倍和12.4 倍，該方法在高負載下查找時間以及查找性能有所減弱。2017 年，Hsu 等[25]采用了一種基于循環(huán)冗余校驗的CRC-32 編碼方案，將所有名稱前綴的長度都適當縮短，并將其部分合并減少名稱前綴識別的次數，從而提高名稱搜索的效率。實驗結果表明，該查找方法將存儲空間減少到26.29%，查找速度比原來的NDN 方法提高了21.63%。然而，該方法與其他查找方法在查找速度與內存開銷占比方面相比仍不占優(yōu)勢。同在2017 年，北京理工大學的Liu等[26]提出一種新的名為CTrie 方法，CTrie 將原來的帕特里夏前綴樹擴展為基于組件和基于字節(jié)的分層名稱前綴樹。實驗結果表明，該結構比基于哈希表的解決方案快3.2 倍，只耗費了38%的內存。該結構適用于為物聯網提供較為彈性的NDN 數據平面。2018 年，Shen 等[27]提出了一種名為CoDE 的高效查找方法，由哈希表和新的數據結構多級二元查找樹EBST（multilevel binary search tree）構成。該方法也擁有防沖突驅動的編碼機制，使其能夠用最少的編碼數量獲得最快的名稱查找與前綴更新。實驗表明，CoDE 的查找速度是NCE 和NameFilter 的12.67 倍與7.36 倍，占用的內存節(jié)省了90.94%和69.79%。

3 綜合對比分析

12 種基于FIB 的查找方法測試結果對比如表2所示，5 種基于PIT 和NDN 路由器的查找方法測試對比分別如表3 和表4 所示。

表2 12 種基于FIB 的查找方法測試結果對比

表3 5 種基于PIT 的查找方法測試結果對比

表4 5 種基于NDN 路由器的查找方法測試結果對比

從表2 可知，對NDN 中的名稱查找方法性能比較以吞吐量與內存占比為主要基準，由于每個方法所比較的對象不同，對于內存消耗，可根據數據集的原始大小來評估內存消耗，吞吐量以MLPS 每秒百萬次搜索為基準來進行對比。

從表3 可知，盡管搜索速度有所提高，但大多數隨機搜索方法依賴于FIB 的重建，可能會導致所謂的回溯問題，從而導致假陰性，以及由于許多無用條目不能及時刪除而造成的內存浪費。

從表4 可知，雖然名稱搜索速度沒有FIB 高，但內存開銷占比明顯減少，可以發(fā)現單純使用某一個方案的查找方法，優(yōu)點和缺點都很明顯。內存消耗少的會產生誤報，內存消耗高，誤報率則隨之降低。綜合查找方案吞吐率和內存開銷雖然沒有明顯的優(yōu)勢，但在查找速度與內存消耗方面非常穩(wěn)定。

FIB 名稱查找是基于LPM 最長前綴匹配算法，PIT 和CS 名稱查找是基于EM 最大期望算法。因為3種組件的原理不同，所以尋找一種合適的處理方案來適應3 種不同組件是比較困難的，因此要分別討論在不同組件上的查找方法，從而最大程度地提高查找效率。

4 結 語

本文整合了FIB、PIT、NDN 路由器的名稱查找方法。分析得出，不同的名稱搜索方案都有比較好的應對未來NDN 網絡挑戰(zhàn)的方法，這些優(yōu)秀的方案共有的特點就是使用2 種及以上的混合查找方法，雖然查找速率不是最快，內存開銷占比不是最佳，但在穩(wěn)定性、有效性、延遲、誤報率等方面有良好表現。本文所研究的NDN 名稱查找方法大多數是在百萬個名稱前綴的基礎上進行實驗，所以不一定完全具有代表性，在未來研究中要多使用更大規(guī)模數據集，實現高速更新。此外，對名稱可擴展性以及低延遲方面還需進一步研究，實現更高質量名稱查找。在未來，NDN 的許多功能特性，如多路徑轉發(fā)、網絡內緩存、安全、可伸縮轉發(fā)以及網絡內緩存等，可以用于網絡應用，如車載通信、軍事通信網絡、會議教育系統(tǒng)、娛樂以及多媒體系統(tǒng)。NDN 在安全性方面也是未來探索研究的一個領域。其中，當用戶節(jié)點和內容提供者之間的所有中間節(jié)點都可以使用內容請求時，攻擊者可以通過監(jiān)視內容請求來跟蹤用戶信息，目前還沒有一個永久性的解決辦法。總之，安全、信任管理和隱私仍然是NDN中一個開放的研究領域。