### Adaptive data structures for IP lookupsAdaptive data structures for IP lookups

Access Restriction
Subscribed

 Author Ioannidis, Ioannis ♦ Grama, Ananth ♦ Atallah, Mikhail Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2005 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword IP lookups ♦ Level compression Abstract The problem of efficient data structures for IP lookups has been well studied in the literature. Techniques such as LC tries and extensible hashing are commonly used. In this paper, we address the problem of generalizing LC tries, based on traces of past lookups, to provide performance guarantees for memory suboptimal structures. As a specific example, if a memory-optimal (LC) trie takes 6 MB and the total memory at the router is 8 MB, how should the trie be modified to make best use of the 2 MB of excess memory? We present a greedy algorithm for this problem and prove that, if for the optimal data structure there are $\textit{b}$ fewer memory accesses on average for each lookup compared with the original trie, the solution produced by the greedy algorithm will have at least 9 × $\textit{b}/11$ fewer memory accesses on average (compared to the original trie). An efficient implementation of this algorithm presents significant additional challenges. We describe an implementation with a time complexity of $\textit{O}(ξ(\textit{d})\textit{n}log$ $\textit{n})$ and a space complexity of $\textit{O}(\textit{n}),$ where $\textit{n}$ is the number of nodes of the trie and $\textit{d}$ its depth. The depth of a trie is fixed for a given version of the Internet protocol and is typically $\textit{O}(log$ $\textit{n}).$ In this case, $ξ(\textit{d})$ = $O(log^{2}$ $\textit{n}).$ We also demonstrate experimentally the performance and scalability of the algorithm on actual routing data. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2005-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 10

#### Open content in new tab

Source: ACM Digital Library