From owner-freebsd-hackers Mon Feb 9 05:11:18 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id FAA27920 for hackers-outgoing; Mon, 9 Feb 1998 05:11:18 -0800 (PST) (envelope-from owner-freebsd-hackers@FreeBSD.ORG) Received: from iq.org (proff@polysynaptic.iq.org [203.4.184.222]) by hub.freebsd.org (8.8.8/8.8.8) with SMTP id FAA27914 for ; Mon, 9 Feb 1998 05:11:11 -0800 (PST) (envelope-from proff@iq.org) Received: (qmail 588 invoked by uid 110); 9 Feb 1998 12:28:44 -0000 To: hackers@FreeBSD.ORG Subject: Free Software for Fast IP-Address Lookup (fwd) From: Julian Assange Date: 09 Feb 1998 23:28:44 +1100 Message-ID: Lines: 31 X-Mailer: Gnus v5.5/XEmacs 20.3 - "Vatican City" Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG 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 To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe hackers" in the body of the message