From owner-freebsd-net Fri May 22 08:27:57 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id IAA08061 for freebsd-net-outgoing; Fri, 22 May 1998 08:27:57 -0700 (PDT) (envelope-from owner-freebsd-net@FreeBSD.ORG) Received: from ns1.yes.no (ns1.yes.no [195.119.24.10]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id IAA08029 for ; Fri, 22 May 1998 08:27:46 -0700 (PDT) (envelope-from eivind@bitbox.follo.net) Received: from bitbox.follo.net (bitbox.follo.net [195.204.143.218]) by ns1.yes.no (8.8.7/8.8.7) with ESMTP id PAA22609; Fri, 22 May 1998 15:27:24 GMT Received: (from eivind@localhost) by bitbox.follo.net (8.8.8/8.8.6) id RAA29980; Fri, 22 May 1998 17:27:19 +0200 (MET DST) Message-ID: <19980522172718.26605@follo.net> Date: Fri, 22 May 1998 17:27:18 +0200 From: Eivind Eklund To: dg@root.com, freebsd-net@FreeBSD.ORG Subject: Re: hash calculation for IP fast forwarding References: <199805221227.FAA00790@implode.root.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 0.89.1i In-Reply-To: <199805221227.FAA00790@implode.root.com>; from David Greenman on Fri, May 22, 1998 at 05:27:16AM -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. Is the hash-function really a significant amount of the time spent in the fast forwarding as it stands? Eivind. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message