Pipelined Multibit Tries

Tries are a natural candidate for pipelined lookups; each trie level can be stored in a different pipeline stage. The controlled prefix-expansion algorithm finds the fixed-stride tries (FST) with the minimum total memory. It can easily be applied to pipelined lookup architecture by fixing the number of trie levels to be the number of pipeline stages. Based on controlled prefix expansion, A. Basu and G. Narlikar have developed an algorithm that attempts to evenly allocate memory across the different stages. The MinMax algorithm attempts to balance the memory allocations across the pipeline stages. One of the motivations behind this was to avoid frequent rebuilding of the trie after incremental updates. Basu and Narlikar propose a node pullup scheme that results in improved multibit tries that are not FSTs. Kim and Sahni propose a partitioning strategy to construct the pipelined multibit tries.