Using XorOffsetTrie for high-performance IPv6 lookup in the backbone network

doi:10.1016/j.comcom.2021.10.027

	Using XorOffsetTrie for high-performance IPv6 lookup in the backbone network
	Zhang, Chunyang 1,3; Xie, Gaogang 2,3
	2022
发表期刊	COMPUTER COMMUNICATIONS
ISSN	0140-3664
卷号	181 页码:438-445
摘要	The development of IPv6 in scale and traffic requires the IPv6 lookup algorithm to perform fast longest prefix matching (LPM), especially in the backbone network. However, existing IPv6 lookup algorithms, e.g., SAIL, Poptrie, and Hi-BST have limited lookup speeds with too many memory accesses. To achieve the highest lookup speed with fewer memory accesses, we propose the XorOffsetTrie method, which is the combination of XorFilter and OffsetTrie. OffsetTrie reduces the memory accesses by combining the offset index and the next hop of rule into an integer. XorFilter further improves lookup speed by matching about 63% rules with one memory access. If a packet matches a rule in XorFilter, we can return the next hop of this rule immediately. Otherwise, we continue to lookup in OffsetTrie. With high efficient data structure for lookup process, the lookup speed of XorOffsetTrie achieves 1.6x, 4.2x, 8.5x that of SAIL, Poptrie, and Hi-BST.
关键词	IPv6 lookup Longest prefix matching LPM
DOI	10.1016/j.comcom.2021.10.027
收录类别	SCI
语种	英语
资助项目	National Key R&D Program of China[2019YFB1802800] ; National Science Fund for Distinguished Young Scholars[61725206]
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000718942600018
出版者	ELSEVIER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/18120
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xie, Gaogang
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China 2.Chinese Acad Sci, Comp Network Informat Ctr, Beijing, Peoples R China 3.Univ Chinese Acad Sci, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Zhang, Chunyang,Xie, Gaogang. Using XorOffsetTrie for high-performance IPv6 lookup in the backbone network[J]. COMPUTER COMMUNICATIONS,2022,181:438-445.
APA	Zhang, Chunyang,&Xie, Gaogang.(2022).Using XorOffsetTrie for high-performance IPv6 lookup in the backbone network.COMPUTER COMMUNICATIONS,181,438-445.
MLA	Zhang, Chunyang,et al."Using XorOffsetTrie for high-performance IPv6 lookup in the backbone network".COMPUTER COMMUNICATIONS 181(2022):438-445.