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

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

0 引 言

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

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

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

1 相關研究

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

2 基于改進型MBF的PIT存儲結構B-MaPIT

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

2.1 PIT的設計需求

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

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

2.2 B-MBF

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

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

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

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

圖1 B-MBF索引結構示意圖Fig.1 Index structure of B-MBF

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

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

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

2.3 B-MaPIT

2.3.1 B-MaPIT存儲結構

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

圖2 B-MaPIT存儲結構示意圖Fig.2 Storage structure of B-MaPIT

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

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

2.3.2 B-MaPIT檢索算法

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

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

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

2.3.3 B-MaPIT性能分析

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

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

P1=(1-ρ)k

(1)

(2)

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

(3)

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

3 B-MaPIT性能評價

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

3.1 實驗設置

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

3.2 B-MaPIT的存儲消耗

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

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

表1 片內存儲單元存儲消耗Tab.1 Memory consumption of on-chip memory

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

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

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

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

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

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

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

3.4 B-MaPIT的吞吐量

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

圖3 PIT結構的吞吐量Fig.3 Throughput of PIT

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

4 結束語

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

[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] 王品，黃焱，王超，等. 基于自相關的寬范圍高精度頻偏估計算法[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.

(編輯：魏琴芳)