Introduction
The IP protocol of the TCP/IP suite supports internetworking at Layer 3. IP creates a virtual network that is independent of the underlying Layer 2 technologies. A unicast IPv4 address identifies an interface in that virtual network. In most cases a host will have only one IP interface and therefore we often say that the IPv4 address uniquely identifies a host.
IPv4 addresses are 32 bit unsigned binary integers. The IP address space is therefore the range of numbers between 0 and (2**32)-1. There are special addresses and addresses ranges within the overall address range such that not all of the addresses can actually be used for a unicast interface. However, to learn the mathematics of working with unicast IPv4 addresses these special cases can be ignored.
IPv4 delivery is hierarchical. Datagrams are delivered first to the correct network and then to the correct host on the network. IPv4 addressing supports this delivery by treating the 32 bit address as two fields: a network part and a host part.
When IP addresses were first conceived the first few most significant bits implicitly identified the boundary between the network part and the host part of the 32 address number in a scheme that is now called classful addressing. However, the resulting address allocation was inefficient.
The current approach to IPv4 addressing is called Classless InterDomain Routing or CIDR. The boundary between the network and host part of the 32 bit address can be anywhere within the address. The boundary must be explicitly identified with a netmask, a second 32 bit unsigned number with ones in the bits that represent the network and zeroes in the bits that represent the host in the companion IP address. These are contiguous fields with the network bits being the more significant bits and therefore appearing on the left side of the two-field netmask. The notation that describes a netmask with N network bits and 32-N=H host bits is /N.
Figure 1: A /20 CIDR netmask showing network and host fields
Although the IPv4 addresses and netmasks are 32 bit unsigned binary integers they can also be represented in thedotted-decimalformat. In dotted decimal the 32 bit numbers are treated as 4 octets of 8 bits each, the octets are converted from binary to decimal, and the decimal values are separated by a dot. Both netmasks and addresses can be expressed in dotted decimal; the /20 netmask in Figure 1 could also be written as 255.255.240.0. A subsequent section shows how to convert between the two notations. Figure 2 illustrates an address in both binary and dotted decimal.
Figure 2: The IPv4 address 172.16.7.195 also shown as a 32-bit, unsigned binary number
The dotted decimal notation can also be thought of as a “base 256” number of 4 places. Recall that in the decimal number system we talk about the 1’s place, the 10’s place, the 100’s place, and the 1000’s place as the first four “places” in a number. Describing these as powers of 10 the places are the 10**0 place, the 10**1 place, and so on. Similarly, the octets in the dotted decimal value (from right to left) are the 256**0, 256**1, 256**2, and 256**3 places respectively, where 256=2**8. Viewing dotted decimal in this manner allows comparison of the mathematics to the somewhat familiar math of hexadecimal (base 16).
Only the network bits are needed to identify the network. Therefore within a given network the network bits are identical on every host and only the host bits change from host to host. Because the host bits are on the right side of the netmask a single network within the internetwork corresponds to a block of contiguous addresses in the address space. These are represented by all of the possible combinations of the host bits. This is called a CIDR block of addresses.
There are two addresses in every CIDR block that have special meaning for that block. The smallest address in the block, i.e., the one with all host bits set to zero, is called the network address for that block. The largest address in the block is the directed-broadcast address for that block. Neither of these addresses can be assigned to an interface on a network.
Figure 3: A /29 CIDR block
By itself the netmask determines the size of a CIDR block but not a specific CIDR block of that size. We can imagine that a netmask of /N divides the 2**32 address space into 2**N blocks of size 2**(32-N) hosts. A particular address will fall into only one of the CIDR blocks of that size.
However, there are theoretically 32 different values of /N and therefore 32 different partitions of the address space into different block sizes. So a particular address that is the network address for a /N block may or may not be the network address for the /N-1 block that contains it, for example. The same is true for the directed-broadcast address. Thus we cannot memorize an address as being a network address or a directed-broadcast address; we must compute these addresses given a netmask of some size and one of the addresses within a particular CIDR block of that size.
We find at least 3 categories of problems that call for these computations: network design, network configuration, and network debugging. In network design problems we may need to create a network that supports some number of current hosts, perhaps a router interface, and some anticipated number of future hosts. How big should we make the CIDR block when requesting addresses for that network?
Once the network is in place we may need to configure the hosts to use the directed broadcast address for that network in a simulation application, for example. Or we may need to specify that network in the routing table of a remote router.
Finally, in debugging we may simply be told that a host with a particular IP address is having trouble talking to a host with a different IP address. Are these on the same network or different networks? What should the routing table entries be on these hosts and on the intervening routers?
These problems call for certain basic conversions. First for a given netmask we must be able to convert between CIDR /N notation and the corresponding dotted-decimal netmask. And we must be able to determine the size of the corresponding block and the number of assignable addresses in that block. For a given netmask and a specific address we must be able to identify the network address and directed-broadcast address for that specific CIDR block. And of course we need to understand these processes well enough to combine them in various ways and to work them in the opposite direction.
Understanding the binary details
The sum of powers of two
Our goal is to develop ways to avoid doing address mathematics the hard way: i.e., by working with the binary address and netmask and then converting to dotted-decimal. Instead, we want to develop shortcuts using mostly the dotted-decimal notation, some knowledge of the powers of two, and the special characteristics of the netmask. We start by looking at the mathematics to see how the shortcuts are developed. If the shortcuts “make sense” mathematically then they are likely to be more easily remembered.
One formula is used repeatedly in the following. The series of powers of two starting with 2**0 is a well-known formula.
Another useful version for our purposes is the following. Try a few examples to verify the result.
The formula above is useful because the netmask is a very structured binary number. If we take the netmask and invert all of the bits, so that the network bits are 0 and the host bits are 1 then we have the following:
Figure 4: A /20 netmask with the bits inverted
If we convert this binary number to decimal we add up the powers of two corresponding to each bit – which is exactly what the formula does for us. So the formula will be useful when working with the netmask.
Working with the binary netmask
Block size
A netmask serves two related purposes in address arithmetic. It fundamentally defines a CIDR block size, but as described above it also partitions the address space into a number of non-overlapping blocks of that size. In other words, a CIDR block of a certain size cannot start at an arbitrary address; it can only start at a multiple of that CIDR block size.
Assume we have a netmask of certain length /N. Nis the number of network bits and therefore the number of host bits is 32-N=H. The CIDR block by definition includes all of the possible combinations of the host bits – so the CIDR block size Bis the number of possible combinations of host bits H.
The first bit combination in each block will be 0. The final combination will be the sum of the powers of 2 from 2**0 to 2**(H-1) as illustrated above in Figure 4. The latter value can be evaluated using the second version of the formula:
Note from Figure 4 above that this is also the value of the inverted netmask for H host bits!
This is almost the total number of combinations – we have to add 1 for the all zero combination. (If you have trouble with this – write out 8 binary numbers starting at 000 and ending with 111). So the total number of combinations of H host bits, the block size B, is B = ((2**H)-1) + 1 or simply B=2**H total combinations. Thus a /N netmask has a block size B=2**(32-N). And the number of assignable address is B-2.
The binary representation of the block size for a CIDR block with H host bits will have the bit H set to one and all other bits set to zero. Note in the normal (non-inverted) netmask this is the least significant bit of the network field. This is the mathematical proof that the network address of a block will be a multiple of the block size. And the math above shows that the block size will be the inverted mask + 1. This can be seen in Figure 4 by adding 1 and carrying all the way until a final carry goes from the host field into the network field. Blocksizes are illustrated in Figure 5 with small blocks at the bottom of the address space.
Figure 5: CIDR blocks starting on a multiple of the block size
Block start
The CIDR block size B also determines the possible starting values for blocks of that size. Once we pick a particular address A to go with that block size there will be exactly one block of that size Bthat contains the address. The first address in that containing block (the network address) must be a multiple of the block size B, so the network address associated with an address A is the smallest multiple of the block size B that is less than or equal to A.
For a given netmask and address there are several ways to compute the network address but the most straightforward (for a computer) is to logically AND the two 32 bit values together. This is why the term netmask is used. The host bits of 0 on the right of the netmask when ANDed with the corresponding bits of the address produce a result of 0. The network bits of 1 on the left side of the netmask when ANDed with the corresponding bits of the address merely copy the network bits to the result. In other words the host bits have been masked off leaving only the network bits in the result.
Figure 7: Binary AND operation with the netmask
Once we have the network address for the block containing a particular address A then it is straightforward to find the directed-broadcast address. For a block size with B=2**H we have already determined that the final address in the block is the network address + (2**H) – 1, or the network address + B – 1. Figure 5 above also illustrates another way to do this while in binary – simply set the host bits to 1.
Working with dotted-decimal notation
Thinking in base 256
If we want to do dotted decimal additional and subtraction we need to think in base 256. When we are adding and we exceed the base then we carry into the next place and keep the remainder in the current place. For dotted decimal base 256 this means addition follows the pattern
0.0.0.255 + 0.0.0.1 = 0.0.0.256 = 0.0.1.0.
Similarly subtraction follows a similar borrowing pattern. For example:
0.4.0.0 – 0.0.0.1 = 0.3.256.0 – 0.0.0.1 = 0.3.255.256 – 0.0.0.1 = 0.3.255.255
We can treat the block size as dotted decimal. If we have a block size of 2**12 = 4096 for H=12then that is equivalent to a block size of (2**4) x (2**8), i.e., a 16 in the third octet, or 0.0.16.0. A block size will always have the form of a power of two in one of the octets with all of the other octets zero.
Similarly the inverted mask can be treated as dotted decimal. For the /20 netmask shown in Figure 4 there are 12 host bits, with 4 in the 3rd octet and 8 in the 4th octet. Each series for powers of two helps here – the 3rd octet is (2**4)-1 = 15, and the 4th octet is (2**8)-1=255. So the inverted mask for /20 is 0.0.15.255. And 0.0.15.255 + 0.0.0.1 = 0.0.16.0 verifying the relationship between the block size and the inverted netmask.
There is one final observation to make about the dotted-decimal numbers. If all of the bits in the netmask were 1 then it would be the dotted decimal value 255.255.255.255. It should be clear that adding a netmask and its inverted netmask will produce this 255.255.255.255. Therefore, if we can find the inverted netmask we can subtract it from 255.255.255.255 to obtain the dotted decimal value of the netmask. For the /20 example we would have 255.255.255.255 – 0.0.15.255 = 255.255.240.0.
Usingthe various observations above we can look at the actual computations.
Converting from a CIDR notation netmask to a dotted-decimal
First consider the problem of changing between /N CIDR netmask notation and the dotted-decimal equivalent. As noted above the key is the number of host bits H=32-N. From that we can immediately compute the block size B=2**H and the number of assignable addresses as B-2.
We allocate the host bits to the various octets from the right. For example, with /N=/20 we have H=32-20=12. We would have 8 host bits in the 4th octet (call that H4=8), 4 host bits in the 3rd octet (H3=4), and 0 host bits in the 1st and 2nd octets (H1= H2=0).
Using the series of powers-of-two formula we can then compute the octets of the inverted netmask.
Octet one: (2**H1)-1 = (2**0)-1 =0;
Octet two: (2**H2)-1 = (2**0)-1 =0;
Octet three: (2**H3)-1 = (2**4)-1=15;
Octet four: (2**H4)-1 = (2**8)-1=255.
The result is 0.0.15.255 and the netmask is therefore 255.255.255.255 – 0.0.15.255 = 255.255.240.0
To compute the mask directly one recognizes that each octet_value=255-((2**Hoctet)-1). That simplifies to 256-(2**Hoctet). So for any octet in the dotted-decimal mask raise 2 to the power of the host bits in that octet and subtract from 256.
Returning to our example: with H1= H2=0 we have 256-2**0=255; H3=4 so 256-2**4=240; and H4=8 so 256-2**8=0. Of course one quickly learns to just do the octet where the network:host boundary occurs, but the math above shows that it works in general. Thus the dotted-decimal mask corresponding to /20 is 255.255.240.0.
Converting from a dotted-decimal netmask to a CIDR notation
Going from the dotted-decimal mask to CIDR is also an octet-by-octet operation initially. For each octet the goal is to find the number of host bits in that octet and then add the four values to obtain the total number of host bits. This value is subtracted from 32 to obtain the /N of the CIDR notation.
In each octet we use the formula from the section above but in the other direction:
So for our example 255.255.240.0, octet 4 has dotted-decimal netmask value of 0; log2(256-0)=log2256=8. For octets 1 and 2, log2(256-255)=log21=0. And for octet 3, log2(256-240)=log216=4. The total number of host bits is 0+0+4+8=12=H, and therefore N=32-H=20 and this is a /20 netmask. Again, the octet with the network:host boundary is the only interesting octet, but the formula works for all octets. Once H is known the block size and number of assignable addresses are the same computation as before.
So this gives us the capability to go between /N notation, the equivalent dotted-decimal netmask, and from either starting point to determine the block size that goes with the netmask.
Finding the network address using dotted-decimal notation
Recall that the network address will be the largest multiple of the block size that is less than or equal to an address. This comparison can also be done using a dotted-decimal block size.
We learned above how to find the block size in dotted decimal given the number of host bits H. The block size converted to dotted decimal only has one octet that is not zero – call that octetblock– because there is only one non-zero bit in the binary representation of the block size. If we were to count by the block size we would go through multiple dotted-decimal network address values with the same values of the octets to the left of octetblockbefore we actually would increment the octet to the left of octetblock.
For example, if the address A is 157.25.34.12 and the block size is 0.0.16.0, then we count 157.25.0.0 to 157.25.240.0 by 0.0.16.0 before we finally get to 157.26.0.0. One of these blocks with network address 157.25.0.0 through 157.25.240.0 must contain the address A – so the network address will always copy the octets in A to the left of octetblock.
Any octet to the right of octetblockmust be zero in the network address – recall that the single non-zero bit of the block size is the least significant bit of the network field in the netmask. So all bits - and therefore all octets - to the right would be zeroed by the masking operation.
What is left is only a comparison in octetblock. We find the largest multiple of octetblock that is less than or equal to that octet’s value in address A. For example, with our /20 we had a block size of 0.0.16.0 in dotted-decimal. If our address A is notionally X.Y.Z.W then we find the smallest value that is 16xJ ≤ Z for some J and write the network address as X.Y.16xJ.0.
More specifically, using the numbers in Figure 5, we have an address of 172.16.7.195 and a netmask of 255.255.255.224. Using our techniques above we determine that this is H=5 and /N=27. H=5 means that the block size is 2**5=32 in the 4th octet. Since we started with a dotted decimal netmask we can also observe that this is 256-224 in the 4th octet – using the same mathematics we used when converting from dotted-decimal netmask to CIDR notation. Either way you arrive at the answer the block size is 0.0.0.32 in dotted-decimal. We have 3 more-significant octets that we simply copy to the network address. In the 4th octet we find the smallest multiple of 32 that is less than or equal to 195. 192=32x6 and 224=32x7 is too large, so the 4thoctet is 192. Thus the network address is 172.16.7.192.