Multi Stride Decision Trie for IP Address Lookup
Multi bit tries have been proposed to improve the search performance of a binary trie by providing flexibility in stride values, which identify the number of bits examined at a time. However, constructing a variable stride multi bit trie is challenging since it is not easy to determine a proper stride value that satisfies the required performance at each node. The aim of this paper is to identify several desired characteristics of a trie for IP address lookup problems, and to propose a multi stride decision trie that has these characteristics. Simulation results using actual routing sets with about 30,000 to 220,000 prefixes show that the proposed multi stride decision trie has the desired characteristics and achieves IP address lookup using 33% to 47% of the 2 bit trie in the average number of node accesses, while requiring a smaller amount of memory.