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