From owner-freebsd-net Mon Jul 2 12:55: 4 2001 Delivered-To: freebsd-net@freebsd.org Received: from goliath.cnchost.com (goliath.cnchost.com [207.155.252.47]) by hub.freebsd.org (Postfix) with ESMTP id D95E037B401; Mon, 2 Jul 2001 12:54:59 -0700 (PDT) (envelope-from bakul@bitblocks.com) Received: from bitblocks.com (adsl-209-204-185-216.sonic.net [209.204.185.216]) by goliath.cnchost.com id PAA25927; Mon, 2 Jul 2001 15:54:49 -0400 (EDT) [ConcentricHost SMTP Relay 1.14] Message-ID: <200107021954.PAA25927@goliath.cnchost.com> To: Wes Peters Cc: Ruslan Ermilov , Deepak Jain , net@FreeBSD.org Subject: Re: fastforwarding? In-reply-to: Your message of "Sun, 01 Jul 2001 15:52:44 MDT." <3B3F9BAC.782B8E00@softweyr.com> Date: Mon, 02 Jul 2001 12:54:49 -0700 From: Bakul Shah 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 > > 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. 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). And you don't have to worry about the size of the cache blowing up (or deleting stale cache entries) or having to check the cache for every route add/delete. At present the cache size is not bound so over a period of time it will blow up in size. since the cache size is a function of distinct IP addresses forwarded to, a user on another host can eat up all memory of (or worse, crash) a freebsd based router by doing an IP address scan. So *overall* you are better off using a trie algorithm. 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. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message