Date: Tue, 03 Jul 2001 09:57:24 -0600 From: Wes Peters <wes@softweyr.com> To: Bakul Shah <bakul@bitblocks.com> Cc: Ruslan Ermilov <ru@FreeBSD.org>, Deepak Jain <deepak@ai.net>, net@FreeBSD.org Subject: Re: fastforwarding? Message-ID: <3B41EB64.3B753DDE@softweyr.com> References: <200107021954.PAA25927@goliath.cnchost.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3B41EB64.3B753DDE>