Narrow Results

IP address lookup engine is the beating heart of a router. For meeting the requirements of a desirable high-speed router, speed, memory consumption, scalability, and reconfigurability of its IP lookup engine are critical. This paper uses a genetic-algorithm approach to optimise the structure of fixed-stride multibit-trie IP lookup methods. In this work, the genetic algorithm is used first in the design phase as an offline optimisation mechanism. This nature-inspired simulation finds the most memory-efficient configuration of IP address segmentation for a fixed number of address segments. Then, for adapting to network variations, the proposed method dynamically changes the number of address segments to compromise between speed and memory consumption. Each time the number of segments changes, an online genetic program is run to optimise the segmentation. Therefore, the lookup engine reconfigures itself to cover more prefixes during the time. The reconfigurability in response to the network variations, and scalability to the number of prefixes improves the life time of a router that uses this method.

Previous research has shown that the search performance of Trie-based algorithms can be improved by adding on-chip Bloom filters. The Bloom filter can identify the membership of a node in an off-chip Trie, and the number of off-chip memory accesses is reduced. But the Trie-based structure has the shortcoming that it is difficult to delete or insert nodes once the Trie has been constructed. In this paper, we propose a new method of utilizing a counting Bloom filter for the IP address lookup of longest prefix match which can make some operations with the Trie nodes. Simulation results show that the best matching prefix can be found with limited off-chip access and much better performance of search can be achieved in our proposed method.