Detect overlap of IP subnets

Abigail Headroom wrote:

I have a IpSubnet model which contains network address and subnet mask

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. 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

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,