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

[Michael Bellion and Thomas Heinz <nf@hipac.org>]

[-- Attachment #1: Type: text/plain, Size: 1446 bytes --]

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@hipac.org>  |  <creatix@hipac.org> |
+-----------------------+----------------------+
|    High Performance Packet Classification    |
|       nf-hipac: http://www.hipac.org/        |
+----------------------------------------------+

[-- Attachment #2: Type: application/pgp-signature, Size: 251 bytes --]