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 last`32 - 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`

.