From owner-freebsd-hackers Fri Feb 13 10:20:38 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id KAA02655 for freebsd-hackers-outgoing; Fri, 13 Feb 1998 10:20:38 -0800 (PST) (envelope-from owner-freebsd-hackers@FreeBSD.ORG) Received: from alpo.whistle.com (alpo.whistle.com [207.76.204.38]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id KAA02614 for ; Fri, 13 Feb 1998 10:20:18 -0800 (PST) (envelope-from julian@whistle.com) Received: (from daemon@localhost) by alpo.whistle.com (8.8.5/8.8.5) id KAA24207 for ; Fri, 13 Feb 1998 10:16:08 -0800 (PST) Received: from UNKNOWN(), claiming to be "current1.whistle.com" via SMTP by alpo.whistle.com, id smtpd024201; Fri Feb 13 10:15:58 1998 Date: Fri, 13 Feb 1998 10:12:10 -0800 (PST) From: Julian Elischer To: hackers@FreeBSD.ORG Subject: Re: fast router code. (fwd) 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 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