Date: Thu, 30 May 2002 11:46:21 +0200 From: Andre Oppermann <oppermann@pipeline.ch> To: Richard A Steenbergen <ras@e-gerbil.net> Cc: "Louis A. Mamakos" <louie@TransSys.COM>, Attila Nagy <bra@fsn.hu>, Luigi Iannone <Luigi.Iannone@lip6.fr>, freebsd-net@FreeBSD.ORG Subject: Re: MPLS Message-ID: <3CF5F4ED.369BCE83@pipeline.ch> References: <Pine.NEB.4.44.0205290915060.28431-100000@tibre.lip6.fr> <Pine.LNX.4.44.0205291108080.7798-100000@scribble.fsn.hu> <3CF4A64A.EE220611@pipeline.ch> <200205291413.g4TEDLRG075458@whizzo.transsys.com> <3CF4E483.2510639@pipeline.ch> <200205291522.g4TFMdRG076033@whizzo.transsys.com> <3CF4FCFC.3D760508@pipeline.ch> <20020529180204.GK33611@overlord.e-gerbil.net> <3CF51E7C.E9A47960@pipeline.ch> <20020529233411.GO33611@overlord.e-gerbil.net>
next in thread | previous in thread | raw e-mail | index | archive | help
Richard A Steenbergen wrote: > > On Wed, May 29, 2002 at 08:31:24PM +0200, Andre Oppermann wrote: > > > Basically just gut the current radix tree and fast-switch like route-cache > > > system, and replace it with something optimized for fast insertions and > > > deletions (and FIB building) but not longest prefix matching for the RIB, > > > and a 4 level 8-bit mtrie (seems to work best for PC hardware) for the > > > FIB. > > > > Hehe... We've come to the same conclusion for the FIB. > > > > First I tried to rip out the current flow-based fast-forward code > > Flow has its benefits, such as netflow export, and maybe even at some > point it could be tied into ipfw to improve performance... I'd like to see > it stay around as a route-cache method, but probably not in its current > form. I don't know if you have looked at the flow in code in FreeBSD but it's nowhere near what you'd expect from something that should do Netflow. IPFW has already something like that, it's called dynamic rules for TCP streams. On the other hand, to get performace you'd have to rewrite ipfw by a great deal or switch to OpenBSDs pf. > > with a highly compact LC-Trie build from the kernels PATRICIA trie. > > I've always prefered mtries myself, very simple... The theorie about the LC-Trie is that it'll fit into L2 cache for the entire default-free forwarding table. > > If only a nexthop changes, adjust it in the LC-Trie. If a prefix > > disappears, mark it as NULL. If Prefix changes, mark it as lookup- > > in-main-table (slow). Either after so many changes or so many slow > > lookups rebuild the LC-Trie. > > I'd suggest a rebuild after a prefix change, with a limit of x number of > rebuilds per y time to prevent it from getting out of control. Better to > continue forwarding to an old destination for a split second after a > routing change then to be kicking packets up to a slow path. > > This lets you get rid of the patricia trie completely, since it will never > be doing longest prefix matches, and make a RIB that is entirely optimized > for insertions, deletions, and FIB builds. This might work on a decicated router system. FreeBSD is being used for servers as well. Also to not to change the userland/kernel interface wrt routing we have to keep all prefixes in the kernel RIB. This means we have to be able to do longest prefix matching. Anyway, I'm confident we'll come up with something that is well balanced and much faster and more memory conserving than what we have today with the patricia trie. (A default-free kernel RIB consumes approx. 30MB of kernel memory in 4-STABLE/5-CURRENT at the moment). -- 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?3CF5F4ED.369BCE83>