Detect overlap of IP subnets

rubyonrails-talk
1

Abigail Headroom wrote:

I have a IpSubnet model which contains network address and subnet mask (strings).

When a new IP subnet is submitted I need to validate it to check if it overlaps any of the existing (> 10.000) IP subnets in the database.

Does anybody have a suggestion on how to approach this?

Here's one idea:

1) Convert each netmask to an IP range (begin IP Address value and end IP Address value)

2) Convert each IP Address value (begin and end) to an integer   e.g. 12.23.45.67 becomes   67 + (256 * 45) + (256 * 256 * 23) + (256 * 256 * 256 * 12)   = 202845507

3) Store the integer Begin and End values in your database as extra columns next to your string netmask

4) When a new netmask is submitted, calculate the begin and end values and do a find in your database (loose algorithm here):   find where new.beginInt is between BeginInt and EndInt   find where new.endInt is between BeginInt and EndInt

If either of those returns any rows, then you have an overlap. Sorry for the absence of any actual ruby code here, I'm thinking as I type.

- Aaron

2

I'm storing IP addresses as integers now. There is the handy IPAddr class which can convert to/from string values. MySQL even has native functions for this.

Unless your database can support unsigned ints (which are not accessible using standard migrations), you'll need to subtract 2147483648 from the value before storing. This converts the unsigned integer IP address to a signed integer to be stored in the database.

Once you're storing IP addresses and netmasks as integers rather than strings, you can do fancy bitwire arithmetic to figure out beginning / ending IP addresses. It also makes sorting IP addresses much easier.

Hope this helps,

Norman