From owner-freebsd-net Tue Jul 3 8:52:55 2001 Delivered-To: freebsd-net@freebsd.org Received: from softweyr.com (softweyr.com [208.247.99.111]) by hub.freebsd.org (Postfix) with ESMTP id 844CC37B403; Tue, 3 Jul 2001 08:52:48 -0700 (PDT) (envelope-from wes@softweyr.com) Received: from localhost.softweyr.com ([127.0.0.1] helo=softweyr.com ident=1649b7c0712cdb73cae8b259f0fd5ed8) by softweyr.com with esmtp (Exim 3.16 #1) id 15HSYG-0000mZ-00; Tue, 03 Jul 2001 09:57:24 -0600 Message-ID: <3B41EB64.3B753DDE@softweyr.com> Date: Tue, 03 Jul 2001 09:57:24 -0600 From: Wes Peters Organization: Softweyr LLC X-Mailer: Mozilla 4.75 [en] (X11; U; Linux 2.2.12 i386) X-Accept-Language: en MIME-Version: 1.0 To: Bakul Shah Cc: Ruslan Ermilov , Deepak Jain , net@FreeBSD.org Subject: Re: fastforwarding? References: <200107021954.PAA25927@goliath.cnchost.com> 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 Bakul Shah wrote: > > > > IMHO you are better off using a recent route lookup algorithm > > > than messing with caches. The PATRICIA tree algorithm is > > > what 33 years old now? > > > > Not true. Any routing algorithm takes longer because they are by > > definition a "fuzzy match." The fastforward algorithm is not, it > > By defn the best match is the longest prefix match. > > > is a simple destination address lookup; the cached route is either > > there or it is not. Fast hashing algorithms are quite effective > > in locating the route if it has been cached. Routing switches > > A simple hashtable will be faster but not significantly so > compared to some of the recent trie algorithms. The implementation I'm most familiar with uses a hardware has (Content Addressable Memory) that always completes the lookup in one clock cycle, so my experience is slightly different. ;^) > And both are > faster than the radix tree used in *BSD. With a trie you can > do just a single route lookup (currently an input packet's > dest. ip addr. is matched against the list of broadcast > addresses for the machine -- this check is free with a trie). So this would be applicable to the fastforwarding code, which has a lot of other advantages besides avoiding the route lookup. In particular, it cuts out a lot of the ip forwarding code path, that's why it's called FAST forwarding. > BTW, the current fastforward code doesn't handle route > add/delete and hence has the same bug I mentioned in my > previous msg. > > > usually speed up the lookup even further by using Content Addressable > > Memory to map the destination address to a cached route or interface > > pointer; it would be interesting to experiment with something like > > that in FreeBSD. > > Even if it takes 0 ns to do a route lookup, a stock freebsd > system can't do more than 20K ~ 100K pkts/second due to many > bottlenecks. In a hardware accelrated router one can easily > do 10M route lookups *without* using an expensive & power > hungry fancy CAM. But they may be worth it if you want to > route 1M+ pkts/second *and* you want to do packet matching. Such as a routing switch would do. Plus you have the added advantage that the route caches scale well to multiple indepdendant "smart" interfaces, which is not likely to be added to a generic FreeBSD system. Except there are all these PCI based smart network cards popping up on the market these days, and it would be possible to scale the fastforwarding code directly onto the network cards... -- "Where am I, and what am I doing in this handbasket?" Wes Peters Softweyr LLC wes@softweyr.com http://softweyr.com/ To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message