A memory-efficient scheme for address lookup using compact prefix tries

We present a new memory-efficient scheme for address lookup that exploits the caching support provided by general-purpose processors. We propose compact prefix tries, in which prefixes occurring at multiple levels of a subtrie are compressed into a single node that fits in a single cache line. The scheme performs well in compressing dense as well as sparse tries. For an IP core router (Mae-West) database with 93354 prefixes, the simulation results for compact prefix tries show up to 70% improvement in lookup performance and up to 33% reduction in memory when compared with LC-tries. In fact, the entire forwarding table for Mae-West required only 829 KB space. Measurements for compact prefix tries, when compared with most existing schemes, show better results in terms of memory usage as well as lookup speeds. Moreover, as the memory usage is significantly less and sparse tries with long paths can be compressed into only a few nodes, this scheme is particularly attractive for IPv6.