# Re: a question on SPP draft ...

Greg,

>   I realize this, but this would seem to be less efficient than checking
>   against an ordered list.  Or am I mistaken?
>
>   Eg. the correlated, ordered list:
>       1. 10.0.0.0/8 -> 10.0.0.0/8
>       2. 0.0.0.0/0   (catch all)
>
>   turns into the decorrelated
>       1. 10.0.0.0/8 -> 10.0.0.0/8
>       2. 0.0.0.0-9.255.255.255 OR 11.0.0.0-255.255.255.255
>
> For a list of size two, you are arguably correct, but the CPU time for
> such a small list is unlikely to matter.  For an ordered list with n
> entries, the search time is \theta(n).  With a decorrelated SPD, one
> can use tree search algorithms, which should operate in log time.
> Note that a given ordered SPD may result in more decorrelated entries
> (2 to 3, above), so this broad linear-vs-log claim is somehat unfair
> and I don't claim to have fully substantiated the point I'm making.

You are right, the decorrelated representation does have several
advantages, and I think it is a valuable concept in many ways.

> That said, if one has hardware that searches ordered SPDs efficiently,
> it might be useful to have a "recorrelation" algorithm.  The
> decorrelated example above has many possible recorrelated examples,
> including the original, but also (dropping the RHS):
[snip]

This is actually the point I am more concerned about.  For IPsec without
IKE, the fact that there are several recorrelated ordered policies is
not a problem.  However, with IKE in the picture things get more
complicated,
since IKE also negotiates traffic selectors, and does not only compare the
selectors of a single packet.

For instance, an offer for protecting 0.0.0.0/0 using a tunnel mode
is accepted by the ordered policy (supposing the action is to use
tunnel mode, etc).  For the decorrelated (and differently recorrelated)
examples this is not so simple.  How should this work?

-Sami