Skip site navigation (1)Skip section navigation (2)
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>