一旦我在Habr上阅读
了有关在路由器上配置BGP
的文章 。 来自那里的指令可用于配置家用路由器，以使到达特定IP地址的流量通过另一个通道。 但是，存在一个问题：IP地址列表可能非常大。
除了列表中的网络之外，该图还添加了相邻网络的最大公共子网。 继续阅读为什么需要这样做。
看起来像是2018年5月来自Roskomnadzor的网络树。首先，我试图通过/ ip route将整个列表添加到我的MikroTik hAP协议中-路由器用尽了磁盘空间。 然后，我通过BGP将所有地址加载到内存中-路由器正常工作并挂起。 很明显，该清单需要修剪。
本文提到了
Unsacrificed中的network-list-parser
实用程序 。 她满足了我的需要，但是在我开始发明我的自行车之后我就看见了她。 然后我出于兴趣而完成了它，因为我做的更好，尽管速度慢得多。
因此，问题的陈述：您需要编写一个脚本，该脚本以IP地址和网络列表作为输入并将其缩短到指定的大小。 在这种情况下，新列表应覆盖旧列表中的所有地址，并且强制添加到该列表中的新地址数应尽可能少。
让我们从构建所有源网络的图表开始（上图中是什么）。 根节点将是网络0.0.0.0/0。 当添加新的子网A时，我们在树中找到了子网B，因此A和B在子网C上，子网C的大小最小（最大掩码）。 换句话说，子网A和B的公共位数应为最大。 我们将此公共子网添加到树中，然后在内部传输子网A和B。也许这可以称为二叉树。
例如，构建一个包含两个子网（192.168.0.1/32和192.168.33.0/24）的树：
获取树：
如果我们添加网络192.168.150.150/32，则树将如下所示：
橙色表示在树构建过程中添加的公用子网。 我们将“折叠”这些通用子网以减小列表的大小。 例如，如果您折叠节点192.168.0.0/16，则我们将网络列表的大小减少2（原始列表中有3个网络，它变为1），但同时我们还覆盖了65536-1-1-256 = 65278 IP地址，未包含在我们的原始列表中。
每个节点都可以方便地计算“崩溃的利润系数”，其中显示了将添加到从列表中删除的每个条目中的IP地址数量：
weight_reversed = net_extra_ip_volume / (in_list_records_count - 1)
我们将使用weight = 1 / weight_reversed 比较方便。 奇怪的是，例如，如果列表中有两个/ 32个网络，它们一起构成一个大/ 31个网络，则权重可以等于无穷大。
因此，权重越大，崩溃这样的网络就越有利可图。
现在，您可以计算网络中所有节点的权重，按权重对节点排序，然后折叠子网，直到获得所需列表的大小为止。 但是，有一个困难：当我们崩溃一个网络时，所有父网络的权重都会改变。
例如，我们有一棵具有计算权重的树：
让我们折叠子网192.168.0.0/30：
父节点的权重已降低。 如果树中的节点的权重大于0.166，则应折叠以下节点。
结果，该列表必须递归压缩。 该算法是这样的：
- 我们计算所有节点的权重。
- 对于每个节点，存储子节点的最大权重（Wmax）。
- 事实证明，根节点的Wmax是整个树中该节点的最大权重（可能有多个权重等于Wmax的节点）。
- 递归压缩权重等于根节点Wmax的所有网络。 在这种情况下，我们重新计算权重。 我们返回到根节点。
- 根节点的Wmax减小-我们执行步骤4，直到获得所需的网络列表大小。
最有趣的是观察运动中的算法。 这是网络列表的示例：
192.168.0.1
192.168.0.2
192.168.0.8/29
192.168.150.1
192.168.150.2
192.168.150.8/29
192.168.20.1
192.168.20.2
192.168.20.3
192.168.20.4
192.168.20.5
192.168.20.6
192.168.20.7在这里，子网192.168.0.0/24和192.168.150.0/24的结构相同-最好查看算法在压缩过程中如何从一个分支跳转到另一个分支。 他添加了192.168.20.0/24子网，以表明压缩父网络有时比子网络更有利可图。 注意子网192.168.20.0/30：填充树后，其权重小于父子网的权重。
树木填充：
这里的黑色字体是原始列表中的真实网络。 黄色-已添加网络。 蓝色是节点的权重。 红色是当前网络。 粉色是一张折叠的网。
压缩方式
有一种想法可以加快网络崩溃算法的速度：为此，不必在每次迭代时仅崩溃具有最大权重的网络。 您可以预先选择重量值，这将为我们提供所需尺寸的列表。 您可以通过二进制搜索进行选择，即 以一定的权重进行压缩，然后查看在输出中获得的列表大小。 是的，为此，您需要两倍的内存并重写代码-我只是没有亲身体验。
现在，可以与有关BGP的文章中的
network-list-parser进行比较。
我的脚本的优点：
- 设置更方便：只需指定所需的网络列表大小，输出将是该大小的列表。 网络列表解析器有很多句柄，您需要找到它们的组合。
- 压缩比适应原始列表。 如果我们从列表中删除一些网络，那么如果添加更多的网络，我们将获得更少的其他地址。 在这种情况下，结果列表的大小将是恒定的。 您可以选择路由器可以处理的最大大小，而不用担心列表有时过大。
- 结果列表包含最少数量的附加网络。 在来自GitHub的测试列表上，我的算法提供了718479个其他IP地址，以及network-list-parser-798761 。相差仅10％ 。
我该如何计算？ 看着1.启动
./network-list-parser-darwin-386-1.2.bin -src-file real_net_list_example.txt -dst-file parsed.txt -aggregation-max-fake-ips 0 -intensive-aggregation-min-prefix 31 2>&1
我们得到了一个没有垃圾的清理清单，并且部分减少了。 我将比较parsed.txt的压缩质量。 （没有此步骤，评估网络列表解析器添加了多少个假IP就会出现问题）。
2.发射
./network-list-parser-darwin-386-1.2.bin -src-file parsed.txt -dst-file parsed1.txt 2>&1
然后我们得到一个压缩列表，看一下输出，一行“添加7.3％IP覆盖率（798761）”。
parsed1.txt文件具有16649个条目。
3.启动
python3 minimal_net_list.py parsed.txt 16649。
我们看到行###不是真正的ips：718479。
我只看到生成的脚本的一个缺点：它可以工作很长时间并且需要大量内存。 在我的MacBook上，按下列表5秒钟。 在Raspberry上-
半分钟 。 在Mac上使用RyPy3的速度更快，我无法在Raspberry上安装PyPy3。 网络列表解析器随处可见。
通常，仅对完美主义者使用此方案是有意义的，因为 为了节省10％的网络，所有其他公司都不太可能花费太多的计算资源。 好吧，有点方便，是的。
链接到GitHub上的项目像这样运行：
python3 minimize_net_list.py real_net_list_example.txt 30000 | grep -v ### > result.txt
实际上，仅此而已。
UPD注释中的
Pochemuk表示计算权重时出错，我进行了修复，现在，当使用相同设置压缩来自示例的相同列表时，将添加原始列表中没有的624925 IP地址。 已经比处理network-list-parser
好22％未经测试的
github.com/phoenix-mstu/net_list_minimizer/tree/unested分支中的新代码