从基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和子网的，如何为我想要创建的新子网找到一个具有特定大小的良好 CIDR块(比如/22)。在我看来，good意味着更好地利用空间。假设我只想要一个小的CIDR块，它不应该在VPC CIDR中间返回CIDR，这样可以防止将来可能出现的大CIDR块。欢迎对良好的其他定义。没有任何初始状态的保证。

我不知道这样的问题是否有标准的算法。我现在想的是使用二叉树。左子表示0，右子表示1。所有叶子表示正在使用的CIDR块。要获得一个新的CIDR块，问题基本上是在某个级别创建一个休假，这取决于所期望的块的大小。如何创建一个好的，我还不知道。

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

Answer 1

二叉树是正确的结构，但它不需要下降到叶级。只要需要就把它取下来。树中的每一片叶子都表示分配或可用块。根据定义，每个CIDR块的大小是2的幂。因此，如果一个节点/块有子节点/块，那么它正好有两个子节点/块。如果节点有子节点(不是叶)，则它的块不可用。

因此，您的顶层块及其初始分配会像这样分解(从左侧边缘表示的树，以便于绘制)。***标记分配的块。我可能在这里提到了一些东西，但基本思想应该很清楚:每个/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块，首先遍历树(按任何顺序)，寻找一个正好是/24大小的块。如果您找到一个，您就完成了；标记它分配并返回它。在遍历过程中，跟踪您发现的大小大于/24的最小块。(显然，如果您到达树中任何小于/24的节点，就不需要再遍历它的子树了，因为它的大小只会从那里向下。)

如果找不到一个完全是/24的块，那么就转到您保存的那个块，它是比/24大的最小块。然后你把这个块切成两个，用两个半尺寸的块代替它。抓住任何一个(任意的)。如果是/24，你就完蛋了。如果没有，您可以拒绝将该块切割成两块，以此类推。最终，您将找到一个/24。

比方说，比/24大的最小块是一个/21。通过这样递归地划分它，您将把/21划分为:两个/24s (一个是您分配的，一个仍然可用)、一个可用的/23和一个可用的/22。

如果一个块返回给您，您可以将它与它的配套块组合起来，如果该块是可用的(即叶，未标记为已分配的)。如果你能把它和它的伴侣结合起来，你也可以把它的父母和它的孪生兄弟结合起来。

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

Answer 2

我认为，如果你能找到Knuth对allocation的描述(在“计算机编程的艺术”第一卷中)，你会看到关于它的各种特性的证明，其中一些可能适用于你正在考虑的那种基于树的分配器，我认为这可以归结为这样的东西。

将可用地址范围作为一组块进行跟踪，其大小为2的幂，以2的倍数对齐。如果您曾经有两个块可以合并生成下一个最大大小的合法块，那么您应该这样做。

当请求一个地址空间块时，从集合中最小的块中分配它，并分配一个大小为2的块。如果在分配后有剩余空间，则将其转换为两个大小块的地址对齐能力。

如果将以前分配的地址空间块返回给您，则将其添加到您的一组大小为2的块中，如果可能的话，将其与其邻接块(其伙伴)合并。