LPM (forwarding table) interface and underlying implemenation

[zeeshanlakhani]

Background

We want Capsule to offer a nice shim/API layer and implementation for LPM-based (Longest prefix match) forwarding table search, especially around setup, insertion, deletion, and lookups¹.

The LPM interface revolves around a key-value pair lookup where we give an IPv4/IPv6 address as a key, which gets matched to cidr essentially (e.g. (prefix, length)), and returns a corresponding value. The algorithm/implementation is mostly used in routing applications where the value represents the next-hop. An LPM table contains one or more rules, where each rule is a pair of an IP with prefix and a value. If the input key IP matches with more than one rules then the rule with the highest prefix will be used to determine the required value.

An LPM structure is usually designed around a Trie data structure. DPDK, for example, exposes an LPM library, including a separate LPM6 one for IPv6 addresses, with an implementation using a variation of the DIR-24-8 algorithm, trading-off memory usage for improved LPM lookup speed. Of note, for the IPv4 library for example, the documentation goes into depth on how the algorithm allows for the lookup operation to be performed with typically a single memory read access. In the statistically rare case when the best match rule is having a depth bigger than 24, the lookup operation requires two memory read accesses. So, the performance of the LPM lookup operation is greatly influenced by whether the specific memory location is present in the processor cache or not. The IPv6 library/version of the data structure is more complicated, working across 14 levels instead of IPv4's 2. We, of course, would have to handle both kinds, IPv4 & IPv6, of structures.

Describe alternatives you've considered?

There are many, many approaches to handling IP lookup, and LPM particularly². DPDK's libraries are well-optimized and used, but definitely have a memory tradeoff. Calculation of the size of an IPV4 LPM table, for example, equates to Size of LPM structure + Size of array of 8-bit table + Size of Rule table.

Another LPM approach that's gained a ton of steam is that of a Poptrie, a data structure that it is sufficiently general to work on prefixes of arbitrary lengths³ and leverages the population count instruction on bit-vector indices for the descendant nodes to compress the data structure within the CPU cache. A Poptrie IP lookup table attempts to reduce the memory footprint of the data structure by way of laying out descendant internal and leaf nodes in a contiguous array, where the indirect index of smaller size is achieved. I have not found a memory footprint comparison between the Poptrie reference implementation and DPDK's libraries (DPDK's LPM6 is newish as well). The Poptrie paper purports better performance than another interesting alternative, the Tree Bitmap⁴.

Another interesting option is using something like a Length Aware Cuckoo Filter for IP lookup, which implemented is more like LACF + LPM trie (in the paper). Though probabilistic in nature, i.e. can contain false positives, the research and possible? performance benefits (e.g. for VPP) are intriguing; and, it handles dynamic deletion of entries.

Possible Solution

After discussion w/ @capsule-rs/maintainers and @capsule-rs/collaborators, the best route would be to offer a nice, somewhat tunable, easy-to-use API/shim module over DPDK's lpm libraries. With a good shim, hopefully, we could easily replace the DPDK library at some other point for something like a Poptrie or offer the consumer/user a choice based on the possible tradeoffs.

Footnoes

¹ libmoon has the spirit of an API layer, just as an example.

² Snabb has various implementations for example.

³ Helpful implementations in C (for reference) and Lua, along with a good blog post on implementing a Poptrie lookup table for Snabb.

⁴ Here's an example of a Rust Tree Bitmap implementation of a IPv4/IPv6 lookup table.