Performance Evaluation and Cache Behavior of LC-Trie for IP-Address Lookup
2006 (English)In: Proc. of IEEE 2006 Workshop on High Performance Switching and Routing (HPSR 2006), IEEE , 2006, 29-35 p.Conference paper (Refereed)
Many IP-address lookup software algorithms use a trie-like data structure to perform longest prefix match. LC-trie is an efficient algorithm that uses level compression and path compression on tries. By using realistic and synthetically generated traces, we study the performance of the LC-trie algorithm. Our study includes trie search depth, prefix vector access behavior, cache behavior, and packet lookup service time. The results show that for a realistic traffic trace, the LC-trie algorithm is capable of performing 20 million packet lookups per second on a Pentium 4, 2.8 GHz computer, which corresponds to a 40 Gb/s link for average sized packets. Further, the results show that LC-trie performs up to five times better on the realistic 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.
Place, publisher, year, edition, pages
IEEE , 2006. 29-35 p.
IdentifiersURN: urn:nbn:se:kth:diva-6670DOI: 10.1109/HPSR.2006.1709677ISI: 000239877600005ScopusID: 2-s2.0-41549151304ISBN: 0780395697ISBN: 978-078039569-5OAI: oai:DiVA.org:kth-6670DiVA: diva2:11444
2006 Workshop on High Performance Switching and Routing, HPSR 2006; Poznan; Poland; 7-9 June 2006
QC 201411172006-12-192006-12-192014-11-17Bibliographically approved