Also see “poptrie” [0] for an efficient way to do routing table-style lookups for CIDRs (longest prefix match). They basically use the “popcnt trick” to implement sparse arrays, use “direct indexing” for the first however many bits to reduce the number of indirections, and have a cool optimization specific to longest prefix match (“hole punching” in the paper).
I ended up using the same basic layout for the database behind a little IP lookup tool I wrote to make lookups somewhat responsive from JavaScript [1]. It ends up working out pretty well.
My internship project involved a tool to look up individual IP addresses as well as checking a range of address blocks. I ended up implementing the trie data structure, which performed well in terms of storage and run-time efficiency.
My initial approach was to store IP addresses into a hashmap but if the average query was to check address blocks like /24, then it'd turn out to be very poor data structure to search through.
I've never really groked tries, so bad for me. But I've built a few IP lookup tables.
For one, I only needed to know a true/false given an ipv4 address (does geolocation of the ip indicate within a specific set of countries), and the lookup needed to be fast and easy.
If you look at every address, a simple boolean array will be too big, 2^29 bytes with 2^3 values per byte covers the address space, but half a gig of memory is too much. Otoh, geolocation by country is unlikely to be more specific than a /24, 2^21 bytes with 2^3 values per byte is only 2 meg of memory devoted to a very fast lookup; less in actual use if you mmap without large pages, because parts of the range will never page in.
That approach isn't great if your value is larger than a boolean or you need ipv6 (you can use /48s as your maximum prefix length, but there's quite a lot of /48s).
If you want a compact table, you can store an ordered set of (low ip, value), and access the table by finding the nearest value equal or less than the observed ip. I used Erlang's ets with ordered set and the ets:prev(Table, IP + 1) which uses a binary tree under the hood, but anything that can handle 128 bit integer should work.
Building the table is a bit of work, because you've got to take inputs of like X.Y.0.0/16 -> A and then X.Y.6.0/24 -> B and turn that into X.Y.0.0 -> A, X.Y.6.0 -> B, X.Y.7.0 -> A ... but all that transformation happens offline.
I think you're more likely to have a language built in for a binary tree than a trie, but some languages have neither.
I heard all those names. In IOS (upper case’i’) the v4 s/w forwarding plane talked about tries. The v6 code was sprinkled with radix. Variable tree stride for different address mapping characteristics was my favourite. I was, and still am, lucky enough to work with the guy who wrote much of that code.
7 comments
[ 3.1 ms ] story [ 33.1 ms ] thread[0]: https://dl.acm.org/doi/10.1145/2829988.2787474
[1] https://cloud-ips.s3-us-west-2.amazonaws.com/index.html
My initial approach was to store IP addresses into a hashmap but if the average query was to check address blocks like /24, then it'd turn out to be very poor data structure to search through.
For one, I only needed to know a true/false given an ipv4 address (does geolocation of the ip indicate within a specific set of countries), and the lookup needed to be fast and easy.
If you look at every address, a simple boolean array will be too big, 2^29 bytes with 2^3 values per byte covers the address space, but half a gig of memory is too much. Otoh, geolocation by country is unlikely to be more specific than a /24, 2^21 bytes with 2^3 values per byte is only 2 meg of memory devoted to a very fast lookup; less in actual use if you mmap without large pages, because parts of the range will never page in.
That approach isn't great if your value is larger than a boolean or you need ipv6 (you can use /48s as your maximum prefix length, but there's quite a lot of /48s).
If you want a compact table, you can store an ordered set of (low ip, value), and access the table by finding the nearest value equal or less than the observed ip. I used Erlang's ets with ordered set and the ets:prev(Table, IP + 1) which uses a binary tree under the hood, but anything that can handle 128 bit integer should work.
Building the table is a bit of work, because you've got to take inputs of like X.Y.0.0/16 -> A and then X.Y.6.0/24 -> B and turn that into X.Y.0.0 -> A, X.Y.6.0 -> B, X.Y.7.0 -> A ... but all that transformation happens offline.
I think you're more likely to have a language built in for a binary tree than a trie, but some languages have neither.
* trie is the basic data structure, in which each node is a vector as wide as the alphabet, and the depth is equal to the length of the keys
* a radix tree is an optimized trie, with path compression and node compression
* a patricia tree is a binary radix tree