基于改進(jìn)型MBF的命名數(shù)據(jù)網(wǎng)PIT存儲結(jié)構(gòu)研究

許亞平，李 卓，劉開華，馬東來，楊奕康

(1.天津大學(xué) 微電子學(xué)院，天津 300072；2.天津師范大學(xué) 天津市無線移動通信與無線能量傳輸重點(diǎn)實(shí)驗(yàn)室，天津 300387;3．中國鐵塔股份有限公司，山西 大同 037000)

0 引 言

近年來，互聯(lián)網(wǎng)規(guī)模呈現(xiàn)爆發(fā)性增長的趨勢，超高清視頻以及人工智能技術(shù)不斷發(fā)展，使用戶不再滿足于傳統(tǒng)的點(diǎn)到點(diǎn)通信方式，而是希望可以廣泛分發(fā)、共享數(shù)據(jù)信息。然而基于傳統(tǒng)TCP/IP(transmission control protocol/internet protocol)技術(shù)的互聯(lián)網(wǎng)通信模型逐漸暴露出IP地址空間耗盡、移動性差等弊端，使得無法滿足用戶對于高質(zhì)量通信的要求。為了應(yīng)對這些不足，一種新型未來網(wǎng)絡(luò)架構(gòu)命名數(shù)據(jù)網(wǎng)(named data networking，NDN)[1]被提出。與傳統(tǒng)的 TCP/IP網(wǎng)絡(luò)不同，NDN使用面向數(shù)據(jù)內(nèi)容的通信方式，以內(nèi)容名稱代替IP地址，不再關(guān)心內(nèi)容存儲在哪里，而僅關(guān)心內(nèi)容本身[2]。NDN通過在網(wǎng)絡(luò)節(jié)點(diǎn)部署緩沖存儲器，極大地提高了網(wǎng)絡(luò)資源的共享率，降低了網(wǎng)絡(luò)負(fù)載，提升了數(shù)據(jù)傳輸?shù)男阅堋?/p>

NDN中的通信由數(shù)據(jù)消費(fèi)者驅(qū)動，通過交換攜帶內(nèi)容名稱的興趣包和數(shù)據(jù)包來實(shí)現(xiàn)[1]。消費(fèi)者通過向網(wǎng)絡(luò)發(fā)送一個(gè)興趣包來向數(shù)據(jù)提供者請求數(shù)據(jù)。當(dāng)NDN路由器接收到興趣包后，路由器轉(zhuǎn)發(fā)平面中的待定 Interest 表(pending interest table, PIT)[1]則會記錄興趣包的名稱以及來源端口。當(dāng)提供者發(fā)送的數(shù)據(jù)包到達(dá)路由器后，通過檢索PIT來獲取轉(zhuǎn)發(fā)該包的端口，并刪除相應(yīng)記錄。路由器無論接收的是興趣包還是數(shù)據(jù)包，都需要對PIT進(jìn)行檢索，因此要求PIT具有極高的處理速度。同時(shí)，考慮到NDN中內(nèi)容名稱長度不定，結(jié)構(gòu)類似于統(tǒng)一資源定位符(uniform resource locator，URL)，遠(yuǎn)比IP地址復(fù)雜，所以PIT需要更多的存儲空間來記錄興趣包的名稱信息。

為滿足PIT對處理速度和存儲空間的需求，本文通過巧妙地利用Bitmap提出一種改進(jìn)的數(shù)據(jù)結(jié)構(gòu)B-MBF(Bitmap-mapping bloom filter)。同時(shí)，在B-MBF的基礎(chǔ)上，提出性能高效的PIT存儲結(jié)構(gòu)B-MaPIT。該存儲結(jié)構(gòu)不但顯著地提高了名稱檢索速度，而且進(jìn)一步降低了存儲消耗。

1 相關(guān)研究

針對轉(zhuǎn)發(fā)平面中PIT面臨的問題，目前研究人員已經(jīng)提出一些有效的算法。2012年，文獻(xiàn)[3]首次提出了名稱組件編碼(name component encoding，NCE)算法，基于該算法，文獻(xiàn)[4]構(gòu)建名稱組件樹以降低存儲在PIT中大量名稱的存儲消耗。為進(jìn)一步減少存儲消耗，文獻(xiàn)[5]提出Radient組件編碼算法。但樹形結(jié)構(gòu)的深度會影響檢索速度的提高，而且組件和編碼之間的映射過程降低了整體的檢索性能。文獻(xiàn)[6-7]提出基于哈希表檢索的算法來提高檢索速度，并用名稱的哈希值代替名稱存儲于哈希表以降低存儲消耗。然而哈希表作為靜態(tài)存儲，會造成大量存儲空間的浪費(fèi)，且哈希沖突也會影響該算法的性能。為規(guī)避樹形結(jié)構(gòu)和哈希表的缺點(diǎn)，文獻(xiàn)[8-9]提出在PIT結(jié)構(gòu)的每個(gè)轉(zhuǎn)發(fā)端口部署一個(gè)Bloom filter來記錄到達(dá)該端口的興趣包。然而，當(dāng)檢索數(shù)據(jù)包時(shí)卻不得不查找每一個(gè)Bloom filter以獲取數(shù)據(jù)包的轉(zhuǎn)發(fā)端口，這樣將造成檢索時(shí)間增加。此外，文獻(xiàn)[10]對Bloom filter進(jìn)行改進(jìn)，提出了MBF(mapping bloom filter)索引結(jié)構(gòu)，該結(jié)構(gòu)的數(shù)據(jù)檢索時(shí)間復(fù)雜度與哈希表相同，且其片內(nèi)存儲消耗可以降低到2.097 MByte。但是，該結(jié)構(gòu)的檢索性能與PIT要求的線性處理速度仍有一定差距。

2 基于改進(jìn)型MBF的PIT存儲結(jié)構(gòu)B-MaPIT

通過對PIT的相關(guān)研究，本節(jié)首先總結(jié)PIT的設(shè)計(jì)需求，在此基礎(chǔ)上，結(jié)合 Bitmap提出一種改進(jìn)的索引結(jié)構(gòu)B-MBF。其次，基于這種索引結(jié)構(gòu)，提出一種PIT存儲結(jié)構(gòu)B-MaPIT，并對其具體的結(jié)構(gòu)、檢索算法以及性能進(jìn)行詳細(xì)地分析。最后，通過仿真實(shí)驗(yàn)，進(jìn)一步測試和驗(yàn)證了B-MaPIT存儲結(jié)構(gòu)在存儲消耗，數(shù)據(jù)表構(gòu)建速度和吞吐量方面的性能高效性。

2.1 PIT的設(shè)計(jì)需求

在NDN路由器中，PIT的作用是記錄已轉(zhuǎn)發(fā)但未得到響應(yīng)的興趣包的轉(zhuǎn)發(fā)信息。當(dāng)興趣包到達(dá)路由器轉(zhuǎn)發(fā)平面后，PIT為其創(chuàng)建或更新條目，其中，每個(gè)條目的內(nèi)容為：[6]。對于到來的數(shù)據(jù)包，路由器則在PIT中檢索該包對應(yīng)的興趣包條目以找到數(shù)據(jù)包的轉(zhuǎn)發(fā)端口，然后刪除該條目。根據(jù)文獻(xiàn)[6，11]，對于10 Gbit/s鏈路速度的網(wǎng)絡(luò)，PIT應(yīng)包含1 000 000個(gè)條目；對于20 Gbit/s鏈路速度的網(wǎng)絡(luò)，PIT則應(yīng)包含1 500 000個(gè)條目。而且，無論興趣包還是數(shù)據(jù)包到達(dá)路由器，都需要進(jìn)行PIT處理，這要求PIT必須支持頻繁的更新操作。因此，作為NDN路由器轉(zhuǎn)發(fā)平面的核心部件，PIT對數(shù)據(jù)存儲結(jié)構(gòu)有著較高的性能需求。

此外，針對檢索過程所使用的匹配算法，由于TCP/IP網(wǎng)絡(luò)路由器使用的最長前綴匹配算法會消耗更多的處理時(shí)間，對于高度動態(tài)的PIT來說，該算法不適用。為了提高PIT的數(shù)據(jù)檢索性能，PIT使用基于字符串的準(zhǔn)確匹配算法[12]對興趣包和數(shù)據(jù)包進(jìn)行檢索。假設(shè)，內(nèi)容名稱為/A/B/C的興趣包或數(shù)據(jù)包到達(dá)，PIT僅需檢索名稱域content name為/A/B/C的條目，然后針對該包進(jìn)行相應(yīng)的處理。

2.2 B-MBF

標(biāo)準(zhǔn)型Bloom filter是空間高效的數(shù)據(jù)結(jié)構(gòu)，且執(zhí)行檢索的時(shí)間復(fù)雜度為O(1)。但是Bloom filter只能判斷某元素是否在集合中，不能確定該元素的具體物理存儲地址。針對Bloom filter的這個(gè)缺點(diǎn)，文獻(xiàn)[10]對其進(jìn)行改進(jìn)，提出了一種衍生數(shù)據(jù)結(jié)構(gòu)MBF。該結(jié)構(gòu)不僅可以同時(shí)支持查找和映射物理存儲地址，而且可以極大降低片內(nèi)存儲消耗。

文獻(xiàn)[10]中，MBF作為索引結(jié)構(gòu)，由2個(gè)比特?cái)?shù)組構(gòu)成：一個(gè)標(biāo)準(zhǔn)型Bloom filter和一個(gè)定位數(shù)組(mapping array，MA)。Bloom filter用于判斷某元素是否在MBF中，定位數(shù)組的映射數(shù)值則作為片外存儲單元的偏移地址。為了實(shí)現(xiàn)Bloom filter到定位數(shù)組的映射，Bloom filter被等分為j部分，定位數(shù)組的大小與Bloom filter等分部分?jǐn)?shù)量相同，也為j比特。同時(shí)，定位數(shù)組的比特位與Bloom filter的每部分一一對應(yīng)。在元素插入前，定位數(shù)組中每一個(gè)比特的初始狀態(tài)都為0。當(dāng)插入元素到MBF時(shí)，如果元素的哈希函數(shù)值映射到Bloom filter的某個(gè)部分，則其對應(yīng)的定位數(shù)組比特位的數(shù)值就被設(shè)置為1。通過k個(gè)哈希函數(shù)到Bloom filter的映射，可以得到定位數(shù)組最終的映射數(shù)值，即片外存儲單元的偏移地址。根據(jù)偏移地址，片外存儲單元中的元素信息就可以被找到。最后，在下一個(gè)元素到來之前，定位數(shù)組再次初始化為全0狀態(tài)。

雖然MBF極大降低了片內(nèi)存儲單元的存儲消耗，但是為存儲元素信息，該結(jié)構(gòu)必須在片外存儲單元部署一個(gè)靜態(tài)存儲，且需要預(yù)留足夠的存儲空間等待元素插入，這樣將增加片外存儲單元的存儲消耗，造成大量存儲空間的浪費(fèi)。此外，MBF的檢索速度仍與線性處理速度具有一定差距。針對這些不足，本文在MBF的基礎(chǔ)上，結(jié)合Bitmap提出一種改進(jìn)的數(shù)據(jù)索引結(jié)構(gòu)B-MBF，以進(jìn)一步降低片外存儲消耗，改善檢索性能。

B-MBF結(jié)構(gòu)由MBF和Bitmap兩部分組成，其具體數(shù)據(jù)結(jié)構(gòu)如圖1所示。其中，Bitmap的槽個(gè)數(shù)和定位數(shù)組的大小成指數(shù)關(guān)系。也就是說，若定位數(shù)組大小設(shè)定為j比特，那么Bitmap的槽個(gè)數(shù)將為2j。同時(shí)，Bitmap被等分為N個(gè)部分，且每個(gè)槽的大小由原來的1比特?cái)U(kuò)展成2字節(jié)，最大可存儲數(shù)值為65 535。因此，在等分Bitmap時(shí)，理論上使得每部分的槽個(gè)數(shù)小于或等于65 536的N值均可取，但為方便管理內(nèi)存分配，N值應(yīng)盡量選擇可取范圍內(nèi)的最大值。此外，每部分將對應(yīng)一個(gè)動態(tài)存儲空間。未存入元素前，所有動態(tài)存儲空間的內(nèi)存大小都為0，其基地址統(tǒng)一存儲在一個(gè)指針數(shù)組中。需要注意的是，當(dāng)某元素插入MBF，定位數(shù)組的映射數(shù)值不再作為片外存儲單元的直接偏移地址，而是指示元素在Bitmap中的位置。在元素插入過程中，首先根據(jù)定位數(shù)組數(shù)值計(jì)算出元素在Bitmap的第幾個(gè)部分，以及該部分中的具體位置。隨后，按照元素進(jìn)入該部分的順序?yàn)槠錁?biāo)號，該序號則被記錄在Bitmap的槽中，作為片外存儲單元的地址偏移量。最后，通過該部分的基地址與元素的地址偏移量，為該元素申請內(nèi)存單元，并將對應(yīng)的元素信息存儲到該內(nèi)存單元。隨著元素的不斷插入，片外存儲單元為其動態(tài)分配內(nèi)存單元，其存儲消耗隨元素?cái)?shù)量增加而增加，避免了存儲空間的浪費(fèi)。

圖1 B-MBF索引結(jié)構(gòu)示意圖Fig.1 Index structure of B-MBF

同時(shí)，在Bloom filter檢索過程中，B-MBF采用一個(gè)哈希函數(shù)對元素進(jìn)行哈希編碼，并將產(chǎn)生的定長二進(jìn)制序列分為多段，每段二進(jìn)制序列作為映射Bloom filter的一個(gè)哈希函數(shù)值。不同于文獻(xiàn)[10]中2個(gè)哈希函數(shù)的計(jì)算復(fù)雜度，B-MBF僅進(jìn)行一次哈希運(yùn)算即可實(shí)現(xiàn)多次哈希映射，從而進(jìn)一步提高了檢索速度。

圖1給出了B-MBF索引結(jié)構(gòu)執(zhí)行元素插入的一個(gè)例子。假設(shè)Bloom filter的大小為16 bit，分為4部分，進(jìn)行2次哈希映射。與此相應(yīng)，定位數(shù)組被設(shè)定為4 bit，Bitmap的槽個(gè)數(shù)設(shè)定為16，并被等分為2部分。在該例子中，3個(gè)元素O，P和Q被依次插入到B-MBF，且每個(gè)元素插入前，定位數(shù)組的初始值都為0。元素O首先插入到MBF中，其定位數(shù)組映射數(shù)值為0110。其次，根據(jù)定位數(shù)組數(shù)值計(jì)算出該元素在Bitmap中的位置為第1部分的第6個(gè)槽。作為第1部分的第1個(gè)元素，元素O被標(biāo)記為序號1，并將該序號記錄在槽中作為片外存儲單元的地址偏移量。與元素O的插入過程相似，元素P的定位數(shù)組映射數(shù)值為0011，需插入到Bitmap的第1部分的第3個(gè)槽，序號被標(biāo)記為2；元素Q的定位數(shù)組映射數(shù)值為1010，即對應(yīng)Bitmap的第2部分的第2個(gè)槽，序號被標(biāo)記為1。

對B-MBF索引結(jié)構(gòu)的檢索算法而言，其過程與插入算法相似。此外，為支持刪除操作，B-MBF可以為Bloom filter配置一個(gè)CBF(counting bloom filter)，并在Bloom filter和CBF之間執(zhí)行同步操作。同時(shí)，B-MBF需記錄Bitmap中刪除的元素序號，當(dāng)元素序號增加到閾值65 535而不能繼續(xù)增加時(shí)，之后插入的元素則重新使用已刪除的序號作為地址偏移量。

2.3 B-MaPIT

2.3.1 B-MaPIT存儲結(jié)構(gòu)

針對2.1節(jié)中所提到的PIT的特點(diǎn)和需求，本文基于B-MBF數(shù)據(jù)結(jié)構(gòu)，提出一種性能高效的PIT存儲結(jié)構(gòu)B-MaPIT，其具體結(jié)構(gòu)如圖2所示。

圖2 B-MaPIT存儲結(jié)構(gòu)示意圖Fig.2 Storage structure of B-MaPIT

考慮到PIT對于大容量、高性能的需求，本文根據(jù)實(shí)際應(yīng)用中的各類存儲器[13]的性能，對B-MaPIT結(jié)構(gòu)采用2級存儲器部署模式：片內(nèi)存儲單元和片外存儲單元。片內(nèi)存儲單元用于部署MBF，使用靜態(tài)隨機(jī)存取存儲器(static random access memory，SRAM)實(shí)現(xiàn)；片外存儲單元部署CBF，Bitmap以及多個(gè)小型存儲空間Packet Store，使用動態(tài)隨機(jī)存取存儲器(dynamic random access memory，DRAM)實(shí)現(xiàn)。在圖2中，B-MBF作為數(shù)據(jù)索引結(jié)構(gòu)，且Bitmap的每一部分對應(yīng)一個(gè)動態(tài)存儲空間Packet Store，用于存儲實(shí)際的興趣包的轉(zhuǎn)發(fā)信息。其中，Bitmap記錄的興趣包的序號作為Packet Store的地址偏移量。通過對片內(nèi)存儲單元中Bloom filter和片外存儲單元中CBF進(jìn)行同步，實(shí)現(xiàn)B-MaPIT的刪除和更新操作。此外，考慮到B-MBF存在哈希沖突，對于映射到Bitmap同一位置的興趣包，其轉(zhuǎn)發(fā)信息將以線性鏈表的形式鏈接在對應(yīng)Packet Store的條目后面。

根據(jù)PIT百萬級別數(shù)據(jù)存儲數(shù)量的事實(shí)，同時(shí)也為了將B-MaPIT的誤判率控制在更合理范圍內(nèi)，MBF結(jié)構(gòu)中Bloom filter的大小被設(shè)置為224bit，定位數(shù)組的大小被設(shè)置為24 bit。與此對應(yīng)，Bitmap的槽個(gè)數(shù)也被設(shè)定為224，并被劃分為256個(gè)部分，即對應(yīng)256個(gè)Packet Store。為了提高檢索速度，B-MaPIT采用性能良好的非加密哈希函數(shù)CityHash256[14]來代替MD5和SHA1，對興趣包的名稱域content name進(jìn)行哈希編碼，產(chǎn)生一個(gè)256 bit的定長二進(jìn)制序列，并將其分為12段，即B-MBF索引結(jié)構(gòu)將采用12個(gè)哈希函數(shù)進(jìn)行哈希映射。

2.3.2 B-MaPIT檢索算法

無論興趣包還是數(shù)據(jù)包到達(dá)路由器，PIT都會對其執(zhí)行相應(yīng)的處理操作。本節(jié)分別針對興趣包和數(shù)據(jù)包詳細(xì)介紹B-MaPIT對2種包的處理算法。

對于到達(dá)的興趣包，路由器首先提取興趣包的名稱域content name，在內(nèi)容存儲(content store，CS)中進(jìn)行檢索。如果CS中沒有響應(yīng)興趣包的數(shù)據(jù)包，那么路由器則會在B-MaPIT中檢索興趣包的轉(zhuǎn)發(fā)信息。在B-MaPIT執(zhí)行檢索操作時(shí)，首先根據(jù)興趣包的名稱域content name在MBF的Bloom filter中查找，通過哈希映射判斷B-MaPIT是否存在興趣包的轉(zhuǎn)發(fā)信息。若轉(zhuǎn)發(fā)信息不存在，則該興趣包將被轉(zhuǎn)發(fā)到轉(zhuǎn)發(fā)信息庫(forwarding information base，F(xiàn)IB)。同時(shí)，興趣包將被插入到Bloom filter與CBF，并在Bitmap中記錄序號，然后根據(jù)該序號和對應(yīng)Packet Store的基地址來申請內(nèi)存單元，記錄轉(zhuǎn)發(fā)信息。若轉(zhuǎn)發(fā)信息存在，則通過B-MBF結(jié)構(gòu)獲取Bitmap中記錄的序號，再依據(jù)序號和基地址訪問 Packet Store，對轉(zhuǎn)發(fā)信息進(jìn)行更新。如果誤判導(dǎo)致轉(zhuǎn)發(fā)信息存在，則將該興趣包轉(zhuǎn)發(fā)到FIB，通過FIB查找并將其轉(zhuǎn)發(fā)到下一跳路由器。

對于到達(dá)的數(shù)據(jù)包，路由器首先提取數(shù)據(jù)包的名稱域content name，在B-MaPIT中進(jìn)行檢索。與興趣包在B-MaPIT中的檢索算法相似，通過哈希映射確定B-MaPIT中是否存在數(shù)據(jù)包匹配的興趣包條目。若存在，則根據(jù)Bitmap中的序號和對應(yīng)Packet Store的基地址訪問Packet Store。如果轉(zhuǎn)發(fā)信息的條目為空，則丟棄該數(shù)據(jù)包，并在CBF中刪除相應(yīng)的記錄；否則，路由器將按照條目中的轉(zhuǎn)發(fā)信息將數(shù)據(jù)包轉(zhuǎn)發(fā)到相應(yīng)端口，并從Bitmap，CBF以及Packet Store中刪除對應(yīng)的條目。最后，為了保證B-MaPIT的信息準(zhǔn)確性，在刪除記錄后，B-MaPIT將執(zhí)行片內(nèi)存儲單元Bloom filter和片外存儲單元CBF的同步操作。

2.3.3 B-MaPIT性能分析

在時(shí)間復(fù)雜度方面，MBF到Bitmap的槽定位過程僅需要進(jìn)行一次除法運(yùn)算和一次取余運(yùn)算，無需迭代，因此，B-MBF結(jié)構(gòu)的時(shí)間復(fù)雜度與MBF[10]相同，都為O(1)。對B-MaPIT而言，執(zhí)行名稱檢索操作時(shí)B-MBF到Packet Store的尋址過程也只需要一次簡單的加法運(yùn)算，其執(zhí)行檢索的時(shí)間復(fù)雜度應(yīng)等于B-MBF的時(shí)間復(fù)雜度，即O(1)。

在誤判概率方面，考慮到Packet Store和Bitmap作為一般的數(shù)據(jù)結(jié)構(gòu)，不會造成誤判，所以，B-MaPIT的誤判概率完全取決于MBF，其誤判率與MaPIT[10]相同，B-MaPIT使用的MBF為概率型數(shù)據(jù)結(jié)構(gòu)，其發(fā)生誤判的概率由Bloom filter和定位數(shù)組的誤判概率組成。根據(jù)文獻(xiàn)[10]，Bloom filter和定位數(shù)組的誤判概率可分別表示為

P1=(1-ρ)k

(1)

(2)

將(1)式和(2)式的誤判概率相加，可得到B-MaPIT發(fā)生誤判的概率為

(3)

(1)—(3)式中：n表示PIT中存儲的元素個(gè)數(shù)；m表示Bloom filter比特?cái)?shù)組的大小；j表示定位數(shù)組的大??；k表示B-MaPIT所使用的哈希函數(shù)個(gè)數(shù)；ρ和α分別表示為ρ=(1-1/m)kn和α=(m/j-1)/(m-1)·j。

3 B-MaPIT性能評價(jià)

本節(jié)使用一臺普通計(jì)算機(jī)對B-MaPIT存儲結(jié)構(gòu)的存儲消耗、數(shù)據(jù)表構(gòu)建速度和吞吐量進(jìn)行測試。其中，計(jì)算機(jī)的操作系統(tǒng)采用32位的Windows7 sp3，核心部件CPU包含2個(gè)核，采用Intel Core i3-3220 3.30 GHz，內(nèi)存為DDR3 4 GB頻率1 333 GHz。通過與基于NCE、哈希表(hash table，HT)的PIT結(jié)構(gòu)以及MaPIT結(jié)構(gòu)進(jìn)行比較，來展現(xiàn)B-MaPIT存儲結(jié)構(gòu)高效的性能。

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

實(shí)驗(yàn)中的4種PIT存儲結(jié)構(gòu)全部采用C++程序語言實(shí)現(xiàn)。同時(shí)，4種PIT結(jié)構(gòu)均使用2級存儲器部署模式：片內(nèi)存儲單元部署索引結(jié)構(gòu)，片外存儲單元記錄PIT的具體信息。此外，基于HT的PIT結(jié)構(gòu)使用MD5和SHA1生成24 bit的二進(jìn)制序列作為哈希函數(shù)的映射值；MaPIT結(jié)構(gòu)則使用MD5和SHA1產(chǎn)生12個(gè)24 bit的二進(jìn)制序列作為哈希函數(shù)的映射值，且定位數(shù)組被設(shè)置為24 bit。考慮到2.1節(jié)中PIT的需求，本節(jié)的實(shí)驗(yàn)輸入數(shù)據(jù)采用來自DMOZ和ALEXA[10]的2 000 000條不同的域名。

3.2 B-MaPIT的存儲消耗

在存儲消耗的實(shí)驗(yàn)中，從片內(nèi)存儲單元和片外存儲單元對比分析了4種PIT結(jié)構(gòu)的存儲消耗。其中，假設(shè)片外存儲單元內(nèi)每條PIT條目的內(nèi)存大小為6字節(jié)。

表1給出了原始數(shù)據(jù)以及4種PIT結(jié)構(gòu)具體的片內(nèi)存儲單元的存儲消耗結(jié)果。參考表1的實(shí)驗(yàn)數(shù)據(jù)，可以明顯看到，B-MaPIT, MaPIT和HT結(jié)構(gòu)的片內(nèi)存儲消耗是靜態(tài)的，而NCE結(jié)構(gòu)的片內(nèi)存儲消耗則隨名稱數(shù)量增加而增加。實(shí)驗(yàn)結(jié)果表明，除HT結(jié)構(gòu)外，其他3種PIT結(jié)構(gòu)均可以有效減少片內(nèi)存儲消耗，但B-MaPIT和MaPIT的片內(nèi)存儲消耗最小，僅為2.097 MByte。

表1 片內(nèi)存儲單元存儲消耗Tab.1 Memory consumption of on-chip memory

表2給出了4種PIT結(jié)構(gòu)在片外存儲單元的存儲消耗結(jié)果。從表2可以看到，MaPIT，NCE結(jié)構(gòu)和HT結(jié)構(gòu)的片外存儲單元是靜態(tài)存儲，其存儲消耗與名稱數(shù)量無關(guān)，均為224×6≈100.66 MByte。B-MaPIT使用Bitmap實(shí)現(xiàn)了內(nèi)存動態(tài)分配，其片外存儲消耗隨名稱數(shù)量增加而增加。在未輸入名稱前，其片外存儲消耗僅取決于Bitmap，為224×2≈33.55 MByte；當(dāng)輸入2 000 000條名稱時(shí)，片外存儲消耗為224×2+2×106×6≈45.55 MByte，仍低于其他PIT結(jié)構(gòu)存儲消耗的一半。因此， B-MaPIT在片外存儲消耗方面具有最優(yōu)秀的表現(xiàn)。

表2 片外存儲單元存儲消耗Tab.2 Memory consumption of off-chip memory

從片內(nèi)和片外存儲消耗的結(jié)果可以看到，B-MaPIT在存儲消耗方面表現(xiàn)非常出色，能夠有效降低整體的存儲消耗，避免存儲空間的浪費(fèi)。

3.3 B-MaPIT數(shù)據(jù)表構(gòu)建速度

針對PIT數(shù)據(jù)表構(gòu)建速度的測試，實(shí)驗(yàn)采用2 000 000條名稱作為輸入數(shù)據(jù)，依次輸入到這4種PIT結(jié)構(gòu)中，且每輸入500 000條名稱記錄一次各PIT結(jié)構(gòu)的運(yùn)行時(shí)間，以測試各結(jié)構(gòu)的構(gòu)建速度。

表3為4種PIT結(jié)構(gòu)的數(shù)據(jù)表構(gòu)建時(shí)間。由表3可知，基于NCE的PIT結(jié)構(gòu)其基本思想是字符查找樹，由于樹形結(jié)構(gòu)查找速度較慢，導(dǎo)致基于NCE的PIT結(jié)構(gòu)的數(shù)據(jù)表構(gòu)建時(shí)間最長。當(dāng)輸入名稱達(dá)到2 000 000條時(shí)，其構(gòu)建時(shí)間約為B-MaPIT結(jié)構(gòu)的24倍。B-MaPIT，MaPIT和HT結(jié)構(gòu)都采用基于哈希的思想，其時(shí)間復(fù)雜度為O(1)，但B-MaPIT結(jié)構(gòu)僅使用一個(gè)哈希函數(shù)實(shí)現(xiàn)12次哈希映射，有效減少哈希運(yùn)算次數(shù)，提高了數(shù)據(jù)表的構(gòu)建速度，其構(gòu)建時(shí)間僅為HT結(jié)構(gòu)的1/12，MaPIT結(jié)構(gòu)的1/9。從表3的數(shù)據(jù)可以明顯看出，B-MaPIT結(jié)構(gòu)在數(shù)據(jù)表構(gòu)建速度性能上表現(xiàn)最佳。

表3 PIT數(shù)據(jù)表構(gòu)建時(shí)間Tab.3 Building time of PIT

3.4 B-MaPIT的吞吐量

在PIT結(jié)構(gòu)吞吐量的實(shí)驗(yàn)測試中，分別針對名稱數(shù)量為1 000 000, 1 500 000和2 000 000條名稱的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，并比較4種PIT結(jié)構(gòu)的吞吐量，其結(jié)果如圖3所示。

圖3 PIT結(jié)構(gòu)的吞吐量Fig.3 Throughput of PIT

圖3表明，隨著查找名稱數(shù)量的增加，基于NCE的PIT結(jié)構(gòu)的吞吐量呈現(xiàn)下降趨勢，而基于哈希算法的3種PIT結(jié)構(gòu)的吞吐量基本保持不變。以每秒百萬數(shù)據(jù)包(million packet per second，MPPS)為單位，當(dāng)查找名稱數(shù)量達(dá)到2 000 000時(shí)，NCE結(jié)構(gòu)、HT結(jié)構(gòu)、MaPIT以及B-MaPIT的吞吐量分別為0.061 MPPS，0.128 MPPS，0.170 MPPS，1.495 MPPS。顯然，由于僅使用一個(gè)哈希函數(shù)完成12次哈希映射，B-MaPIT結(jié)構(gòu)在吞吐量性能方面遠(yuǎn)優(yōu)于其他幾種PIT結(jié)構(gòu)。

4 結(jié)束語

根據(jù)PIT大容量、高性能的設(shè)計(jì)需求，本文基于Bitmap提出了一種改進(jìn)的索引結(jié)構(gòu)B-MBF，以提高檢索速度，并進(jìn)一步減少片外存儲單元的存儲消耗。同時(shí)，在此數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，設(shè)計(jì)了高效的PIT存儲結(jié)構(gòu)B-MaPIT，滿足了PIT對存儲空間和檢索速度的要求。經(jīng)過實(shí)驗(yàn)測試，本文提出的B-MaPIT在存儲消耗，數(shù)據(jù)表構(gòu)建速度和吞吐量性能方面有了極大的改善，提高了轉(zhuǎn)發(fā)平面的工作性能。未來的工作是以多線程實(shí)現(xiàn)B-MaPIT存儲結(jié)構(gòu)，并在FPGA(field programmable gate array)或GPU(graphic processing unit)上進(jìn)行部署，以進(jìn)一步測試該存儲結(jié)構(gòu)的性能。

[1] ZHANG Lixia, ESTRIN D, BURKE J, et al. Named data networking (NDN) project[J]. Transportation Research Record Journal of the Transportation Research Board, 2010, 1892(1):227-234.

[2] 王品，黃焱，王超，等. 基于自相關(guān)的寬范圍高精度頻偏估計(jì)算法[J]. 計(jì)算機(jī)工程, 2011, 37(4):102-103.

WANG Pin, HUANG Yan, WANG Chao, et al. Autocorrelation-based frequency offset estimation algorithm with wide range and high accuracy[J]. Computer Engineering, 2011, 37(4):102-103.

[3] WANG Yi, HE Keqiang, DAI Huichen, et al. Scalable name lookup in NDN using effective name component encoding[C]// IEEE. Distributed Computing Systems, 2012 IEEE 32nd International Conference on. Macau, China: IEEE, 2012:688-697.

[4] DAI Huichen, LIU Bin, CHEN Yan, et al. On pending interest table in named data networking[C]//Proceedings of the eighth ACM/IEEE symposium on Architectures for networking and communications systems. Austin, Texas, USA: ACM, 2012: 211-222.

[5] SAXENA D, RAYCHOUDHURY V. Radient: scalable, memory efficient name lookup algorithm for named data networking[J]. Journal of Network and Computer Applications, 2016, 63: 1-13.

[6] VARVELLO M, PERINO D, LINGUAGLOSSA L. On the design and implementation of a wire-speed pending interest table[C]//IEEE. Computer Communications Workshops (INFOCOM WKSHPS), 2013 IEEE Conference on. Turin, Italy: IEEE, 2013: 369-374.

[7] YUAN Haowei,CROWLEY P.Scalable pending interest table design:from principles to practice[C]//IEEE. IEEE INFOCOM 2014-IEEE Conference on Computer Communications.Toronto,Canada:IEEE,2014:2049-2057.

[8] YOU W, MATHIEU B, TRUONG P, et al. Dipit: a distributed bloom-filter based pit table for ccn nodes[C]// IEEE. Computer Communications and Networks (ICCCN), 2012 21st International Conference on. Munich, Germany: IEEE, 2012: 1-7.

[9] LI Zhaogeng, BI Jun, WANG Sen, et al. Compression of pending interest table with bloom filter in content centric network[C]//Proceedings of the 7th International Conference on Future Internet Technologies. Seoul, Korea: ACM, 2012: 46-46.

[10] LI Zhuo, LIU Kaihua, ZHAO Yang, et al. MaPIT: an enhanced pending interest table for NDN with mapping bloom filter[J]. IEEE Communications Letters, 2014, 18(11): 1915-1918.

[11] PERINO D, VARVELLO M. A reality check for content centric networking[C]//Proceedings of the ACM SIGCOMM workshop on Information-centric networking. Toronto, Ontario, Canada: ACM, 2011: 44-49.

[12] YUAN Haowei, SONG Tian, CROWLEY P. Scalable NDN forwarding: concepts, issues and principles[C]//IEEE. Computer Communications and Networks (ICCCN), 2012 21st International Conference on. Munich, Germany: IEEE, 2012: 1-9.

[13] ROSSINI G, ROSSI D, GARETTO M, et al. Multi-terabyte and multi-gbps information centric routers[C]//IEEE. INFOCOM, 2014 Proceedings IEEE. Toronto, Canada: IEEE, 2014: 181-189.

[14] Google Project Hosting. The City family of hash functions[EB/OL]. (2013-12-18)[2017-08-24]. http://code.google.com/p/cityhash.

(編輯：魏琴芳)