基于前缀扩展的快速路由查找算法

该文对路由器中的快速路由查找算法进行了研究。针对路由查找算法在查找速度、算法空间复杂度以及插入和删除表项的难度算方法存在的问题，提出了一种快速路由查找算法。该算法通过构造两级索引表结构来减小路由查找的访存次数以提高查找速度；利用前缀扩展的特性并采用特殊的数据结构来构建索引表，能支持动态插入、删除和更新路由；采用压缩技术对二级索引表进行压缩，从而大大减小了路由所需的存储空间。该算法最多四次访存，最少两次访存就完成一次路由查找。由于采用了压缩方法，所需存储空间很小，该算法不仅适合于软件实现，也适合于硬件实现。查找速度快、存储空间小并支持动态插入和删除是该算法的主要特点。

Fast IP-Routing Lookup Algorithm Based on Prefix Expansion

The Internet is becoming ubiquitous, and the burst growth of Internet makes the size of the router's routing table increaseing rapidly. This brings forward a challenging problem for the router to lookup IP addresses as fast as possible because of increasing routing table sizes. This paper studies the fast IP-Routing lookup for IP router. Existing IP-Routing lookup algorithms have some problems in lookup speed, space complexity, and adding and deleting entries, and it is difficult to achieve a compromise among them. This paper proposes a fast IP-Routing lookup algorithm based on prefix expansion, which can reduce the memory access times by constructing two levels of index tables. For the index tables, if the length of the prefix is more than sixteen, the first sixteen bits of the prefix is used to construct the first level index table, the remaining bits of the prefix is used to construct the second index table, otherwise expands the prefix to sixteen bits and constructs the first level index table. Constructing the index tables is based on the characteristics of the prefix expansion, and these characteristics enable this algorithm to add and delete entries dynamically. In order to reduce the memory size of the index tables, this algorithm applies a special technique to compress the second index table, which makes the space of the forwarding table smaller. Special data structures are designed for the index tables, which make it easy to implement this algorithm. Most lookups need only two memory accesses to get the routing information, no lookup requires more than four memory accesses. Because this algorithm employs compression to reduce memory size and the process of lookup for the best match address is very simple, it can be implemented not only in software but also in hardware. This algorithm is characterized by fast IP-Routing lookup, small memory needs, adding and deleting entries dynamically.