Prefix caching improves the performance of IP lookup by exploiting spatial and temporal locality of IP references. However, it cannot cache non-leaf prefixes, so several prefix expansion schemes have been proposed to handle those prefixes. Such schemes have some drawbacks to incur modification of routing table or severe miss penalty. We propose an efficient prefix expansion scheme which achieves good performance without additional burden to lookup scheme. In the proposed scheme a non-leaf prefix is expanded to the length of the longest immediate descendant prefix when it is cached. Evaluation result shows our scheme achieves very low miss ratio even though it does not increase the size of routing table and cache miss penalty.

High-speed IP address lookup with fast prefix update is essential for designing wire-speed packet forwarding routers. The developments of optical fiber and 100 Gbps interface technologies have placed IP address lookup as the major bottleneck of high performance networks. In this paper, we propose a novel structure named Compressed Multi-way Prefix Tree (CMPT) based on B+ tree to perform dynamic and scalable high-speed IP address lookup. Our contributions are to design a practical structure for high-speed IP address lookup suitable for both IPv4 and IPv6 addresses, and to develop efficient algorithms for dynamic prefix insertion and deletion. By investigating the relationships among routing prefixes, we arrange independent prefixes as the search indexes on internal nodes of CMPT, and by leveraging a nested prefix compression technique, we encode all the routing prefixes on the leaf nodes. For any IP address, the longest prefix matching can be made at leaf nodes without backtracking. For a forwarding table with u independent prefixes, CMPT requires O(logmu) search time and O(mlogmu) dynamic insert and delete time. Performance evaluations using real life IPv4 forwarding tables show promising gains in lookup and dynamic update speeds compared with the existing B-tree structures.

Although IP address lookup schemes using ternary content addressable memory (TCAM) can perform high speed packet forwarding, TCAM is much more expensive than ordinary memory in implementation cost. As a low-cost solution, binary search algorithms such as a binary trie or a binary search tree have been widely studied. This paper proposes an efficient IP address lookup scheme using balanced binary search with minimal entries and optimal prefix vectors. In the previous scheme with prefix vectors, there were numerous pairs of nearly identical entries with duplicated prefix vectors. In our scheme, these overlapping entries are combined, thereby minimizing entries and eliminating the unnecessary prefix vectors. As a result, the small balanced binary search tree can be constructed and used for a software-based address lookup in small-sized routers. The performance evaluation results show that the proposed scheme offers faster lookup speeds along with reduced memory requirements.

In this work, we propose a scheme of routing table compaction for IP forwarding engines based on ternary content addressable memory (TCAM). Our scheme transforms the original routing table into a form with only disjoint prefixes. The most prevalent next hop of the routing table is then calculated and the route prefixes corresponding to the next hop are replaced by one TCAM entry. In combination with Espresso-II logic minimization algorithm, the proposed scheme reduces the TCAM storage requirements by more than 75% compared to the original routing tables. We also present an effective approach to support incremental updates.

This letter proposes a fast IP address lookup algorithm based on search space reduction. Prefixes are classified into three types according to the nesting relationship and a large forwarding table is partitioned into multiple small trees. As a result, the search space is reduced. The results of analyses and experiments show that the proposed method offers higher lookup and updating speeds along with reduced memory requirements.