摘要： 在研究路由表地址前缀分布特点的基础上，提出了前缀长度二分查找方案。该方案采用前缀扩展技术，将前缀数量相对稀少的若干种前缀合并成一种，降低了查找树的高度，减少了存储器访问次数，提高了查找速度，分析了一种实用的Marker存储算法，探讨了IPv6的路由查找问题。

关键词: IP路由, 前缀长度, 最长前缀匹配, 二分查找

Abstract: Analyzing on the distribute of IP address prefix in core routers, this paper describes an improved algorithm for the longest matching prefix using binary search on hash tables organized by prefix lengths. It uses prefix expansion to reduce the numbers of the prefix length. Thereby, it decreases the number of hash tables and lowered the height of the search tree. The paper provides a concise and utility Marker store algorithm also, and gives some viewpoints for IPv6 routing lookups.

Key words: IP routing, prefix length, longest match prefix, binary search

中图分类号: 

• TP301.6