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

From: Michael Bellion and Thomas Heinz (
Date: Tue Aug 12 2003 - 10:46:21 EST

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 ...".


| Michael Bellion | Thomas Heinz |
| <mbellion@xxxxxxxxx> | <creatix@xxxxxxxxx> |
| High Performance Packet Classification |
| nf-hipac: |

Attachment: pgp00023.pgp
Description: PGP signature