**Next message:**jamal: "Re: [RFC] High Performance Packet Classifiction for tc framework"**Previous message:**Michael Bellion and Thomas Heinz: "Re: [RFC] High Performance Packet Classifiction for tc framework"**In reply to:**Jamie Lokier: "Re: [RFC] High Performance Packet Classifiction for tc framework"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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/ |

+----------------------------------------------+

**Attachment:
pgp00023.pgp**

**Next message:**jamal: "Re: [RFC] High Performance Packet Classifiction for tc framework"**Previous message:**Michael Bellion and Thomas Heinz: "Re: [RFC] High Performance Packet Classifiction for tc framework"**In reply to:**Jamie Lokier: "Re: [RFC] High Performance Packet Classifiction for tc framework"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]