Search code examples
algorithmmathnetwork-programminglogarithmsubnet

How to compute gaps between IP subnets?

What is the most efficient algorithm to compute all gaps between input IP subnets?

Example input

192.168.1.24 / 29
192.168.1.40 / 30
192.168.1.64 / 28

Example output

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

So far research:

Step 1. For input pair: 192.168.1.0/28, 192.168.1.24/29

Let's compute the difference between numeric representation of IP subnets:

diff = 3232235800 - 3232235776 = 24

Then compute logarithm in base 2:

log2 = log2(24) = 4.58

And then we can compute CIDR and length of the subnet:

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

So we add to the list:

192.168.1.0/28

But there is still a gap so:

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

So we add the second one:

192.168.1.16/29

And so on. However, is there a more efficient way to find the gaps and generate the subnets?

Solution

  • Suppose the subnets are listed in ascending order. We consider the 32-digit binary string s along with the length n of the corresponding subnet mask.

    Consider the prefix of s of length n. By adding 1 to the number represented by this prefix, we obtain the prefix of the very first address in the next subnet. To see this, imagine filling in everything to the right of the prefix with 1s; this is the largest address possible in the subnet for s, so the next address must be in the next subnet. Adding 1 to that will carry to the part of the address inside the subnet mask, so we can consider that directly.

    This gives us the bit string we need, but it doesn't tell us the length n of the corresponding subnet mask. Certainly, n must be at least long enough to include all non-zero digits of the string we've obtained. Otherwise, it can be shown that we would be including addresses in the current subnet. However, we may need even more of the 0s to avoid overlapping with the next subnet in our list. We must also make sure that we keep enough zeroes so that our new subnet differs from the next one in the list by at least one digit: the last non-zero digit in the next address.

    Here's an example on your problem:

    192.168.1.24 / 29
192.168.1.40 / 30
192.168.1.64 / 28

    We will read these as

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

    Now, consider the first of these

    11000000 10101000 00000001 00011000 / 29

    We consider the prefix of length 29:

    11000000 10101000 00000001 00011

    Add one:

    11000000 10101000 00000001 00100

    Our n must be at least 27. To see whether it needs to be longer, consider the next subnet in our list:

    11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 00100
                               ^

    Our subnet differs from the next one in the 29th position which is also the rightmost nonzero position in the next subnet. Therefore, n = 29; we have created a new subnet:

    11000000 10101000 00000001 00100000 / 29

    If we apply the same procedure to the subnet just created, we would find we generate exactly the same prefix as corresponds to the next subnet in our original list. We can detect this and recognize this means there are no more gaps to fill here, and move on.

    The next subnet is 

    11000000 10101000 00000001 00101000 / 30

    The prefix of length 30 is

    11000000 10101000 00000001 001010

    Add one:

    11000000 10101000 00000001 001011

    Compare to the next subnet: 

    11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 001011

    We must choose n = 30 at minimum, so we get subnet:

    11000000 10101000 00000001 00101100 / 30

    Consider the prefix of length 30 and add one:

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

    Compare to the next:

    11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 001100

    We must have n at least 28, so we get

    11000000 10101000 00000001 00110000 / 28

    Consider the substring of length 28, add one and we get the same bit string as belongs to the next subnet in the original list. We recognize this means we have filled in the gaps and so we move on.

    We are looking at the last of the original inputs so there is nothing left to fill. Complete. Our subnets:

    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

    Note that this doesn't create subnet ranges outside of the provided input. If you want to do that, your algorithm can prepend to the list the minimum subnet, and append to the list the maximum subnet. Let's do minimum with 0.0.0.0/1 as the minimum subnet ad 255.255.255.255/32 as the maximum subnet:

    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    <<<<<<<<<

    The next one will give us the first real input subnet. The subnets are now:

    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

    We can repeat the exercise on the other end:

    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    <<<<<<<

    Rather than list out all the terms, because that's going to get monotonous, we can notice that when we have strings of 0s, we are going to decrease n by one and move the rightmost left one space left. So, we skip ahead:

    => 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    <<<<<<<

    We notice that 01^k becomes 10^k with n decreased by k; so we skip ahead again adding

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

    Back to rule #1:

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

    The next move, we get a subnet that matches the end of our range, so we must include an extra zero to make it distinct:

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

    If we really care about the 255.255.255.255 subnet, the right way is to continue this out by increasing n and the number of 1s by one each time to get something like 27 more subnets. However, if we just want to fill in the gaps we can recognize our present condition and add:

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

    This covers the rest of the range, including 255.255.255.255, so it isn't a solution to the augmented problem per se, but it does solve the original problem of filling in the gaps. Our complete list is as follows:

    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  <<<

    Instead of having two /4 subnets as explained above, I put a single /3 subnet in this list, since it is equivalent.