java - 使用什么算法从基本 CIDR 获取子 CIDR？

Question

我有一个 VPC，假设它的 CIDR block 是 10.0.0.0/16。我在那个 VPC 中有几个随机子网。他们的 CIDR 可能类似于 10.0.128.0/19、10.0.32.0/19、10.0.208.0/22。子网的 CIDR block 必须被 VPC 的 CIDR block 覆盖。此外，不允许子网之间的 CIDR 重叠。

我的问题是:给定这样的 VPC 和子网，如何为我要创建的新子网(比方说/22)找到具有特定大小的好 CIDR block 。在我看来，好 意味着更好地利用空间。比方说，如果我只想要一个小的 CIDR block ，它不应该在 VPC CIDR 的中间返回一个 CIDR，这样可以防止将来放置潜在的大 CIDR block 。欢迎使用其他好的定义。没有任何初始状态的保证。

我不知道是否有针对此类问题的标准算法。我目前正在考虑的是利用二叉树。左 child 表示 0，而右 child 表示 1。所有叶子代表正在使用的 CIDR block 。要获得一个新的 CIDR block ，问题基本上是在某种程度上创建一个休假取决于所需的 block 大小。如何创造一个好的叶子我还不知道。

顺便说一句，我正在编写 Java 代码。我找不到这个图书馆。如果有现有的库，也请告诉我!

Answer 1

二叉树是正确的结构，但它不需要深入到叶级。仅在需要时将其取下。树中的每个叶子代表一个分配或一个可用 block 。根据定义，每个 CIDR block 的大小都是 2 的幂。因此，如果一个节点/ block 有子节点，则它正好有两个。如果节点有子节点(不是叶节点)，则其 block 不可用。

因此，您的顶级 block 及其初始分配像这样分解(从左边缘表示的树以便于绘制。*** 标记分配的 block 。[我可能很胖-在这里指指点点，但基本思想应该很清楚:每个/16 有两个/17 子节点，每个/17 有两个/18 子节点，等等。除非该节点可用，在这种情况下它没有子节点。]):

                    /---- 10.0.0.0/19
                    |
            /---  10.0.0.0/18
            |       |
            |       \---- 10.0.32.0/19***
            |
     /--- 10.0.0.0/17
    |       \
    |        ---- 10.0.64.0/18
    |
  10.0.0.0/16
    |
    |               /---- 10.0.128.0/19***
    |               |
    |       /---- 10.0.128.0/18
    |       |       |
    |       |       \---- 10.0.160.0/19
    |       |
     \--- 10.0.128.0/17
            |
            |               /---- 10.0.192.0/20
            |               |
            |       /---- 10.0.192.0/19
            |       |       |
            |       |       |               /---- 10.0.208.0/22***
            |       |       |               |
            |       |       |       /---- 10.0.208.0/21
            |       |       |       |       |
            |       |       |       |       \---- 10.0.212.0/22
            |       |       |       |        
            |       |       \---- 10.0.208.0/20
            |       |               |
            |       |               \---- 10.0.216.0/21
            |       |
            \---- 10.0.192.0/18
                    |
                    \---- 10.0.224.0/19

因此，例如，要找到/24 的 block ，首先遍历树(以任何顺序)寻找大小恰好为/24 的 block 。如果你找到一个，你就完成了；将其标记为已分配并返回。在遍历过程中，跟踪您发现的小于/24 的最小块。。 (显然，如果您到达树中小于/24 的任何节点，则不需要进一步遍历其子树，因为大小只会从那里下降。)

如果您没有找到恰好是/24 的 block ，那么您将转到您保存的 block ，它是大小大于/24 的最小块。然后将该 block 切成两半，用两个半尺寸 block 替换它。捕获其中之一(任意)。如果它是/24 你就完成了。如果不是，则递归将该 block 一分为二，依此类推。最终，您会找到/24。

假设大于/24 的最小块是/21。通过以这种方式递归分割，您会将/21 分割成:两个/24(一个您已分配，一个仍然可用)、一个可用的/23 和一个可用的/22。

如果一个 block 被返回给你，你可以将它与它的伴随 block 组合起来，前提是该 block 可用(即一个叶子并且没有标记为已分配)。如果您可以将它与它的同伴结合起来，您也许也可以将它的 parent 与 parent 的双胞胎结合起来。

(顺便说一句，这与@mcdowella 的回答兼容；只是添加了细节。)