Date: Tue, 13 Aug 2002 12:35:21 -0700 From: Bakul Shah <bakul@bitblocks.com> 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: <200208131935.PAA04492@agamemnon.cnchost.com> In-Reply-To: Your message of "Tue, 13 Aug 2002 21:30:08 %2B0300." <20020813183008.GA29747@sunbay.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> Hmm, it has a non-obvious impact on rt_gwroute's, but the idea > sounds promising. Not a problem as far as I can see. rt_gwroute points to a host route (of a directly connected next hop). If this host route needs to be invalidated (because it is cloned from a less specific route than a newly added one), this will be caught when rt_gwroute gets used for forwarding. I should point at present something very similar occurs when a route is deleted. If a netroute is deleted, all cloned routes are also deleted but routes using such a cloned route don't know about it until they tried to use it. > > Second, this entirely avoids the need to walk the whole tree > > on addition/deletion/change of any route. > > > It was never an intent. What I meant is this: by moving an rtentry we get rid of the treewalking already present in the code to deal with cloned routes (see rtrequest, rt_setgate and rtsock.c). This can be a big expense when you have 50k+ routes in your table! > > Third, we can dispense with the silliness of cloned routes > > alltogether and go back to keeping a separate host route > > cache. > > > 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. During the "bubble" years a lot of research was done to speed up route lookups: some of these newfangled methods can do a route lookup on the order of a couple of microseconds (on a 200Mhz Ppro). So yes, a separate host route cache doesn't necessarily help performance. My main issue with cloned routes is the complications they introduce. I see them as a different beast from normal routes. It has been a while so I don't remember all the details but for example, a normal route is added either statically or by a routing daemon. A cloned route is created on the fly -- in effect it is kind of a cache. Ideally you don't want to report cloned route changes on a routing socket (the routing daemon doesn't care). There is some duplication of link level information due to both having an arp cache and a cloned route and one can see strange behavior if you change ip address of a directly connected host. I found it simplified things if cloned routes were treated as just another kind of cache. Let me hasten to add, I am only talking about moving out cloned routes, not host routes (added statically or by a routing daemon) which stay in the routing table. 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?200208131935.PAA04492>