BART, The Little Routing Table Package That Became Indispensable (A Success Story)
If a package implements an algorithm known from an academic paper only, what's the probability of reaching widespread use?
In case of
gaissmai/bart, the probability is 1, as it already happened. Numerous users, including some well-known companies, use bart in their projects. But what does bart do?
The package implements a balanced routing table whose design is based on Donald E. Knuth's Allotment Routing Table (ART) algorithm. (The paper linked above describes the ART algorithm in detail. The author isn't Don Knuth; don't let this confuse you. See the Acknowledgements section on page 11, and the addendum at the end of this Spotlight.)
“Balanced routing table”, you might think, “yeah, so what?”
Routers and network hosts use routing tables to store IP routes to particular network destinations. A major challenge of designing routing tables is the need to store large amounts of routes and retrieve them quickly. Charly Gaissmaier (a former
Master Go student, BTW) sat down to write a routing library for his own purposes. The library implements a balanced routing table (hence the package name bart ) that improves upon the original ART algorithm in terms of memory usage.
Charly didn't stop after the first iteration. He continued working on the code to improve lookup performance, memory usage, and update performance, until bart became the best-in-town package for these metrics.
Benchmarks reveal that –
bartis the fastest software algorithm for IP address lookup in routing tables.barthas two orders of magnitude lower memory consumption compared toartand is similar in low memory consumption to (…)cidrtreebut much faster in lookup times.bartis by far the fastest algorithm for inserts and one of the fastest for delete.
(cited from the readme)
Wow. That's not too shabby for a routing table package, is it?
But it gets even better: Although it would seem that few projects need routing tables, the package has accumulated over 260 dependent packages and, including indirect dependencies, over 320 dependent repositories. 🥳
Among bart’s users are well-known companies and popular projects, including Tailscale, Slack, ProjectDiscovery, Clickhouse, Control D, Daytona, and more, enjoying swift and memory-conserving routing table operations.
Fast, memory-efficient, and popular… talk about routing your way to the top!
Addendum: Why Donald Knuth never published the ART algorithm
Charly shared this email excerpt with me, where the author of the aforementioned paper explains how it happened that he, and not Donald Knuth, wrote the paper:
On Fri, Jan 17, 2025 at 4:50 PM Yoichi Hariguchi <[email protected]> wrote:
...
...
Please allow me to tell you a brief history of this algorithm. I came up with a multibit trie based longest prefix match algorithm by myself in 2000. I did not know that George Varghese published a similar algorithm. I later read his paper and found that his paper did not mention route deletion, which my algorithm addresses. Here is the URL of my paper.
https://hariguchi.org/yoichi/smart.pdf
Don and I went to the same Lutheran church (we still go to the same church). So I asked Don to review my paper, saying, "I am afraid that I might waste your time." His answer was, "Yoichi, no worries. I will stop reading it if it is not interesting."
He not only read my paper to the end (of which I am still proud) but also called me in a few days and told me that he came up with another idea for a multibit trie based longest prefix match algorithm, which is ART on my Gihuhub page. He was not interested in publishing papers anymore (unless he was asked to do so). So I wrote a short paper about his algorithm, converted his CWEB code into C, and then extended it to configurable stride length (hence supporting IPv6).
Extra Bonus: The original ART implementation by Donald Knuth, written in CWEB: