内容中心网络中名字查找技术的研究

doi:10.3969／j.issn.1000-0801.2014.09.002

摘要/Abstract

摘要：

内容中心网络作为一种新型的未来网络体系架构被提出，以满足当前互联网信息共享的需求。内容中心网络使用类似域名的层次化名字结构对内容进行标识、路由和查找。由于互联网中内容众多，使用名字前缀构建的路由表，比传统的IP路由表大2～5个数量级，且由于名字查找依旧遵循最长前缀匹配原则，使得实现高速名字查找是一个富有挑战性的难题。分析了名字查找的技术挑战、实施难点，介绍了主要技术方法以及当前在名字查找领域的主要研究成果。

关键词: 内容中心网络, 名字查找, 最长前缀匹配

Abstract:

Named data networking（NDN）proposed as a new future architecture for the internet, aims to satisfy the requirement of information sharing among the users. NDN applies the hierarchical names to identify contents, route packets and retrieve information. Given the massive amount of contents and the longest prefix matching principle, achieving high speed name lookup exhibits a big challenge to implement NDN in real networks. The technical challenges of name lookup were firstly analyzed, then the main techniques to achieve wire-speed name lookup and their corresponding research results were introduced.

Key words: named data networking, named lookup, longest prefix matching

刘斌,汪漪. 内容中心网络中名字查找技术的研究[J]. 电信科学, 2014, 30(9): 10-17.

Bin Liu,Yi Wang. Researcb on Name Lookup in Named Data Networking[J]. Telecommunications Science, 2014, 30(9): 10-17.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

表2

参考文献 17

1	Web server survey.
2	Content-addressable memory.
3	Wang Y , Zu Y , Zhang T , et al. Wire speed name lookup: a GPU-based approach. Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation （NSDI'13）,Lombard, IL USA, 2013
4	Wang Y , He K Q , Dai H C , et al. Scalable name lookup in NDN using effective name component encoding. Proceedings of the 32nd International Conference on Distributed Computing Systems（ICDCS）,Macau, China, 2012
5	Wang Y , Pan T , Mi Z A , et al. NameFilter: achieving fast name lookup with low memory cost via applying two-stage bloom filters. Proceedings of INFOCOM 2013, Mini-Conference,Turin, Italy, 2013
6	Wang Y , Xu B Y , Tai D Z , et al. Fast name lookup for named data networking. Proceedings of IWQoS 2014,Hong Kong, China, 2014
7	NVIDIA's next generation CUDA computer architecture: fermi. ,2014
8	Zu Y , Yang M , Xu Z , et al. GPU-based NFA implementation for high speed memory efficient regular expression matching. Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming （PPoPP）,New Orleans, Louisiana, 2012
9	Edward F . Trie memory. Communications of the ACM, 1960,3,(9):490～499
10	Bloom B H . Space／time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970,13,(7):422～426
11	Named data networking（NDN）project. ,2014
12	Bonomi F , Mitzenmacher M , Panigrahy R , et al. An improved construction for counting bloom filters. Proceedings of the 14th Annual European Symposium,Zurich, Switzerland, 2006
13	Qiao Y , Li T , Chen S G . One memory access bloom filters and their generalization. Proceedings of the 30th Annual IEEE International Conference on Computer Communications（INFOCOM）,Shanghai, China, 2011
14	DJB hash function. ,2012
15	Wang Y , Dai H C , Jiang J C , et al. Parallel name lookup for named data networking. Proceedings of the IEEE Global Telecommunications Conference （Globecom）,Houston, Texas, United States, 2011
16	Wang Y , Tai D Z , Zhang T , et al. Greedy name lookup for named data networking. Proceedings of ACM SIGMETRICS,Pittsburgh, PA, 2013
17	Wang Y , Dai H C , Zhang T , et al. GPU-accelerated name lookup with component encoding. Elsevier Computer Networks, 2013,57,(16):3165～3177

名字路由表	Trace		名字查找吞吐率／MSPS
名字路由表	Trace	CharacterTrie	BloomHash	BloomFilter	NameFilter
3M	平均负载	0.188	1.043	0.203	2.033
3M	重负载	0.156	0.977	0.185	1.903
10M	平均负载	0.124	1.024	0.185	1.895
10M	重负载	0.102	0.834	0.178	1.834

名字路由表		存储空间／MB
名字路由表	CharacterTrie	BloomHash	BloomFilter	NameFilter
3M	283.21	184.35	52.63	64.73
10M	1 026.34	680.49	190.10	234.27

[1]	黄丹,宋荣方. 基于内容价值的缓存替换策略[J]. 电信科学, 2018, 34(11): 59-66.
[2]	曲桦,李岩松,刘军,赵季红,郭涯. 一种基于SDN的CCN集中控制缓存决策方法[J]. 电信科学, 2017, 33(5): 12-20.
[3]	伊鹏,张震,程东年,兰巨龙. 一种面向内容且性特征的自适应管线传输机制[J]. 电信科学, 2015, 31(9): 73-82.
[4]	刘宗海,王鹏,张校辉,金飞蔡. 内容中心网络中基于温度场的路由算法[J]. 电信科学, 2015, 31(12): 32-39.
[5]	张行功,牛童,郭宗明. 未来网络之内容中心网络的挑战和应用[J]. 电信科学, 2013, 29(8): 24-31.
[6]	胡骞,武穆清,郭嵩. 以内容为中心的未来通信网络研究综述[J]. 电信科学, 2012, 28(9): 74-80.
[7]	林啸. 以内容为中心的新一代互联网体系架构研究[J]. 电信科学, 2010, 26(5): 1-7.