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@hipac.org> | <creatix@hipac.org> | +-----------------------+----------------------+ | High Performance Packet Classification | | nf-hipac: http://www.hipac.org/ | +----------------------------------------------+
Attachment:
pgp00082.pgp
Description: PGP signature
