Paper Info
Title
Spider: Parallelizing Longest Prefix Matching with Optimization for SIMD Instructions
Abstract
Longest prefix matching (LPM) is a fundamental process in IP routing used not only in traditional hardware routers but also in modern software middleboxes such as the applications of Network Function Virtualization. However, the performance of recent LPM methods in software routers is insufficient for high-speed packet processing such as two or more 100 Gbps throughput. To improve the performance of LPM, we propose Spider, a new LPM method that achieves a fully parallelized LPM procedure using single instruction, multiple data (SIMD) instructions in a CPU. The evaluation shows that the proposed method has 1.8-1.9 times faster LPM performance compared with the state-of-the-art methods in this study area. We describe the Spider's lookup procedure fully parallelized by SIMD instructions and the design of the routing table efficiently processed by the procedure. We also report the following three evaluations: (1) The effect of parallelization by SIMD instructions on the performance of Spider; (2) the scalability of Spider with the number of CPU cores; and (3) the performance comparison with the previous methods in terms of randomly generated and real-trace traffic patterns.
Year
DOI
Venue
2020
10.1109/NetSoft48620.2020.9165306
2020 6th IEEE Conference on Network Softwarization (NetSoft)
Keywords
DocType
ISBN
IP Routing,LPM,SIMD,Software Middlebox
Conference
978-1-7281-5685-9
Citations 
PageRank 
References 
0
0.34
11
Authors
4
Name
Order
Citations
PageRank
Yukito Ueno100.34
ryo nakamura244.25
Yohei Kuga332.93
Hiroshi Esaki440974.27