One bit network masks

The number of IP addresses is:

    4.2949e9   IPv4 addresses
    3.4028e38  IPv6 addresses

The addresses are simply bitstrings of length 32 and 128 respectively. So the numbers are just 2³² and 2¹²⁸.

But how many networks are there?

Networks

In the following I will only use IPv4, as it is simpler. But our findings will also apply to IPv6.

Networks have two parts, a network address and a network mask. At first glance it looks like two IP addresses, because it is two bitstrings of length 32.

The second bitstring, the network mask, always starts with a run of 1s, after which it is all 0s. Written with bits, the example looks like this:

As the mask always has this pattern, many just writes networks by using the number of 1s in the mask, like this:

This is called CIDR notation.

Now, let us just for the fun of it imagine that we want to save some memory.

Notice that the mask only has 32 bits, so it can only take 33 different values. We clearly dont need 32 bits to write those values. It can be done with 6 bits. So our example network could be written this way:

But it can be done even better than that. Notice that the network address ends in 0s the same way that the 32 bit mask does. So we should be able to save something here. There are some complications though, because the number of 0s depend on the mask, so it is variable. Also the network address can be valid for more than one mask. At least all smaller masks. So what to do?

Well, as you guessed it from the headline, we can effectively reduce the mask down to one bit. This is how to do it:

Take only the part of the network address where the 32 bit mask is 1. Note what the last bit in it is. Then append the opposite bit until the length is n+1.

For our example, the result will look like this:

Can we save more memory than this? No. All /32 networks are the same as all IP addresses, and as we know they take 32 bits to represent. So using only 32 bits will not leave any space to represent networks larger than /32.

0.0.0.0/0

When the 32 bit mask only contains 0s, that is when the network is 0.0.0.0/0, our method for finding the one bit network mask breaks down. There are no bits in the network address we can start with. We dont know whether to fill the 33 bits with 0s or 1s.

I have chosen to say that we should use 0s.

If you start doing arithmetic with bitstrings, you find out that the bitstring that has only 1s in it, behaves in weird ways. So it is indeed called "weird". That is the reason I chose that it also should be the one that is weird when we are working with one bit network masks.

But how many?

It is simple to reverse the "compression" I just showed you. All you have to do is to reverse the steps.

Now, note two interesting facts. 1: No matter what bitstring of length 33 that we receive, it can be "decrompessed" into a network. 2: Two different non-weird strings will always "decompress" into two different networks...

What we have is better than compression and decompression. We have a one-to-one correspondence between networks and non-weird bitstrings of length 33.

That makes it easy to answer the question from the beginning of the article... How many networks are there?

    8.5899e9   IPv4 networks
    6.8056e38  IPv6 networks*

Which is 2³³-1 and 2¹²⁹-1 respectively.

*) This is a theoretical number. In IPv6 all subnets should be /64, giving us instead a number of 2⁶⁵-1 ≈ 3.6893e19 IPv6 networks. But this number also comes with a caveat, as networks smaller than /64 are being regularly used in a number of cases.

In practice

The reason IPv4 networks are represented by network addresses and masks, is that they are incredibly efficient to compute with. With that representation most computations can be done with bitwise logic operations, which are part of the instruction set of any decent processor. You dont get much faster computation than that.

You may also have noticed that processors are the reason behind the size of the bitstrings, as 32 bits was the word size of the powerful processors, back when IPv4 was designed.

The algorithms for, and storage of IPv6 networks are more complicated. But their representation is also heavily influenced by processors and performance.

Indeed, hardware aligned formats permeates all of networking. Network formats are possibly the closest to assembler that you will get for data formats.

In general

If we forget networking for a moment, what we are really dealing with when we have a "network", is a bitstring of length less than or equal to 32. Let us also forget the number 32, then what we have is a bitstring of length less than or equal to n. So our correspondance applies in general between those bitstrings, and non-weird bitstrings of fixed length n+1.

The functions are very simple. One is the inverse of the other, and vice versa. Here they are in pseudo code:

function to_fixed( b , n )
// b: Bitstring of length ≤ n.
// n: Positive integer.
// Map b into a bitstring of length n+1.
    if b is empty
        set lastbit to 1
    else
        set lastbit to the last bit of b
    append (not lastbit) to b as long as its length is ≤ n
    return b

function from_fixed( b )
// b: Non-weird bitstring of length n+1.
// Map b into a bitstring of length ≤ n.
    set lastbit to the last bit of b
    remove the last bit of b as long as it is equal to lastbit
    return b

These functions can also gain from low-level instructions. But because they contain loops, they can never be as efficient as the address+mask functions.