Date: Fri, 7 Jul 2000 13:36:11 -0400 (EDT) From: Garrett Wollman <wollman@khavrinen.lcs.mit.edu> To: net@FreeBSD.ORG Subject: Re: deleting cloned routes Message-ID: <200007071736.NAA38634@khavrinen.lcs.mit.edu> In-Reply-To: <20000707090503.A9860@sofia.csl.sri.com> References: <20000706192402.A25086@yahoo-inc.com> <200007071420.KAA37794@khavrinen.lcs.mit.edu> <20000707090503.A9860@sofia.csl.sri.com>
next in thread | previous in thread | raw e-mail | index | archive | help
<<On Fri, 7 Jul 2000 09:05:03 -0700, Marco Molteni <molter@sofia.csl.sri.com> said: > as you may remember, I am interested in the routing code. Do you care > to elaborate a little more about "separate out the three functions > currently bundled together in the routing table" ? There are currently three (or perhaps four) functions handled by the routing code in FreeBSD. These are: 1) Forwarding table -- the traditional function of the routing code: given a packet addressed to w.x.y.z, to whom should I send that packet to start it on its journey? 2) Next-hop table -- which bits do I glom on the front of packets addressed to a.b.c.d in order to get them there, and out which interface(s) should I send them? 3) Per-host cache -- just a random collection of information that we think is useful to remember about a host that we have talked to, but we don't care if it gets thrown away from time to time. 4) Routing table -- expression of the generalized mapping <K,M> -> *(<Fwd,NH>) Currently, in FreeBSD, we have a data structure which is designed to do (4) quite well, and was hacked by me into doing (3) and by people at Berkeley into doing (2). The function of (1) is entirely subsumed into (4). (It's actually even worse than that: if the system is running an actual routing process, it has at least two independent copies of (4): one in the routing process and one in the kernel.) The trouble with doing this is that the (4) data structure is not particularly efficient (in either space or time) for the functions of (1)-(3). For example, on an ILP32 architecture, `struct rtentry' contains ~80 bytes of overhead which are not required for per-host cache entries. (What can I say? When all you have is a radix tree, everything looks like a route.) A different data structure, taking advantage of the fixed address length and disposability of this information would be much more efficient. As another example, there are algorithms for creating a forwarding table which while computationally expensive result in data structures small enough to fit into a L2 cache, even for a full 70,000-route border router. -GAWollman -- Garrett A. Wollman | O Siem / We are all family / O Siem / We're all the same wollman@lcs.mit.edu | O Siem / The fires of freedom Opinions not those of| Dance in the burning flame MIT, LCS, CRS, or NSA| - Susan Aglukark and Chad Irschick 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?200007071736.NAA38634>