查找覆盖 IP 地址列表所需的最少子网

Question

给定一个 IP 地址列表，我想自动生成一系列子网掩码来覆盖这些 IP，而不覆盖其他 IP。

例如，192.168.0.16/30 将涵盖以下 IP 地址输入列表：

192.168.0.16
192.168.0.17
192.168.0.18
192.168.0.19

对于不相交的输入，我需要多个子网，而不是一个覆盖不在列表中的条目的较大子网。结果子网中不应有“误报”。例如这个输入和输出：

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

我知道这是一个可以解决的计算问题，我希望找到一个预构建的工具或已知的算法来实现它。我没有找到这个，因为所有在线工具都可以计算另一个方向。

有人知道这个操作的名称或解决方案的实现吗？

Answer 1

你要找的可以看成一棵二叉树，每个树节点对应一个子网

您首先将获得的所有 ip 放置为 /32 子网...

然后你遍历所有节点并查看它们的兄弟节点（因为这是一棵二叉树，所以只能有一个兄弟节点）...如果兄弟节点存在，你可能会折叠当前节点和兄弟节点节点到它们的父节点...

这样做，直到运行没有可折叠节点...

保留在列表中的所有节点都是您要查找的子网...

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();
        }
    }
}

查找覆盖 IP 地址列表所需的最少子网

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

algorithm

networking

ip-address

subnet