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

Question

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?

Answer 1

what you are looking for can be seen as a binary tree where each tree node corresponds to a subnet

you start by placing all ips you got as /32 subnets ...

then you walk all nodes you have and look at their sibling (as this is a binary tree, there can only be one sibling) ... if the sibling is there, you may collapse the current node and the sibling node to their parent node ...

do that until you run out of collapsible nodes...

all nodes that remain on your list are the subnets you are looking for ...

quick and dirty example implementation in c#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SoExamples.IpNetCalc
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = new string[] {
                "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"
            };

            //for calculation purposes i use uint32s as a representation for the adresses:
            //simply concatinate all 4 bytes of an address 
            var addresses = input.Select(x => ToUInt32(x)).OrderBy(x => x).Distinct().ToArray();

            var queue = new Queue<UInt32>(addresses);
            var nets = addresses.ToDictionary(x => x, x => 32); // we start with treating every address as a /32 net
            //basically what i do here is collapsing a binary tree
            //an entry in the nets dictionary means: all nodes thet have a longer netmask are present
            //so if there is an entry for 192.168.0.16 with 30 that means .16 .17 .18 and .19 are present
            //but that also means that if 192.168.0.16/30 is in the dictionary, .17 .18 and .19 will not be there.
            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                int currBits;
                if (nets.TryGetValue(current, out currBits) && currBits > 1)
                {
                    //the net is not already collapsed
                    //we can collapse this node to its parent if and only if its sibling is there
                    //so let's calculate parent and sibling
                    var parent = addr2NetAddr(current, currBits - 1);
                    var sibling = current ^ (UInt32)(1 << 32 - currBits);
                    if (nets.ContainsKey(sibling))
                    {
                        //we found the sibling -> we may collapse current and sibling to parrent
                        nets.Remove(current);
                        nets.Remove(sibling);
                        nets.Add(parent, currBits - 1);
                        queue.Enqueue(parent);
                    }
                }
            }
            foreach (var net in nets)
            {
                Console.WriteLine($"{ToIpString(net.Key)}/{net.Value}");
            }
        }

        private static UInt32 addr2NetAddr(UInt32 addr, int maskBits)
        {
            UInt32 mask = 0;
            for (int i = 0; i < 32; i++)
            {
                mask = mask << 1;
                if (maskBits-- > 0)
                    mask |= 1;
            }
            return addr & mask;
        }
        private static UInt32 ToUInt32(string ipStr)
        {
            UInt32 r = 0;
            var arr = ipStr.Split('.');
            foreach (var n in arr)
            {
                r = r << 8;
                r |= uint.Parse(n);
            }
            return r;
        }
        private static string ToIpString(UInt32 addr)
        {
            var sb = new StringBuilder();
            for (int i = 0; i < 4; i++)
            {
                sb.Append(addr >> (24 - 8 * i) & 255);
                if (i < 3)
                    sb.Append('.');
            }
            return sb.ToString();
        }
    }
}