How to discern between network flows

Question

I want to be able to discern between networks flows. I am defining a flow as a tuple of three values (sourceIP, destIP, protocol). I am storing these in a c++ map for fast access. However, if the destinationIP and the sourceIP are different, but contain the same values, (e.g. )

[packet 1: source = 1.2.3.4, dest = 5.6.7.8] 

[packet 2: source = 5.6.7.8, dest = 1.2.3.4 ]

I would like to create a key that treats these as the same.

I could solve this by creating a secondary key and a primary key, and if the primary key doesn't match I could loop through the elements in my table and see if the secondary key matches, but this seems really inefficient.

I think this might be a perfect opportunity for hashing, but the it seems like string hashes are only available through boost, and we are not allowed to bring in libraries, and I am not sure if I know of a hash function that only computes on elements, not ordering.

How can I easily tell flows apart according to these rules?

Answer 1

Compare the values of the source and dest IPs as 64-bit numbers. Use the lower one as the hash key, and put the higher one, the protocol and the direction as the values.

Do lookups the same way, use the lower value as the key.

Answer 2

If you consider that a single client can have more than one connection to a service, you'll see that you actually need four values to uniquely identify a flow: the source and destination IP addresses and the source and destination ports. For example, imagine two developers in the same office are searching StackOverflow at the same time. They'll both connect to stackoverflow.com:80, and they'll both have the same source address. But the source ports will be different (otherwise the company's firewall wouldn't know where to route the returned packets). So you'll need to identify each node by an <address, port> pair.

Some ideas:

• As stark suggested, sort the source and destination nodes, concatenate them, and hash the result.

• Hash the source, hash the destination, and XOR the result. (Note that this may weaken the hash and allow more collisions.)

• Make 2 entries for each flow by hashing
  <src_addr, src_port, dst_addr, dst_port> and also
  <dst_addr, dst_port, src_addr, src_port>. Add them both to the map and point them both to the same data structure.