Scaling Akvorado BMP RIB with sharding

To associate routing information—like AS paths or BGP communities—to flows, Akvorado can import routes through the BGP Monitoring Protocol (BMP). As the Internet routing table contains more than 1 million routes, Akvorado needs to scale to tens of millions of routes.1 This has been a long-standing challenge,2 but I expect this issue is now fixed by using RIB sharding, a method that splits the routing database into several parts to enable concurrent updates. Previous implementation Storing routes in a map Interning routes Why does it not scale? RIB sharding First step: basic sharding Second step: lock-free reads Previous implementation Akvorado connects 2 elements to build its RIB: a prefix tree, and a list of routes attached to each prefix. Akvorado BMP RIB implementation without sharding. One single read/write lock. In the diagram above, the RIB stores five IPv4 prefixes and two IPv6 prefixes. One of them, 2001:db8:1::/48, contains three routes: from peer 3, next hop 2001:db8::3:1,…