Best choice for in memory data structure for IP address filter in Java

Question

I have file that is CIDR format like this 192.168.1.0/24 and it is converted into this two column strucutre

3232236030 3232235777

Each string IP address convertion happens with this code:

String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);

Inet4Address a = (Inet4Address) InetAddress.getByName(utils.getInfo().getHighAddress());
long high = bytesToLong(a.getAddress());
Inet4Address b = (Inet4Address) InetAddress.getByName(utils.getInfo().getLowAddress());
long low = bytesToLong(b.getAddress());

private static long bytesToLong(byte[] address) {
   long ipnum = 0;
   for (int i = 0; i < 4; ++i) {
       long y = address[i];
       if (y < 0) {
           y += 256;
       }
       ipnum += y << ((3 - i) * 8);
   }
   return ipnum;
}

Consider that there are over 5 million entries of (low high : 3232236030 3232235777).
Also there will be intersects so the IP can originate from multiple ranges. Just the first one is more than OK.
The data is read only.
What would be the fastest way to find the range the ipToBefiltered belongs to? The structure will be entirely in memory so no database lookups.

UPDATE:

I found this Peerblock project (it has over million download so I'm thinking it must have some fast algorithms): http://code.google.com/p/peerblock/source/browse/trunk/src/pbfilter/filter_wfp.c

Does anyone know what technique is the project using for creating the list of ranges and than searching them?

Answer 1

When it comes down to it I just need to know if the IP is present in any of the 5M ranges.

I would consider an n-ary tree, where n=256, and work from the dotted address rather than the converted integer.

The top level would be an array of 256 objects. A null entry means "No" there is no range that contains the address, so given your example 192.168.1.0/24 array[192] would contain an object, but array[100] might be null because no range was defined for any 100.x.x.x/n

The stored object contains a (reference to) another array[256] and a range specifier, only one of the two would be set, so 192.0.0.0/8 would end up with a range specifier indicating all addresses within that range are to be filtered. This would allow for things like 192.255.0.0/10 where the first 10 bits of the address are significant 1100 0000 11xx xxxx -- otherwise you need to check the next octet in the 2nd level array.

Initially coalescing overlapping ranges, if any, into larger ranges... e.g. 3 .. 10 and 7 .. 16 becomes 3 .. 16 ... allows this, since you don't need to associate a given IP with which range defined it.

This should require no more than 8 comparisons. Each octet is initially used directly as an index, followed by a compare for null, a compare for terminal-node (is it a range or a pointer to the next tree level)

Worst case memory consumption is theoretically 4 GB (256 ^ 4) if every IP address was in a filtering range, but of course that would coalesce into a single range so actually would be only 1 range object. A more realistic worst-case would probably be more like (256 ^ 3) or 16.7 MB. Real world usage would probably have the majority of array[256] nodes at each level empty.

This is essentially similar to Huffman / prefix coding. The shortest distinct prefix can terminate as soon as an answer (a range) is found, so often you would have averages of < 4 compares.

Answer 2

I would use a sorted array of int (the base address) and another array the same size (the end address). This would use 5M * 8 = 40 MB. The first IP is the base and the second IP is the last address in range. You would need to remove intersections.

To find if an address is filtered to a binary search O(log N) and if not an exact match, check it is less than (or equal to) the upper bound.