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

Question

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

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

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

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

Answer 1

我想如果你能找到 Knuth 对 https://en.wikipedia.org/wiki/Buddy_memory_allocation 的描述（在 "The Art of Computer Programming" 第一卷中）你会看到关于它的各种属性证明，其中一些可能适用于树的种类 -基于您正在考虑的分配器，我认为这可以归结为这样的事情。

将可用地址范围作为一组块来跟踪，这些块的大小是 2 的幂，并按 2 的幂的倍数对齐。如果你有两个块可以合并以产生下一个最大尺寸的合法块，你应该这样做。

当请求地址块 space 时，从您的集合中可能的最小块开始分配它，并分配一个大小为 2 的幂的块。如果分配后还有space剩余，将其转化为地址对齐的2个大小块的幂。

如果先前分配的地址块 space 返回给您，请将其添加到大小为 2 的幂的块集中，如果可能，将其与相邻块（它的伙伴）合并。

Answer 2

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

因此，您的 top-level 块及其初始分配像这样分解（为便于绘图，从左边缘表示的树。*** 标记分配的块。[我可能 fat-fingered 这里有些东西，但基本思想应该很清楚：每个 /16 有两个 /17 children，每个 /17 有两个 /18 children，等等，除非该节点在这种情况下可用没有 children.]):

                    /---- 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 的块，首先遍历树（以任何顺序）寻找大小正好为 /24 的块。如果你找到一个，你就完成了；标记它已分配并 return 它。在遍历过程中，跟踪您发现的最小块大于的大小比 /24。（显然，如果您到达树中小于 /24 的任何节点，则不需要进一步遍历其子树，因为大小只会从那里下降。）

如果您没有找到恰好是 /24 的块，那么您将转到您保存的块，它是大小大于 /24 的最小块。然后将该块一分为二，用两个 half-size 块替换它。抓住其中之一（任意）。如果它是 /24 你就完成了。如果不是，则递归将该块一分为二，依此类推。最终，您会找到 /24。

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

如果一个块是 returned 给你的，你可以将它与它的伴随块组合起来，前提是该块可用（即一个叶子并且没有标记为已分配）。如果您可以将它与它的同伴结合，您可能也可以将它的 parent 与 parent 的双胞胎结合起来。

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

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

What algorithm to use for getting a sub CIDR from a base CIDR?

java

algorithm

network-programming

cidr