Fast address look-up for Internet routers

Stefan Nilsson and Gunnar Karlsson

We consider the problem of organizing address tables for internet routers to enable fast searching. Our proposal is to build an efficient, compact and easily searchable implementation of an IP routing table by using an LC-trie, a trie structure with combined path and level compression. A node in the trie can be coded in only four bytes and the size of the main search structure never exceeds 500 kB for the tables in the US core routers. We present a software implementation that can sustain approximately half a million lookups per second on a 133 MHz Pentium personal computer, and two million lookups per second on a more powerful SUN Sparc Ultra II workstation.