Implementation of CIDR routing table in Rust

Classless Inter-Domain Routing (CIDR) is a method of allocating IP addresses. This method is used in low-level routing and other Computer Science fields, especially in the Cloud. For example, in AWS, you manage a VPC and subnets. They contain a set of IP ranges in the form of CIDR blocks.

As I mentioned earlier, CIDR is used for routing. The main idea of routing is to identify the most exact CIDR block for a given IP address or indicate that such does not exist. This task becomes more complex when you have hundreds of thousands of CIDR blocks.

Routers are bones of the internet. That’s why it’s crucial to deliver the fastest software possible to provide maximum performance and throughput.

In this article, I will implement the basic CIDR routing table in Rust, optimize the routing algorithm, and benchmark different solutions for comparison.

Project setup

First of all, we need to create a project. To do that, we use this command:

cargo new --lib cidr-routing-table

That’s it. Open the created folder and start coding.

Errors module

Let’s start our project by defining the error type. It should be located in the file called errors.rs. There are 4 possible errors during the execution:

• CIDR string is wrong
• CIDR prefix string can’t be converted to a number
• IPv4 address string is wrong
• The prefix length is wrong

use std::{net::AddrParseError, num::ParseIntError};

#[derive(PartialEq, Eq, Debug)]
pub enum NetworkParseError {
    AddrParseError(AddrParseError),
    ParseIntError(ParseIntError),
    CidrParseError,
    NetworkLengthError,
}

Utils module

Before implementing the Routing Table, we need to define some useful functions. Good practice in software development is to create a separate file called utils.rs, which contains some shared code for the project. Let’s create such a class inside the src folder and paste this code.

use crate::errors::NetworkParseError;
use std::net::Ipv4Addr;

pub const MAX_LENGTH: u8 = 32;

pub fn get_cidr_mask(len: u8) -> Result<u32, NetworkParseError> {
    if len > MAX_LENGTH {
        Err(NetworkParseError::NetworkLengthError)
    } else {
        let right_len = MAX_LENGTH - len;
        let all_bits = u32::MAX as u64;
        let mask = (all_bits >> right_len) << right_len;

        Ok(mask as u32)
    }
}

pub fn cut_addr(addr: Ipv4Addr, len: u8) -> Result<Ipv4Addr, NetworkParseError> {
    if len > MAX_LENGTH {
        Err(NetworkParseError::NetworkLengthError)
    } else {
        let right_len = MAX_LENGTH - len;
        let bits = u32::from(addr) as u64;
        let new_bits = (bits >> right_len) << right_len;

        Ok(Ipv4Addr::from(new_bits as u32))
    }
}

First, I defined constant MAX_LENGTH, which equals 32, because IPv4 is 32 bits long. We will use it sometimes in our program.

Then, I added to functions:

• get_cidr_mask takes CIDR prefix length in range 0..32 and returns binary mask in the form ....111000.... This function should handle the wrong input when the prefix length is bigger than 32. That’s why its return type is Result<..>.
• cut_addr is another shared function. It’s used to modify the given IPv4 address by applying binary AND operation between the address and CIDR mask of length len. In the same way, this function may return an error for invalid input.

CIDR definition

After that, we should define the CIDR structure. Rust std library includes an implementation for IPv4 address, but CIDR is missing. You can use the one from cidr crate, but we will implement our own.

CIDR structure

CIDR consists of two parts: IPv4 address and prefix length. Let’s write it in Rust code:

use std::{net::Ipv4Addr, str::FromStr};

use crate::{
    errors::NetworkParseError,
    utils::{get_cidr_mask, MAX_LENGTH},
};

#[derive(PartialEq, Eq, Debug, Clone, Copy, Hash)]
pub struct Ipv4Cidr {
    addr: Ipv4Addr,
    len: u8,
}

CIDR implementation

Let’s implement this structure. The next part contains a lot of code, but I will try to describe all the parts one by one.

• new method is used to create CIDR from a given IPv4 address and prefix length. This method may return an error if the prefix length is longer than 32 or it’s now compatible with the IPv4 address (IPv4 address mask contains more 1s than the prefix length).
• new_host returns CIDR from a given IPv4 address with a prefix length equal to 32.
• len returns prefix length.
• min returns the first available address in the block.
• max returns the latest available address. It’s done by reverting all 0s to 1s in the given address skipping len bits from left.
• contains verifies if the given address belongs to the block.

impl Ipv4Cidr {
    pub fn new(addr: Ipv4Addr, len: u8) -> Result<Self, NetworkParseError> {
        let mask = get_cidr_mask(len)?;
        let bits = u32::from(addr);

        if (bits & mask) != bits {
            Err(NetworkParseError::NetworkLengthError)
        } else {
            Ok(Self { addr, len })
        }
    }

    pub fn new_host(addr: Ipv4Addr) -> Self {
        Self {
            addr,
            len: MAX_LENGTH,
        }
    }

    pub fn len(&self) -> u8 {
        self.len
    }

    pub fn min(&self) -> Ipv4Addr {
        self.addr
    }

    pub fn max(&self) -> Ipv4Addr {
        let bits = u32::from(self.addr);
        let mask = get_cidr_mask(self.len).expect(&format!(
            "{} should always be lower than or equal to 32",
            self.len
        ));
        let reversed_mask = u32::MAX ^ mask;

        let max_bits = bits | reversed_mask;
        Ipv4Addr::from(max_bits)
    }

    pub fn contains(&self, addr: Ipv4Addr) -> bool {
        let lower = self.min();
        let upper = self.max();

        lower <= addr && addr <= upper
    }
}

FromStr implementation

As an exercise, we should allow library users to convert strings to CIDR. To do that, implement FromStr trait for Ipv4Cidr:

impl FromStr for Ipv4Cidr {
    type Err = NetworkParseError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let parts: Vec<&str> = s.split('/').collect();

        if parts.len() != 2 {
            return Err(NetworkParseError::CidrParseError);
        }

        let addr = Ipv4Addr::from_str(parts[0]).map_err(NetworkParseError::AddrParseError)?;
        let len = parts[1]
            .parse::<u8>()
            .map_err(NetworkParseError::ParseIntError)?;

        Self::new(addr, len)
    }
}

Routing Table Implementation

Routing Table trait

Finally, we can start implementing CIDR Routing Table trait. Let’s make it simple and add only these methods:

• add_cidr to add CIDR Block to the table.
• remove_cidr to remove CIDR Block from the table.
• find_exact_cidr to find the most exact CIDR for this Ipv4Addr.

pub trait RoutingTable {
    fn add_cidr(&mut self, cidr: Ipv4Cidr);

    fn remove_cidr(&mut self, cidr: Ipv4Cidr);

    fn find_exact_cidr(&self, addr: Ipv4Addr) -> Option<Ipv4Cidr>;
}

List Routing Table

Brute Force implementation of CIDR Routing Table uses Vec. add_cidr and remove_cidr operations are push and retain methods of Vec accordingly. find_exact_cidr method is more interesting. The idea is to iterate over all stored CIDR Blocks and select one that contains this address and has the most extended prefix length.

#[derive(Default)]
pub struct ListRoutingTable {
    cidrs: Vec<Ipv4Cidr>,
}

impl ListRoutingTable {
    pub fn new() -> Self {
        Self { cidrs: Vec::new() }
    }
}

impl RoutingTable for ListRoutingTable {
    fn add_cidr(&mut self, cidr: Ipv4Cidr) {
        self.cidrs.push(cidr);
    }

    fn remove_cidr(&mut self, cidr: Ipv4Cidr) {
        self.cidrs.retain(|cur| cur != &cidr);
    }

    fn find_exact_cidr(&self, addr: Ipv4Addr) -> Option<Ipv4Cidr> {
        self.cidrs.iter().fold(None, |acc, cidr| {
            if cidr.contains(addr) {
                match acc {
                    None => Some(*cidr),
                    Some(other) if other.len() < cidr.len() => Some(*cidr),
                    Some(_) => acc,
                }
            } else {
                acc
            }
        })
    }
}

This implementation takes amortized O(1) for add_cidr, O(n) for remove_cidr and O(n) for find_exact_cidr. This implementation is widespread among libraries. It’s easy to implement to extend and works perfectly fine for small route tables.

Hash Routing Table

We can implement CIDR Routing Table by using a hashmap. It will give us O(1) for add_cidr and remove_cidr, but we still need to iterate over all CIDR Blocks to find the most appropriate one.

But, instead of iterating over all blocks, we can do this:

1. given Ipv4Addr, let’s iterate over all possible prefix lengths from 32 to 0;
2. apply cut_addr, discussed earlier, to the address;
3. generate CIDR Block from this address and prefix length;
4. if CIDR Routing Table contains this CIDR Block, then return it, else continue from step 2

#[derive(Default)]
pub struct HashRoutingTable {
    cidrs: HashSet<Ipv4Cidr>,
}

impl HashRoutingTable {
    pub fn new() -> Self {
        Self {
            cidrs: HashSet::new(),
        }
    }
}

impl RoutingTable for HashRoutingTable {
    fn add_cidr(&mut self, cidr: Ipv4Cidr) {
        self.cidrs.insert(cidr);
    }

    fn remove_cidr(&mut self, cidr: Ipv4Cidr) {
        self.cidrs.remove(&cidr);
    }

    fn find_exact_cidr(&self, addr: Ipv4Addr) -> Option<Ipv4Cidr> {
        for len in (0..=32).rev() {
            let new_addr = cut_addr(addr, len).expect("Len is correct");
            let cidr =
                Ipv4Cidr::new(new_addr, len).expect("Len and Ipv4Addr should always be valid.");

            if self.cidrs.contains(&cidr) {
                return Some(cidr);
            }
        }

        None
    }
}

The advantage of this algorithm is time complexity, which is O(1). That’s a way we have a routing table that works in O(1) for all methods. Of course, you will need to spend O(n) to build a table with n CIDR Blocks, but it’s impossible to do that faster.

Compare and benchmark two approaches

Cargo.toml update

The best way to compare the performance of the two approaches is to benchmark them. In Rust, we can use the criterion crate. Add these lines to your Cargo.toml file:

[dev-dependencies]
criterion = "0.3"
rand = "0.8.4"

[[bench]]
name = "routing_table_bench"
harness = false

Benchmark implementation

Then you need to create a file called routing_table_bench.rs inside the benches folder (note, this folder is neighbor to the src folder, not inside it). First of all, we should create a utility function to generate Ipv4Cidr randomly. We will use the rand crate to generate two numbers: u32 to represent address and u8 in range 0..=32 to represent prefix length. Then we can create Ipv4Cidr with this utility function:

fn generate_cidr(bits: u32, len: u8) -> Ipv4Cidr {
    let mask = get_cidr_mask(len).expect("Len should be smaller than equal to 32");
    let new_bits = bits & mask;
    let addr = Ipv4Addr::from(new_bits);

    Ipv4Cidr::new(addr, len).expect("Input is correct")
}

To implement benchmark add this code below generate_cidr function:

fn bench_routing_table(c: &mut Criterion) {
    let mut rng = rand::thread_rng();
    let mut group = c.benchmark_group("CidrManager");
    let sizes = [10, 100, 1000, 10000, 100000, 1000000];

    for size in sizes {
        let cidrs = repeat_with(|| generate_cidr(rng.gen(), rng.gen_range(0..=32))).take(size);
        let mut hash_routing_table = HashRoutingTable::new();
        let mut list_routing_table = ListRoutingTable::new();

        for cidr in cidrs {
            hash_routing_table.add_cidr(cidr);
            list_routing_table.add_cidr(cidr);
        }

        group.bench_function(BenchmarkId::new("HashCidrManager", size), |b| {
            let mut addresses = repeat_with(|| Ipv4Addr::from(rng.gen::<u32>()));

            b.iter_batched(
                || addresses.next().unwrap(),
                |addr| {
                    hash_routing_table.find_exact_cidr(addr);
                },
                criterion::BatchSize::SmallInput,
            );
        });

        group.bench_function(BenchmarkId::new("ListCidrManager", size), |b| {
            let mut addresses = repeat_with(|| Ipv4Addr::from(rng.gen::<u32>()));

            b.iter_batched(
                || addresses.next().unwrap(),
                |addr| {
                    list_routing_table.find_exact_cidr(addr);
                },
                criterion::BatchSize::SmallInput,
            );
        });
    }

    group.finish();
}

criterion_group!(benches, bench_routing_table);
criterion_main!(benches);

This code does the following:

• Create a random number generator, benchmarking group, and different routing table sizes to test.
• Iterate over different sizes
• Generate size different CIDR Blocks and append them to List and Hash routing tables.
• Benchmark these routing tables by generating random addresses and calling the find_exact_cidr method.

Benchmark results

To benchmark in Rust, we should type cargo bench in the console. It will evaluate our routing tables by running several million tests, doing some maths, and storing results in HTML for further investigation. I received these results on my ryzen 7 5800h (Note, it’s benchmarking only on 1 core. this table can have a much higher throughput if run on several threads).

CidrManager/HashCidrManager/10                                                                            
                        time:   [472.52 ns 473.57 ns 474.74 ns]
                        change: [+0.6508% +1.2357% +1.8285%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 7 outliers among 100 measurements (7.00%)
  6 (6.00%) high mild
  1 (1.00%) high severe
CidrManager/ListCidrManager/10                                                                             
                        time:   [18.294 ns 18.348 ns 18.406 ns]
                        change: [+3.4341% +4.1794% +5.0281%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 7 outliers among 100 measurements (7.00%)
  3 (3.00%) high mild
  4 (4.00%) high severe
CidrManager/HashCidrManager/100                                                                            
                        time:   [449.58 ns 451.30 ns 453.26 ns]
                        change: [-14.021% -13.608% -13.187%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 10 outliers among 100 measurements (10.00%)
  10 (10.00%) high mild
CidrManager/ListCidrManager/100                                                                            
                        time:   [128.38 ns 128.79 ns 129.20 ns]
                        change: [+5.1381% +5.7605% +6.4238%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 6 outliers among 100 measurements (6.00%)
  6 (6.00%) high mild
CidrManager/HashCidrManager/1000                                                                             
                        time:   [567.11 ns 568.42 ns 569.90 ns]
                        change: [+2.5129% +3.0587% +3.6174%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 11 outliers among 100 measurements (11.00%)
  11 (11.00%) high mild
CidrManager/ListCidrManager/1000                                                                             
                        time:   [1.2644 us 1.2680 us 1.2721 us]
                        change: [+1.1998% +1.8870% +2.6534%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 15 outliers among 100 measurements (15.00%)
  9 (9.00%) high mild
  6 (6.00%) high severe
CidrManager/HashCidrManager/10000                                                                            
                        time:   [348.91 ns 350.75 ns 352.68 ns]
                        change: [+0.3763% +1.2080% +2.1543%] (p = 0.01 < 0.05)
                        Change within noise threshold.
Found 4 outliers among 100 measurements (4.00%)
  3 (3.00%) high mild
  1 (1.00%) high severe
CidrManager/ListCidrManager/10000                                                                             
                        time:   [25.319 us 25.379 us 25.442 us]
                        change: [-1.5982% -0.9720% -0.3965%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 9 outliers among 100 measurements (9.00%)
  1 (1.00%) low mild
  3 (3.00%) high mild
  5 (5.00%) high severe
CidrManager/HashCidrManager/100000                                                                            
                        time:   [347.88 ns 351.19 ns 354.72 ns]
Found 9 outliers among 100 measurements (9.00%)
  6 (6.00%) high mild
  3 (3.00%) high severe
CidrManager/ListCidrManager/100000                                                                            
                        time:   [265.57 us 266.80 us 268.05 us]
Found 5 outliers among 100 measurements (5.00%)
  1 (1.00%) low mild
  2 (2.00%) high mild
  2 (2.00%) high severe
CidrManager/HashCidrManager/1000000                                                                             
                        time:   [478.77 ns 490.45 ns 502.73 ns]
                        change: [-7.5643% -1.9065% +3.8173%] (p = 0.53 > 0.05)
                        No change in performance detected.
Found 8 outliers among 100 measurements (8.00%)
  3 (3.00%) high mild
  5 (5.00%) high severe
CidrManager/ListCidrManager/1000000                                                                             
                        time:   [2.5858 ms 2.6177 ms 2.6495 ms]
                        change: [-1.3429% +0.3593% +2.0520%] (p = 0.68 > 0.05)
                        No change in performance detected.
copy

So, finding an address in a routing table with 1 million CIDR Blocks will take an average of 512 ns in HashRoutingTable and 2.65 ms in ListRoutingTable. The difference is enormous!

This chart shows that ListRoutingTable is linearly growing with the number of CIDR Blocks, while HashRoutingTable is constant every time. Below is the same chart, but with logarithmic scaling. You can see that List implementation is faster for tables with lower than 1000 CIDR Blocks, but it’s much slower after that.

Summary

This article built a CIDR Routing Table from scratch and implemented two different approaches: ListRoutingTable and HashRoutingTable. While the former is easy to implement and extend, it’s much slower than the latter one when the number of CIDR Blocks is bigger than 1000.

You can view the final code in my public repo.