From owner-freebsd-net Wed May 29 16:34:28 2002 Delivered-To: freebsd-net@freebsd.org Received: from overlord.e-gerbil.net (e-gerbil.net [64.186.142.66]) by hub.freebsd.org (Postfix) with ESMTP id 9181E37B408 for ; Wed, 29 May 2002 16:34:21 -0700 (PDT) Received: by overlord.e-gerbil.net (Postfix, from userid 1000) id 126A815E4A; Wed, 29 May 2002 19:34:12 -0400 (EDT) Date: Wed, 29 May 2002 19:34:11 -0400 From: Richard A Steenbergen To: Andre Oppermann Cc: "Louis A. Mamakos" , Attila Nagy , Luigi Iannone , freebsd-net@FreeBSD.ORG Subject: Re: MPLS Message-ID: <20020529233411.GO33611@overlord.e-gerbil.net> References: <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> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <3CF51E7C.E9A47960@pipeline.ch> User-Agent: Mutt/1.3.27i 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 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 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