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

Abstract 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.