[quagga-dev 12156] Re: [PATCH 3/4] lib: use trie structure for prefix list matching

David Lamparter david at opensourcerouting.org
Sun Apr 19 13:26:20 BST 2015

On Sun, Apr 19, 2015 at 12:26:40PM +0200, David Lamparter wrote:
> I've put some thought into adapting something similar for lib/table.c;
> however I haven't come to a satisfying idea yet.

And I forgot the most important counterargument:  route_table is
actually not even used that much for LPM matches.  There are 27 calls to
(bgp|route)_node_match(|_ipv4|_ipv6) throughout the code, while we have
a whopping 177 to (bgp|route)_node_(get|lookup)!  And the latter is in
fact what I'm starting to see in profiling results - exact match, not

As such, for route_table, we could possibly be better of adding a hash
to speed up exact-match lookups.

Prefix list application, on the other hand, is always LPM (even though
in many cases the prefix to be matched might be equal to the prefix list


More information about the Quagga-dev mailing list