algorithmnetwork-programmingip-addresssubnet

Finding the minimal subnets required to cover a list of IP addresses

Given a list of IP addresses I would like to automatically generate a series of subnet masks that cover those IPs and no others.

For example the following input list of IP addresses would be covered by 192.168.0.16/30:

192.168.0.16
192.168.0.17
192.168.0.18
192.168.0.19

For disjoint inputs I need multiple subnets, not a single larger one that covers entries that aren't in the list. There should be no "false positives" in the resulting subnets. For example this input and output:

192.168.0.16
192.168.0.17
192.168.0.18
192.168.0.19
192.168.0.66
192.168.0.122
192.168.0.123

192.168.0.16/30
192.168.0.66/32
192.168.0.122/31

I understand this is a solvable computational problem, I'm hoping to find a prebuilt tool or known algorithm to achieve it. I'm having no luck searching for this because of all the tools online for calculating the other direction.

Does anyone know of the name of this operation or an implementation of the solution?

Solution

  • Five years later, but: The utility aggregate (it's in Debian & Redhat default repos; can't find a specific source though) is very good at this.

    rbos@bingo:~$ cat asdf 
192.168.0.16
192.168.0.17
192.168.0.18
192.168.0.19
192.168.0.66
192.168.0.122
192.168.0.123
rbos@bingo:~$ cat asdf | sed 's#$#/32#' | aggregate -q
192.168.0.16/30
192.168.0.66/32
192.168.0.122/31