From owner-freebsd-net Thu May 30 2:48:14 2002 Delivered-To: freebsd-net@freebsd.org Received: from mailtoaster1.pipeline.ch (mailtoaster1.pipeline.ch [62.48.0.70]) by hub.freebsd.org (Postfix) with SMTP id EE70C37B497 for ; Thu, 30 May 2002 02:47:31 -0700 (PDT) Received: (qmail 567 invoked from network); 30 May 2002 09:47:11 -0000 Received: from unknown (HELO pipeline.ch) ([62.48.0.53]) (envelope-sender ) by mailtoaster1.pipeline.ch (qmail-ldap-1.03) with SMTP for ; 30 May 2002 09:47:11 -0000 Message-ID: <3CF5F4ED.369BCE83@pipeline.ch> Date: Thu, 30 May 2002 11:46:21 +0200 From: Andre Oppermann X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: Richard A Steenbergen Cc: "Louis A. Mamakos" , Attila Nagy , Luigi Iannone , freebsd-net@FreeBSD.ORG Subject: Re: MPLS 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> <20020529233411.GO33611@overlord.e-gerbil.net> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit 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 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