2018/04/24 by Maksim Yegorov, Yegorov, Maksim
Computer Science · #C.2.2 #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #cs.NI
paper · pdf · doi:10.48550/arxiv.1804.09254
Bloom filter, Longest Matching Prefix, Forwarding Lookups
arxiv created 2018/04/24 · arxiv updated 2018/04/26
Longest prefix matching has long been the bottleneck of the Bloom filter-based solutions for packet forwarding implemented in software. We propose a search algorithm to match a destination IP address against a compact representation of the FIB table in CPU cache on general purpose hardware with an average performance target of O(log n) for an n-bit address.