From owner-freebsd-net Tue Aug 13 11:48:39 2002 Delivered-To: freebsd-net@freebsd.org Received: from mx1.FreeBSD.org (mx1.FreeBSD.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id B5B6837B405 for ; Tue, 13 Aug 2002 11:48:37 -0700 (PDT) Received: from mailtoaster1.pipeline.ch (mailtoaster1.pipeline.ch [62.48.0.70]) by mx1.FreeBSD.org (Postfix) with SMTP id 5BF2543E72 for ; Tue, 13 Aug 2002 11:48:36 -0700 (PDT) (envelope-from oppermann@pipeline.ch) Received: (qmail 3196 invoked from network); 13 Aug 2002 18:46:47 -0000 Received: from unknown (HELO pipeline.ch) ([62.48.0.53]) (envelope-sender ) by mailtoaster1.pipeline.ch (qmail-ldap-1.03) with SMTP for ; 13 Aug 2002 18:46:47 -0000 Message-ID: <3D59542C.6796FC6D@pipeline.ch> Date: Tue, 13 Aug 2002 20:47:08 +0200 From: Andre Oppermann X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: Ruslan Ermilov Cc: Bakul Shah , Luigi Rizzo , net@FreeBSD.ORG Subject: Re: Consistency of cached routes References: <20020813021333.A4507@iguana.icir.org> <200208131722.NAA21497@wellington.cnchost.com> <20020813183008.GA29747@sunbay.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org Ruslan Ermilov wrote: > Stevens says, in TCP/IP Ill. Vol 2 in section 18.12: > > : The Patricia tree data structure is well suited to routing tables. > : Routing table lookups occur much more frequently than adding or > : deleting routes, so from a performance standpoint using Patricia > : trees for the routing table makes sense. Patricia trees provide > : fast lookups at the expense of additional work in adding and > : deleting. Measurements in [Sklower 1991] comparing the radix > : tree approach to the Net/1 hash table show that the radix tree > : method is about two times faster in building a test tree and > : four times faster in searching. This is correct for routing when you have to do a longest match on a prefix. For explicit host routes this is not true. -- Andre To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message