Hi David
You wrote:
The ipv4 FIB hash tables tackle exactly this problem. The resulting
worse cast complexity is O(n_bits_in_prefix_mask).
The problem you've described is exactly the same as trying to use
hashing for routing tables.
Yes, that's true for the 1-dimensional case. You refer to the
following algorithm, don't you?
min_prio := infinity
match_rule := nil
for all list_entries e: { // at most w+1 entries where w is the bit
// width of the keys
rule = lookup(hash(e), packet) // let's assume O(1) here
if (prio(rule) < min_prio) {
min_prio = prio(rule)
match_rule = rule
}
}
return match_rule
This algorithm has running time O(w).
[In fact it's O(number of different prefix lengths) which is O(w)
in the worst case.]
But what about the d-dimensional case? If you extend this
approach to handle rules with d prefix based matches you end
up in a running time of: O(w^d)
(assuming w to be the max. bit width)
This is definitely not desirable.
Regards,
+-----------------------+----------------------+
| Michael Bellion | Thomas Heinz |
| <mbellion@xxxxxxxxx> | <creatix@xxxxxxxxx> |
+-----------------------+----------------------+
| High Performance Packet Classification |
| nf-hipac: http://www.hipac.org/ |
+----------------------------------------------+
pgp2IcR9poTKn.pgp
Description: PGP signature
|