Persistent notes

How often you see something like this:

192.168.255.0/24

For those of us who do not frequently configure IP networks such notation may seem tricky and it has nothing to do with URI(s), ports and etc.

This is a “slash” notation which is formally called Classless Inter-Domain Routing (CIDR) notation.
It allows you to specify the network or the range of IP addresses in a more compact way.

Normaly for 192.168.255.0/24 the we would write:

Network: 192.168.255.0
Subnet mask: 255.255.255.0

which means there is network of 255 IP addresses starting at address 192.168.255.1.

The number after “/” sign denotes number of non-zero bits in the submask left to right.

Another example:

192.168.128.0/25 means:
Network: 192.168.128.0
Subnet mask: 255.255.128.0

which is a network with first address 192.168.128.1 and last address 192.168.255.255.

This notation is also called IP prefix notation.

It comes especially useful, when you want to use a trie in order to match the IP address with some predefined pool of partial values. Such task is relevant for IP routes and is known as Longest prefix match.

For example, let’s see how this all works together.
Let’s say in the routing table we have the following entries:

Route1 192.168.0.0/16
Route2 192.168.20.16/28
Route3 192.168.20.17/32

When these entries are put into Radix trie (Particia), we use binary representation so the prefix trie
would loook liks this (simplified view):


[ROOT_EMPTY_NODE]
|
11000000 10101000 [max index = 16, represents element 192.168.0.0]
|
00010100 0001 [max index 28, represents element 192.168.20.16]
|
0001 [max bit index = 32, represents element 192.168.20.17]


Radix trie has a nice feature which guarantees complexity of O(k) for all operations where k is the length of the input. In our special example the length of IP addresses is 32 bits so we will have no more than 32 comparisons to insert of delete new elements.

Why IP prefix notation is so useful.

See the “max index” values above?
It is the exact position where common parts of the addresses end. When we built Radix trie from raw data, we have to find this index every time we insert new entry.

When we have IP prefix notation, the index is already known to us so we can utilize this fact in
order to speed up the insertions!

If we look into algorithm of Patricia (Radix) trie which is used to store (IP routing) prefixes we would see
that trie will look different depending on the order of the insertions. One of the advantages of IP prefix notation is that it allows you to utilize the network mask bits in order to create a trie in a faster way, with less comparisons than in usual way.

Originally when new element is inserted in to the trie, we are comparing it with nodes bit by bit until
we find the common parts of the key. When branching index is already known (this is our /slash notation
number or subnet mask) we can keep all data sorted by this parameter before inserting into the trie.

Then inserting the entire routing table into the trie becomes faster since we only need to check the bit in the position of the branching index and store the pointer to the current node for the next insertion.

It turns out the slash notation is not only convenient for people but also for software.

For the implementation of the Patricia trie I would suggest the following article by Radu Gruian.

For the wonderful explanation and details about Radix trie and others please see Robert Sedgewick’s “Algorithms in C++“.