North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Free Software for Fast IP-Address Lookup

  • From: Michael Dillon
  • Date: Wed Feb 04 17:14:09 1998

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


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

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  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