分组IP路由最长前缀匹配查找算法研究

介绍了几种常见的IP路由查找算法，并简单分析其优点与不足。二进制Trie树结构虽占用空间较小，但因其查找时间太长而很少运用于实际生活中，目前常见的算法都是在查找时间与存储空间上寻找折衷点．本文在此基础之上提出了一种基于分组IP路由最长前缀匹配查找算法，通过将IP前缀按其长度进行分组，并在各组内采用Trie树结构进行存储，最长只需4次存储器访问，且因利用了公共前缀，固能节约存储空间，实验结果表明，本算法在查找时间上取得了非常理想的效果。

Algorithm Research of Grouped IP Address for Longest Matching Prefix Lookup

Several common IP routing search algorithm are introduced. Their advantages and disadvantages are analyzed. Although the binary Tile tree structure takes less space,but rarely used in the real life for the long search time,the current common algorithms is used to find a proper point between the search time and storage space. On this basis, a group-based IP routing longest prefix match search algorithm is giv- en, by grouping the IP prefix according to its length, storing each group with the Trie tree strUcture. 0nly 4 times memory access is needed at most. And because of the used of the public prefix,much storage space can be saved. The experiment result shows that this algorithm get a very good results in the search time.