Re: [RFC] High Performance Packet Classifiction for tc framework

Ralph Doncaster wrote:

However if you have 32 tables (one for each prefix length) I can't see any
possible way of avoiding a search in each table for the worst case.  So if
my packet is destined to 217.109.118.70 you need to start looking for a
match for a /32 route, and if not found continue checking each prefix size
until you've reached /0.

You would start by search for a 217.109.0.0/16 entry.  That's
the root in the search tree.

That would match, and the matching tree node would tell you to search
a specific table for 217.109.118.0/24.  (Actually, just
0.0.118.0/0.0.255.0, because this node can assume the first 16 bits).

That would match, and the matching tree node tells you to search a
specific table for 217.109.118.64/28 (0.0.0.64/0.0.0.240).

That would match, and the matching tree node tells you to search a
specific table for 217.109.118.68/32 (0.0.0.6/0.0.0.15).

That would match, and is your result.

Without the optimisation you said you understand, there would be a few
more steps, narrowing to /30, /31 then /32, but for such small hashes,
not only is it faster, it also uses less memory to just use a single
4-bit table lookup than to have a tree of tiny hash tables.

-- Jamie