一种新的IP路由表快速搜索技术

A New Algorithm for Fast Routing Lookups

随着因特网的飞速发展以及128位地址的IPv6的出现,路由表变得日益庞大,这给IP目标地址的查找速度提出了更高的要求。另外最长前缀匹配技术的出现使过去传统哈希搜索技术不再适用。为此,论文针对现有IP查找技术的缺点和不足,提出了一种新的二叉搜索算法。文中还对新的路由表数据结构进行了详细描述,并给出了该算法的一种软件实现方案。这种算法具有良好的可扩展性,不需要对现有协议进行改动,在实践中证明其具有良好的报文转发性能。

IP routing lookup is a challenging problem because the longest matching prefix required finding the routing entry has been difficult for the conventional solutions like hashing to deal with.In this paper,the authors discuss that existing schemes have problems of either performance,scalability,generality or cost.And they describe an optimal search algorithm based on precomputation that has good performance,excellent scalability and does not require protocol changes.The authors also present their new routing table data structure designed for quick routing lookups.Lastly,they show a cheap,fast software implementation including algorithm to build the data structure.