如何计算 IP 子网之间的差距?

How to compute gaps between IP subnets?

计算输入 IP 子网之间所有间隙的最有效算法是什么?

示例输入

192.168.1.24 / 29
192.168.1.40 / 30
192.168.1.64 / 28

示例输出

192.168.1.0 / 28   <--- auto-created
192.168.1.16 / 29  <--- auto-created
192.168.1.24 / 29  <--- INPUT
192.168.1.32 / 29  <--- auto-created
192.168.1.40 / 30  <--- INPUT
192.168.1.44 / 30  <--- auto-created
192.168.1.48 / 28  <--- auto-created
192.168.1.64 / 28  <--- INPUT
192.168.1.80 / 28  <--- auto-created
192.168.1.96 / 27  <--- auto-created
192.168.1.128 / 25 <--- auto-created

目前研究:

第 1 步。对于输入对:192.168.1.0/28、192.168.1.24/29

让我们计算 IP 子网的数字表示之间的差异:

diff = 3232235800 - 3232235776 = 24

然后计算以 2 为底的对数:

log2 = log2(24) = 4.58

然后我们可以计算 CIDR 和子网的长度:

cidr = 32 - 4 = 28
ipStart = 3232235776 
ipEnd = 3232235776 + 2^4 - 1 = 3232235776 + 15 = 3232235791

所以我们添加到列表中:

192.168.1.0/28

但是还是有差距所以:

diff = 3232235800 - 3232235792 = 8
log2 = log2(8) = 3
cidr = 32-3=29
ipStart = 3232235792
ipEnd = 3232235799

所以我们添加第二个:

192.168.1.16/29

等等。但是,有没有更有效的方法来找到差距并生成子网?

假设子网按升序排列。我们考虑 32 位二进制字符串 s 以及相应子网掩码的长度 n。

考虑长度为n的s的前缀。通过将此前缀表示的数字加 1,我们获得下一个子网中第一个地址的前缀。要看到这一点,请想象用 1 填充前缀右侧的所有内容;这是 s 在子网中可能的最大地址,因此下一个地址必须在下一个子网中。将其加1会携带到子网掩码内的地址部分,所以我们可以直接考虑。

这给了我们需要的位串,但是没有告诉我们相应子网掩码的长度n。当然,n 必须至少足够长以包含我们获得的字符串的所有非零数字。否则,可以表明我们将包括当前子网中的地址。但是,我们可能需要更多的 0 以避免与列表中的下一个子网重叠。我们还必须确保保留足够的零,以便我们的新子网与列表中的下一个子网至少有一位不同:下一个地址中的最后一个非零数字。

这里有一个关于你的问题的例子:

192.168.1.24 / 29
192.168.1.40 / 30
192.168.1.64 / 28

我们将这些解读为

11000000 10101000 00000001 00011000 / 29
11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 01000000 / 28

现在,考虑第一个

11000000 10101000 00000001 00011000 / 29

我们考虑长度为29的前缀:

11000000 10101000 00000001 00011

加一个:

11000000 10101000 00000001 00100

我们的 n 必须至少为 27。要查看它是否需要更长,请考虑我们列表中的下一个子网:

11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 00100
                               ^

我们的子网在第29个位置与下一个不同,这也是下一个子网中最右边的非零位置。因此,n = 29;我们创建了一个新的子网:

11000000 10101000 00000001 00100000 / 29

如果我们对刚刚创建的子网应用相同的过程,我们会发现我们生成的前缀与原始列表中的下一个子网对应的前缀完全相同。我们可以检测到这一点并认识到这意味着这里没有更多的空白可以填补,然后继续前进。

下一个子网是

11000000 10101000 00000001 00101000 / 30

长度为30的前缀是

11000000 10101000 00000001 001010

加一个:

11000000 10101000 00000001 001011

与下一个子网比较:

11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 001011

我们必须至少选择 n = 30,所以我们得到子网:

11000000 10101000 00000001 00101100 / 30

考虑长度为30的前缀加一个:

11000000 10101000 00000001 001011
+                               1
=================================
11000000 10101000 00000001 001100

与下一个比较:

11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 001100

我们必须至少有 n 个 28,所以我们得到

11000000 10101000 00000001 00110000 / 28

考虑长度为28的子串,加一,我们得到与原始列表中下一个子网相同的位串。我们认识到这意味着我们已经填补了空白,所以我们继续前进。

我们正在查看最后一个原始输入,因此没有任何内容可填充。完全的。我们的子网:

11000000 10101000 00000001 00011000 / 29
11000000 10101000 00000001 00100000 / 29 <<<
11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 00101100 / 30 <<<
11000000 10101000 00000001 00110000 / 28 <<<
11000000 10101000 00000001 01000000 / 28

请注意,这不会在提供的输入之外创建子网范围。如果你想这样做,你的算法可以将最小子网添加到列表中,并将最大子网附加到列表中。让我们以 0.0.0.0/1 作为最小子网 ad 255.255.255.255/32 作为最大子网来做最小化:

00000000 00000000 00000000 00000000 / 1
0
+1
=1
 11000000 10101000 00000001 00011000 / 29
  ^
 => n = 2
 => 10000000 00000000 00000000 00000000 / 2    <<<<<<<<<

10000000 00000000 00000000 00000000 / 2
10
+1
=11
 11000000 10101000 00000001 00011000 / 29
          ^
=> n = 9
=> 11000000 00000000 00000000 00000000 / 9    <<<<<<<<<

11000000 00000000 00000000 00000000 / 9
11000000 0
+1
= 11000000 1
  11000000 10101000 00000001 00011000 / 29
             ^
=> n = 11
=> 11000000 10000000 00000000 00000000 / 11    <<<<<<<<<

11000000 10000000 00000000 00000000 / 11
11000000 100
+1
= 11000000 101
  11000000 10101000 00000001 00011000 / 29
               ^
=> n = 13
=> 11000000 10100000 00000000 00000000 / 13    <<<<<<<<<

11000000 10100000 00000000 00000000 / 13
11000000 10100
+1
= 11000000 10101
  11000000 10101000 00000001 00011000 / 29
                           ^
=> n = 24
=> 11000000 10101000 00000000 00000000 / 24    <<<<<<<<<

11000000 10101000 00000000 00000000 / 24
11000000 10101000 00000000
+1
= 11000000 10101000 00000001
  11000000 10101000 00000001 00011000 / 29
                                ^
=> n = 28
=> 11000000 10101000 00000001 00000000 / 28    <<<<<<<<<

11000000 10101000 00000001 00000000 / 28
11000000 10101000 00000001 0000
+1
= 11000000 10101000 00000001 0001
  11000000 10101000 00000001 00011000 / 29
                                 ^
=> n = 29
=> 11000000 10101000 00000001 00010000 / 29    <<<<<<<<<

下一篇会给我们第一个真实的输入子网。子网现在是:

00000000 00000000 00000000 00000000 / 1  <<<
10000000 00000000 00000000 00000000 / 2  <<<
11000000 00000000 00000000 00000000 / 9  <<<
11000000 10000000 00000000 00000000 / 11 <<<
11000000 10100000 00000000 00000000 / 13 <<<
11000000 10101000 00000000 00000000 / 24 <<<
11000000 10101000 00000001 00000000 / 28 <<<
11000000 10101000 00000001 00010000 / 29 <<<

11000000 10101000 00000001 00011000 / 29
11000000 10101000 00000001 00100000 / 29 <<<
11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 00101100 / 30 <<<
11000000 10101000 00000001 00110000 / 28 <<<
11000000 10101000 00000001 01000000 / 28

我们可以在另一端重复练习:

11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 0100
+1
= 11000000 10101000 00000001 0101
  11111111 11111111 11111111 11111111
                                ^
=> n = 28 (must include rightmost 1 of s + 1)
=> 11000000 10101000 00000001 01010000 / 28    <<<<<<<

11000000 10101000 00000001 01010000 / 28
11000000 10101000 00000001 0101
+1
= 11000000 10101000 00000001 0110
  11111111 11111111 11111111 11111111
                               ^
=> n = 27
=> 11000000 10101000 00000001 01100000 / 27    <<<<<<<

11000000 10101000 00000001 01100000 / 27
11000000 10101000 00000001 011
+1
= 11000000 10101000 00000001 100
  11111111 11111111 11111111 11111111
                             ^
=> n = 25
=> 11000000 10101000 00000001 10000000 / 25    <<<<<<<

11000000 10101000 00000001 10000000 / 25
11000000 10101000 00000001 1
+1
= 11000000 10101000 00000010 0
  11111111 11111111 11111111 11111111
                           ^
=> n = 23
=> 11000000 10101000 00000010 00000000 / 23    <<<<<<<

我们没有列出所有项,因为那样会变得单调,我们可以注意到,当我们有 0 串时,我们会将 n 减一,并将最右边的一个向左移动 space左边。所以,我们跳过:

=> 11000000 10101000 00000100 00000000 / 22    <<<<<<<
=> 11000000 10101000 00001000 00000000 / 21    <<<<<<<
=> 11000000 10101000 00010000 00000000 / 20    <<<<<<<
=> 11000000 10101000 00100000 00000000 / 19    <<<<<<<
=> 11000000 10101000 01000000 00000000 / 18    <<<<<<<
=> 11000000 10101000 10000000 00000000 / 17    <<<<<<<
=> 11000000 10101001 00000000 00000000 / 16    <<<<<<<
=> 11000000 10101010 00000000 00000000 / 15    <<<<<<<
=> 11000000 10101100 00000000 00000000 / 14    <<<<<<<

我们注意到01^k变成了10^k,n减少了k;所以我们再次跳过添加

=> 11000000 10110000 00000000 00000000 / 12    <<<<<<<
=> 11000000 11000000 00000000 00000000 / 10    <<<<<<<
=> 11000001 00000000 00000000 00000000 / 8     <<<<<<<

回到规则#1:

=> 11000010 00000000 00000000 00000000 / 7     <<<<<<<
=> 11000100 00000000 00000000 00000000 / 6     <<<<<<<
=> 11001000 00000000 00000000 00000000 / 5     <<<<<<<
=> 11010000 00000000 00000000 00000000 / 4     <<<<<<<

下一步,我们得到一个匹配范围末尾的子网,因此我们必须包含一个额外的零以使其不同:

=> 11100000 00000000 00000000 00000000 / 4     <<<<<<<

如果我们真的关心 255.255.255.255 子网,正确的方法是通过每次增加 n 和 1 的数量来继续这个,以获得大约 27 个子网。但是,如果我们只是想填补空白,我们可以认识到我们目前的状况并添加:

=> 11110000 00000000 00000000 00000000 / 4     <<<<<<<<

这涵盖了范围的其余部分,包括 255.255.255.255,因此它本身并不是扩充问题的解决方案,但它确实解决了原始问题填补空白。我们的完整名单如下:

00000000 00000000 00000000 00000000 / 1  <<<
10000000 00000000 00000000 00000000 / 2  <<<
11000000 00000000 00000000 00000000 / 9  <<<
11000000 10000000 00000000 00000000 / 11 <<<
11000000 10100000 00000000 00000000 / 13 <<<
11000000 10101000 00000000 00000000 / 24 <<<
11000000 10101000 00000001 00000000 / 28 <<<
11000000 10101000 00000001 00010000 / 29 <<<

11000000 10101000 00000001 00011000 / 29
11000000 10101000 00000001 00100000 / 29 <<<
11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 00101100 / 30 <<<
11000000 10101000 00000001 00110000 / 28 <<<
11000000 10101000 00000001 01000000 / 28

11000000 10101000 00000001 01010000 / 28 <<<
11000000 10101000 00000001 01100000 / 27 <<<
11000000 10101000 00000001 10000000 / 25 <<<
11000000 10101000 00000010 00000000 / 23 <<<
11000000 10101000 00000100 00000000 / 22 <<<
11000000 10101000 00001000 00000000 / 21 <<<
11000000 10101000 00010000 00000000 / 20 <<<
11000000 10101000 00100000 00000000 / 19 <<<
11000000 10101000 01000000 00000000 / 18 <<<
11000000 10101000 10000000 00000000 / 17 <<<
11000000 10101001 00000000 00000000 / 16 <<<
11000000 10101010 00000000 00000000 / 15 <<<
11000000 10101100 00000000 00000000 / 14 <<<
11000000 10110000 00000000 00000000 / 12 <<<
11000000 11000000 00000000 00000000 / 10 <<<
11000001 00000000 00000000 00000000 / 8  <<<
11000010 00000000 00000000 00000000 / 7  <<<
11000100 00000000 00000000 00000000 / 6  <<<
11001000 00000000 00000000 00000000 / 5  <<<
11010000 00000000 00000000 00000000 / 4  <<<
11100000 00000000 00000000 00000000 / 3  <<<

我没有像上面解释的那样有两个 /4 子网,而是在这个列表中放了一个 /3 子网,因为它是等价的。