Date: Mon, 02 Jul 2001 16:52:24 -0700 From: Bakul Shah <bakul@bitblocks.com> To: Jeffrey Hsu <hsu@FreeBSD.org> Cc: freebsd-net@freebsd.org Subject: Re: fastforwarding? Message-ID: <200107022352.TAA11491@warspite.cnchost.com> In-Reply-To: Your message of "Mon, 02 Jul 2001 13:39:54 PDT." <0GFV00LBT5EXRH@mta8.pltn13.pbi.net>
next in thread | previous in thread | raw e-mail | index | archive | help
> > a stock freebsd system can't do more than 20K ~ 100K pkts/second due to > > many bottlenecks > > I'd be interested in knowing where those bottlenecks were and fixing them. > I currently hit the packets/sec limit running on gigabit ethernet cards, but > so far I've been blaming it on the relatively old firm-ware based Tigon II NIC > and not the BSD stack. > > > Even if it takes 0 ns to do a route lookup, > > So are you saying route lookup is not the bottleneck? The radix tree lookup is definitely slow. My point was that you need to look at the entire forwarding path to improve performance even if you replace the radix tree with something faster. For instance, - interrupt overhead as Luigi (and others) have noted - an input packet is queued twice: once on the device queue and once on the ip input queue. - If your router has a many interfaces, the input packet is checked against the directed broadcast address for every interface. - mbuf processing. - processing the same packet multiple times. For example, checking that 127.x.x.x does not come in from outside. bpf. ipfilter, ipfw, dummynet etc. - The cost of modularity and layering. Probably better to use inlining judiciously so that the compiler can flatten out call sequences. - The common case is not optimized. For a router the common case is forwarding a packet, for a host it is not. You need two different routines optimizing each case and plug in the right function, depending on the application. Similarly for firewalls etc. you have different common cases. Not rocket science, mostly compiler tricks! Just what you can do by removing duplication, knowing and optimizing the common case, code movement (move processing from per packet to route add/delete etc.), use brute force (switch or jumptable instead of a bunch of if-then-elses), strength reduction (use a cheaper operation), all based on measuring hotspots. Most of this is just plain old boring engineering so likely there are not many papers on them :-) > > So *overall* you are better off using a trie algorithm. > > I'm thinking of the probability-shifted lc-trie algorithm described in > http://klamath.stanford.edu/~pankaj/research.html > Do you have a better algorithm in mind? That or even simpler algorithms will suffice. Once you bring the cost of route lookup below 1 to 5% it doesn't matter much. 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?200107022352.TAA11491>