I've seen a number of messages recently about the generation of
encapsulation boundaries. All the algorithms I've seen described
suffer from at least one (usually two or more) of the following
problems:
o non-bounded time to generate a correct boundary
o only probabilistic correctness (of whatever degree)
o complexity of generation
o ugliness when viewed with older UA
My acceptance of this proposal for encapsulation boundaries was
contingent on the existance of a simple, time-bounded, guaranteed
correct algorithm for generating them. As I recall the moment in St.
Louis when this happened, it only took me a few seconds to come up
with such an algorithm and so I assumed that others would, too. Since
I'm pretty sure my algorithm is "better" (in some sense) than any
presented publicly, let me state that algorithm here, so that people
can discuss whether it does, in fact, have the right properties. I
would also like to encourage (in the light of some recent general IETF
discussion on including rationale in RFCs) a sample algorithm be
included in the RFC. Anyway, here's the algorithm...
Encapsulation boundaries are of a form that contains at one point a
single number of arbitrary precision. The details are not important,
but as an example let me offer "Message separator (ID nnnn)" as one
possibility. Remember, the exact form can be different for different
systems generating these. The way you generate a specific separator
is with a single scan of the parts looking for any lines that look
like separators with this text and remembering the largest number that
appears. You then add one to that number and use it as the seperator
for the combined multipart message, this can't possibly exist in any
of the constituent parts, you have guaranteed correctness. A simple
implementation of this takes O(n) time, you can do better with
application of Boyer-Moore searching. The message separators are
pretty clear, even if you have an old UA that doesn't help you, in
most cases the "ID" is just a small integer which counts the amount of
nesting.
-Mike Patton
P.S. Let me state for the record (and any eavesdropping lawyers
:-) that this algorithm is my own work and not subject to any
restrictions known to me. It is derived independently from any
specific prior work. I hereby renounce any proprietary claims and
release it to the public domain.