From owner-freebsd-net Fri May 22 17:22:35 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id RAA25882 for freebsd-net-outgoing; Fri, 22 May 1998 17:22:35 -0700 (PDT) (envelope-from owner-freebsd-net@FreeBSD.ORG) Received: from implode.root.com (implode.root.com [198.145.90.17]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id RAA25810 for ; Fri, 22 May 1998 17:22:21 -0700 (PDT) (envelope-from root@implode.root.com) Received: from implode.root.com (localhost [127.0.0.1]) by implode.root.com (8.8.5/8.8.5) with ESMTP id RAA06112; Fri, 22 May 1998 17:21:55 -0700 (PDT) Message-Id: <199805230021.RAA06112@implode.root.com> To: Eivind Eklund cc: freebsd-net@FreeBSD.ORG Subject: Re: hash calculation for IP fast forwarding In-reply-to: Your message of "Fri, 22 May 1998 17:27:18 +0200." <19980522172718.26605@follo.net> From: David Greenman Reply-To: dg@root.com Date: Fri, 22 May 1998 17:21:55 -0700 Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.org >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