ISSN : 1796-2056
Volume : 2    Issue : 3    Date : June 2007

Improving and Analyzing LC-Trie Performance for IP-Address Lookup
Jing Fu, Olof Hagsand, and Gunnar Karlsson
Page(s): 18-27
Full Text:
PDF (430 KB)

IP-address lookup is a key processing function of Internet routers. The lookup is challenging
because it needs to perform a longest prefix match. In this paper, we present our modifications to
an efficient lookup algorithm, the LC-trie, based on a technique called prefix transformation.
Thereafter, the LC-trie’s performance is analyzed for both the original and our modified algorithm
using real and synthetically generated traces. The performance study includes trie search depth,
prefix vector access behavior, cache behavior and packet lookup time. The study is based both on
experiments and a model for packet lookup time. The results show that the modified algorithm
requires only 30% of the lookup time of the original algorithm. In particular, the modified algorithm is
capable of performing 60 million packet lookups per second on a Pentium 4, 2.8 GHz, computer for
a real traffic trace. Further, the results show that the performance is about five times better on the
real trace compared to a synthetically generated network trace. This illustrates that the choice of
traces may have a large influence on the results when evaluating lookup algorithms.

Index Terms
IP-address lookup, trie, prefix transformation, performance evaluation