NDN中名稱查找方法對(duì)比

周炳晟，苗笛，楊俊杰，王優(yōu)祎康（天津職業(yè)技術(shù)師范大學(xué)電子工程學(xué)院，天津300222）目前，互聯(lián)網(wǎng)上大量的多媒體內(nèi)容被廣泛傳輸，并且移動(dòng)應(yīng)用的使用也變得越來越流行，因此高速數(shù)據(jù)傳輸?shù)幕ヂ?lián)網(wǎng)流量正在飛速增長。在基于傳統(tǒng)的IP網(wǎng)絡(luò)中，IP地址用來路由、尋址和傳遞數(shù)據(jù)包。用戶如想訪問互聯(lián)網(wǎng)中的信息，應(yīng)該基于內(nèi)容提供商和信息請(qǐng)求者的IP地址，在他們之間建立主機(jī)到主機(jī)的通信鏈路。如果多個(gè)用戶向單個(gè)主機(jī)頻繁請(qǐng)求相同的內(nèi)容，則會(huì)出現(xiàn)傳輸瓶頸。為了解決這一問題，命名數(shù)據(jù)網(wǎng)絡(luò)（namedatanetworking，NDN）被認(rèn)為是一個(gè)有前途的未來互聯(lián)網(wǎng)技術(shù)。NDN是一種互聯(lián)網(wǎng)架構(gòu)，用于將內(nèi)容請(qǐng)求分發(fā)到網(wǎng)絡(luò)中以前集中在內(nèi)容源上的不同節(jié)點(diǎn)，其采用內(nèi)容名稱作為網(wǎng)絡(luò)地址，使用前綴名稱處理尋址、路由和傳遞的內(nèi)容問題。NDN的節(jié)點(diǎn)具有緩存能力，可以臨時(shí)存儲(chǔ)通過其路由的內(nèi)容。如果NDN節(jié)點(diǎn)接收到已經(jīng)緩存在其緩存空間中的內(nèi)容請(qǐng)求，其將立即向相應(yīng)的用戶提供所請(qǐng)求的內(nèi)容。NDN體系結(jié)構(gòu)通過將內(nèi)容存儲(chǔ)在路由器等網(wǎng)絡(luò)節(jié)點(diǎn)中，并重復(fù)提供不同用戶請(qǐng)求的內(nèi)容，有效地減少了網(wǎng)絡(luò)流量。NDN的提出有效地解決網(wǎng)絡(luò)擁塞以及網(wǎng)絡(luò)安全性不足等諸多問題。本文分析NDN內(nèi)容名稱的命名特點(diǎn)，以及現(xiàn)有NDN名稱查找策略的發(fā)展過程及其優(yōu)缺點(diǎn)，對(duì)不同的查找策略進(jìn)行綜合對(duì)比，并提出NDN名稱查找策略下一步的研究方向。1NDN的結(jié)構(gòu)及名稱查找NDN[1]路由器的組件包括：①內(nèi)容緩存（contentstore，CS），用于存儲(chǔ)數(shù)據(jù)以響應(yīng)新請(qǐng)求者即將到來的興趣；②待定興趣表（pendinginteresttable，PIT），它是一個(gè)用于臨時(shí)存儲(chǔ)興趣包直至被滿足的表；③轉(zhuǎn)發(fā)興趣表（forwardinginformationdatabase，F(xiàn)IB），通過最長前綴匹配（LPM）將興趣包轉(zhuǎn)發(fā)給下一個(gè)路由器。NDN使用2種類型的包，分別為興趣包和數(shù)據(jù)包。NDN通信由消費(fèi)者驅(qū)動(dòng)，消費(fèi)者發(fā)送興趣包以請(qǐng)求內(nèi)容，內(nèi)容提供商將數(shù)據(jù)包作為對(duì)興趣包的響應(yīng)轉(zhuǎn)發(fā)給消費(fèi)者，如果從消費(fèi)者到內(nèi)容提供商的路徑上的任何中間節(jié)點(diǎn)具有滿足興趣包的數(shù)據(jù)包，則該節(jié)點(diǎn)可以提供該數(shù)據(jù)包。在通信時(shí)，數(shù)據(jù)包與興趣包沒有任何接口或主機(jī)地址[2]。興趣包由消費(fèi)者發(fā)送，而數(shù)據(jù)包由興趣包建立的信息傳遞回來。在傳統(tǒng)IP網(wǎng)絡(luò)的傳輸架構(gòu)下，隨著數(shù)據(jù)的大量增加，數(shù)據(jù)傳輸效率變得低效。而NDN的結(jié)構(gòu)區(qū)別于傳統(tǒng)的IP結(jié)構(gòu)，它把內(nèi)容作為網(wǎng)絡(luò)處理的基本對(duì)象，用名稱作為數(shù)據(jù)查找的依據(jù)，為數(shù)據(jù)的高質(zhì)量傳輸提供了更多的可能性。NDN的每個(gè)數(shù)據(jù)包的名稱都是獨(dú)一無二的，每個(gè)NDN名稱由多個(gè)可變長度的名稱組成。NDN名稱采用分層的方式來組合構(gòu)成，如名稱為/a/b/c/有3個(gè)a/、b/、c/，名稱組件被“/”分隔開；其名稱前綴為/a/、/a/b/、和/a/b/c/。采用分層結(jié)構(gòu)能夠聚合名稱，降低規(guī)范命名的工作量，減輕路由的壓力并在一定程度上加快名稱的查找速度。由于網(wǎng)絡(luò)內(nèi)容的龐大，路由會(huì)承受越來越大的壓力，造成工作效率的降低，所以名稱的結(jié)構(gòu)也會(huì)影響名稱的查找。盡管NDN重新構(gòu)建了以數(shù)據(jù)為核心的網(wǎng)絡(luò)架構(gòu)，但其轉(zhuǎn)發(fā)機(jī)制與傳統(tǒng)網(wǎng)絡(luò)類似，并且名稱前綴依賴于最長前綴匹配（LPM），所以還不足以實(shí)現(xiàn)高質(zhì)量快速查找。使用高速數(shù)據(jù)包轉(zhuǎn)發(fā)，NDN的名稱查找面臨以下挑戰(zhàn)：①長度不固定的名稱。與固定長度的IP地址不同，NDN名稱類似于統(tǒng)一資源定位符（URL）[3]，它有一個(gè)分層結(jié)構(gòu)，由一系列帶任何類型字符的分隔組件組成。另外，名稱的長度不固定，理論上沒有上限。因此，傳統(tǒng)網(wǎng)絡(luò)中的查找算法很難延續(xù)到NDN。②大型轉(zhuǎn)發(fā)表。在NDN中每個(gè)傳入的名稱都會(huì)搜索一個(gè)帶有一組名稱前綴的前綴數(shù)據(jù)庫。從這個(gè)意義上說，大規(guī)模的名稱前綴數(shù)據(jù)庫會(huì)極大降低性能。事實(shí)上，NDN命名前綴數(shù)據(jù)庫的規(guī)模至少比傳統(tǒng)網(wǎng)絡(luò)大一個(gè)數(shù)量級(jí)。因此，迫切需要專用的名稱查找算法來實(shí)現(xiàn)高吞吐量。③頻繁更新。隨著物聯(lián)網(wǎng)、云計(jì)算和網(wǎng)絡(luò)功能虛擬化的發(fā)展，網(wǎng)絡(luò)應(yīng)用必須在極短的時(shí)間內(nèi)響應(yīng)不同的用戶需求，所請(qǐng)求的數(shù)據(jù)、拓?fù)浜筒呗詫㈩l繁改變，使得數(shù)萬個(gè)新的名稱前綴被動(dòng)態(tài)地插入名稱前綴數(shù)據(jù)庫，并且許多舊的名稱前綴將同時(shí)被刪除。因此，快速前綴更新是NDN的一大挑戰(zhàn)。2NDN名稱查找策略2.1名稱查找分類近年來，國內(nèi)外眾多科研小組圍繞NDN名稱查找策略開展了系統(tǒng)的研究，研究方向大致分為FIB名稱查找、PIT名稱查找以及NDN路由器的通用解決方案3類。每個(gè)方案中的名稱查找技術(shù)大致分為3種：①基于前綴樹查找方法。前綴樹是一種有序的樹形結(jié)構(gòu)，已廣泛應(yīng)用于IP地址查找[4-5]，在IP領(lǐng)域是一種較為成熟的查找方法。在NDN領(lǐng)域中前綴樹將NDN名稱排成樹形結(jié)構(gòu)，從樹根開始依次分叉開到樹葉，然后根據(jù)要查找的名稱，從低級(jí)別向高級(jí)別搜索，直到完全匹配。根據(jù)其結(jié)構(gòu)特性的優(yōu)勢(shì)，前綴樹可以通過聚合名稱中的前綴冗余減少內(nèi)存消耗，但前綴樹的查找效率相對(duì)較差。②基于哈希表查找方法。哈希表也叫散列表，原理是將關(guān)鍵碼值映射到表中的一個(gè)位置，以此來加快搜索速度。哈希表查找方法比其他方法要消耗更多內(nèi)存，這是因?yàn)槠湫枰鎯?chǔ)整個(gè)名稱字符串來處理哈希沖突并確保正確轉(zhuǎn)發(fā)，還會(huì)造成假陰性的弊端。③基于布隆過濾器查找方法。布隆過濾器可以檢測一個(gè)名稱組件是否在一個(gè)集合當(dāng)中。該方法是一種高效查找方法并且內(nèi)存消耗較低，布隆過濾器從不生成假陰性，但可能會(huì)因哈希沖突而生成假陽性。據(jù)調(diào)查，目前并沒有關(guān)于CS名稱查找方面的研究文獻(xiàn)，因?yàn)镃S原理與FIB相同。命名數(shù)據(jù)網(wǎng)絡(luò)查找方案分類如表1所示。表1命名數(shù)據(jù)網(wǎng)絡(luò)查找方案分類2.2當(dāng)前解決方案2.2.1FIB查找方法FIB也稱轉(zhuǎn)發(fā)信息庫，維護(hù)NDN路由轉(zhuǎn)發(fā)表的轉(zhuǎn)發(fā)信息。目前，在FIB方向基于前綴樹的NDN名稱查找的相關(guān)工作有很多，代表性的有：2014年，湖南大學(xué)Li等[6]研究了基于FPGA的加速名稱查找方法（hierarchicalalignedtransitionarray，HATA）來代替GPU名稱查找方法（multi-ATA，MATA）。雖然多對(duì)齊轉(zhuǎn)換數(shù)組MATA有效地提高了查找速度，并且在一定程度上壓縮了儲(chǔ)存空間，但其查找延遲較嚴(yán)重。為了解決這一問題，該研究組提出分層對(duì)齊過渡數(shù)組HATA來表示名稱樹，在FPGA平臺(tái)上實(shí)現(xiàn)了流水線加速NDN名稱查找。實(shí)驗(yàn)結(jié)果表明，內(nèi)存占比為63.45%，與現(xiàn)有的GPU解決方案相比，該方法的內(nèi)存成本降低了90%以上，延遲降低了3個(gè)數(shù)量級(jí)，吞吐量達(dá)到125MLPS。2016年，Lee等[7]提出了一種名為路徑壓縮名稱前綴樹（path-compressednameprefixtree，PC-NPT）來降低內(nèi)存需求，提高搜索性能。這種新的用于FIB表查找的結(jié)構(gòu)將路徑壓縮應(yīng)用于名稱前綴樹中，進(jìn)行單個(gè)子空節(jié)點(diǎn)的壓縮。仿真結(jié)果表明，空節(jié)點(diǎn)數(shù)減少了97%以上。2016年，Li等[8]提出了一種基于多對(duì)齊轉(zhuǎn)換數(shù)組（MATA）的P-tire結(jié)構(gòu)，該結(jié)構(gòu)可以加快名稱查找過程并且解決了轉(zhuǎn)發(fā)的可擴(kuò)展性問題。Ptire結(jié)構(gòu)的LPM算法能夠提前獲取結(jié)束端口，且在不匹配時(shí)立刻返回端口。實(shí)驗(yàn)結(jié)果表明，P-tire結(jié)構(gòu)的吞吐量是MATA的3倍。同樣也有一部分FIB方向基于哈希表的NDN名稱查找方法，如2014年，Wang等[9]提出了一種自適應(yīng)貪婪策略來搜索最長的匹配前綴（greedy-SPHT）。其優(yōu)點(diǎn)是通過動(dòng)態(tài)調(diào)整搜索路徑來進(jìn)行應(yīng)變。該方法不僅可以加快名稱查找速度，還能夠防御名稱的攻擊。該團(tuán)隊(duì)還開發(fā)出一種新型哈希表數(shù)據(jù)結(jié)構(gòu)，將許多小的稀疏完美哈希表組合成一個(gè)更大哈希表，提高了查找速度并且減少了內(nèi)存的壓力。實(shí)驗(yàn)表明，在3M與10M條目下greedy-SPHT的吞吐量達(dá)到57.14MLPS，并且分別將內(nèi)存消耗顯著降低到72.95MB和247.20MB，內(nèi)存占比為45.11%。2013年，Wang等[10]提出了單獨(dú)使用基于布隆過濾器的FIB查找方法，該查找方法分為2個(gè)階段。在第一階段，將名稱前綴的長度發(fā)送到布隆過濾器中，并且通過查詢布隆過濾器來確定名稱的最長前綴。在第二階段，根據(jù)第一階段的結(jié)果，在多個(gè)布隆過濾器的簡化組中查找名稱。在本文中使用布隆過濾器進(jìn)行查找，可以有效減少內(nèi)存消耗，加速名稱查找。實(shí)驗(yàn)結(jié)果表明，NameFilter在僅使用了237.27MB內(nèi)存的情況下，實(shí)現(xiàn)了37MLPS的吞吐量，比經(jīng)典的字符前綴樹查找法快約12倍，節(jié)省了4倍內(nèi)存，內(nèi)存占比為30.1%。NameFilter在平均工作負(fù)載和繁重工作負(fù)載下分別達(dá)到37MSPS和32.59MSPS。與其他方法相比，內(nèi)存消耗占比提高不大，并且NameFilter的性能取決于前綴長度和路由器接口的數(shù)量，只能在特定環(huán)境發(fā)揮優(yōu)勢(shì)。也有很多混合方法，將各個(gè)查找方法相融合，取其所長，代表性的有：2015年，Tan等[11]為解決內(nèi)存效率問題，提出了一種名為名稱分裂字符樹法（splitnamecharactertree，SNT）。該方法首先將名稱分解成多個(gè)組件，然后對(duì)這些組件分別進(jìn)行哈希運(yùn)算后構(gòu)建成一個(gè)前綴樹，再將該前綴樹分成2部分，分別對(duì)這2部分進(jìn)行查找。實(shí)驗(yàn)結(jié)果表明，SNT通過哈希計(jì)算可以減少約30%的內(nèi)存開銷，通過分解前綴樹可以進(jìn)一步減少約30%內(nèi)存消耗。雖然維護(hù)哈希表需要額外的內(nèi)存成本，但該方法仍將內(nèi)存效率提高了23%～49%。2015年，華盛頓大學(xué)的Yuan等[12]提出了一種基于哈希表與二分搜索法的最長名稱前綴匹配（longestnameprefixmatching，LNPM）設(shè)計(jì)。在每個(gè)節(jié)點(diǎn)，如果在相應(yīng)的哈希表中找到匹配的前綴，則前進(jìn)到右子樹來搜索更長的匹配前綴；如果沒有搜索到，那么最長的匹配前綴必須在左子樹中。當(dāng)?shù)竭_(dá)葉FIB條目時(shí)，則查找過程結(jié)束。實(shí)驗(yàn)結(jié)果表明，在7個(gè)組件名稱表中使用10億個(gè)最長名稱前綴可以達(dá)到6MLPS的吞吐量。2017年，He等[13]對(duì)二分搜索法進(jìn)行了深入的研究，團(tuán)隊(duì)提出了一種新的算法以確?？焖偎阉髀窂?，并且無需額外的回溯代價(jià)和多余的內(nèi)存消耗。該算法是一種布隆過濾器輔助的二分搜索法（BBS）算法，二分搜索法的散列查找次數(shù)比LNPM少得多，但是在NDN直接應(yīng)用可能會(huì)占據(jù)大量內(nèi)存，因此BBS使用布隆過濾器在保持快速查找的同時(shí)，還可以減少內(nèi)存消耗。實(shí)驗(yàn)表明，在查找速度方面，隨著名稱前綴數(shù)量的增加，BBS的速度會(huì)比LNPM的速度有較慢的衰減，BBS僅比LNPM增加了4%的內(nèi)存消耗。2019年，Wu等[14]提出名為SNBS（splitthenameintobasisandsuffix）的名稱查找方法，將名稱拆分為2部分，前半部分的組件存儲(chǔ)在計(jì)數(shù)布隆過濾器CBF中進(jìn)行并行查找，降低假陽性發(fā)生的概率，后半部分使用樹形圖來減少樹的長度，這樣隨著前綴名稱數(shù)量的增加，其也可以保持相對(duì)穩(wěn)定高效的查找性能。實(shí)驗(yàn)表明，SNBS的吞吐量可以達(dá)到10MLPS。2019年，Byun等[15]提出了一種用于FIB查找的階級(jí)優(yōu)先樹算法（LPT）和實(shí)現(xiàn)LPT的2階段布隆過濾器結(jié)構(gòu)。當(dāng)搜索LPT時(shí)，如果遇到普通節(jié)點(diǎn)，則記住該級(jí)別，然后搜索下一個(gè)級(jí)別；當(dāng)沒有后續(xù)節(jié)點(diǎn)時(shí)，訪問最后一個(gè)匹配級(jí)別的哈希表。如果哈希表所返回級(jí)別的名稱前綴與輸入的匹配，則可以完成對(duì)給定輸入的搜索。2階段布隆過濾器的前半部分為級(jí)別布隆過濾器I-BF和端口布隆過濾器p-BF。儲(chǔ)存在LPT的級(jí)別信息被編程為I-BF，儲(chǔ)存在FIB的輸出信息被編程為p-BF。由于所提出的架構(gòu)足夠小，可以存儲(chǔ)在片內(nèi)存儲(chǔ)器中，因此僅通過查詢片內(nèi)布隆過濾器而不訪問片外散列表，F(xiàn)IB查找性能得到了極大的提高。2020年，Lee等[16]提出了一種新的布隆過濾器，名為雙負(fù)載布隆過濾器（DLBF），其能夠在單個(gè)布隆過濾器中保存成員信息與返回值。本文將PC-NPT存儲(chǔ)在DLBF中，用來加速名稱的查找。DLBF在FIB的片內(nèi)，PC-NPT在片外。且PC-NPT的每個(gè)節(jié)點(diǎn)都被編程到片內(nèi)DLBF并存儲(chǔ)在片外FIB中。仿真結(jié)果表明，在使用內(nèi)存更少的情況下，吞吐量為48.5MLPS。2020年，Kim等[17]提出一種方法，該方法將分層哈希表與帕特里夏前綴樹相結(jié)合，在每個(gè)組件上分層構(gòu)建多個(gè)哈希表，每個(gè)哈希表可以動(dòng)態(tài)變化。在產(chǎn)生哈希沖突時(shí)，可以使用帕特里夏前綴樹解決。實(shí)驗(yàn)結(jié)果表明，該方法吞吐量可達(dá)到14.2MLPS。2.2.2PIT查找方法PIT也稱待定信息表，通過上游接受興趣信息與下游接受數(shù)據(jù)信息的方式參與轉(zhuǎn)發(fā)過程。在PIT中，基于前綴樹的查找方法最典型的是在2016年Saxena等[18]提出的Radient。其將所有傳入的名稱請(qǐng)求分為多個(gè)組件，給每個(gè)組件分配一個(gè)令牌，使所有相同的組件都接受相同的令牌。當(dāng)名稱的所有組成部分都分配到令牌后，編碼的名稱就存儲(chǔ)到前綴樹中，以便更加快速查找。實(shí)驗(yàn)結(jié)果表明，在2900×104個(gè)真實(shí)數(shù)據(jù)中編碼的存儲(chǔ)名稱比不編碼存儲(chǔ)名稱減少了87.63%的內(nèi)存消耗，比ENPT方案減少了35.45%的內(nèi)存消耗，吞吐量為0.051MLPS。雖然該方法比其他方法減少了更多的內(nèi)存消耗，但在查找速率以及數(shù)據(jù)傳輸穩(wěn)定性方面略有不足。2013年，So等[19]提出了基于哈希表的PIT查找方法SipHash，解決了惡意生成興趣包導(dǎo)致哈希沖突的問題，并發(fā)揮了更好的性能。在FIB的名稱查找，使用了2階段LPM算法。結(jié)果表明，在20GbpsNDN流量的吞吐量為8.8MLPS。然而該方法使用哈希表導(dǎo)致了較高的內(nèi)存成本，內(nèi)存開銷占比過高。2014年，Yuan等[20]提出了一種新型PIT，將網(wǎng)絡(luò)路由器分為核心路由器與邊緣路由器。核心路由器存儲(chǔ)16bit的指紋而不是名稱字符串，邊緣過濾器用來過濾。興趣聚合功能解放了核心路由器，因此即使在指紋沖突發(fā)生時(shí)，也能保證數(shù)據(jù)包得到傳遞。實(shí)驗(yàn)結(jié)果表明，該吞吐量為0.83MLPS，內(nèi)存消耗為64.49MB。同樣有一部分基于布隆過濾器的PIT查找方法。如在2015年，Carofiglio等[21]提出了一種新的實(shí)現(xiàn)PIT的方法，該方法開發(fā)了一個(gè)PIT動(dòng)力學(xué)作為相關(guān)系統(tǒng)參數(shù)函數(shù)的分析模型，構(gòu)建了高速內(nèi)容路由器實(shí)現(xiàn)的實(shí)驗(yàn)平臺(tái)研究PIT動(dòng)態(tài)，并確認(rèn)分析結(jié)果的準(zhǔn)確性，提供最優(yōu)PIT尺寸的指導(dǎo)方針，并分析具有跟蹤驅(qū)動(dòng)數(shù)據(jù)包延遲分布的ISP聚合網(wǎng)絡(luò)的情況。實(shí)驗(yàn)結(jié)果表明，該方法的內(nèi)存消耗為70.35MB，實(shí)現(xiàn)了更高的吞吐量。2014年，Li等[22]提出了PIT的增強(qiáng)版MaPIT，提出一種新的數(shù)據(jù)結(jié)構(gòu)MappingBloomfilter（MBF）來滿足PIT縮減其大小和快速操作的需求，在MBF的基礎(chǔ)上提出了MaPIT。實(shí)驗(yàn)結(jié)果表明，在片內(nèi)存儲(chǔ)中減少了99.34%的內(nèi)存消耗。2.2.3NDN路由器查找方法目前，NDN路由器的查找方法一般為哈希查找以及布隆過濾器查找。2015年，F(xiàn)eng等[23]提出了一種新的編碼機(jī)制，將NDN名稱用拆分運(yùn)算符分層，在每一層使用哈希增量函數(shù)獲得哈希序列，并且通過狀態(tài)轉(zhuǎn)移數(shù)組將哈希函數(shù)簡化并且更新，使對(duì)名稱的搜索、修改、刪除更加快速。但是，該方法容易使NDN路由器背負(fù)相當(dāng)大的負(fù)載壓力。同樣在2015年，Dai等[24]提出一種名為BFAST的數(shù)據(jù)索引結(jié)構(gòu)，該結(jié)構(gòu)采用計(jì)數(shù)布隆過濾器平衡哈希表之間的負(fù)載，使每個(gè)非空哈希表的前綴數(shù)量接近1，這樣減少了查找時(shí)間并且提高了查找性能。實(shí)驗(yàn)結(jié)果表明，BFAST的吞吐量可以達(dá)到36.41MLPS，速度分別是NameFilter、NCE和CCNx的1.27倍、4.49倍和12.4倍，該方法在高負(fù)載下查找時(shí)間以及查找性能有所減弱。2017年，Hsu等[25]采用了一種基于循環(huán)冗余校驗(yàn)的CRC-32編碼方案，將所有名稱前綴的長度都適當(dāng)縮短，并將其部分合并減少名稱前綴識(shí)別的次數(shù)，從而提高名稱搜索的效率。實(shí)驗(yàn)結(jié)果表明，該查找方法將存儲(chǔ)空間減少到26.29%，查找速度比原來的NDN方法提高了21.63%。然而，該方法與其他查找方法在查找速度與內(nèi)存開銷占比方面相比仍不占優(yōu)勢(shì)。同在2017年，北京理工大學(xué)的Liu等[26]提出一種新的名為CTrie方法，CTrie將原來的帕特里夏前綴樹擴(kuò)展為基于組件和基于字節(jié)的分層名稱前綴樹。實(shí)驗(yàn)結(jié)果表明，該結(jié)構(gòu)比基于哈希表的解決方案快3.2倍，只耗費(fèi)了38%的內(nèi)存。該結(jié)構(gòu)適用于為物聯(lián)網(wǎng)提供較為彈性的NDN數(shù)據(jù)平面。2018年，Shen等[27]提出了一種名為CoDE的高效查找方法，由哈希表和新的數(shù)據(jù)結(jié)構(gòu)多級(jí)二元查找樹EBST（multilevelbinarysearchtree）構(gòu)成。該方法也擁有防沖突驅(qū)動(dòng)的編碼機(jī)制，使其能夠用最少的編碼數(shù)量獲得最快的名稱查找與前綴更新。實(shí)驗(yàn)表明，CoDE的查找速度是NCE和NameFilter的12.67倍與7.36倍，占用的內(nèi)存節(jié)省了90.94%和69.79%。3綜合對(duì)比分析12種基于FIB的查找方法測試結(jié)果對(duì)比如表2所示，5種基于PIT和NDN路由器的查找方法測試對(duì)比分別如表3和表4所示。表212種基于FIB的查找方法測試結(jié)果對(duì)比表35種基于PIT的查找方法測試結(jié)果對(duì)比表45種基于NDN路由器的查找方法測試結(jié)果對(duì)比從表2可知，對(duì)NDN中的名稱查找方法性能比較以吞吐量與內(nèi)存占比為主要基準(zhǔn)，由于每個(gè)方法所比較的對(duì)象不同，對(duì)于內(nèi)存消耗，可根據(jù)數(shù)據(jù)集的原始大小來評(píng)估內(nèi)存消耗，吞吐量以MLPS每秒百萬次搜索為基準(zhǔn)來