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

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

现在，我们在第一级上的第一个节点是根节点（无），第一级节点存储第一个字节（如10），第二级节点存储第二个字节，第三级节点存储第三个字节，第四级节点存储第四个字节。要将网络标记为“take”，我们只需要在节点中切换一个标志，该标志对应于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范围。为此，我们只需搜索子节点以查找作为该节点后代的结束节点。这将需要O（2^b*32/b）。对于常数b，这将具有恒定的时间效率