Improving and Analyzing LC-Trie Performance for IP-Address Lookup

Abstract

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.