Improving and Analyzing LC-Trie Performance for IP-Address Lookup
2007 (English)In: Journal of Networks, ISSN 1796-2056, Vol. 2, no 3, 18-27 p.Article in journal (Refereed) Published
IP-address lookup is a key processing function of Internet routers. The lookupis challenging because it needs to perform a longest prefix match. In this paper, wepresent our modifications to an efficient lookup algorithm, the LC-trie, based ona technique called prefix transformation. Thereafter, the LC-trie’s performance isanalyzed for both the original and our modified algorithm using real and syntheticallygenerated traces. The performance study includes trie search depth, prefixvector access behavior, cache behavior and packet lookup time. The study is basedboth on experiments and a model for packet lookup time. The results show thatthe modified algorithm requires only 30% of the lookup time of the original algorithm.In particular, the modified algorithm is capable of performing 60 millionpacket lookups per second on a Pentium 4, 2.8 GHz, computer for a real traffictrace. Further, the results show that the performance is about five times better onthe real trace compared to a synthetically generated network trace. This illustratesthat the choice of traces may have a large influence on the results when evaluatinglookup algorithms.
Place, publisher, year, edition, pages
2007. Vol. 2, no 3, 18-27 p.
IP-address lookup, trie, prefix transformation, performance evaluation
IdentifiersURN: urn:nbn:se:kth:diva-9411ScopusID: 2-s2.0-51049091794OAI: oai:DiVA.org:kth-9411DiVA: diva2:113876
QC 201007262008-10-302008-10-302013-09-09Bibliographically approved