Date: Sat, 14 Feb 1998 09:55:46 +0900 (JST) From: Michael Hancock <michaelh@cet.co.jp> To: Julian Elischer <julian@whistle.com> Cc: hackers@FreeBSD.ORG Subject: Re: fast router code. (fwd) Message-ID: <Pine.SV4.3.95.980214095331.11010B-100000@parkplace.cet.co.jp> In-Reply-To: <Pine.BSF.3.95.980213101032.18313B-100000@current1.whistle.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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 <sni@cs.hut.fi> > To: Julian Elischer <julian@whistle.com> > Cc: Gunnar Karlsson <gunnar@tcm.hut.fi> > 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.SV4.3.95.980214095331.11010B-100000>