From: "Michael K. Edwards" <[EMAIL PROTECTED]>
Date: Wed, 21 Feb 2007 13:15:51 -0800
> it had better be a 2-left hash with a compact
> overflow pool for the rare case of second collision.
Just like Evgeniy, you should do your research too :-))))
The gain for multiple-hash schemes, such as 2-left, exists only if you
can parallelize the N lookups in hardware. This is an assumption
built into all the papers you will read on this subject, including the
one you reference by Mitzenmacher.
If you read any paper on IP route lookup algorithms, prefix
your reading of that paper with something that reads like:
And by the way we are targeting implementations in
hardware that can parallelize and pipeline memory
accesses to fast SRAM. Do not consider this algorithm
seriously for running on general purpose processors
in software.
Probably a few read's of Network Algorithmics would help your
understanding in this area as well.
Tries and similar structures do help in the case of our routing
because we're going from a potential 32-hashtable probe down
to a relatively small number of probes into a trie. That's what
Robert's LC-Trie and upcoming TRASH work do.
But it won't help the same when going from hashes to a trie,
as would be the case for TCP.
If we can get the sockets into the TRASH entries, as Eric will
experiment with, we'll be able to eliminate the TCP hash lookup
in the fast path entirely. It is the only reasonable suggestion
I've seen made in this area to date.
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
