Optimization and performance evaluation of ip lookup algorithms

Abstract

The number of people accessing the internet grows exponential and soon half of the world’s population will have access to internet. New services and applications are also added daily on the popular IP networks and this trend is likely to continue into the future. More precisely, this development is in three major parameters of the internet activity: the number of connected nodes and endpoints is increasing, resulting in growth of routing table sizes, the number of users increases, resulting in larger internet traffic, and the complexity of the provided services increases, also causing an increase in traffic by delivering higher amounts of data per transaction. All these translate into a growing increase in traffic demands, which can only be answered by improvement in the service given by internet routers. Due to the rapid growth of traffic in the Internet, backbone links of several gigabits per second are commonly deployed. To handle gigabit-per-second traffic rates, the backbone routers must be able to forward millions of packets per second on each of their ports. Fast IP address lookup in the routers, which uses the packet’s destination address to determine for each incoming packet the next hop, is therefore crucial to achieve the packet forwarding rates required. IP address lookup is difficult because it requires a longest matching prefix search. In this research work, I consider the problem of organizing the Internet forwarding tables in such a way as to enable fast routing lookup performance. In the last couple of years, various algorithms for high performance IP address lookup have been proposed. I present a brief survey of state-of-the-art IP address lookup algorithms. I concentrate on four recently proposed methods and try to evaluate their performance. I describe my implementation of the methods and results of performance measurements on artificially generated input data. Some conclusions about the general behavior of all methods, based on the measurements and theoretical reasoning is presented. Finally, I comment on the results, suggesting preference among the methods.