Tags: #routing #VLSM #CIDR #IP #calculator #solver #regex #validation
Classless Inter-Domain Routing
Why building yet another online solver/calculator of Classless Inter-Domain Routing (CIDR) for Internet Protocol version 4 (IPv4)? First, it is fun, enriching and fulfilling; and second, it digs a bit more into the details…
IPv4 CIDR VLSM Calculator
After putting reasonable inputs, the remaining ones can be calculated using the Send
button.
Introduction
A brief history: The Internet Protocol (IP) was designed back in the 1970s, versions 0 to 3 were experimental and finally, IPv4 was defined in RFC 791. As time passed, the Internet “spread like a disease” and the industry realised that the address space will not suffice. Thus, private address space, defined in RFC 1918, appeared including IP masquerading technique, also known as the Network (or Protocol) Address Translation (NAT/PAT).
There are differences among NAT types and PAT. However, they are commonly mixed and used to one’s content usually in reference to a private subnet “hidden” behind a single public IPv4 address. Obviously, NAT was not the silver bullet and a new protocol version 6 (IPv6) emerged and has been defined in RFC 8200.
Mathematics
In order to comprehend the “language of the computers”, it is necessary to understand binary. Once knowing binary, it is easy to understand hexadecimal, since both share the same feature, i.e. their base (radix) is an n
-th power of 2, where n
is 1, 2, 3, ...
; in other words, n
is a positive integer.
Assuming four bits (i.e. 4 binary digits), the amount of numbers they can generate is 2^4 = 16
and the finite set can be expressed in different numeral systems as follows:
0000, 0001, ..., 1111
in binary,0, 1, 2, ..., 15
in decimal,0, 1, 2, ..., f
in hexadecimal.
It is worth noticing that exactly four bits form a single hexadecimal number. Furthermore, 4*n
bits generate exactly n
hexadecimal numbers (n
is a positive integer).
It is also important to understand Boolean algebra and knowing what logical AND
(&
), OR
(|
), negation (~
), XOR
(^
) mean and how they behave. For example:
a & ~a = 0 (false)
,a | ~a = 1 (true)
,a & 1 = a
,a | 0 = a
,a | 1 = 1
, etc.
Theory (IPv4)
Generally, IP makes sure that information (data packets, datagrams) is relayed across network boundaries. A label called the IP address is assigned to each node in order to identify senders from recipients. The IPv4 address is 32bits (4bytes) long, while IPv6 address is 128bits (16bytes) long. The IPv4 address space can be expressed in various numeral systems as follows:
Binary | Decimal | Hexadecimal |
---|---|---|
00000000.00000000.00000000.00000000 | 0.0.0.0 | 00.00.00.00 |
00000000.00000000.00000000.00000001 | 0.0.0.1 | 00.00.00.01 |
00000000.00000000.00000000.00000010 | 0.0.0.2 | 00.00.00.02 |
… | … | … |
00001010.00010100.00011110.00101000 | 10.20.30.40 | 0a.14.1e.28 |
… | … | … |
11111111.11111111.11111111.11111111 | 255.255.255.255 | ff.ff.ff.ff |
Computer (data) networks allow nodes to share resources. Each network range (the range of IPv4 addresses) starts with the lowest address called the network address and ends with the highest address called the broadcast address. Considering the binary notation, addresses within a network will always share a specific feature that identifies the network, which is the most-significant bit-group. Therefore, each IPv4 address can be logically divided into two parts:
- a network identifier (also called routing prefix or network prefix)
- and a host identifier.
Classful Inter-Domain Routing
In classful inter-domain routing, the first four bits of an IPv4 address determined the five classes as follows:
Class | Lead. bits | Net-id size | Host-id size |
---|---|---|---|
A | 0xxxxxxx | 8bits | 24bits |
B | 10xxxxxx | 16bits | 16bits |
C | 110xxxxx | 24bits | 8bits |
D | 1110xxxx | undef | undef |
E | 1111xxxx | undef | undef |
In the IPv4 environment, networks can be characterised by a network mask (netmask), which is an IPv4 address (bitmask) that has the following feature: When applied by the logical AND
to any IPv4 address in the network, it results in the network address, i.e. prefix.
network-mask AND IPv4-address = network-address (prefix)
Generally, the IPv4 address structure of A
, B
and C
classes (D
and E
are omitted as represent multicast and publicly unroutable IPv4 ranges) and their default netmasks are depicted as follows:
Class | IPv4 Address Structure | Default Netmask |
---|---|---|
A | 0nnnnnnn.HHHHHHHH.HHHHHHHH.HHHHHHHH | 255.0.0.0 |
B | 10nnnnnn.nnnnnnnn.HHHHHHHH.HHHHHHHH | 255.255.0.0 |
C | 110nnnnn.nnnnnnnn.nnnnnnnn.HHHHHHHH | 255.255.255.0 |
where n
represents a single network ID bit and H
a single host ID bit.
Classless Inter-Domain Routing
The classfull approach turned up to be a waste of the IPv4 range. Regardless of the real need for IPv4 address, 2^N - 2
host IDs were always assigned per class, where N
is the host size (N = 32 - prefix_length)
and the subtraction of 2
represents the use of host-id for network address and host-id for broadcast address). Therefore, classless inter-domain routing (CIDR) came into place and introduced the following concepts:
- variable-length subnet masking (VLSM) technique, which allows the specification of prefixes of arbitrary-lengths (i.e. the original host ID is further divided into subnet ID and host ID);
- CIDR notation of writing IPv4 addresses, where the routing prefix is written with a suffix indicating the number of bits of the prefix (i.e. prefix length);
- contiguous prefixes of IPv4 address can be aggregated into supernets, resulting into reducing of the number of records in routing tables.
Considering the aforementioned classes, their default netmasks can be rewriten in CIDR notation as follows:
Class | IPv4 Netmask in Binary | Prefix Length | CIDR Notation |
---|---|---|---|
A | 11111111.00000000.00000000.00000000 | 8 bits | /8 |
B | 11111111.11111111.00000000.00000000 | 16 bits | /16 |
C | 11111111.11111111.11111111.00000000 | 24 bits | /24 |
However, classes are no longer used in CIDR. Therefore, every IPv4 address needs to be specified with appropriate network (subnet) mask (netmask) or prefix in CIDR notation.
CIDR/VLSM Example
In order to understand the VLSM, the following example can be considered:
An administrator was assigned a
/24
prefix. Based on the requirements, the available range of 256 IPv4 addresses can be consumed in various ways, e.g. as:
- a single
/24
subnet; or - two halves, i.e. two
/25
subnets; or - four quarters, i.e. four
/26
subnets; or - one
/25
and two/26
subnets; or - one
/25
, one/26
and two/27
subnets; or - one
/25
, four/27
subnets; or - two
/26
and four/27
subnets; or - etc.
It is important to understand that the networks can’t start and end arbitrarily. Each subnet position is strictly defined by its appropriate binary representation, which means that regardless of the prefix:
- a
/24
subnet will always have its 4th byte (last 8 bits):- in network address equal to
00000000
, - in broadcast address equal to
11111111
,
- in network address equal to
- a
/25
subnet will always have its last 7 bits:- in network address equal to
0000000
, - in broadcast address equal to
1111111
;
- in network address equal to
- a
/26
subnet will always have its last 6 bits:- in network address equal to
000000
, - in broadcast address equal to
111111
;
- in network address equal to
- generally, a
/prefix_length
subnet will always have its last32 - prefix_length
bits:- in network address equal to
32 - prefix_length
zeros, - in broadcast address equal to
32 - prefix_length
ones.
- in network address equal to
The assigned address space can be imagined as a circle. Until there is no more space, the circle can be divided in segments that are always halves of the previous halves, because the address space is binary and it is always possible to “borrow” a bit (or n
bits) from the former host ID part of the IPv4 address. The downside of this approach is that with each division, 2 addresses are “lost” for network address (prefix) and broadcast address within each subnet.
Considering the previous example of an assigned /24
subnet, the net-id
will be always:
net-id (/24 ~ 24-bits) | host-id |
---|---|
nnnnnnnn.nnnnnnnn.nnnnnnnn | see next table |
and the former host-id
(8bits long in this example) can be used as follows (s
represents a single bit of former host-id H
which became a subnet-id bit in CIDR):
requirement | subnet-id | host-id | hosts per subnet |
---|---|---|---|
1x /24 | none | HHHHHHHH | 2^8 - 2 = 254 |
requirement | subnet-id | host-id | hosts per subnet |
---|---|---|---|
2x /25 | 0 | sHHHHHHH | 2^7 - 2 = 126 |
1 | sHHHHHHH | 2^7 - 2 = 126 |
requirement | subnet-id | host-id | hosts per subnet |
---|---|---|---|
4x /26 | 00 | ssHHHHHH | 2^6 - 2 = 62 |
01 | ssHHHHHH | 2^6 - 2 = 62 | |
10 | ssHHHHHH | 2^6 - 2 = 62 | |
11 | ssHHHHHH | 2^6 - 2 = 62 |
requirement | subnet-id | host-id | hosts per subnet |
---|---|---|---|
1x /25 | 0 | sHHHHHHH | 2^7 - 2 = 126 |
2x /26 | 10 | ssHHHHHH | 2^6 - 2 = 62 |
11 | ssHHHHHH | 2^6 - 2 = 62 |
requirement | subnet-id | host-id | hosts per subnet |
---|---|---|---|
1x /25 | 0 | sHHHHHHH | 2^7 - 2 = 126 |
1x /26 | 10 | ssHHHHHH | 2^6 - 2 = 62 |
2x /27 | 110 | sssHHHHH | 2^5 - 2 = 30 |
111 | sssHHHHH | 2^5 - 2 = 30 |
etc.
The smallest network possible is a /30
, i.e. 2-bit host-ID resulting in a subnet of only four addresses: one for network prefix, 2 for nodes and one for broadcast address. There is an exception for point-to-point links where a /31
subnet can be used. A /32
is always a single IPv4 only (the host-ID has zero bits).
It is always a good practice to start with the biggest subnet and continuing with the second biggest until reaching the smallest. This is to prevent the designer from making mistakes and to refrain from overlapping subnets.
Analogically, the contiguous network prefixes can be aggregated into supernets as follows:
- two subsequent
/24
networks into one/23
supernet, - four subsequent
/23
networks into one/21
supernet, - etc.
Thinking as a Network Interface
As mentioned earlier, the following bitwise operation is the definition of an IPv4 netmask:
prefix = netmask & address
Using Boolean algebra, several operations can be applied to the previous formula in order to express the netmask“ as follows“:
- while keeping the equation in balance, both sides can be expanded with the same term
| ~address
, - the left side can be reduced due to the complementation law:
a | ~a = TRUE
, - the left side can be further reduced due to the identity law:
b & TRUE = b
.
The previous thought can be mathematically expressed as follows:
netmask & address = prefix
netmask & address | ~address = prefix | ~address
netmask & TRUE = prefix | ~address
netmask = prefix | ~address
... therefore:
netmask = prefix | ~broadcast
Since the previous equation is valid for any IPv4 address within the range given by the network prefix (or network mask), the following is true as well:
netmask & address = prefix
Therefore:
netmask & broadcast = prefix
broadcast & netmask = prefix
broadcast & netmask | ~netmask = prefix | ~netmask
broadcast & TRUE = prefix | ~netmask
broadcast = prefix | ~netmask
Note: A wildcard mask is yet another term for the complementary netmask (esp. in Cisco Press publications):
wildcard = ~netmask
Bit shifting is a bitwise operation, which moves each digit in a number’s binary representation in a specific direction:
- left: usually written as
<<
, a zero bit (0
) is added from right and the left-most bit is lost (the most-significant bit) - right: usually written as
>>
, a zero bit (0
) is added from left and the right-most bit is lost (the least-significant bit).
A couple of examples as follows:
10011001 << 1 ... 00110010
10011001 >> 1 ... 01001100
Note: A single shift left equals binary multiplication by 2. A single shift right equals binary division by 2.
Input Validation
Because user input can never be trusted, it is always a good practice to validate inputs and re-validate outputs.
IPv4 address validation can be performed using a regular expression (regex). The following regex considers that an IPv4 address is a string that starts with 250-255
or 200-249
or (zero or one) of 0-1
followed by 0-9
followed by zero or one 0-9
(which matches the range of 0-199
), followed by a dot character (.
), and it all repeats 3
times; and ultimately, it is followed by the the same sequence defined prior to the dot character:
^((25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$
IPv4 netmask validation can be performed using bit shifting. When a network mask is subtracted (logical OR
) from the same netmask multiplied by 2 (a bit shift to the left) and the result is again a network mask (due to the fact that netmask contains the most-significant bits set to 1
and the least to 0
). However, this is only true if calculating with 32-bit long integers, as the most significant bit is lost due to variable overflow. Usually, programming languages provide larger variable types than integer, so it is important to subtract the result by the most significant bit of 2^32 = 4294967296
:
correction = 4294967296;
bitshift = netmask << 1;
if (netmask == ((bitshift | $netmask) - correction)){
return true; // mask is valid
}else{
return false; // mask is invalid
}
CIDR notation validation can be performed using a regular expression. The following regex considers that CIDR can contain numbers in the range of 1-9
or 10-29
or 30-32
:
^([1-9]|[1-2][0-9]|3[0-2])$
Conversion of a netmask to CIDR notation can be performed by subtraction of result of logarithm to base two of argument: netmask XOR-ed with the global broadcast address (i.e. 255.255.255.255
) increased by one from 32, which is the maximum possible CIDR value:
32 - log2( (netmask XOR global_broadcast) + 1)
Conversion of a CIDR notation to netmask can be performed using the bitshift operation by shifting 32 - CIDR
-times left starting from -1
:
-1 << (32 - CIDR)
Finding the largest CIDR notation to find the smallest possible subnet when the network and CIDR masks are not specified can be achieved by sequential bit shifting right until the right-shifted IPv4 address becomes equal to either the right-shifted broadcast address or the network address (depending on what the user provided). The number of shifts represents the number of subnet bits and it needs to be subtracted from 32 to get the CIDR notation.
Practical Calculations
Depending on two known parameters, the rest of the parameters can be calculated in regards to the aforementioned formulas as follows:
1) Known: address
and netmask
:
- Calculation:
prefix = address & netmask
,broadcast = address | ~netmask
,CIDR = conversion of netmask
.
- Check and correction of prefix as per calculated broadcast:
prefix = broadcast & netmask
.
2) Known: address
and CIDR
:
- Calculation:
netmask = conversion of CIDR
,prefix = address & netmask
,broadcast = address | ~netmask
.
- Check and correction of prefix as per calculated broadcast:
prefix = broadcast & netmask
.
3) Known: address
and broadcast
(the “smallest possible subnet” problem):
- Check if IP address is smaller than the broadcast address
- Calculation:
CIDR = 32 - number of bitshifts until address = broadcast
,netmask = conversion of CIDR
,prefix = broadcast & netmask
.
4) Known: address
and prefix
(the “smallest possible subnet” problem):
- Check if IP address is bigger than the network address
- Calculation:
CIDR = 32 - number of bitshifts until address = prefix
,netmask = conversion of CIDR
,broadcast = address | ~netmask
.
5) Known: prefix
and broadcast
:
- Calculation:
netmask = prefix | ~broadcast
,CIDR = conversion of netmask
.
- Check and correction of :
prefix = broadcast & netmask
.
6) Known: prefix
and netmask
:
- Calculation:
broadcast = prefix | ~netmask
,CIDR = conversion of netmask
.
- Check and correction of prefix as per calculated broadcast:
prefix = broadcast & netmask
.
7) Known: prefix
and CIDR
:
- Calculation:
netmask = conversion of CIDR
,broadcast = prefix | ~netmask
.
- Check and correction of prefix as per calculated broadcast:
prefix = broadcast & netmask
.
8) Known: broadcast
and netmask
:
- Calculation:
prefix = broadcast & netmask
,CIDR = conversion of netmask
.
- Check and correction of broadcast as per calculated prefix:
broadcast = prefix | ~netmask
.
9) Known: broadcast
and CIDR
:
- Calculation:
netmask = conversion of CIDR
,prefix = broadcast & netmask
.
- Check and correction of broadcast as per calculated prefix:
broadcast = prefix | ~netmask
.