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

[Michael Bellion and Thomas Heinz <nf@xxxxxxxxx>]

Hi Jamie

You wrote:
> You can do it in O(log(n_bits_in_prefix_mask)).
>
> This is achieved using binary search on the prefix lengths which
> appear in the table.  (So if only a few prefix lengths are used, the
> tree is small).
>
> [example snipped]

That's true for the one dimensional PCP (with prefix rules) if
the following condition holds:
for all rules r1, r2: (prefix(r1) > prefix(r2)) &&
                      (r1 & prefix(r2) == r2 & prefix(r2))
                   => prio(r1) < prio(r2)
                      [smallest prio wins]

It's quite reasonable to assume that this condition holds
for the one dimensional case since there would be never
matching rules otherwise.

> This generalises to multiple dimensions e.g. for doing multiple
> prefixes on source+target + different combinations of other bits such
> as protocol, TOS etc. - i.e. arbitrary bit-subset classifiers.  The
> basic principle and the algorithm are the same.

Hm, how do you want to solve the d-dimensional PCP by
doing binary search for each dimension? Remember that
PCP is not related to longest prefix matching. Instead
priorities are used.

Maybe you should describe in little more detail what you mean
by "This generalises to multiple dimensions ...".


Regards,

+-----------------------+----------------------+
|   Michael Bellion     |     Thomas Heinz     |
| <mbellion@xxxxxxxxx>  |  <creatix@xxxxxxxxx> |
+-----------------------+----------------------+
|    High Performance Packet Classification    |
|       nf-hipac: http://www.hipac.org/        |
+----------------------------------------------+

pgpZ4bV2iKDfw.pgp
Description: PGP signature