ABSTRACT
A trie structure that allows the inspection of bits in strides of several bits is called a multibit trie. The standard implementation of a trie, where a set of children pointers are stored at each internal node is not a good solution, because it has a large space overhead. The modified Level Compression-trie stores all prefixes either in the internal nodes or the leaf nodes. The building algorithm does not change, but each entry in the data structure has five fields. In a multibit trie, the stride of a node is the number of bits used at that node to determine which branch to take. The Stanford hardware trie is based on the following two key observations: On backbone routers there are very few routes with prefixes longer than 24-bits and memory is getting cheaper and cheaper.
