[michael@memra.com: Free Software for Fast IP-Address Lookup]

--MimeMultipartBoundary
Content-Type: text/plain; charset=us-ascii

oooold message...

Faster ACL lookups?

-----Forwarded message from Michael Dillon <michael@memra.com>-----

Date: Wed, 4 Feb 1998 13:33:44 -0800 (PST)
From: Michael Dillon <michael@memra.com>
To: nanog@merit.edu
Subject: Free Software for Fast IP-Address Lookup

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

-----End of forwarded message-----

A followup:

Date: Wed, 04 Feb 1998 19:56:22 -0800
From: Vadim Antonov <avg@pluris.com>

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

 I don't know what's wrong with their algorithm but we're doing it about 7 time
s
 faster on the same hardware with pretty boring radix trees.

 Actually, i'll be talking about it at the NANOG meeting.

 --vadim

--MimeMultipartBoundary--
Received on Tue Jul 29 2003 - 13:15:47 MDT