Skip site navigation (1)Skip section navigation (2)
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>