The problem of efficient data structures for IP

lookups has been well studied in literature. Techniques such as

LC tries and Extensible Hashing are commonly used. In this

paper, we address the problem of generalizing LC tries and

Extensible Hashing, based on traces of past lookups, to provide

performance guarantees for memory sub-optimal structures. As

a specific example, if a memory-optimal (LC) trie takes 6MB and

the total memory at the router is 8MB, 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 b fewer memory accesses