Date: Mon, 02 Jul 2001 12:54:49 -0700 From: Bakul Shah <bakul@bitblocks.com> To: Wes Peters <wes@softweyr.com> Cc: Ruslan Ermilov <ru@FreeBSD.org>, Deepak Jain <deepak@ai.net>, net@FreeBSD.org Subject: Re: fastforwarding? Message-ID: <200107021954.PAA25927@goliath.cnchost.com> In-Reply-To: Your message of "Sun, 01 Jul 2001 15:52:44 MDT." <3B3F9BAC.782B8E00@softweyr.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> > 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200107021954.PAA25927>