A library that provides abstractions for a BGP Routing Information Base (RIB) for different AFI/SAFI types, as a database.

The data structures provided by this crate can be used to store and query routes (and route-like data) in memory and on-disk, for both current and historical data.

The main data structures that this crate implements are firstly a tree bitmap, largely as described in this paper^1 - but with a twist. There's also a blog post^2 about the tree bitmap, and similar data structures. Secondly, this repo implements a concurrent chained hash table (called cht throughout this repo), geared towards keys that are "prefix-like", i.e. variable-length bitfields, that fit within a primitive integer type.

The log-structured merge tree ("lsm_tree") used in this library is provided by the lsm_tree crate - the crate that powers fjall.

rotonda-store

An In-Memory Routing Information Base (RIB) for IPv4 and IPv6 Prefixes. Part of the Rotonda modular BGP engine.

Although this store is geared towards storing routing information, it can store any type of metadata for a prefix.

It features as secondary key a u32 value, which can be used to store multiple values for one prefix, e.g. representing different peers, or add_path routes.

The built-in tree-bitmap[^1] allows for fast querying of IP prefixes and their more- and less-specific prefixes.

This crate provides a data-structure intended for single-threaded use, and a data-structure for multi-threaded use.

[^1]: Read more about the data-structure in this blog post.