java - 在 CIDR 网络 block 中查找免费前缀

Question

我正在尝试找出一种方法，在给定网络 block 和其中的分配列表的情况下确定 CIDR 网络 block 内的“自由前缀”。

例如:

让网络 block = 10.0.0.0/22

让赋值 = { 10.0.0.0/24, 10.0.1.0/24 }

计算 10.0.0.0/22 范围内的“空闲”网络 block 的最有效的计算方法是什么？对于上面的示例，我需要输出 10.0.2.0/23。

我尝试过研究，但大多一无所获。我想到的唯一方法(可能是由于我对网络编程缺乏经验)是:

1. CIDR -> IP 扩展列表
2. 匹配常用 IP 并将其从列表中删除
3. 将修改后的列表转换回 CIDR 表示法。

但这听起来相当低效(我将其称为“暴力”方法)。

我对通用算法很满意，它不必是 Java 特定的答案。

谢谢! :)

Answer 1

给定一个地址 x/y，当你从一组地址中减去它时，剩下的是集合 a/y 中的地址，其中 a < x，以及集合 b/y 中的地址，其中b > x

因此，在您的示例中，当您从 10.0.0.0/22 中减去 10.0.0.0/24 时，剩下 10.0.1-3.0/24。

10.0.0.0/22 中没有地址 x/24，其中 x < 10.0.0.0。 10.0.0.0/22 中的地址 y/24(其中 y > 10.0.0.0)为 10.0.1.0/24、10.0.2.0/24 和 10.0.3.0/24，即 10.0.1-3.0/24。

另一种看待方式:您将删除前 24 位为 10.0.0 的所有地址

因此，剩下前 24 位较大的所有地址，以及前 24 位较小的所有地址。其中每一个都可以表示为一个范围。

只需迭代地重复此过程即可。