Hi Thomas Graf,
On Wed, 6 Apr 2005 14:30:36 +0200, Thomas Graf <tgraf@xxxxxxx> wrote:
> * Wang Jian <20050406143842.026B.LARK@xxxxxxxxxxxx> 2005-04-06 14:45
> > On 05 Apr 2005 12:11:35 -0400, jamal <hadi@xxxxxxxxxx> wrote:
> > > i.e if you fed the jenkins hash with 256 buckets - lets pick the number
> > > 1024
> > > samples of the data you showed earlier for how fwmark looks like,
> > > how well would the result look like.
> > > And what if you fed it with something like 1024 incremental fwmark from
> > > say 1..1024?
> > >
> >
> > The test result looks not good. See attached file.
> >
> > So let's find a better way.
>
> We need to provide some kind of option to the user so he can specify
> the needs. The & 0xFF will suit most just fine but has one essential
> drawback which is that no distribution is done at all if the lower 8
> bits are set to 0. For static marks this is no issue at all and even
> for enumerated marks growing it takes quite some time to grow into
> an area where it starts hurting. The problem obviously is if someone
> splits the mark field into 2 parts and uses the upper 16 bits for
> some special purpose just like you did. In such as case it would make
> sense to either take all bits into account or let the user specify
> a bitmask + shift.
>
> So here is the same idea I posted before but revised:
>
> Let the user specify one of the hash tables via a new TLV:
> - default: & 0xFF
> - ((mark & mask) >> shift) & 0xFF
> - jenkins for 16, 32, and 64 bits
> - FNV for 16, 32, and 64 bits
>
> Why variations for type sizes? The chance of collisions reduces
> a lot if the user exactly knows he'll never use more than 16bits
> but 255 marks are not enough.
>
> I'm cooking up a patch for this today together with a fix to
> allow 64bit values for the mark.
Given that no 1-hash-fit-all solution exists, I think your solution is
quite elegant.
--
lark
|