劉開華，閆　柳，李　卓，宮霄霖，彭　鵬，王彬志

基于神經(jīng)網(wǎng)絡(luò)的命名數(shù)據(jù)網(wǎng)學(xué)習(xí)型FIB研究

劉開華，閆柳，李卓，宮霄霖，彭鵬，王彬志

(天津大學(xué)微電子學(xué)院，天津 300072)

針對(duì)命名數(shù)據(jù)網(wǎng)轉(zhuǎn)發(fā)信息庫快速檢索差異化名稱數(shù)據(jù)、高效存儲(chǔ)轉(zhuǎn)發(fā)信息和有效支持最長(zhǎng)名稱前綴匹配機(jī)制的需求和挑戰(zhàn)，提出了基于神經(jīng)網(wǎng)絡(luò)的命名數(shù)據(jù)網(wǎng)學(xué)習(xí)型FIB整體方案，稱L-FIB．首先，介紹了L-FIB的索引結(jié)構(gòu)Learning Tree，通過使用塔式兩級(jí)神經(jīng)網(wǎng)絡(luò)模型學(xué)習(xí)索引內(nèi)容在存儲(chǔ)器中的分布情況，實(shí)現(xiàn)更均勻的數(shù)據(jù)映射，降低映射沖突，提高存儲(chǔ)效率．其次，研究了L-FIB的存儲(chǔ)結(jié)構(gòu)和名稱數(shù)據(jù)檢索算法，片內(nèi)高速存儲(chǔ)器部署多個(gè)與不同名稱前綴組件數(shù)相對(duì)應(yīng)的索引結(jié)構(gòu)Learning Tree，片外低速存儲(chǔ)器部署多個(gè)與索引結(jié)構(gòu)Learning Tree對(duì)應(yīng)的FIB存儲(chǔ)池，并通過相應(yīng)的名稱數(shù)據(jù)檢索算法實(shí)現(xiàn)對(duì)興趣包的轉(zhuǎn)發(fā)信息檢索和轉(zhuǎn)發(fā)信息更新操作，有效支持了命名數(shù)據(jù)網(wǎng)的最長(zhǎng)名稱前綴匹配機(jī)制，提高了名稱數(shù)據(jù)檢索速度．實(shí)驗(yàn)結(jié)果表明，L-FIB在誤判概率、存儲(chǔ)消耗和吞吐量方面的綜合性能明顯優(yōu)于其他對(duì)比方案．在誤判概率低于1%的條件下，L-FIB的索引結(jié)構(gòu)存儲(chǔ)消耗僅為58.258MB，能夠部署于高速存儲(chǔ)器SRAM上．L-FIB的實(shí)際吞吐量約為11.64×106數(shù)據(jù)包/s，可以滿足當(dāng)前命名數(shù)據(jù)網(wǎng)對(duì)數(shù)據(jù)包快速處理的要求．

命名數(shù)據(jù)網(wǎng)；轉(zhuǎn)發(fā)信息庫；神經(jīng)網(wǎng)絡(luò)；名稱數(shù)據(jù)檢索

互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大，虛擬現(xiàn)實(shí)、全息通信、高清視頻傳輸[1]等全新應(yīng)用在傳統(tǒng)行業(yè)的不斷呈現(xiàn)，加速了互聯(lián)網(wǎng)由“通信信道”向“數(shù)據(jù)處理平臺(tái)”的角色轉(zhuǎn)變[2]．為了應(yīng)對(duì)互聯(lián)網(wǎng)內(nèi)容化、個(gè)性化等未來業(yè)務(wù)需求，國(guó)內(nèi)外許多研究機(jī)構(gòu)都在積極探索未來互聯(lián)網(wǎng)架構(gòu)的革新問題．作為未來互聯(lián)網(wǎng)架構(gòu)的一個(gè)典型范例，命名數(shù)據(jù)網(wǎng)(named data networking，NDN)[3]于2010年被提出，其不僅可以通過使用名稱數(shù)據(jù)實(shí)現(xiàn)互聯(lián)網(wǎng)面向內(nèi)容的通信模式，而且可以通過在網(wǎng)絡(luò)節(jié)點(diǎn)部署內(nèi)容存儲(chǔ)池，實(shí)現(xiàn)真正意義上的內(nèi)容共享，極大地降低網(wǎng)絡(luò)的負(fù)載[4]．因此，命名數(shù)據(jù)網(wǎng)被認(rèn)為是非常具有應(yīng)用前景的未來互聯(lián)網(wǎng)架構(gòu)之一.

在命名數(shù)據(jù)網(wǎng)中，所有通信均由消費(fèi)者驅(qū)動(dòng)，通過交換包含名稱標(biāo)識(shí)的興趣包和數(shù)據(jù)包實(shí)現(xiàn)[5]．為了請(qǐng)求所需數(shù)據(jù)，消費(fèi)者首先向網(wǎng)絡(luò)發(fā)送一個(gè)興趣包，路由器記錄興趣包的傳入接口，并利用興趣包的名稱根據(jù)轉(zhuǎn)發(fā)信息庫(forwarding information base，F(xiàn)IB)[3]轉(zhuǎn)發(fā)，直至到達(dá)含有相應(yīng)數(shù)據(jù)包的網(wǎng)絡(luò)節(jié)點(diǎn)，將該數(shù)據(jù)包發(fā)回給消費(fèi)者[6]．因此，F(xiàn)IB的設(shè)計(jì)直接關(guān)系到命名數(shù)據(jù)網(wǎng)轉(zhuǎn)發(fā)平面的工作性能．然而，由于內(nèi)容名稱不同于IP地址的諸多特征，命名數(shù)據(jù)網(wǎng)的FIB研究面臨著一系列亟待解決的問題和挑戰(zhàn)．其一，F(xiàn)IB以名稱字符串為索引主鍵，具有變長(zhǎng)、無邊界的基本特點(diǎn)[3]，且內(nèi)容名稱在不同應(yīng)用場(chǎng)景下極具個(gè)性化[5]，如何支持差異化名稱快速檢索成為公認(rèn)的難題．其二，F(xiàn)IB條目數(shù)可達(dá)百萬級(jí)別[7]，且需要更多的存儲(chǔ)空間來記錄遠(yuǎn)比IP地址復(fù)雜的內(nèi)容名稱及轉(zhuǎn)發(fā)信息，如何高效地將轉(zhuǎn)發(fā)信息存儲(chǔ)在有限的內(nèi)存中是一個(gè)極具挑戰(zhàn)的問題．其三，命名數(shù)據(jù)網(wǎng)FIB具有不同于IP網(wǎng)絡(luò)的最長(zhǎng)名稱前綴匹配(longest name prefix matching，LNPM)[6]機(jī)制，如何支持這種機(jī)制仍是有待解決的問題．

自2010年命名數(shù)據(jù)網(wǎng)被提出以來，轉(zhuǎn)發(fā)平面FIB的研究和設(shè)計(jì)引起了國(guó)內(nèi)外學(xué)術(shù)界的廣泛關(guān)注．目前針對(duì)FIB的設(shè)計(jì)方案主要基于Trie、哈希表和Bloom filter 3種數(shù)據(jù)結(jié)構(gòu)[6]．例如，Ghasemi等[8]提出NameTrie方案，通過ASCII優(yōu)化來高效存儲(chǔ)轉(zhuǎn)發(fā)信息；Dai等[9]提出CONSERT方案，通過刪除冗余來減少名稱前綴數(shù)量；Lee等[10]提出PC-NPT方案，通過路徑壓縮來優(yōu)化查找速度；Song等[11]提出Binary Patricia Trie方案，通過使用比特級(jí)編碼以支持變長(zhǎng)名稱數(shù)據(jù)檢索和路由表增量更新；Yuan[12]提出FHT方案，利用指紋技術(shù)來壓縮存儲(chǔ)；Yuan等[13]提出Binary Search方案，通過二分查找來提高名稱數(shù)據(jù)檢索效率；Wang等[14]提出NameFilter方案，提出將Bloom filter部署于路由器每個(gè)端口；Dai等[15]提出BFAST方案，將Bloom filter與哈希表組合以映射數(shù)據(jù)地址；Li等[16-17]提出MaFIB和B-MaFIB方案，將Bloom filter與定位數(shù)組和Bitmap組合以實(shí)現(xiàn)數(shù)據(jù)映射．但是，目前提出的FIB設(shè)計(jì)方案難以很好地兼顧存儲(chǔ)消耗和名稱檢索速度，且未充分考慮如何有效支持差異化名稱檢索和LNPM機(jī)制[6]．因此，急需提出新的解決思路，設(shè)計(jì)新穎的FIB整體解決方案，以充分應(yīng)對(duì)上述問題和挑戰(zhàn)．

針對(duì)上述挑戰(zhàn)和研究現(xiàn)狀，本文提出了基于神經(jīng)網(wǎng)絡(luò)的命名數(shù)據(jù)網(wǎng)學(xué)習(xí)型FIB整體方案，稱L-FIB．首先，對(duì)L-FIB的索引結(jié)構(gòu)Learning Tree展開介紹，通過使用塔式兩級(jí)神經(jīng)網(wǎng)絡(luò)模型學(xué)習(xí)索引內(nèi)容在存儲(chǔ)器中的分布情況，實(shí)現(xiàn)更均勻的數(shù)據(jù)映射，降低映射沖突，提高存儲(chǔ)效率．其次，對(duì)L-FIB的存儲(chǔ)結(jié)構(gòu)和名稱數(shù)據(jù)檢索算法進(jìn)行設(shè)計(jì)，通過采用多個(gè)Learning Tree和多級(jí)存儲(chǔ)器的部署模式，有效支持命名數(shù)據(jù)網(wǎng)的LNPM機(jī)制，并提高名稱數(shù)據(jù)的檢索速度．實(shí)驗(yàn)結(jié)果表明，L-FIB在誤判概率、存儲(chǔ)消耗和吞吐量方面的綜合性能明顯優(yōu)于其他對(duì)比方案．

1?FIB的設(shè)計(jì)要素

與IP網(wǎng)絡(luò)不同，命名數(shù)據(jù)網(wǎng)FIB中每個(gè)條目的內(nèi)容為：＜name prefix，stale time，interface ID，routing preference，RTT，status，rate limit＞[7]．每次轉(zhuǎn)發(fā)興趣包，都需要根據(jù)興趣包的內(nèi)容名稱在FIB中檢索相應(yīng)的轉(zhuǎn)發(fā)信息．因此，F(xiàn)IB的設(shè)計(jì)要素包含3點(diǎn)：索引結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)檢索算法[18]．

1.1?索引結(jié)構(gòu)

命名數(shù)據(jù)網(wǎng)FIB索引的主鍵是變長(zhǎng)、無邊界的名稱字符串，比固定長(zhǎng)度的IP地址更加復(fù)雜[3]．應(yīng)用驅(qū)動(dòng)的數(shù)據(jù)命名規(guī)則，不但使內(nèi)容名稱在不同應(yīng)用場(chǎng)景下極具個(gè)性化[5]，更使轉(zhuǎn)發(fā)平面FIB條目數(shù)可達(dá)超百萬級(jí)別[7]．此外，每次轉(zhuǎn)發(fā)興趣包或FIB更新時(shí)，都需要使用相應(yīng)的名稱以實(shí)用的高速在FIB中執(zhí)行檢索操作．因此，如何設(shè)計(jì)可支持差異化名稱檢索，且內(nèi)存消耗小、檢索速度快的索引結(jié)構(gòu)，是FIB設(shè)計(jì)的要素之一．

1.2?存儲(chǔ)結(jié)構(gòu)

目前存儲(chǔ)器技術(shù)中，可快速訪問的存儲(chǔ)器芯片通常存儲(chǔ)空間較小(如SRAM)，而提供較大存儲(chǔ)空間的芯片通常訪問速度較低(如DRAM)[11]．如果只能將FIB部署在具有較大存儲(chǔ)空間的低速存儲(chǔ)器上，那么路由器將很難完成快速轉(zhuǎn)發(fā)操作．因此，如何設(shè)計(jì)適合于當(dāng)前存儲(chǔ)器硬件水平的高效存儲(chǔ)結(jié)構(gòu)，是FIB設(shè)計(jì)的要素之二．

1.3?數(shù)據(jù)檢索算法

不同于IP地址最長(zhǎng)匹配原則，命名數(shù)據(jù)網(wǎng)FIB的數(shù)據(jù)檢索基于LNPM機(jī)制，通過名稱前綴匹配進(jìn)行，以興趣包名稱的每個(gè)分隔符為斷點(diǎn)，按名稱組件粒度找到最長(zhǎng)匹配的名稱前綴[6]．因此，如何設(shè)計(jì)可支持LNPM機(jī)制的名稱數(shù)據(jù)快速檢索算法，是FIB設(shè)計(jì)的要素之三．

2?L-FIB的索引結(jié)構(gòu)Learning Tree

根據(jù)命名數(shù)據(jù)網(wǎng)FIB的研究挑戰(zhàn)和設(shè)計(jì)要素，本文首次提出了基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)型FIB整體方案，稱為L(zhǎng)-FIB．本節(jié)介紹了L-FIB的索引結(jié)構(gòu)Learning Tree，闡述其具體結(jié)構(gòu)以及其中神經(jīng)網(wǎng)絡(luò)模型的參數(shù)選擇．

2.1?Learning Tree基本結(jié)構(gòu)

傳統(tǒng)哈希表因操作速度上的明顯優(yōu)勢(shì)而被廣泛使用，然而，它的不足在于數(shù)據(jù)映射的不均勻性和大量的哈希沖突，這大大降低了存儲(chǔ)效率[6]．鑒于此，Learning Tree通過使用神經(jīng)網(wǎng)絡(luò)來學(xué)習(xí)索引內(nèi)容在存儲(chǔ)器中的分布情況，實(shí)現(xiàn)更均勻的數(shù)據(jù)映射，降低映射沖突，提高存儲(chǔ)效率．具體效果如圖1所示．

圖1?哈希表與Learning Tree映射對(duì)比

Learning Tree實(shí)現(xiàn)均勻映射的原理闡述如下．首先，利用大量?jī)?nèi)容名稱構(gòu)建神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練數(shù)據(jù)集，按照字符串值對(duì)其進(jìn)行排序，并將排序后的序號(hào)作為標(biāo)簽與內(nèi)容名稱一一標(biāo)定．其次，利用該訓(xùn)練集訓(xùn)練神經(jīng)網(wǎng)絡(luò)，學(xué)習(xí)出能反映索引內(nèi)容在存儲(chǔ)器中分布情況的累積分布函數(shù)(cumulative distribution function，CDF)．訓(xùn)練完成后，對(duì)于輸入的數(shù)據(jù)，通過神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)CDF值，將該值乘以映射表的大小即可得到該數(shù)據(jù)在映射表中的具體位置．CDF的均勻分布特性使得數(shù)據(jù)在映射表上的位置必將服從均勻分布.

基于上述思想，Learning Tree的結(jié)構(gòu)設(shè)計(jì)如圖2所示．該結(jié)構(gòu)共包含3個(gè)單元：輸入單元、模型單元和輸出單元．

圖2?Learning Tree基本結(jié)構(gòu)

輸入單元用于將變長(zhǎng)的內(nèi)容名稱轉(zhuǎn)變?yōu)楣潭ňS數(shù)的輸入向量．假設(shè)輸入向量的維數(shù)是，且一個(gè)長(zhǎng)度為的內(nèi)容名稱可以視為一個(gè)維向量．對(duì)于長(zhǎng)度的名稱，令y＝x(0＜)，y＝0(＜)；對(duì)于＞的名稱，將每個(gè)元素拆分為一個(gè)子向量，然后令y等于所有子向量中第個(gè)元素執(zhí)行按位異或運(yùn)算的結(jié)果(0＜)．因此得到維輸入向量．

模型單元設(shè)計(jì)為由小型BP神經(jīng)網(wǎng)絡(luò)(back propagation neural network，BPNN)[19]搭建的塔式兩級(jí)結(jié)構(gòu)，用于分類訓(xùn)練、預(yù)測(cè)CDF值．該塔式結(jié)構(gòu)包括第1級(jí)1個(gè)BPNN、第2級(jí)1000個(gè)BPNN．其中，第1級(jí)BPNN輸出1000個(gè)分類值，第2級(jí)BPNN輸出預(yù)測(cè)的CDF值，以支持轉(zhuǎn)發(fā)平面百萬級(jí)別的數(shù)據(jù)分類索引需求．模型單元的訓(xùn)練過程簡(jiǎn)述如下．假設(shè)BPNN代表模型單元中第級(jí)的第個(gè)BPNN．首先，將訓(xùn)練集分類標(biāo)定為編號(hào)從小到大的若干區(qū)域，對(duì)BPNN1.0進(jìn)行訓(xùn)練．BPNN1.0分類訓(xùn)練結(jié)果的每個(gè)區(qū)域值對(duì)應(yīng)一個(gè)BPNN2.k．隨后，繼續(xù)分別訓(xùn)練第2級(jí)的每個(gè)BPNN2.k，學(xué)習(xí)得到CDF函數(shù)的一個(gè)部分．最終訓(xùn)練完成后，所有BPNN2.k的預(yù)測(cè)范圍將可以覆蓋整個(gè)CDF．即，訓(xùn)練后的塔式神經(jīng)網(wǎng)絡(luò)將是一個(gè)CDF的預(yù)測(cè)函數(shù)．

輸出單元部署一個(gè)Bitmap結(jié)構(gòu)，用于獲得實(shí)際存儲(chǔ)器索引地址．其中，Bitmap被均分為若干個(gè)部分，其中每個(gè)槽記錄名稱數(shù)據(jù)插入該部分的順序，以實(shí)現(xiàn)實(shí)際存儲(chǔ)單元的動(dòng)態(tài)內(nèi)存分配．通過將模型單元已預(yù)測(cè)的CDF值乘以Bitmap中槽的總個(gè)數(shù)，即可得到Bitmap中的映射槽位置．最后，根據(jù)該槽所在部分對(duì)應(yīng)的基地址和該槽中數(shù)字序號(hào)所代表的地址偏移量，即可求得實(shí)際存儲(chǔ)器索引地址．

圖2給出了一個(gè)訓(xùn)練完成后通過Learning Tree進(jìn)行索引的實(shí)例．對(duì)于一個(gè)輸入的NDN內(nèi)容名稱/NDN/TJU/maps，首先將其拆分并執(zhí)行按位異或運(yùn)算，以獲得輸入向量(26，116，98，97，66)．隨后，將該向量輸入到模型單元．假設(shè)BPNN1.0計(jì)算得到的區(qū)域編號(hào)為2，則選擇BPNN2.2進(jìn)行CDF計(jì)算．假設(shè)BPNN2.2計(jì)算得到的CDF值為0.2，則該內(nèi)容名稱在Bitmap中的映射位置為0.2×15(槽個(gè)數(shù))＝3．由于位置3處在Bitmap分塊的第一部分，且其中記錄的數(shù)字序號(hào)為2，所以最終索引內(nèi)容的實(shí)際地址等于第一部分對(duì)應(yīng)的實(shí)際存儲(chǔ)基地址加地址偏移量2．

2.2?模型單元參數(shù)選擇

在Learning Tree的模型單元中，一個(gè)BPNN輸入向量的維數(shù)和隱藏層神經(jīng)元的個(gè)數(shù)會(huì)直接決定神經(jīng)網(wǎng)絡(luò)模型的分類準(zhǔn)確率和輸入沖突率，并影響索引結(jié)構(gòu)的存儲(chǔ)消耗和檢索速度．本節(jié)通過分析不同參數(shù)設(shè)置下BPNN的性能，確定Learning Tree中最佳的BPNN參數(shù)．

參數(shù)分析結(jié)果如圖3所示．圖3(a)表明，當(dāng)輸入向量維數(shù)大于等于5時(shí)，系統(tǒng)的輸入沖突率可遠(yuǎn)遠(yuǎn)低于1%，滿足當(dāng)前互聯(lián)網(wǎng)對(duì)丟包率小于1%的要求[20]；當(dāng)輸入向量維數(shù)小于等于6時(shí)，BPNN的分類準(zhǔn)確率可達(dá)到80%以上．圖3(b)表明，當(dāng)隱藏層神經(jīng)元數(shù)大于等于20時(shí)，分類準(zhǔn)確率可穩(wěn)定在85%左右．此外，考慮到模型的存儲(chǔ)消耗和執(zhí)行速度，參數(shù)選擇應(yīng)使模型盡可能小巧．因此，輸入向量維數(shù)和隱藏層神經(jīng)元個(gè)數(shù)分別確定為5和20，以實(shí)現(xiàn)滿足分類準(zhǔn)確率和輸入沖突率要求的、簡(jiǎn)單可靠的BPNN．

圖3?1個(gè)BPNN在不同參數(shù)設(shè)置下的性能分析

3?L-FIB的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)檢索算法

本節(jié)介紹了L-FIB的存儲(chǔ)結(jié)構(gòu)和名稱數(shù)據(jù)檢索算法．首先闡述其多級(jí)存儲(chǔ)器的部署模式，然后展示其對(duì)興趣包的轉(zhuǎn)發(fā)信息檢索和轉(zhuǎn)發(fā)信息更新的操作流程．

3.1?L-FIB的存儲(chǔ)結(jié)構(gòu)

考慮到當(dāng)前存儲(chǔ)器硬件水平和名稱數(shù)據(jù)檢索速度的需求，L-FIB的存儲(chǔ)結(jié)構(gòu)采用多級(jí)存儲(chǔ)器的部署模式．如圖4所示，該存儲(chǔ)結(jié)構(gòu)由片內(nèi)和片外兩個(gè)存儲(chǔ)單元構(gòu)成．其中，片內(nèi)存儲(chǔ)單元使用高速存儲(chǔ)器，部署多個(gè)與不同名稱前綴組件數(shù)相對(duì)應(yīng)的索引結(jié)構(gòu)Learning Tree，以實(shí)現(xiàn)基于LNPM機(jī)制的名稱數(shù)據(jù)快速索引；片外使用存儲(chǔ)空間較大的低速存儲(chǔ)器，部署多個(gè)與Learning Tree輸出單元對(duì)應(yīng)的FIB存儲(chǔ)池，以存儲(chǔ)實(shí)際轉(zhuǎn)發(fā)信息．此外，對(duì)于片內(nèi)索引結(jié)構(gòu)Learning Tree可能產(chǎn)生的誤判，在片外FIB存儲(chǔ)池中使用鏈地址法來處理沖突，即映射到相同地址的數(shù)據(jù)以鏈表的形式連接．

為了確定片內(nèi)存儲(chǔ)單元中所需部署的索引結(jié)構(gòu)Learning Tree的數(shù)量，需要統(tǒng)計(jì)名稱前綴組件數(shù)的分布特點(diǎn)．統(tǒng)計(jì)結(jié)果如表1所示，對(duì)于200萬條名稱數(shù)據(jù)，名稱前綴組件數(shù)的分布非常集中，組件數(shù)為4的內(nèi)容名稱占總數(shù)的82.34%，組件數(shù)為其他的所有內(nèi)容名稱只占總數(shù)的17.66%．因此，L-FIB的片內(nèi)存儲(chǔ)單元部署兩個(gè)索引結(jié)構(gòu)Learning Tree即可滿足設(shè)計(jì)要求，其中，第1個(gè)Learning Tree對(duì)應(yīng)組件數(shù)為4的內(nèi)容名稱，第2個(gè)Learning Tree對(duì)應(yīng)組件數(shù)為其他的內(nèi)容名稱．

圖4?L-FIB的存儲(chǔ)結(jié)構(gòu)

表1?名稱前綴組件數(shù)統(tǒng)計(jì)

Tab.1 Number of names under different numbers of components

3.2?L-FIB的數(shù)據(jù)檢索算法

命名數(shù)據(jù)網(wǎng)FIB工作機(jī)制包括對(duì)興趣包的轉(zhuǎn)發(fā)信息檢索操作和轉(zhuǎn)發(fā)信息更新操作．因此，本小節(jié)描述了L-FIB的上述操作算法．

L-FIB對(duì)興趣包的轉(zhuǎn)發(fā)信息檢索過程包括以下步驟．

(1) 片內(nèi)輸入處理：輸入名稱前綴，拆分為若干子向量，然后對(duì)所有子向量中相同位置的元素執(zhí)行按位異或運(yùn)算，得到定長(zhǎng)輸入向量．

(2) 片內(nèi)模型運(yùn)算：將定長(zhǎng)輸入向量輸入模型單元，計(jì)算預(yù)測(cè)的CDF值．

(3) 片內(nèi)位置映射：將已預(yù)測(cè)的CDF值乘以Bitmap中槽的總數(shù)，得到Bitmap中的映射槽位置．

(4) 片內(nèi)數(shù)據(jù)存在性判斷：如果該槽的值不為0，則繼續(xù)；如果為0，則說明不在該FIB中，輸出檢索結(jié)果“無法匹配”，結(jié)束．

(5) 片內(nèi)索引地址計(jì)算：根據(jù)該槽所在部分對(duì)應(yīng)的基地址和該槽中數(shù)字序號(hào)所代表的地址偏移量求得索引地址．

(6) 片外轉(zhuǎn)發(fā)信息輸出：根據(jù)索引地址訪問片外FIB存儲(chǔ)池，輸出下一跳路由轉(zhuǎn)發(fā)信息，結(jié)束．

L-FIB對(duì)轉(zhuǎn)發(fā)信息更新的過程包括以下步驟．

(1) 片內(nèi)輸入處理：輸入名稱前綴，拆分為若干子向量，然后對(duì)所有子向量中相同位置的元素執(zhí)行按位異或運(yùn)算，得到定長(zhǎng)輸入向量．

(2) 片內(nèi)模型運(yùn)算：將定長(zhǎng)輸入向量輸入模型單元，計(jì)算預(yù)測(cè)的CDF值．

(3) 片內(nèi)位置映射：將已預(yù)測(cè)的CDF值乘以Bitmap中槽的總數(shù)，得到Bitmap中的映射槽位置，并計(jì)算該槽所在的部分．

(4) 片內(nèi)更新類型判斷：如果更新類型為“添加”，則繼續(xù)；如果為“修改”，則轉(zhuǎn)到(7)；如果為“刪除”，則轉(zhuǎn)到(8)．

(5) 片內(nèi)添加操作：將插入與其前綴長(zhǎng)度對(duì)應(yīng)的Learning Tree中，并計(jì)算索引地址．

(6) 片外添加操作：根據(jù)索引地址訪問片外FIB存儲(chǔ)池，插入相應(yīng)的路由轉(zhuǎn)發(fā)信息，結(jié)束．

(7) 片外修改操作：計(jì)算索引地址，訪問片外FIB存儲(chǔ)池，修改相應(yīng)的路由轉(zhuǎn)發(fā)信息，結(jié)束．

(8) 片外刪除操作：計(jì)算索引地址，訪問片外FIB存儲(chǔ)池，刪除相應(yīng)的路由轉(zhuǎn)發(fā)信息．

(9) 片內(nèi)刪除操作：Bitmap中該槽清零，結(jié)束．

4?L-FIB性能評(píng)價(jià)

本節(jié)從誤判概率、存儲(chǔ)消耗和吞吐量3方面，通過與Binary Patricia Trie-FIB[11]、哈希表(Hash Table，HT)-FIB[21]以及B-MaFIB[17]進(jìn)行比較，來評(píng)估L-FIB的性能．

4.1?實(shí)驗(yàn)設(shè)置

所有實(shí)驗(yàn)均在一臺(tái)配置為Intel Xeon E5-1650 v2 3.50GHz、DDR3 24GB SDRAM的小型工作站上進(jìn)行．對(duì)神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練利用MATLAB神經(jīng)網(wǎng)絡(luò)工具箱實(shí)現(xiàn)．訓(xùn)練完成后，提取模型的權(quán)重和偏置參數(shù)，然后利用C++語言實(shí)現(xiàn)L-FIB．考慮到實(shí)驗(yàn)對(duì)比的公平性，Binary Patricia Trie-FIB、HT-FIB和B-MaFIB同樣使用C++語言實(shí)現(xiàn)．

L-FIB中，每個(gè)BPNN設(shè)置為5個(gè)輸入神經(jīng)元、20個(gè)隱藏神經(jīng)元和1個(gè)輸出神經(jīng)元；Bitmap每個(gè)槽的大小設(shè)置為2bytes．Binary Patricia Trie-FIB中，每個(gè)地址指針為4bytes．HT-FIB分別采用MD5[21]、SHA1[21]和CityHash256[17]作為哈希函數(shù)實(shí)現(xiàn)，每個(gè)地址指針同樣為4bytes．B-MaFIB中，Bloom filter大小設(shè)為224bit，定位數(shù)組大小設(shè)為24bit，Bitmap每個(gè)槽的大小設(shè)為2bytes．

實(shí)驗(yàn)名稱數(shù)據(jù)使用當(dāng)前互聯(lián)網(wǎng)域名，因?yàn)槊麛?shù)據(jù)網(wǎng)內(nèi)容名稱由結(jié)構(gòu)化的變長(zhǎng)字符串構(gòu)成，與域名類似[3]．考慮到轉(zhuǎn)發(fā)平面FIB條目數(shù)可達(dá)超百萬級(jí)??別[7]，實(shí)驗(yàn)訓(xùn)練集包含1億個(gè)不同的域名，4個(gè)測(cè)試集分別包含50×104、100×104、150×104和200×104個(gè)不同的域名，具體信息如表2所示．

表2?實(shí)驗(yàn)數(shù)據(jù)集

Tab.2?Experimental dataset

4.2?誤判概率

本小節(jié)針對(duì)L-FIB、HT-FIB和B-MaFIB的誤判概率進(jìn)行比較和分析．實(shí)驗(yàn)中，Bitmap和哈希表的槽個(gè)數(shù)均暫定為3200×104個(gè)，依次向L-FIB、HT-FIB和B-MaFIB中插入50×104、100×104、150×104和200×104個(gè)不同名稱，記錄誤判概率．結(jié)果如圖5和表3所示，L-FIB的誤判概率分別為0.079％、0.240％、0.483％和0.820％，已滿足當(dāng)前互聯(lián)網(wǎng)對(duì)丟包率低于1％的要求[20]．相比之下，HT-FIB和B-MaFIB的誤判概率遠(yuǎn)遠(yuǎn)高于L-FIB，B-MaFIB最高達(dá)到了9.074％，原因即在于其映射的不均勻性和大量的沖突．

圖5?L-FIB的誤判概率性能分析

表3?L-FIB的誤判概率性能分析

Tab.3?False positive probability of the L-FIB

4.3?存儲(chǔ)消耗

對(duì)于相同的測(cè)試數(shù)據(jù)集，L-FIB、Binary Patricia Trie-FIB、HT-FIB和B-MaFIB存儲(chǔ)轉(zhuǎn)發(fā)信息所需的存儲(chǔ)空間大小是相同的．因此，本小節(jié)將只對(duì)比分析各方案中索引結(jié)構(gòu)的存儲(chǔ)消耗．

對(duì)于L-FIB、HT-FIB和B-MaFIB，其索引結(jié)構(gòu)的存儲(chǔ)消耗主要由映射表的大小決定．因此，實(shí)驗(yàn)中首先測(cè)試了在誤判概率低于1％[20]的條件下，L-FIB、HT-FIB和B-MaFIB索引結(jié)構(gòu)的映射表所需槽總數(shù)．實(shí)驗(yàn)結(jié)果如表4所示，名稱數(shù)量達(dá)到200×104個(gè)時(shí)，L-FIB的映射表需要2800×104個(gè)槽，而HT-FIB和B-MaFIB的映射表所需槽總數(shù)比L-FIB高約1～?2個(gè)數(shù)量級(jí)．原因在于L-FIB通過學(xué)習(xí)數(shù)據(jù)的分布情況實(shí)現(xiàn)了更均勻的映射，提高了存儲(chǔ)效率；而HT-FIB和B-MaFIB的地址映射都含有大量沖突，需要極大地增加映射表的大小才可將誤判概率降到1％以下．

表4?不同名稱數(shù)量下映射表所需槽總數(shù)

Tab.4 Number of slots required under different numbers of names 104

對(duì)于50×104、100×104、150×104和200×104個(gè)名稱，由表4所示映射表的大小，得出L-FIB中Bitmap的存儲(chǔ)消耗分別為8MB、20MB、34MB和56MB．對(duì)于L-FIB中的神經(jīng)網(wǎng)絡(luò)模型，每個(gè)BPNN由5個(gè)輸入神經(jīng)元、20個(gè)隱藏神經(jīng)元和1個(gè)輸出神經(jīng)元組成，且兩個(gè)Learning Tree共包含2002個(gè)BPNN，得出神經(jīng)網(wǎng)絡(luò)模型的存儲(chǔ)消耗為(20×5＋20×1＋1×20＋1×1)×8B×2002≈2.258MB．因此，對(duì)于4組不同數(shù)量的名稱數(shù)據(jù)，L-FIB中索引結(jié)構(gòu)的存儲(chǔ)消耗總計(jì)分別為10.258MB、22.258MB、36.258MB和58.258MB．

圖6顯示了L-FIB和其他方案中的索引結(jié)構(gòu)存儲(chǔ)消耗性能對(duì)比．相比之下，L-FIB和Binary Patricia Trie-FIB的索引結(jié)構(gòu)存儲(chǔ)消耗更低，因?yàn)長(zhǎng)-FIB通過相對(duì)均勻的映射提高了存儲(chǔ)效率，Binary Patricia Trie-FIB通過相同前綴的比特級(jí)集成降低了存儲(chǔ)消耗．表5給出了更詳細(xì)的結(jié)果．一個(gè)4SRAM線卡的最大存儲(chǔ)空間可達(dá)128.746MB[11]，如表6所示，因此L-FIB的片內(nèi)存儲(chǔ)單元能夠使用高速存儲(chǔ)器SRAM，部署其索引結(jié)構(gòu)．而HT-FIB和B-MaFIB的索引?結(jié)構(gòu)都需要較大的存儲(chǔ)空間，難以完全部署在SRAM上．

圖6?L-FIB的存儲(chǔ)消耗性能分析

表5?L-FIB的存儲(chǔ)消耗性能分析

Tab.5?Memory consumption of the L-FIB

表6?當(dāng)前線卡存儲(chǔ)器技術(shù)指標(biāo)

Tab.6?Memory devices in a line card

4.4?吞吐量

圖7給出了L-FIB和其他對(duì)比方案的吞吐量性能，更詳細(xì)的結(jié)果如表7所示．由于L-FIB和Binary Patricia Trie-FIB可以完全將索引結(jié)構(gòu)部署在SRAM上，因此它們的吞吐量遠(yuǎn)遠(yuǎn)大于其他方案．在這兩者之間，L-FIB的性能更優(yōu)，吞吐量可以達(dá)到大約11.64×106數(shù)據(jù)包/s，因?yàn)長(zhǎng)-FIB中的神經(jīng)網(wǎng)絡(luò)模型足夠小巧，能夠在命名數(shù)據(jù)網(wǎng)轉(zhuǎn)發(fā)平面中快速運(yùn)行．Binary Patricia Trie-FIB的吞吐量比L-FIB稍低，原因在于Binary Patricia Trie較高的深度影響了名稱數(shù)據(jù)檢索的速度．而HT-FIB和B-MaFIB的索引結(jié)構(gòu)需要較大的存儲(chǔ)空間，必須完全部署或部分部署在DRAM上，因此它們的吞吐量大大降低，難以滿足當(dāng)前互聯(lián)網(wǎng)對(duì)數(shù)據(jù)包快速處理的要求．

圖7?L-FIB的吞吐量性能分析

表7?L-FIB的吞吐量性能分析

Tab.7?Throughput of the L-FIB

5?結(jié)　語

本文提出了基于神經(jīng)網(wǎng)絡(luò)的命名數(shù)據(jù)網(wǎng)學(xué)習(xí)型FIB整體方案，L-FIB．具體地，首先介紹了L-FIB的索引結(jié)構(gòu)Learning Tree，然后在此基礎(chǔ)上設(shè)計(jì)了L-FIB的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)檢索算法，以提高存儲(chǔ)效率，有效支持LNPM機(jī)制，并提高名稱數(shù)據(jù)檢索速度．實(shí)驗(yàn)結(jié)果表明，在誤判概率為1%的條件下L-FIB的索引結(jié)構(gòu)存儲(chǔ)消耗為58.258MB，L-FIB的實(shí)際吞吐量約為11.64×106數(shù)據(jù)包/s，綜合性能明顯優(yōu)于對(duì)比方案．未來的工作是將L-FIB以多線程實(shí)現(xiàn)，并測(cè)試其在實(shí)際通信環(huán)境下的誤判概率、存儲(chǔ)消耗和吞吐量等性能指標(biāo)，驗(yàn)證其在命名數(shù)據(jù)網(wǎng)中的實(shí)際工作性能．

［1］ 衛(wèi)津津，金志剛，張瑞. 面向網(wǎng)絡(luò)傳輸?shù)牧Ⅲw視頻QoE評(píng)價(jià)模型[J]. 天津大學(xué)學(xué)報(bào)：自然科學(xué)與工程技術(shù)版，2016，49(12)：1248-1254.

Wei Jinjin，Jin Zhigang，Zhang Rui. QoE evaluation model for stereoscopic video network business[J]. Journal of Tianjin University：Science and Technology，2016，49(12)：1248-1254(in Chinese).

［2］ 孫立軍，劉藝偉. 流量計(jì)校準(zhǔn)網(wǎng)絡(luò)監(jiān)控管理系統(tǒng)[J]. 天津大學(xué)學(xué)報(bào)：自然科學(xué)與工程技術(shù)版，2018，51(8)：825-831.

Sun Lijun，Liu Yiwei. Monitoring and management system for flowmeter calibration network[J]. Journal of Tianjin University：Science and Technology，2018，51(8)：825-831(in Chinese).

［3］ Zhang L，Estrin D，Burke J，et al. Named Data Networking(NDN)Project[EB/OL]. http://named-data.net/，2010-10-31.

［4］ 石建，李卓，劉開華，等. 基于內(nèi)容中心網(wǎng)絡(luò)的高速鐵路通信系統(tǒng)架構(gòu)研究[J]. 天津大學(xué)學(xué)報(bào)：自然科學(xué)與工程技術(shù)版，2016，49(12)：1236-1242.

Shi Jian，Li Zhuo，Liu Kaihua，et al. Research on high speed railway communication system based on named data networking[J]. Journal of Tianjin University：Science and Technology，2016，49(12)：1236-1242(in Chinese).

［5］ Zhang L，Afanasyev A，Burke J，et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review，2014，44(3)：66-73.

［6］ Li Z，Xu Y，Zhang B，et al. Packet forwarding in named data networking requirements and survey of solutions[J]. IEEE Communications Surveys & Tutorials，2018，21(2)：1950-1987.

［7］ 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.

［8］ Ghasemi C，Yousefi H，Shin K G，et al. A fast and memory-efficient trie structure for name-based packet forwarding[C]//2018 IEEE 26th International Conference on Network Protocols. Cambridge，UK，2018：302-312.

［9］ Dai H，Liu B. CONSERT：Constructing optimal name-based routing tables[J]. Computer Networks，2016，94(1)：62-79.

［10］ Lee J，Lim H. A new name prefix trie with path compression[C]//2016 IEEE International Conference on Consumer Electronics-Asia. Seoul，Korea，2016：1-4.

［11］ Song T，Yuan H，Crowley P，et al. Scalable name-based packet forwarding：From millions to billions[C]//Proceedings of the 2nd ACM Conference on Information-Centric Networking. San Francisco，USA，2015：19-28.

［12］ Yuan H. Data Structures and Algorithms for Scalable NDN Forwarding[D]. St Louis：School of Engineering & Applied Science，Washington University in St. Louis，2015.

［13］ Yuan H，Crowley P. Reliably scalable name prefix lookup[C]//Proceedings of the 11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. Oakland，USA，2015：111-121.

［14］ Wang Y，Pan T，Mi Z，et al. Namefilter：Achieving fast name lookup with low memory cost via applying two-stage Bloom filters[C]//2013 Proceedings IEEE INFOCOM. Turin，Italy，2013：95-99.

［15］ Dai H，Lu J，Wang Y，et al. BFAST：High-speed and memory-efficient approach for NDN forwarding engine[J]. IEEE/ACM Transactions on Networking，2017，25(2)：1235-1248.

［16］ Li Z，Liu K，Liu D，et al. Hybrid wireless networks with FIB-based named data networking[J]. EURASIP Journal on Wireless Communications and Networking，2017，2017(1)：54-60.

［17］ Li Z，Xu Y，Liu K，et al. 5G with B-MaFIB based named data networking[J]. IEEE Access，2018，6(1)：30501-30507.

［18］ Yuan H，Song T，Crowley P. Scalable NDN forwarding：Concepts，issues and principles[C]//2012 21st International Conference on Computer Communications and Networks. Munich，Germany，2012：1-9.

［19］ Rumelhart D E，Hinton G E，Williams R J. Learning representations by back-propagating errors[J]. Nature，1986，323(6088)：533-536.

［20］ You W，Mathieu B，Truong P，et al. DiPIT：A distributed bloom-filter based PIT table for CCN nodes[C]//2012 21st International Conference on Computer Communications and Networks. Munich，Germany，2012：1-7.

［21］ Kirsch A，Mitzenmacher M，Varghese G. Hash-based techniques for high-speed packet processing[G]//Algori-thms for Next Generation Networks. London，UK：Springer，2010：181-218.

A Learning Forwarding Information Base for Named Data Networking with Neural Networks

Liu Kaihua，Yan Liu，Li Zhuo，Gong Xiaolin，Peng Peng，Wang Binzhi

(School of Microelectronics，Tianjin University，Tianjin 300072，China)

Designing an effective forwarding information base(FIB)for named data networking(NDN)is a major challenge within the overall NDN research area，since an FIB has to perform fast lookups for complex names，provide high capacity，and accurately support the mechanism of longest name prefix matching (LNPM). Therefore，a learning FIB based on neural networks，called L-FIB，was proposed. First，the index of L-FIB，named Learning Tree，used a two-level neural network model to learn the distribution characteristic of data indexed in static memory，which achieved more uniform mapping，reduced the false positive probability and improved memory utili-zation. Second，the storage structure and name lookup algorithms of L-FIB were put forward. The on-chip memory using SRAMs deployed multiple Learning Trees corresponding to the name prefixes with different numbers of compo-nents，while the off-chip memory using DRAMs deployed multiple FIB stores corresponding to the Learning Trees. The name lookup algorithms were also described to implement the retrieval of forwarding information for the Interest packets and the update of forwarding information. This well supported the LNPM mechanism and realized fast name lookups. Experimental results showed that the overall performance of L-FIB was superior to the compared schemes in terms of false positive probability，memory consumption，and the throughput. The index of L-FIB significantly re-duced memory consumption to 58.258MB with the probability of false positive＜1%，which meant it was deployable on SRAMs in commercial line cards. The throughput of L-FIB was about 11.64 million packets per second，which met current network requirements for fast packet processing.

named data networking(NDN)；forwarding information base(FIB)；neural network；name lookup

the National Natural Science Foundation of China(No.61602346).

TP393.0

A

0493-2137(2020)08-0825-08

10.11784/tdxbz201905032

2019-05-09；

2019-08-29.

劉開華（1956—??），男，博士，教授，liukaihua@tju.edu.cn.Email：m_bigm@tju.edu.cn

李卓，zli@tju.edu.cn.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61602346).

(責(zé)任編輯：王曉燕)