从数据集中获取IP冲突列表的优化

Question

我有一个包含ID号的网络数据列表，它是网络IP和虚拟IP。示例如下所示。

    ID  Network IP    Virtual IP
    1   10.1.1.0/24   -
    2   10.2.2.0/24   -
    3   10.3.3.0/24   10.4.4.88
    4   10.4.4.0/24   -
    5   10.1.0.0/16   -
    6   ...
    ...
    ...

目的是检测并输出列表中是否存在任何网络IP或虚拟IP冲突/重叠，其中包括产生的冲突的网络IP和备注。 eg. Network IP conflict --> 10.1.1.0/24 overlaps with 10.1.0.0/16和Virtual-ip conflict --> 10.4.4.88 is in range of 10.4.4.0/24 (of different ID)

这是代码的示例输出。

ID  Network IP    Virtual IP    Result        Remark
5   10.1.0.0/16   -             10.1.0.0/16   Network Conflict
1   10.1.1.0/24   -             10.1.0.0/16   Network Conflict
3   10.3.3.0/24   10.4.4.88     10.4.4.0/24   Virtual-ip Conflict
4   10.4.4.0/24   -             10.4.4.0/24   Virtual-ip Conflict

下面是示例代码，目前我正在使用嵌套的“ for”循环，这非常慢。因此，我想知道是否有更有效的算法来解决此问题，尤其是在比较100k +数据时？

import ipaddress

class Network:
    def __init__(self, ID='-', IPNet='-', VIP='-', Result='-', Remark='-'):
        self.ID = ID          # ID Number
        self.IPNet = IPNet    # Network IP
        self.VIP = VIP        # Virtual IP
        self.Result = Result  # Resulting Network IP that conflicts
        self.Remark = Remark
    def __eq__(self, other):
        return self.ID == other.ID and self.IPNet == other.IPNet and self.VIP == other.VIP and \
               self.Result == other.Result and self.Remark == other.Remark
    def __hash__(self):
        return hash((self.ID, self.IPNet, self.VIP, self.Result, self.Remark))

Final_List = []
Input_List = [Network('1', '10.1.1.0/24', '-', '-', '-'),
              Network('2', '10.2.2.0/24', '-', '-', '-'),
              Network('3', '10.3.3.0/24', '10.4.4.88', '-', '-'),
              Network('4', '10.4.4.0/24', '-', '-', '-'),
              Network('5', '10.1.0.0/16', '-', '-', '-')]

for in1 in Input_List:
    IPNet1 = in1.IPNet
    for in2 in Input_List:
        IPNet2 = in2.IPNet

        # Resolving overlapping Network IP
        if in1.ID != in2.ID and ipaddress.ip_network(IPNet1).overlaps(ipaddress.ip_network(IPNet2)):
            Remark = 'Network Conflict'
            Result = '-'

            # Comparing size of network range. Resulting network IP will be the one with larger size
            size1 = ipaddress.ip_network(IPNet1).num_addresses
            size2 = ipaddress.ip_network(IPNet2).num_addresses
            if size1 >= size2:
                Result = IPNet1
            else:
                Result = IPNet2

            _in1 = Data(in1.ID, IPNet1, in1.VIP, Result, Remark)
            Final_List.append(_in1)
            _in2 = Data(in2.ID, IPNet2, in2.VIP, Result, Remark)
            Final_List.append(_in2)
            break
        # Resolving Virtual IP conflicts
        elif in1.ID != in2.ID and in1.VIP != '-' and ipaddress.ip_address(in1.VIP) in ipaddress.ip_network(IPNet2):
            Remark = 'Virtual-ip Conflict'
            Result = IPNet2
            _in1 = Data(in1.ID, IPNet1, in1.VIP, Result, Remark)
            Final_List.append(_in1)
            _in2 = Data(in2.ID, IPNet2, in2.VIP, Result, Remark)
            Final_List.append(_in2)
            break

Final_List = list(set(Final_List))  # Remove duplicates
Final_List = sorted(Final_List, key=lambda x: (ipaddress.ip_network(x.IPNet), x.ID), reverse=False)

Answer 1

您可能将数据存储在树中以便快速查找。

将每个IP网络与每个其他IP网络中的地址进行比较需要在网络数量上进行for循环，并且可能需要O（log n）算法来确定它们是否重叠。这使您的速度为O（n ^ 2 log n），非常慢。

我们可以创建一个名为IPTree的类，该类根据IP的最高有效位对其进行分割。如果您的所有网络都像大多数普通网络一样以1字节（/32, /24, /16, /8）为增量，则可以在每个树级别使用256的分支因数，这样您就不必研究太多树了。我将根据您的示例进行此假设，但是如果您想支持任何类型的网络，则可以按位而不是按字节分割。

现在，我们在第一级上的第一个节点将是根（无），第一级节点将存储第一个字节（例如10），第二级将存储第二个字节，第三级将存储第三个字节，第四级将存储第四字节。要将网络标记为“已采用”，我们只需要在节点中切换一个标记即可，其中该节点对应于L = n/8级别，其中n是网络掩码中的位数。

但是等等！这样存储一棵完整的树将需要2 ^ 32整数！当然，我们只能减少几个网络的内存量。我们可以通过使用稀疏树来做到这一点。

从根元素开始，然后对于每个网络，将网络的每个字节添加到树的级别，将最后一个节点标记为“结束”节点。树的其余部分仅填充有None。节点的存在（“是否结束”）表示树中的该点至少部分地被另一个网络或主机使用，因此不能放入新的网络中。一个“结束”节点的存在表示该树中的该点已被网络占用，并且您不能在其中放置网络。

这里是该解决方案的粗略图示，其中绿色节点代表“结束”节点：

使用此解决方案，我们可以完成搜索并添加O（32 / b），其中b是每层的位数（8表示字节，1表示位数），这将使比较n个网络O（n / b）。对于常数b，这将与O（n）缩放。

现在，对于问题的第二部分，您希望能够找出与要添加的网络冲突的IP地址或网络。我们有两种方法可以执行此操作，每种方法都适用于不同类型的冲突：

对于到达“结束”节点的冲突，我们知道我们正在尝试在一个已经占用的范围内分配一个IP范围或IP，并且我们知道占用的范围是多少，因为我们有相应的“结束”节点。我们需要做的就是将节点及其每个父节点连接起来，用零填充末端，并附加网络中的位数（可通过父节点的数量找到）。例如，尝试在上面的树中分配10.1.1.3，将使我们到达位于10的结束节点。-> 1.-> 1.，即10.1.1.0/24。这将花费O（1）。

对于尚未到达“结束”节点但已被占用的冲突，我们知道我们正在尝试分配一个IP范围，该IP范围内有一个占用的IP范围。为此，我们只需对子节点执行搜索即可找到作为该节点后代的末端节点。这将花费O（2 ^ b * 32 / b）。使用常数b，这将具有恒定的时间效率。