Michael Bellion and Thomas Heinz wrote: > >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. I don't know what you mean by "PCP", so can't answer the question. > Maybe you should describe in little more detail what you mean > by "This generalises to multiple dimensions ...". I mean that the lookup algorithm works for multi-dimensional searches. Creating the search tree can be a little more involved, and I am not sure how much (if any) node duplication is needed when some kinds of rule priorities are used. It may help to say that you don't have to do binary search for each dimension separately, although that is a possible strategy for prefix matching. You can build a tree where each node represents a point (a,b,c...) in prefix-length space, and whose children are other points in that space, if you choose to see the general problem as matching multiple prefixes. At one extreme, a general bit matcher (i.e. no non-power-of-2 numerical ranges) can be treated as a multi-dimensional prefix match where each prefix is length 0 or 1. You see that, if the input rule set is _equivalent_ to a longest-prefix single-dimensional rule set, the optimal multi-dimensional search tree is trivally found and it does not do binary search on each dimension separately. -- Jamie - : send the line "unsubscribe linux-net" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
