[Coral-dev] dnsstat hash functions

[Srinivas Krishnan]

Ken,

You are right, I forgot these were unsigned long's.  Also, was there
analysis done to pick 59 as the prime multiplier ?

-srinivas


On Fri, Jul 9, 2010 at 10:47 AM, Ken Keys <kkeys at caida.org> wrote:

>  On Fri, Jul 09, 2010 at 12:26:45AM -0700, Srinivas Krishnan wrote:
> > I was wondering if some one could explain the 2 hash functions used in
> > crl_dnsstat.c. At first it struck as purely multiplicative hashing way.
> But
> > running through the possible math for make_key_flowstats
> >
> > it seems like the second term in the hash function (f->ip_proto << 16) +
> > (f->src.s_addr * 59) + (f->dst.s_addr);   could potentially cause
> overflows
> > when returning values as the return value is only 32 bits long.
> >
> > Am I missing something ?
> >
> > -srinivas
>
> If arithmetic on unsigned values would cause an overflow, it just
> truncates the high bits instead.  So some information (less than 6
> bits) is lost for the hash, but there's no error.
>
> I don't have an analysis handy, but I suspect that attempting
> to preserve that information would not improve the uniqueness
> of the hash value enough to justify the extra computational cost.
>
> --
> Ken Keys
> kkeys at caida.org
> CoralReef:  http://www.caida.org/tools/measurement/coralreef/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://rommie.caida.org/pipermail/coral-dev/attachments/20100709/919c7458/attachment.htm