Help hashing ip sockets

yaplej · 11-10-2010, 12:30 AM

Hello again,

I have a very bad attempt at hashing the components of an tcp session to assign/locate the session in a hash table bucket. I am pretty sure that it has a very high collision rate and when there are a very large number of tcp sessions my application is having to search a long linked list to find the session within the bucket.

All the hashing functions I have found take a single string input where I need to input several integers and hash them into a single result. My guess is that any real hashing function is going to produce better results than what I am currently doing.

Code:

/*
 * Calculates the hash of a session provided the IP addresses, and ports.
 */

static inline __u16
sessionhash(__u32 largerIP, __u16 largerIPPort, 
__u32 smallerIP, __u16 smallerIPPort){

        __u16 hash1 = 0, hash2 = 0, hash3 = 0, hash4 = 0, hash = 0;

        hash1 = (largerIP ^ smallerIP) >> 16;
        hash2 = (largerIP ^ smallerIP);
        hash3 = hash1 ^ hash2;
        hash4 = largerIPPort ^ smallerIPPort;
        hash = hash3 ^ hash4;
        return hash;
 }

Thanks.

aluser · 11-10-2010, 06:19 PM

Check out the download section here: http://www.partow.net/programming/hashfunctions/ (I just found it with google, but the writeup has plenty of references..)

A reasonable hit for hasing ip addresses is here: http://www.derkeiler.com/Newsgroups/.../msg00397.html

and you could look up CRC, which is a common (set of?) checksum algorithm which could be used for hashing

aluser · 11-11-2010, 08:19 PM

I should have added, concatenating all the input data before hashing it is a reasonable way to get a combined hash. If you hash the component parts and XOR the hashes, that works unless your hash function works better for some output bit positions than others. (E.g., it wouldn't work well if the hash function makes more "random" high order bits than low order bits, or vice versa.) XORing the hashes of the components also has the property that swapping the contents of two of the components doesn't affect the final hash, which is iffy.