[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
LPM(!)

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
entry...)


-David




More information about the Quagga-dev mailing list