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
|