从数据集中获取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 )算法来确定它们是否重叠。这使得您的速度为O(n^2 log n)，这是相当慢的。

我们可以创建一个名为IPTree的类，它根据IP的最高有效位来划分IP。如果您的所有网络都像大多数常见的网络一样以1字节(/32, /24, /16, /8)为增量，那么您可以在每个树级别使用256的分支因子，这样您就不需要向下探索那么多树。我将根据您的示例做出这个假设，但是如果您想支持任何类型的网络，您可以按位而不是按字节拆分。

现在，第一层上的第一个节点将是根(无)，第一层节点将存储第一个字节(例如10)，第二层将存储第二个字节，第三层将存储第三个字节，第四层将存储第四个字节。要将网络标记为"taken"，我们只需在与L = n/8级别对应的节点中切换一个标志，其中n是网络掩码中的位数。

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

从根元素开始，然后对于每个网络，将网络的每个字节添加到树的某个级别，将最后一个节点标记为“结束”节点。树的其余部分只填充了None。节点"end“或非”end“的存在表示树中的该点至少部分地被另一个网络或主机使用，因此不能放入新的网络中。"end“节点的出现表明树中的这一点已经被网络占用，您不能将网络放在其中。

以下是解决方案的粗略说明，绿色节点表示“结束”节点：

​

​

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

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

对于到达"end“节点的冲突，我们知道我们正在尝试分配已经占用的范围内的IP范围或IP，并且我们知道占用的范围是什么，因为我们有相应的"end”节点。我们所需要做的就是连接节点和它的每个父节点，用零填充末端，并附加网络中的位数(可以通过父节点的计数找到)。例如，尝试在上面的树中分配10.1.1.3将导致我们到达10. -> 1. -> 1.的结束节点，它变成了10.1.1.0/24。这将花费O(1)。

对于尚未到达"end“节点，但该节点已被占用的冲突，我们知道我们正在尝试分配一个IP范围，其中包含一个已占用的IP范围。为此，我们只需搜索子节点，以找到作为该节点的后代的结束节点。这将需要O(2^b * 32/b)。对于常数b，这将具有恒定的时间效率。