Date: Tue, 13 Aug 2002 20:47:08 +0200 From: Andre Oppermann <oppermann@pipeline.ch> To: Ruslan Ermilov <ru@FreeBSD.ORG> Cc: Bakul Shah <bakul@bitblocks.com>, Luigi Rizzo <rizzo@icir.org>, net@FreeBSD.ORG Subject: Re: Consistency of cached routes Message-ID: <3D59542C.6796FC6D@pipeline.ch> References: <20020813021333.A4507@iguana.icir.org> <200208131722.NAA21497@wellington.cnchost.com> <20020813183008.GA29747@sunbay.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3D59542C.6796FC6D>