Extended Brain Storage

Classless Inter-Domain Routing

Posted on March 15, 2018

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:

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:

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:

BinaryDecimalHexadecimal
00000000.00000000.00000000.000000000.0.0.000.00.00.00
00000000.00000000.00000000.000000010.0.0.100.00.00.01
00000000.00000000.00000000.000000100.0.0.200.00.00.02
………
00001010.00010100.00011110.0010100010.20.30.400a.14.1e.28
………
11111111.11111111.11111111.11111111255.255.255.255ff.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:

Classful Inter-Domain Routing

In classful inter-domain routing, the first four bits of an IPv4 address determined the five classes as follows:

ClassLead. bitsNet-id sizeHost-id size
A0xxxxxxx8bits24bits
B10xxxxxx16bits16bits
C110xxxxx24bits8bits
D1110xxxxundefundef
E1111xxxxundefundef

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:

ClassIPv4 Address StructureDefault Netmask
A0nnnnnnn.HHHHHHHH.HHHHHHHH.HHHHHHHH255.0.0.0
B10nnnnnn.nnnnnnnn.HHHHHHHH.HHHHHHHH255.255.0.0
C110nnnnn.nnnnnnnn.nnnnnnnn.HHHHHHHH255.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:

Considering the aforementioned classes, their default netmasks can be rewriten in CIDR notation as follows:

ClassIPv4 Netmask in BinaryPrefix LengthCIDR Notation
A11111111.00000000.00000000.000000008 bits/8
B11111111.11111111.00000000.0000000016 bits/16
C11111111.11111111.11111111.0000000024 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:

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:

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.nnnnnnnnsee 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):

requirementsubnet-idhost-idhosts per subnet
1x /24noneHHHHHHHH2^8 - 2 = 254
requirementsubnet-idhost-idhosts per subnet
2x /250sHHHHHHH2^7 - 2 = 126
1sHHHHHHH2^7 - 2 = 126
requirementsubnet-idhost-idhosts per subnet
4x /2600ssHHHHHH2^6 - 2 = 62
01ssHHHHHH2^6 - 2 = 62
10ssHHHHHH2^6 - 2 = 62
11ssHHHHHH2^6 - 2 = 62
requirementsubnet-idhost-idhosts per subnet
1x /250sHHHHHHH2^7 - 2 = 126
2x /2610ssHHHHHH2^6 - 2 = 62
11ssHHHHHH2^6 - 2 = 62
requirementsubnet-idhost-idhosts per subnet
1x /250sHHHHHHH2^7 - 2 = 126
1x /2610ssHHHHHH2^6 - 2 = 62
2x /27110sssHHHHH2^5 - 2 = 30
111sssHHHHH2^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:

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

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:

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:

2) Known: address and CIDR:

3) Known: address and broadcast (the “smallest possible subnet” problem):

4) Known: address and prefix (the “smallest possible subnet” problem):

5) Known: prefix and broadcast:

6) Known: prefix and netmask:

7) Known: prefix and CIDR:

8) Known: broadcast and netmask:

9) Known: broadcast and CIDR:

Tags: #routing #VLSM #CIDR #IP #calculator #solver #regex #validation

⏴ Previous Post Next Post ⏵

maro | 2021 | Powered by Zola

This work is licensed under a CC0 1.0 Universal (CC0 1.0) Public Domain Dedication.