Prefix Partitioning Based in Genetic Algorithms for Memory-Efficient IPv4/6 Lookup

Abstract

IP address lookup speed in core routers has a significant impact on service quality in communications inside the Internet. The rapid growth of traffic in the Internet and the development of communications links working at speeds of several gigabits per second imply that IP lookup is a challenge for routers on Internet. There are different IP lookup schemes based on counts of set bits of a bit-vector that encode the routing information in structures of constant size that guarantee fast IP lookups. However, these schemes have exponential memory complexity and then the prefix partitioning schemes are used to save memory consumption, this performing the IP lookup in stages. In this work, we propose an IP lookup scheme based in a precalculated count of set bits of a bit-vector and a prefix-partitioning scheme that optimize the available memory usage in IP lookups in accordance with the prefix distribution in forwarding tables. A complete IPv4/6 lookup has an instruction cost of two memory accesses in the best case and twice the number of stages in the worst case. The proposed prefix-partitioning scheme is based on heuristic search using genetic algorithms to find an optimal partitioning. Our proposal can be implemented in general purpose hardware for IPv4/6 lookups.