From owner-freebsd-hackers Fri Feb 13 16:56:37 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id QAA21624 for freebsd-hackers-outgoing; Fri, 13 Feb 1998 16:56:37 -0800 (PST) (envelope-from owner-freebsd-hackers@FreeBSD.ORG) Received: from parkplace.cet.co.jp (parkplace.cet.co.jp [202.32.64.1]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id QAA21611 for ; Fri, 13 Feb 1998 16:56:31 -0800 (PST) (envelope-from michaelh@cet.co.jp) Received: from localhost (michaelh@localhost) by parkplace.cet.co.jp (8.8.8/CET-v2.2) with SMTP id AAA11116; Sat, 14 Feb 1998 00:55:46 GMT Date: Sat, 14 Feb 1998 09:55:46 +0900 (JST) From: Michael Hancock To: Julian Elischer cc: hackers@FreeBSD.ORG Subject: Re: fast router code. (fwd) In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG Actually, the 4.4BSD implementation is a radix trie (Try-ee), you can read about it in "Algorithms for C", by Robert Sedgewick. It is not a Patricia Tree as mentioned in one of Stevens books. Mike Hancock On Fri, 13 Feb 1998, Julian Elischer wrote: > I thought I would forward a comment from the author of the > fast router code mentionned here a few days ago. > > julian > ---------- Forwarded message ---------- > Date: Fri, 13 Feb 1998 14:45:53 +0200 (EET) > From: Stefan Nilsson > To: Julian Elischer > Cc: Gunnar Karlsson > Subject: Re: fast router code. > > On Thu, 12 Feb 1998, Julian Elischer wrote: > > > your project was recently publicised in the FreeBSD forums. > > > > Do you have any comparative speed numbers comparing the > > speed of your trie based system with the radix-tree > > based system used in BSD4.4 based systems? > > No, we haven't done such a comparison yet and I just > realize that we faile to give a reference > to this implementation. We'll certainly fix that > in the final version of the paper. > > I haven't looked at the code for the BSD algorithm > and don't know how hard it would be do to an actual > experimental comparison. > However, from what I've read about the BSD algorithm > it should be very similar to ours. It's also based on > a trie (Patricia tree), it uses path compression but > not level compression. In fact, if you turn off the > level compression from our implementation you loose > a factor 5 in speed and the depth of the structure > increases from 2 to 20. > > Hence my guess is that, using level compression > as suggested in our paper, it possible to improve > the BSD algorithm by a factor of at least 5. > > Stefan > -- > Stefan Nilsson > Department of Computer Science +358 9 4514850 tel > Helsinki University of Technology +358 9 4513293 fax > P.O. Box 1100, FIN-02015 HUT www.cs.hut.fi/~sni > Finland > > > > > To Unsubscribe: send mail to majordomo@FreeBSD.org > with "unsubscribe freebsd-hackers" in the body of the message > -- michaelh@cet.co.jp http://www.cet.co.jp CET Inc., Daiichi Kasuya BLDG 8F, 2-5-12 Higashi Shinbashi, Minato-ku, Tokyo 105 Japan Tel: +81-3-3437-1761 Fax: +81-3-3437-1766 To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message