dc.description.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. | en |