cttest-0.3

cttest-0.3

[Patrick Schaaf]

There is now a "cttest-0.3" at http://bei.bof.de/cttest-0.3.tar.gz.

Also see
	http://bei.bof.de/ex2
	http://bei.bof.de/ex2rt
	http://bei.bof.de/ex2abcd
	http://bei.bof.de/ex2crc
for four example runs contrasting different hash function approaches
on my transproxy dataset.

I incorporated hash functions from recent mails of Don and Joakim. Thanks!

The code has been augmented with some comments.

best regards
  Patrick

Re: cttest-0.3

[Martin Josefsson]

On Sun, 2002-07-07 at 15:17, Patrick Schaaf wrote:
> There is now a "cttest-0.3" at http://bei.bof.de/cttest-0.3.tar.gz.
> 
> Also see
> 	http://bei.bof.de/ex2
> 	http://bei.bof.de/ex2rt
> 	http://bei.bof.de/ex2abcd
> 	http://bei.bof.de/ex2crc
> for four example runs contrasting different hash function approaches
> on my transproxy dataset.
> 
> I incorporated hash functions from recent mails of Don and Joakim. Thanks!

The rt hash doesn't do well at all on your data. The winner on your data
is crc32 which is very robust in all tests on all data it seems. It's
just a shame that it's so cpu-consuming compared to the other hashes.

No real diffrence between crc32 and crc32_bof, crc32_bof is slightly
more cpu-consuming but that's it.

Have you tested crc32 with initial seed as well?
crc32 + seed that's randomly generated at conntrack init would probably
work well.

-- 
/Martin

Never argue with an idiot. They drag you down to their level, then beat
you with experience.

Re: cttest-0.3

[Patrick Schaaf]

> The rt hash doesn't do well at all on your data. The winner on your data
> is crc32 which is very robust in all tests on all data it seems. It's
> just a shame that it's so cpu-consuming compared to the other hashes.

The abcd hash also fares very well, if we disregard the results for
the (avoidable) bad bucket counts. abcd plus prime bucket counts would
be as good as crc32, if I did not overlook some result.

On the other hand, I would not dismiss one or the other function right
now. We lack a thorough understanding for plausible attack vectors.

> No real diffrence between crc32 and crc32_bof, crc32_bof is slightly
> more cpu-consuming but that's it.

I'm not really worried about the relative CPU usage of the functions
we have now; they are all faster than a single random memory reference.

And the crc32 could be optimized more. I'll probably work on that
for a bit, now.
 
> Have you tested crc32 with initial seed as well?
> crc32 + seed that's randomly generated at conntrack init would probably
> work well.

For the abcd hash, random generation of the multipliers is also an option.
This, together with the possibility to chose the bucket count as the
"randomly Nth smaller prime" than the value given by the user, should give
a potential attacker a pretty hard time.

But I'll stay undecided on the issue for some more time. We are still lacking
any data from genuine web servers, and we only have a vague feeling about
what an attacker may do.

best regards
  Patrick

Re: cttest-0.3

[Patrick Schaaf]

Now also see:

	http://bei.bof.de/ex3
	http://bei.bof.de/ex3rt
	http://bei.bof.de/ex3abcd
	http://bei.bof.de/ex3crc

This is the same calculations as before, but with a different data set.
These are from a web server farm (a web portal), with the server farm
running on a single virtual IP address [*]. I have accumulated the
/proc/net/ip_conntracks from all servers in the farm. There are
37608 unique conntrack entries, and all but 2385 of them refer
to the virtual service IP and port 80. This dataset is to show
the extreme case of a single-address-and-port server.

best regards
  Patrick

[*] we use Cisco IOS SLB for loadbalancing

cttest-0.4

[Patrick Schaaf]

> 	http://bei.bof.de/ex2crc
> 	http://bei.bof.de/ex3crc

These are updated with a faster version of crc32, called crc32_bof for now.
A seed is XORed with the source IP, and an unrolled CRC is done over the
sport, dip, and dport. Curves look close enough to crc32, as far as I
can see. For the speedup, I must caution that the timing is done for
the unrealistic case of a dense loop doing not much of anything
besides calculating the hash function over and over. This means that
the 1k crc32_table will be in L1 cache on all interesting processors.
However, this may not be the case for a system doing more than calculating
hashes. It is likely that the crc32 timings here are best-case values.
For the other hashes, the timings should reflect reality.

I have made cttest-0.4.tar.gz. In addition to the crc32_bof, this includes
seed selection, which may be interesting for experimentors. The seed used
in the crc32 hashes, can be set in the ctreport.hashes.XXX control file,
by appending "+1234" to the hash name.  Append "+R" for random seed
selection. By default, the new crc32 functions use one of Don's
constants (C) as a default seed. The crc32 itself is unmodified.

I haven't done anything yet with that seed selection. Feel free to play.

While you compare these functions, I'd like to mention something we _may_ need
to look out for. Some of the hash functions we are looking at, behave the
same whether big endian or little endian. Others factually are two different
hash functions, one on little endian, and one on big endian. Up to now I did
not care much about this, but I see all our known results so far have been
on little endian machines. We need some runs on big endian gear.

That's it for today - have a nice evening, whereever you are.

best regards
  Patrick