kohler/click — pull request #43 by mvenk (2012-02-25 01:10:31+00:00)
Title: Cache-aware RadixIPLookup.

Contains three changes to RadixIPLookup which contribute to better
performance (0.87x original lookup time):

1] Removed derviable fields from the Radix class:
_n, _nchildren and _bitshift have been removed from the Radix
class. _n and _bitshift are now stored in an array indexed by the
level of the radix node. _nchildren was read only in free_radix()
to check for existing children. This check has been removed, since
it is possible to safely free existing children by checking if
r->children[i].child is not NULL.

2] Changed branching factor to (16, 4, 4, 4, 4) from (8, 4, 4, 4,
4, 4, 4). There are 2^16 nodes in level zero followed by 2^4 nodes
in all subsequent levels.

3] Added a compressed vector (_lookup) for route lookups. _lookup
holds unique combinations of (gateway, port) pairs. When a route is
added to the vector, it is added to _v unconditionally. The route is
added to _lookup only if its (gateway, port) does not already exist
in _lookup. The higher order 8 bits of the key index into _lookup,
the remaining 24 bits index into _v. _lookup is limited to 256
entries and _v to 16777216.

Tested for correctness using tests in test/ip.
Benchmarked against the original RadixIPLookup, DirectIPLookup, RangeIPLookup
as well as variants of RadixIPLookup.
Benchmarks are available in the perf direcotry of mvenk/click cache_aware_radixtree.

This is joint work with Rohit Krishna Kumar,
under the supervision of Eddie Kohler.