Efficient construction of variable-stride multibit tries for IP lookup

Srinivasan and Varghese (1999) have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose an O(n _*W²_* k) dynamic programming algorithm to determine the strides for an optimal variable-stride trie that has at most k levels. Here, n is the number of prefixes in the routing table and W is the length of the longest prefix. We improve on this algorithm by providing an alternative dynamic programming formulation. The complexity of our algorithm is O(n_* W_*k), on real router data sets. This is an improvement by a factor of W over the corresponding algorithm of Srinivasan. Experiments conducted by us indicate that our variable-stride algorithm is between 2 and 17 times as fast for IPv4 routing table data