Free Software for Fast IP-Address Lookup

Wed Feb 4 21:33:44 UTC 1998

Here's an interesting note I ran across today....
--------------forwarded message begins-----------

FREE SOFTWARE FOR FAST IP-ADDRESS LOOKUP 

Efficient, compact and easily searchable IP routing tables can be built
by using an LC-trie, a trie structure with combined path and level
compression. The depth of the LC-trie grows as O(log log N) with the
number of entries N for a large class of distributions. A node in the
trie can be coded in only four bytes and holds 128-bit addresses without
modification.

We are now making a software implementation publically available 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 for random traffic. The number
of lookups roughly doubles for real traffic owing to better caching. The
size of the main search structure never exceeds 500 kB for the tables in
the US core routers. Our results include the full lookup from a given
32-bit address to the resulting port number and next-hop address.

The source code and an accompanying paper can be fetched from URL
http://www.cs.hut.fi/~sni/papers/router/router.html  No patents are
pending or awarded for the algorithm.

Stefan Nilsson
Department of Computer Science 
Helsinki University of Technology, Finland

Gunnar Karlsson
Swedish Institute of Computer Science
Sweden