From owner-freebsd-net Tue Aug 13 12:38:17 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 A8C1937B400; Tue, 13 Aug 2002 12:38:14 -0700 (PDT) Received: from agamemnon.cnchost.com (agamemnon.cnchost.com [207.155.252.31]) by mx1.FreeBSD.org (Postfix) with ESMTP id 3CE2243E65; Tue, 13 Aug 2002 12:38:14 -0700 (PDT) (envelope-from bakul@bitblocks.com) Received: from bitblocks.com (adsl-209-204-185-216.sonic.net [209.204.185.216]) by agamemnon.cnchost.com id PAA04492; Tue, 13 Aug 2002 15:35:21 -0400 (EDT) [ConcentricHost SMTP Relay 1.14] Message-ID: <200208131935.PAA04492@agamemnon.cnchost.com> To: Ruslan Ermilov Cc: Bakul Shah , Luigi Rizzo , net@FreeBSD.ORG Subject: Re: Consistency of cached routes In-reply-to: Your message of "Tue, 13 Aug 2002 21:30:08 +0300." <20020813183008.GA29747@sunbay.com> Date: Tue, 13 Aug 2002 12:35:21 -0700 From: Bakul Shah 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 > 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