Efficient construction of multibit tries for IP lookup
Srinivasan and Varghese (1999) have proposed the use of multibit tries to represent touting tables used for Internet (IP) address lookups. They propose dynamic programming algorithms to determine the strides of optimal multibit fixed-stride and variable-stride tries. We improve on these algorithms by providing alternative dynamic programming formulations, for both fixed-and variable-stride tries. While the asymptotic complexities of our algorithms are the same as those for the corresponding algorithms of Srinivasan and Varghese experiments using real IPv4 routing table data indicate that our algorithms run considerably faster. Our fixed-stride. trie algorithm is two to four times faster on a SUN workstation and 1.5 to three times faster on a Pentium IV PC. On a SUN workstation, our variable-stride trie algorithm is between two and 17 times faster than the correspondinig algorithm of Srinivasan and Varghese; on a Pentium IV PC, our algorithm is between three and 47 times faster. An added feature of our variable-stride trie algorithm is the ability to insert and delete prefixes taking a fraction of the time needed to construct an optimal variable-stride trie "from scratch."
dynamic programming controlled prefix expansion longest matching prefix multibit trie packet routing