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.

RouteDb

An Routing Information Base (RIB) as a Database. 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 a configurable compound secondary key, that can hold a route Distuingisher, a Path ID (for the ADD_PATH capability) and more.

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.

This crate is the successor of rotonda-store, which was a more narrowly defined in-memory RIB.

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