Crate ts_bart 

bart

“BAlanced Routing Table”, a path-compressed radix trie optimized for fast IP address and prefix lookup with minimal memory footprint.

Based on the Go implementation of the same name.

Examples

use core::{
    str::FromStr,
    net::IpAddr,
};
use ts_bart::{
    Table,
    RoutingTable,
    RoutingTableExt,
};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mut table = Table::default();

    let route_prefix = "1.0.0.0/8".parse()?;
    let forward_dst = "7.8.9.10".parse::<IpAddr>()?;

    // Insert a route into the table
    table.insert(route_prefix, forward_dst);

    // It can be retrieved with `lookup`
    assert_eq!(Some(&forward_dst), table.lookup("1.0.0.1".parse()?));

    let new_dst = "8.9.10.11".parse()?;

    // Modify the route in-place
    table.modify(route_prefix, |entry| {
        let entry = entry.unwrap();
        *entry = new_dst;

        ts_bart::RouteModification::Noop // do not remove or insert a new route
    });
    assert_eq!(Some(&new_dst), table.lookup("1.2.3.4".parse()?));

    // More-specific routes are preferred in lookups
    let child_prefix = "1.1.0.0/16".parse()?;
    let child_dst = "32.32.32.32".parse()?;
    table.insert(child_prefix, child_dst);

    assert_eq!(Some(&child_dst), table.lookup("1.1.3.4".parse()?));

    // Remove the route
    let removed_value = table.remove(route_prefix);
    assert_eq!(Some(new_dst), removed_value);
    assert_eq!(None, table.lookup("1.8.7.254".parse()?));

    Ok(())
}

Performance

You can run the benchmarks with:

$ cargo bench

Current performance figures put us in the same ballpark as go-bart.

Memory utilization

Amortized memory utilization for a large route table is about 24 bytes/route for IPv4 routes and 40 bytes/route for IPv6 routes – this is just the prefix storage, the actual memory size will vary with the stored value type. This is slightly worse than go-bart, which on my machine reports 20 bytes/rt for combined IPv4/IPv6, 37 bytes/rt for IPv6, and confusingly 101 bytes/rt for IPv4-only.

If using the table as a RIB (IpAddr table values), this comes out to ~48 bytes/rt for IPv4 and ~75 bytes/rt for IPv6.

Implementation status

The current implementation should be usable as a routing table, though it hasn’t been tested in anger yet. Some of the more involved functionality provided by bart is lacking, however:

• Table inspection (sorted prefix walk primarily, we do provide a DFS node iterator)
• Table merging and intersection
• Optional persistent data structure functionality (shallow clone on mutate)
• Subnet/supernet queries

Modules

iptrie

Operations for multi-level tries of IP-addressed nodes.

table

Facilities for complete routing tables.

Structs

BaseIndex

A “base index” as described in Hariguchi’s ART paper; a linearized address for a prefix/octet tuple when considering the hierarchy of possible prefixes for a given 8-bit address.

Node

A trie node logically covering a single (octet) address stride.

Stats

Stats about a node and its descendants.

Enums

BoxStorage

Storage that stores values in boxes.

Child

Entries in a node’s children array.

InlineStorage

Storage that stores values inline.

RouteModification

A set of actions that can be taken as part of a call to modify.

Constants

LUT_MEMORY

Total memory usage of all lookup tables in the crate.

Traits

PrefixOps

Trie node operations for accessing and mutating prefixes.

PrefixOpsExt

Extension methods relating to prefixes.

PrefixReadOps

Read-only operations on prefixes stored in nodes.

RoutingTable

Abstracts routing table operations.

RoutingTableExt

Automatic extension methods for implementors of RoutingTable.

Storage

Generic data storage mechanism.

StrideBase

Base trait for stride operations.

StrideOps

Single-stride operations supported by a trie node.

StrideOpsExt

Extension methods for nodes implementing StrideOps.

Functions

allot_fringe

The returned bitset contains all /8 fringe indices covered by the prefix at index. This is essentially the 9th-bit extension of prefix, where we’re using a priori knowledge to select the meaning of BaseIndex: a “fringe” index is actually the index value plus 256 in terms of Knuth’s encoding.

allot_prefix

Returns the bitsets for base indices 1..255 (prefixes up to /7). For each index, the returned bitset contains all descendant (strictly more-specific) indices in that are covered by the prefix indicated by index.

lpm

Retrieve the bitset that can be used to calculate the longest prefix match for the given index in one shot.

Type Aliases

DefaultNode

Type alias for Node with DefaultStorage. Provided to improve inference by concretizing the storage type.

DefaultStorage

Type alias defining the default child storage type.

SimpleTable

Table for single-IP-stack environments.

Table

General-purpose table type.