Date: Fri, 22 May 1998 17:21:55 -0700 From: David Greenman <dg@root.com> To: Eivind Eklund <eivind@yes.no> Cc: freebsd-net@FreeBSD.ORG Subject: Re: hash calculation for IP fast forwarding Message-ID: <199805230021.RAA06112@implode.root.com> In-Reply-To: Your message of "Fri, 22 May 1998 17:27:18 %2B0200." <19980522172718.26605@follo.net>
next in thread | previous in thread | raw e-mail | index | archive | help
>On Fri, May 22, 1998 at 05:27:16AM -0700, David Greenman wrote: >> As I mentioned recently in freebsd-net, the hash function that the fast >> IP forwarding code uses is expensive (16 adds, 12 shifts, 6 subtracts, and >> 6 compares). I think the following will provide a hash with similar quality, >> but I might be missing something. This assumes that the table is 256 buckets >> large, but it should work for larger tables as well. Opinions? > >I think this will tend to be overly much influenced by the tendency of >IP-addresses to be loaded in the lower end of each octet. For a good >hash, you'll want to mix bits on a non-octet level. However, to >really find out if this is significant you'd have to do measurements. That might cause a small statistical shift, but I don't think it will be significant since that it really only true for the LSB and all of the octets are xored together. >Is the hash-function really a significant amount of the time spent in >the fast forwarding as it stands? Yes. -DG David Greenman Co-founder/Principal Architect, The FreeBSD Project 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?199805230021.RAA06112>