A Routing Lookup Algorithm Based on Fast Search Trees
基于快速搜索树的路由查表算法

This paper describes a novel algorithm for implementing high speed IP routing lookups which splits the route rules into several subsets according to the prefix length distributions and constructs fast search trees for each subset. Using the hash compression index tables and Bloom Filters the speed of lookup is improved dramatically. This scheme can be easily implemented in hardware using a pipeline fashion and the results of the experimental and application show that it is practical and efficient. This approach is equally attractive for IPv6.