基于深度布隆過(guò)濾器的NDN網(wǎng)絡(luò)三級(jí)名字查找方法

吳慶濤; 師君如; 張明川; 王倩玉; 朱軍龍; 張宏科

doi:10.11999/JEIT200766

基于深度布隆過(guò)濾器的NDN網(wǎng)絡(luò)三級(jí)名字查找方法

doi: 10.11999/JEIT200766 cstr: 32379.14.JEIT200766

1.
河南科技大學(xué)信息工程學(xué)院洛陽(yáng) 471023
2.
北京交通大學(xué)下一代互聯(lián)網(wǎng)互聯(lián)設(shè)備國(guó)家工程實(shí)驗(yàn)室北京 100044

基金項(xiàng)目: 國(guó)家自然科學(xué)基金(61871430, 61976243)，中原科技創(chuàng)新領(lǐng)軍人才(214200510012)，河南省教育廳基礎(chǔ)研究專項(xiàng)(19zx010)，河南省教育廳重點(diǎn)科研項(xiàng)目(20A520011)

詳細(xì)信息

作者簡(jiǎn)介:
吳慶濤：男，1975年生，教授，研究方向?yàn)樵朴?jì)算、物聯(lián)網(wǎng)、下一代網(wǎng)絡(luò)

師君如：女，1997年生，碩士生，研究方向?yàn)樾畔⒅行木W(wǎng)絡(luò)

張明川：男，1977年生，教授，研究方向?yàn)槲锫?lián)網(wǎng)、下一代網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)

王倩玉：女，1991年生，碩士生，研究方向?yàn)樾畔⒅行木W(wǎng)絡(luò)

朱軍龍：男，1982年生，副教授，研究方向?yàn)槿斯ぶ悄?、機(jī)器學(xué)習(xí)、新型網(wǎng)絡(luò)

張宏科：男，1957年生，教授，研究方向?yàn)橄乱淮W(wǎng)絡(luò)、智慧協(xié)同網(wǎng)絡(luò)

通訊作者:
張明川　zhang_mch@haust.edu.cn

中圖分類號(hào): TN919.2; TP393
計(jì)量
- 文章訪問(wèn)數(shù): 663
- HTML全文瀏覽量: 441
- PDF下載量: 57
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2020-08-27
- 修回日期: 2021-09-24
- 網(wǎng)絡(luò)出版日期: 2021-10-22
- 刊出日期: 2021-12-21

A Three-level Name Lookup Method Based on Deep Bloom Filter for Named Data Networking

1.
School of Information Engineering, Henan University of Science and Technology, Luoyang 471023, China
2.
National Engineering Laboratory for Next Generation Internet Interconnection Devices, Beijing Jiaotong University, Beijing 100044, China

Funds: The National Natural Science Foundation of China (61871430, 61976243), The Leading Talents of Science and Technology in the Central Plain of China (214200510012), The Basic Research Projects in the University of Henan Province (19zx010), The Key Project of the Education Department Henan Province (20A520011)

摘要

摘要: 為提高命名數(shù)據(jù)網(wǎng)絡(luò)(Name Data Networking, NDN)路由過(guò)程中內(nèi)容名字查找的效率，該文提出一種基于深度布隆過(guò)濾器的3級(jí)名字查找方法。該方法使用長(zhǎng)短記憶神經(jīng)網(wǎng)絡(luò)(Long Short Term Memory, LSTM)與標(biāo)準(zhǔn)布隆過(guò)濾器相結(jié)合的方法優(yōu)化名字查找過(guò)程；采用3級(jí)結(jié)構(gòu)優(yōu)化內(nèi)容名字在內(nèi)容存儲(chǔ)器(Content Store, CS)、待定請(qǐng)求表(Pending Interest Table, PIT)中的精確查找過(guò)程，提高查找精度并降低內(nèi)存消耗。從理論上分析了3級(jí)名字查找方法的假陽(yáng)性率，并通過(guò)實(shí)驗(yàn)驗(yàn)證了該方法能夠有效節(jié)省內(nèi)存、降低查找過(guò)程的假陽(yáng)性。
- 命名數(shù)據(jù)網(wǎng)絡(luò) /
- 內(nèi)容名字查找 /
- 深度布隆過(guò)濾器 /
- 內(nèi)存消耗
Abstract: A three-level name lookup method based on deep Bloom filter is proposed to improve the searching efficiency of content name in the routing progress of the Named Data Networking (NDN). Firstly, in this method, the Long Short Term Memory (LSTM) is combined with standard Bloom filter to optimize the name searching progress. Secondly, a three-level structure is adopted to optimize the accurate content name lookup progresses in the Content Store (CS) and the Pending Interest Table (PIT) to promote lookup accuracy and reduce memory consumption. Finally, the error rate generated by content name searching method based on deep Bloom filter structure is analyzed in theory, and the experiment results prove that the proposed the three-level lookup structure can compress memory and decrease the error effectively.
- Named Data Networking (NDN) /
- Content name lookup /
- Deep Bloom filter /
- Memory consumption

HTML全文

圖 1 深度布隆過(guò)濾器查找結(jié)構(gòu)

下載: 全尺寸圖片幻燈片

圖 2 學(xué)習(xí)模型結(jié)構(gòu)

下載: 全尺寸圖片幻燈片

圖 3 名字字符串長(zhǎng)度分布

下載: 全尺寸圖片幻燈片

圖 4 初始過(guò)濾器系數(shù)選擇對(duì)假陽(yáng)性率的影響

下載: 全尺寸圖片幻燈片

圖 5 GRU大小對(duì)假陰性率和假陽(yáng)性率的影響

下載: 全尺寸圖片幻燈片

圖 6 閾值τ大小對(duì)假陽(yáng)性率和假陰性率的影響

下載: 全尺寸圖片幻燈片

圖 7 假陽(yáng)性率

下載: 全尺寸圖片幻燈片

圖 8 內(nèi)存消耗

下載: 全尺寸圖片幻燈片

表 1 面向深度布隆過(guò)濾器的名字查找算法

輸入：內(nèi)容集合S，非內(nèi)容集合U，閾值$\tau $
輸出：內(nèi)容名字x
1: 調(diào)用LSTM架構(gòu)使用集合S和集合U獲得一個(gè)集合D；
2: 查找x在初始過(guò)濾器中進(jìn)行精確匹配；
3: while 對(duì)每一個(gè)$x \in S$ do
4：　If b[i]=1 then
5: 　　將匹配內(nèi)容x發(fā)送到深度學(xué)習(xí)模型中；
6: 　else
7：　　將未匹配的x發(fā)送到FIB表中進(jìn)行最長(zhǎng)前綴匹配查找；
8: end while
9: if $(x, y) \in D $ then//在第2級(jí)深度學(xué)習(xí)模型中進(jìn)行精確匹配查找
10:　計(jì)算$f(x)=\dfrac{1}{1+{ \rm{e} }^{-x} }$；
11: end if
12: if $x \in S $且$ f(x) < \tau $ then
13:　將查找獲得的內(nèi)容名x在路由表中對(duì)應(yīng)的數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)；
14: else if $x \in S $且$f(x) < \tau $ then
15:　將未匹配的內(nèi)容名字x發(fā)送到第3級(jí)備份過(guò)濾器進(jìn)行查找；
16:　while在備份布隆過(guò)濾器查找b[i]=1 do
17:　　將查找獲得的內(nèi)容名x在路由表中對(duì)應(yīng)的數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)；
18:　end while
19: else
20:　將第3級(jí)未匹配的內(nèi)容發(fā)送到FIB表中進(jìn)行最長(zhǎng)前綴匹配查找；
21: end if

下載: 導(dǎo)出CSV

表 2 服務(wù)器配置

主要模塊	具體配置
主板	LENOVO-LNVNB161216
CPU	Intel Core? i7-9750H (6核，主頻2.60 GHz)
內(nèi)存	DDR4 8GB (內(nèi)存頻率 2667 MHz)

下載: 導(dǎo)出CSV

表 3 GRU和隱藏層參數(shù)配置與編號(hào)

配置編號(hào)	參數(shù)配置	配置編號(hào)	參數(shù)配置	配置編號(hào)	參數(shù)配置
I型	GRU大小=32，隱藏層大小=8	IV型	GRU大小=16，隱藏層大小=8	VII型	GRU大小=8，隱藏層大小=4
II型	GRU大小=32，隱藏層大小=4	V型	GRU大小=16，隱藏層大小=4	VIII型	GRU大小=4，隱藏層大小=4
III型	GRU大小=16，隱藏層大小=16	VI型	GRU大小=8，隱藏層大小=8	VIIII型	GRU大小=4，隱藏層大小=8

下載: 導(dǎo)出CSV

參考文獻(xiàn)(23)

[1]	楊國(guó)威, 徐泓, 李丹, 等. 未來(lái)互聯(lián)網(wǎng)體系結(jié)構(gòu)研究現(xiàn)狀與趨勢(shì)[J]. 中國(guó)基礎(chǔ)科學(xué), 2018, 20(3): 32–34. doi: 10.3969/j.issn.1009-2412.2018.03.006 YANG Guowei, XU Hong, LI Dan, et al. Research status and trends of future internet architecture[J]. China Basic Science, 2018, 20(3): 32–34. doi: 10.3969/j.issn.1009-2412.2018.03.006
[2]	黃韜, 劉江, 霍如, 等. 未來(lái)網(wǎng)絡(luò)體系架構(gòu)研究綜述[J]. 通信學(xué)報(bào), 2014, 35(8): 184–197. doi: 10.3969/j.issn.1000-436x.2014.08.023 HUANG Tao, LIU Jiang, HUO Ru, et al. Survey of research on future network architectures[J]. Journal on Communications, 2014, 35(8): 184–197. doi: 10.3969/j.issn.1000-436x.2014.08.023
[3]	YAO Haipeng, LI Mengnan, DU Jun, et al. Artificial intelligence for information-centric networks[J]. IEEE Communications Magazine, 2019, 57(6): 47–53. doi: 10.1109/MCOM.2019.1800734
[4]	ZHANG Lixia, AFANASYEV A, BURKE J, et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 66–73. doi: 10.1145/2656877.2656887
[5]	伊鵬, 李根, 張震. 內(nèi)容中心網(wǎng)絡(luò)中能耗優(yōu)化的隱式協(xié)作緩存機(jī)制[J]. 電子與信息學(xué)報(bào), 2018, 40(4): 770–777. doi: 10.11999/JEIT170635 YI Peng, LI Gen, and ZHANG Zhen. Energy optimized implicit collaborative caching scheme for content centric networking[J]. Journal of Electronics &Information Technology, 2018, 40(4): 770–777. doi: 10.11999/JEIT170635
[6]	GRITTER M and CHERITON D R. An architecture for content routing support in the Internet[C]. Proceedings of the 3rd USENIX Symposium on Internet Technologies and Systems, San Francisco, USA, 2001: 4.
[7]	BARI M F, CHOWDHURY S R, AHMED R, et al. A survey of naming and routing in information-centric networks[J]. IEEE Communications Magazine, 2012, 50(12): 44–53. doi: 10.1109/MCOM.2012.6384450
[8]	許志偉, 陳波, 張玉軍. 針對(duì)層次化名字路由的聚合機(jī)制[J]. 軟件學(xué)報(bào), 2019, 30(2): 381–398. doi: 10.13328/j.cnki.jos.005572 XU Zhiwei, CHEN Bo, and ZHANG Yujun. Hierarchical name-based route aggregation scheme[J]. Journal of Software, 2019, 30(2): 381–398. doi: 10.13328/j.cnki.jos.005572
[9]	FREDKIN E. Trie memory[J]. Communications of the ACM, 1960, 3(9): 490–499. doi: 10.1145/367390.367400
[10]	DHARMAPURIKAR S, KRISHNAMURTHY P, and TAYLOR D E. Longest prefix matching using bloom filters[J]. IEEE/ACM Transactions on Networking, 2006, 14(2): 397–409. doi: 10.1109/TNET.2006.872576
[11]	TAN Yun and ZHU Shuhua. Efficient name lookup scheme based on hash and character trie in named data networking[C]. Proceedings of the 12th Web Information System and Application Conference, Ji’nan, China, 2015: 130–135. doi: 10.1109/WISA.2015.72.
[12]	KRASKA T, BEUTEL A, CHI E H, et al. The case for learned index structures[EB/OL]. https://arxiv.org/abs/1712.01208, 2020.
[13]	MITZENMACHER M. Optimizing learned bloom filters by sandwiching[EB/OL]. https://arxiv.org/abs/1803.01474, 2018.
[14]	LI Fu, CHEN Fuyu, WU Jianming, et al. Fast longest prefix name lookup for content-centric network forwarding[C]. Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, Austin, USA, 2012: 73–74. doi: 10.1145/2396556.2396569.
[15]	LI Dagang, LI Junmao, and DU Zheng. An improved trie-based name lookup scheme for named data networking[C]. Proceedings of 2016 IEEE Symposium on Computers and Communication, Messina, Italy, 2016: 1294–1296.
[16]	LEE J, SHIM M, and LIM H. Name prefix matching using bloom filter pre-searching for content centric network[J]. Journal of Network and Computer Application, 2016, 65: 36–47. doi: 10.1016/j.jnca.2016.02.008
[17]	GOVINDARAJAN P, SOUNDARAPANDIAN R K, GANDOMI A H, et al. Classification of stroke disease using machine learning algorithms[J]. Neural Computing and Applications, 2020, 32(3): 817–828. doi: 10.1007/s00521-019-04041-y
[18]	SUTSKEVER I, VINYALS O, and LE Q V. Sequence to sequence learning with neural networks[C]. Proceedings of the 27th International Conference on Neural Information Processing Systems, Montreal, Canada, 2014: 3104–3112.
[19]	CHO K, VAN M?RRIENBOER B, GULCEHRE C, et al. Learning phrase representations using RNN encoder-decoder for statistical machine translation[C]. Proceedings of 2014 Conference on Empirical Methods in Natural Language Processing, Doha, Qatar, 2014: 1724–1734. doi: 10.3115/v1/D14-1179.
[20]	BLOOM B H. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7): 422–426. doi: 10.1145/362686.362692
[21]	BRODER A and MITZENMACHER M. Network applications of bloom filters: A survey[J]. Internet Mathematics, 2004, 1(4): 485–509. doi: 10.1080/15427951.2004.10129096
[22]	Blacklist[DB/OL]. http://squidguard.mesd.k12.or.us/blacklists.tgz.2020.7.5.
[23]	WANG Qianyu, WU Qingtao, ZHANG Mingchuan, et al. Learned bloom-filter for an efficient name lookup in information-centric networking[C]. Proceedings of 2019 IEEE Wireless Communications and Networking Conference, Marrakesh, Morocco, 2019: 1–6.