Date: Wed, 29 May 2002 19:34:11 -0400 From: Richard A Steenbergen <ras@e-gerbil.net> To: Andre Oppermann <oppermann@pipeline.ch> 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: <20020529233411.GO33611@overlord.e-gerbil.net> In-Reply-To: <3CF51E7C.E9A47960@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>
next in thread | previous in thread | raw e-mail | index | archive | help
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. > with a highly compact LC-Trie build from the kernels PATRICIA trie. I've always prefered mtries myself, very simple... > 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. > Unfortunatly the whole routing stuff in BSD is so cross-pointered that > untangling it is a medium task in front of it. It made have sense 15 > years ago to have pointers from the INPCBs directly to the route node > and the if-structures doing the same and vice versa, but today it's > simply messy. Indeed. -- Richard A Steenbergen <ras@e-gerbil.net> http://www.e-gerbil.net/ras PGP Key ID: 0x138EA177 (67 29 D7 BC E8 18 3E DA B2 46 B3 D8 14 36 FE B6) 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?20020529233411.GO33611>