Best way to compute hash for tcp connection table when doing tcp reassembly

Question

What are some good algorithms to compute the hash from (192.168.0.1, 34829, 80.229.161.151, 80, 6) which I can use to lookup the connection in a hash table?

192.168.0.1:34829 -> 80.229.161.151:80
(3232235521, 34829, 1357226391, 80, 6)

I read in this article that a popular way to do this, is to sum the integers then mod N, were N is the maximum number of connections.

3232235521 + 34829 + 1357226391 + 80 + 6 = 4589496827 mod 65536 = 10747

However this would collide with the following:

3232235521 + 34818 + 1357226391 + 80 + 17 = 4589496827 mod 65536 = 10747

Would it be better to do this?

3232235521 ⊕ 34829 ⊕ 1357226391 ⊕ 80 ⊕ 6 mod 65536

Just to make sure, the following TCP connection isn't possible because the source port 80 isn't available, as it's already in listening mode on that host?

80.229.161.151:80 ->192.168.0.1:34829
(1357226391, 80, 3232235521, 34829, 6)

Could I use the toeplitz hash or is that just for load balancing packets to cpu cores?

You have marked this with cryptography, however none of your methods is secure wrt cryptography. Also, you don't have specified is speed is an issue. Generally you can just use SHA-2 (SHA-256 or SHA-512, the latter is usually faster on 64 bit machines) for cryptographic hashes. If you need a relatively fast crypto hash then have a look at Blake2. If you need a very fast non-cryptographic hash you could have a look at e.g. xxHash. XOR is not much better than addition, and neither option is very good. — Maarten Bodewes
Just look at how python or java hash a list of integers. It's fast, simple, and seems to work well enough, and easy to port to whatever language you're using. — President James K. Polk

Ankor Ankor · Accepted Answer · 2018-08-21T00:47:36

You can just concatenate the input as strings and then use any common hash function like SHA-1, which is fast (about 10—30 million hashes per second on a modern PC). You can concatenate the values as bytes instead of strings but it doesn't really matter (e.g. in case of SHA-1 anything under 56 bytes is a one block).

If your computational resources are constrained and you need higher speed, you can use CRC32 or something like xxHash or MurmurHash. Some modern CPUs support crc32c instruction and then the throughput is up to one billion hashes per second per core.

You can use Toeplitz hash as well but it's really primitive and collisions are more likely.

Best way to compute hash for tcp connection table when doing tcp reassembly

1 Answers