Subject: Re: [manet] Regarding packetbb constraints on ordering and uniqueness.

From: Thomas Clausen <[email-masked]>
Date: Wed, 7 Nov 2007 15:43:43 +0100

On 2Nov , 2007, at 2:55 PM, Russ White wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
>> Perhaps, in my mind, the most amazing thing about
>> this discussion is just that it is so unnecessary.  The
>> type ordering and specific algorithms for sorting really
>> need to be on a per-protocol basis.  That would solve the
>> whole problem in my mind, and the only issue raised
>> against that has to do with an internal parser optimization
>> that is wholly outside the realm of typical protocol
>> discussions.
>
> Agreed--putting in the packet ordering as something all protocols  
> using
> packetbb MUST use is unnecessary--it should be an optional, per
> protocol/user thing.

As has been indicated in (several) previous postings by myself and  
others, this won't work in that it will give all of the  
inconveniences and none of the benefits, considering that the MANET  
wg is designing multiple protocols sharing the same format. I'll not  
rehash the arguments yet again, but refer to previous postings by  
Chris and myself on this subject.

Thomas

-- 
Thomas Clausen
[email-masked]
http://www.thomasclausen.org/
http://hipercom.thomasclausen.org/

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 07 Nov 2007 08:22:01 -0800

Hello Thomas,

You wrote:
>>
>> Agreed--putting in the packet ordering as something all protocols using
> others, this won't work in that it will give all of the inconveniences 
> and none of the benefits, considering that the MANET wg is designing 
> multiple protocols sharing the same format. I'll not rehash the 
> arguments yet again, but refer to previous postings by Chris and 
> myself on this subject.
>

I have read through every single mailing list message
on this matter.  Even though you have made this
claim before, I don't find any real substantiation for
it.  And the counterclaim is much more compelling.

To rehash (as you say) the matter, the argument for
mandating the ordering is that it is claimed to be useful
for some protocols, for the purpose of enabling some
sort of abbreviated parsing on the receiving side.
But I question even whether this is valuable, especially
since the sending side then must do some unneeded
work.

There are several compelling arguments against this
mandate.
1. Not all protocols need it (if, indeed, any at all do)
2. Such ordering isn't mandated by any other IETF protocols.
3. By the time the packet has been captured, the
    major portion of the cost has been expended and the
    additional parsing cost is negligible in the extreme.
And these are just the ones I remember right off the
top of my head.  For a full recapitulation ("rehash"),
please ask and I will do the seemingly thankless task
of rehashing the rehashed arguments from months ago.
None of these three points has ever been rebutted.

Plus we have had several examples of good designs
that would be prohibited by these restrictions.

I urge you to reconsider.

Regards,
Charlie P.

---

From: Thomas Clausen <[email-masked]>
Date: Wed, 7 Nov 2007 18:07:20 +0100

Hello Charlie,

Hope all is well in your neck of the woods?

On 7Nov , 2007, at 5:22 PM, Charles E. Perkins wrote:

>> inconveniences and none of the benefits, considering that the  
>> MANET wg is designing multiple protocols sharing the same format.  
>> I'll not rehash the arguments yet again, but refer to previous  
>> postings by Chris and myself on this subject.
>>
>
> claim before,

It is not a claim. Chris has shown in his argumentation the clear  
benefits in terms of processing overhead. Chris, I and others have  
pointed out other benefits in detail.

> I don't find any real substantiation for

No, I disagree strongly.

> for some protocols,

No, you've got it wrong here. It has nothing to do with protocols and  
everything to do with efficiently encoding, transmitting and  
(uniquely and efficiently) parsing some information. The I-D in  
question does not specify how information is generated nor  
processed.....THAT is what the protocols shall do, and that is what  
they are free to do in whichever order is appropriate.

> for the purpose of enabling some

....that is one of the benefits, yes, although I believe that  
striving for (and, indeed, in the specification as it is, achieving)  
linear parsing by a receiving node can not be said to be a bad goal,  
can it? As you will have seen in previous emails, there are other  
benefits beyond this.

> since the sending side then must do some unneeded

If I have the choice, I'd rather have the sending node do some extra  
work, if that means that the recipient is able to do something more  
efficient. I'd argue that there are benefits in that, since I suspect  
that most nodes will receive more incoming messages than the generate  
themselves. E.g. in a classic link-state protocol, each node will for  
each message it generates, receive (ignoring duplicate, which makes  
it even more compelling) n messages in a n+1 nodes large network.  So  
optimising the message content for the receiver seems sensible.

So I would argue that this is, indeed, very valuable and that the  
sending side does very much needed work that has an overall benefit  
for the network.

> 1. Not all protocols need it (if, indeed, any at all do)

Again, it has nothing to do with protocols and everything to do with  
efficiently and uniquely encoding, transmitting and parsing  
information....parsing happening before the encoded and transmitted  
information is handed off to the protocol.

> 2. Such ordering isn't mandated by any other IETF protocols.

I don't think that's a valid argument here: the reason may be that in  
packetbb, there's the two-dimensional (in lack of better terms)  
aspect of address-block TLVs which is slightly different from other  
TLV-based protocols out there (and, I add, is different for the  
purpose of efficient encoding....) -- which necessitates this  
treatment to be efficient.

>    additional parsing cost is negligible in the extreme.

That's an one-sided assertion. You do have a specific environment in  
mind where this may be true. I have a different environment in mind  
where this cost is not negligible at all. I shall add that the  
constraints were something that I had to be "talked into" initially  
from people actually building/running OLSRv2, and for whom the costs  
were everything but negligible.

I could add something about the fact that eliminating the per-message- 
processing-overhead for the receiver has some benefits wrt. DoS also,  
but I think it suffice to say that I fail to see the argument for  
making something more costly, when we know how to make it less costly.

As an academic, I'll just stick to my send-1-message-process-n- 
messages example from above as an argument in favour of reducing per- 
message-processing-overhead, since I believe that it illustrates a  
point quite nicely.

> None of these three points has ever been rebutted.

As far as I am concerned, these points have all been addressed and  
the benefit of retaining the constraint on uniqueness and ordering  
remain clear. I'd take it that you do not dispute the brief example  
given previously in this email.

> that would be prohibited by these restrictions.

I disagree. I'll first say that the design examples presented have  
been hypothetical. Second, the designs examples could equally well be  
accomplished with the current design of packetbb. So, as such, I do  
not see that anything has been prohibited.

> I urge you to reconsider.

As I see it, there are a great number of benefits to retaining the  
current design of packetbb as it is (and these benefits have been  
enumerated elsewhere), and I have seen no compelling benefits  
presented of altering the design. In particularly not since the  
alterations proposed incur large penalties in terms of parsing  
ambiguity and parsing overhead at the receiver.

Hence, while I continue to reconsider my position and technical  
opinion on any matter I am involved in, I do not believe that the  
constraints on ordering and uniqueness for TLVs in packetbb should be  
altered since the benefits of doing so are questionable, while the  
drawbacks considerable. As has been previously pointed out in emails  
from myself and others.

Cheers,

Thomas

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 07 Nov 2007 10:25:35 -0800

Hello Thomas,

I'll try to answer your comments here.

> pointed out other benefits in detail.

 I strongly disagree that Chris has shown this.
If you will (perhaps in private email) direct me
to his strongest argument, I will take another
look.  Right now, I only remember what seemed
to me very vague and unsubstantiated assertions
about the way someone's current parser had been
written.
> everything to do with efficiently encoding, transmitting and (uniquely 
> and efficiently) parsing some information. The I-D in question does 
> not specify how information is generated nor processed.....THAT is 
> what the protocols shall do, and that is what they are free to do in 
> whichever order is appropriate.

 Yes, you are right that I was thinking about the protocols.
So since this mandate has nothing to do with protocols,
I very strongly believe it should be omitted from the protocol
specification.  But wait!  packetbb is not a protocol specification.
No, it is a meta-protocol specification.  Thus, the parsing-related
mandate is _TWO_ steps removed from appropriateness for
inclusion in this document.
> ....that is one of the benefits, yes, although I believe that striving 
> for (and, indeed, in the specification as it is, achieving) linear 
> parsing by a receiving node can not be said to be a bad goal, can it? 
> As you will have seen in previous emails, there are other benefits 
> beyond this.
 I am thinking about the quick-abort feature...  which I have
argued is at least questionable if not downright anti-IETF in
flavor.
> efficient.
This is, then, according to your personal taste.  However, it does
not stand up to logical scrutiny.

Here is another formulation to expose what I claim is the fallacy.

1. The receiver wants to make sure of some uniqueness (we don't
        know why, no general argument was given, only that the
        authors favor the variable-assignment paradigm).
2. Thus, the sender has to work harder to insure that the receiver
       can make this check.

First, I point out that a protocol could RECOMMEND that
the sender implement the ordering.  Second, absolutely no
malicious behavior is prevented by this mandate.

Thus, there are absolutely no efficiency gains evident so far.

> I'd argue that there are benefits in that, since I suspect that most 
> nodes will receive more incoming messages than the generate 
> each message it generates, receive (ignoring duplicate, which makes it 
> even more compelling) n messages in a n+1 nodes large network.  So 
It's even better to avoid making the check entirely.  And I don't see
any downside to the more generous behavior, except for possibly
adding another sentence of text to whatever protocol specification
seems to have a need for this exclusivity and sorting.
> sending side does very much needed work that has an overall benefit 

First, let's hope that most networks are not dominated by the
kind of one-to-many flooding that seems to be motivating this
specification.  Second, you _could_ make it for the particular
protocol.  Third, as pointed out above, the gain in efficiency
is really illusory.  I think it is really just a gain in mental satisfaction
that some packet universe might somehow be more organized.
> information is handed off to the protocol.

Again, if it has nothing to do with protocols, then it just does
not belong in the specification.  And, the unique encoding
is _only_ of interest to fit Justin's model of TLVs as a sort
of variable assignment mechanism.  TLVs do not have to
fit that restrictive model.
> packetbb, there's the two-dimensional (in lack of better terms) aspect 
> of address-block TLVs which is slightly different from other TLV-based 
> protocols out there (and, I add, is different for the purpose of 
> efficient encoding....) -- which necessitates this treatment to be 
> efficient.

Sorry, Thomas, this makes very little sense to me.  The
variable-assignment model is just not right for many cases.
And I cannot yet identify the coordinate axes that would
enable me to define some two-dimensional understanding
of what you're talking about.  Perhaps you meant that
the TLV ordering structure is an array of intervals.
Then one axis would be <contiguous subsets of address ranges>
[dimensionality on the order of 0.5*(address range^2)].
What would the other axis be?  The scalar value for the
value to be assigned?

Anyway this is a very poor basis for discussing any sort
of ordering mandate...
> That's an one-sided assertion.
 I think it is quite easy to see in practice.  Calculate the energy
expenditure from the radio interface, and compare it to the
expenditure from reading a string into memory.  Calculate the
time spent from the bandwidth delay and compare it to the
CPU time expenditure by a processing unit made in the last
50 years.  You can get a lot of martinis from me if you find
that the processing side is anywhere near similar.
> You do have a specific environment in mind where this may be true. I 
> have a different environment in mind where this cost is not negligible 
> at all.
Please do tell!

> I shall add that the constraints were something that I had to be 
> "talked into" initially from people actually building/running OLSRv2, 
> and for whom the costs were everything but negligible.

Any documentation you can share??

But then why isn't this in the OLSRv2 specification
instead of packetBB?

I really am very skeptical about this.

>
> I could add something about the fact that eliminating the 
> per-message-processing-overhead for the receiver has some benefits 
> wrt. DoS also, but I think it suffice to say that I fail to see the 
> argument for making something more costly, when we know how to make it 
> less costly.

I very much claim that eliminating the mandate is less costly.

There is absolutely no resilience against DoS
provided by making this mandate.

>
> As an academic, I'll just stick to my 
> send-1-message-process-n-messages example from above as an argument in 
> favour of reducing per-message-processing-overhead, since I believe 
> that it illustrates a point quite nicely.

Is packetBB intended only for one-to-many protocol processing?

Besides that, there just isn't any advantage.  At most, your
argument seems to mean that the parser can avoid allocating
a few most slots for storing the TLV structure data and avoid
a subroutine call for the higher-level protocol processing.
And for this we are going to pay through the nose by having
all of these protocol restrictions and additional parsing steps
for protocols that have zero use for the restrictions?

I am definitely not seeing it.

> As far as I am concerned, these points have all been addressed and the 
> benefit of retaining the constraint on uniqueness and ordering remain 
> clear. I'd take it that you do not dispute the brief example given 
> previously in this email.

I hope my counterargument for your rebuttal will
be of some interest.
> I disagree.

Gee thanks...  I guess you mean that my design is not good, sigh.
 
> I'll first say that the design examples presented have been hypothetical.

Well, if it exists in protocol specification, simulation, and code is it
still hypothetical?

> Second, the designs examples could equally well be accomplished with 
> the current design of packetbb.

Not without drastic packet-size enlargement.

In fact, one could do ANYTHING in the variable-assignment
model of operation, thusly:
- identify all desired multi-sets of values by way of indices
    from the range [1, googolplex].
- distribute the per-TLV databases to all nodes
- use an index to identify the appropriate multiset of values
   within the packetBB-parsable TLV.

I do not think this is a viable model of operation in today's world.

> enumerated elsewhere),
  I am still not seeing it, Thomas.  The efficiency gains
are either very small or else not even there at all.

> and I have seen no compelling benefits presented of altering the 
> design. In particularly not since the alterations proposed incur large 
> penalties in terms of parsing ambiguity and parsing overhead at the 
> receiver.

I think that you have unfairly dismissed the
non-IETFness of this restriction and exaggerated
the occasional benefits by perhaps several orders
of magnitude, while dismissing the corresponding
costs by pointing out that they are not to your taste.

Even aside from the questionable nature of the benefits
themselves, I can find nothing in your response that
indicates the need for their universal application to all
future packetBB protocols.

Regards,
Charlie P.

---

From: Thomas Clausen <[email-masked]>
Date: Wed, 7 Nov 2007 20:38:03 +0100

Charlie,

Comments below.

> about the way someone's current parser had been

I remember Chris had a well-phrased argument to this effect in a  
previous email. I am sure that it is in the archives.

>> No, you've got it wrong here. It has nothing to do with protocols  
>> and everything to do with efficiently encoding, transmitting and  
>> processed.....THAT is what the protocols shall do, and that is  
>> what they are free to do in whichever order is appropriate.
>

I'll try again, then, since it's apparently not yet clear:

	o	packetbb is defining an  encoding for exchanging information  
relevant to a specific problem-domain;
	o 	this encoding is made such that this information is transmitted  
in a way that allows efficient and unique decoding;
	o	subsequent to the decoding, an unique data structure results;
	o	this data structure can be used in a way which is to be specified  
by a protocol specification.

The first 3 is the domain of packetbb -- the last (using the decoded  
data structure) is the domain of a protocol specification.

I do not understand what is meant by "meta-protocol" and the like in  
your paragraph above -- however as has been explained many times  
over, the constraints serve to ensure that the encoding can be parsed  
into unique data structures (and that two nodes receiving the same  
encoded information will be able to, despite being two different  
implementations, decode identical data structures) linearly.

>> striving for (and, indeed, in the specification as it is,  
>> achieving) linear parsing by a receiving node can not be said to  
>> be a bad goal, can it? As you will have seen in previous emails,  
>> there are other benefits beyond this.

Quick-abort is one, minor, benefit of this encoding. However if you  
consult previous emails, you will note that the efficiency goes  
beyond "quick-abort" and has to do with the complexity of the parsing  
algorithm.

>> If I have the choice, I'd rather have the sending node do some  
>> extra work, if that means that the recipient is able to do  
>> something more efficient.
> This is, then, according to your personal taste.

Not at all. I believe that the example I provided gives ample  
justification for why a low parsing-overhead is beneficial, and why a  
little extra effort on the sending side to achieve a gain on the  
receiver is desirable. I am of the understanding that a low per- 
packet-parsing-overhead is generally favoured.

> However, it does

I disagree.

>        authors favor the variable-assignment paradigm).

No, Charlie, ample arguments have been given in previous emails as to  
why this is beneficial.

> 2. Thus, the sender has to work harder to insure that the receiver

No, the sender has to ensure that the encoding is done as specified,  
whereby the recipient can parse it linearly.

I thought you were agnostic to the cost of "processing"? You argue  
that processing by the receiver is insignificant, in which case  
processing by the sender is even MORE insignificant -- and thus, I do  
not understand why processing in the sender suddenly is important?

Recall my simple flooding-example? Each node will send 1 packet but  
receive n, in a n+1 large network. Hence, if processing-time is  
insignificant to you, and you are willing to add extraneous overhead  
in n nodes, why is it not better to add a little overhead in the one  
node (the one that sends) against a saving of extraneous overhead in  
the n nodes that receive?

Sorry, Charlie, but that does -- to reuse your phrase -- "not stand  
up to logical scrutiny".

> the sender implement the ordering.

No, not at all since that no longer becomes something that can be  
done at parse-time, but at a higher level -- which means that the  
work (without the constraint, now no longer doable in O(n)) of  
parsing already has been done. So this will clearly lead to  
inefficiencies.

Secondly, you are ignoring the points made regarding the MANET wg  
doing multiple protocols and genericity (is that a word?) of parsing.

>   Second, absolutely no

No, but the impact of malicious behavior as part of a DoS attack is  
lower the lower the per-packet-parsing-overhead is. That was kind of  
my point.

> Thus, there are absolutely no efficiency gains evident so far.

Other than that parsing can be done linearly in n nodes, of course.....

>
>> I'd argue that there are benefits in that, since I suspect that  
>> most nodes will receive more incoming messages than the generate  
>> themselves. E.g. in a classic link-state protocol, each node will  
>> for each message it generates, receive (ignoring duplicate, which  
>> makes it even more compelling) n messages in a n+1 nodes large  
>> network.  So optimising the message content for the receiver seems  
>> sensible.

And the fact that the parsing can no longer:

	- be generic, regardless of which protocol uses packetbb
	- be linear without backtracking,
	- ensure that the resulting data structure is unique, specifically
	- that two implementations will result in the same data structure  
given the same input

Of course, I consider the above to be important, especially when no  
expressiveness is lost in doing so.

>> sending side does very much needed work that has an overall  
>> benefit for the network.
>
> specification.

So what you are saying is that you hope that networks are not  
dominated by protocols which, say, specify that a node (a source for  
a traffic flow) issue a request to discover the network topology  
(say, a Route Request), with this Route Request being flooded  
throughout the network....? Since in that case, one node generates a  
message, which is being retransmitted by n nodes in our n+1 large  
network.....

> Second, you _could_ make it for the particular
> protocol.

No, see the four benefits listed above....

>   Third, as pointed out above, the gain in efficiency

No, not at all.

>> Again, it has nothing to do with protocols and everything to do  
>> with efficiently and uniquely encoding, transmitting and parsing  
>> information....parsing happening before the encoded and  
>> transmitted information is handed off to the protocol.
>
> not belong in the specification.

Yes, it belongs in the packetbb specification -- it does NOT belong  
in a protocol specification using packetbb since this is already *in*  
packetbb.

> And, the unique encoding
>> I don't think that's a valid argument here: the reason may be that  
>> in packetbb, there's the two-dimensional (in lack of better terms)  
>> aspect of address-block TLVs which is slightly different from  
>> other TLV-based protocols out there (and, I add, is different for  
>> the purpose of efficient encoding....) -- which necessitates this  

Read the packetbb I-D, and note the difference between packet/message  
TLVs and address-block TLVs. It should be fairly obvious what I am  
hinting to. Also note that I said "in lack of better terms" in my  
comment above.

But, it should be fairly obvious why the TLVs are as they are if you  
read the I-D.

> that the processing side is anywhere near similar.

Therein our differences: you have an a-priori of having infinite  
computational/storage capacity and limited power. I am saying that  
sometimes you have limited computational/storage capacity AND limited  
power.

>> You do have a specific environment in mind where this may be true.  
>> I have a different environment in mind where this cost is not  
>> negligible at all.
> Please do tell!
>

Done above.

>> "talked into" initially from people actually building/running  
>> OLSRv2, and for whom the costs were everything but negligible.
>

Was discussed at Paris and subsequent IETFs -- I believe that you  
were party to that a long night in Vancouver too.

> But then why isn't this in the OLSRv2 specification

Because it belongs in packetbb for the reasons given above and by  
Chris, Justin, myself and others in other emails.

>> I could add something about the fact that eliminating the per- 
>> message-processing-overhead for the receiver has some benefits  
>> wrt. DoS also, but I think it suffice to say that I fail to see  
>> the argument for making something more costly, when we know how to  
>> make it less costly.
>

We disagree.

>> messages example from above as an argument in favour of reducing  
>> per-message-processing-overhead, since I believe that it  
>> illustrates a point quite nicely.
>

No, it is intended for many things -- but since in AODV/DYMO/OLSR/ 
OLSRv2 this seems to be a common scenario, packetbb is designed to  
also be efficient for that.

> Besides that, there just isn't any advantage.

We disagree

> At most, your

No, that is not what I say. It is a very very small part of the  
argument.

> for protocols that have zero use for the restrictions?

Protocols can impose their own restrictions. Packetbb is concerned  
with the encoding as is transmitted over the wire -- not with how  
protocols process the data structure constructed from successful  
parsing of a message. There are, therefore, nothing to "pay", no  
"restrictions", no "additional parsing steps| for protocols.

I think that it would be beneficial to re-read the email that I wrote  
a while ago in which I discussed encoding/parsing/processing in  
greater details, since I feel that you have a misunderstanding on  
that front.

> I am definitely not seeing it.

See above.

>> remain clear. I'd take it that you do not dispute the brief  
>> example given previously in this email.
>

I suspect that you have misunderstood the purpose of packetbb. Any  
constraints in there are only on how information is encoded, in order  
to ensure efficiency, genericity and unambiguity -- NOT on how a  
protocol can use it.

>> Second, the designs examples could equally well be accomplished  
>> with the current design of packetbb.
>

I suspect that you have misunderstood the purpose of packetbb. Any  
constraints in there are only on how information is encoded, in order  
to ensure efficiency, genericity and unambiguity -- NOT on how a  
protocol can use it.

> are either very small or else not even there at all.

I refer to my previous example, and respectfully disagree.

>> design. In particularly not since the alterations proposed incur  
>> large penalties in terms of parsing ambiguity and parsing overhead  
>> at the receiver.
>
> themselves,

Sorry, Charlie, I will not entertain discussions which call on  
arguments such as "non-IETFness" or "dismissing based on taste".  I  
further recent that you label my arguments as "occasional benefits"  
and of "questionable nature"  when I present you with a common  
example (a flooding.....which happens in AODV/OLSR/OLSRv2/DYMO all  
the time) and point to the balance between in such a case having a  
(processing) overhead in one node vs. in n nodes. This is a technical  
argument and a very common scenario -- so common, in fact, that all  
MANET wg protocols do it....and yet you counter-argument is:

> Let's hope that most networks are not dominated by the
> specification.

I would like to suggest that we return this discussion to sober and  
technical matters with technical arguments, least I see no point in  
continuing?

> I can find nothing in your response that

I suspect that you have misunderstood the purpose of packetbb. Any  
constraints in there are only on how information is encoded, in order  
to ensure efficiency, genericity and unambiguity -- NOT on how a  
protocol can use it. The benefits are outlined above, in this and in  
many other emails from myself and from others.

Thomas

---

From: "Justin Dean" <[email-masked]>
Date: Wed, 7 Nov 2007 14:52:00 -0500

I would like to comment on one of the points being discussed. 

>> Plus we have had several examples of good designs that would be 
>> prohibited by these restrictions.
>
> I disagree.

To me its not that your design isn't good. Its that the example which you
have presented do not fall within the scope of packetbb, in that it doesn't
use the packetbb format to begin with but a more specific, efficient packet
format only tangentially related to packetbb.  I think your 'hello' example
would be more clear, with regards to how the restrictions would negatively
effect your design if it actually used packetbb.  

I honestly think there is still a lot of misunderstanding on what is and
isn't possible with the current design.  Most examples which use packetbb
layout but require a relaxation of the restrictions, seem to me, not to
actually require restrictions being lifted if a different TLV design/layout
is used.  And in most cases I have thought about the new design is often
just as efficient and almost always less ambiguous.  

Justin

> -----Original Message-----
> From: Charles E. Perkins [mailto:[email-masked]] 
> Sent: Wednesday, November 07, 2007 1:26 PM
> To: ext Thomas Clausen
> Cc: Manet
> Subject: Re: [manet] Regarding packetbb constraints on 
> ordering and uniqueness.
> 
> 
> Hello Thomas,
> 
> If you will (perhaps in private email) direct me to his 
> strongest argument, I will take another look.  Right now, I 
> only remember what seemed to me very vague and 
> unsubstantiated assertions about the way someone's current 
> parser had been written.
> >
> >
> >>
> >> To rehash (as you say) the matter, the argument for mandating the 
> >> ordering is that it is claimed to be useful for some protocols,
> >
> So since this mandate has nothing to do with protocols, I 
> very strongly believe it should be omitted from the protocol 
> No, it is a meta-protocol specification.  Thus, the 
> parsing-related mandate is _TWO_ steps removed from 
> appropriateness for inclusion in this document.
> >
> argued is at least questionable if not downright anti-IETF in flavor.
> >
> >
> >> But I question even whether this is valuable, especially since the 
> >> sending side then must do some unneeded work.
> >
> This is, then, according to your personal taste.  However, it 
> does not stand up to logical scrutiny.
> 
> First, I point out that a protocol could RECOMMEND that the 
> sender implement the ordering.  Second, absolutely no 
> It's even better to avoid making the check entirely.  And I 
> don't see any downside to the more generous behavior, except 
> for possibly adding another sentence of text to whatever 
> protocol specification seems to have a need for this 
> exclusivity and sorting.
> >
> >
> specification.  Second, you _could_ make it for the 
> particular protocol.  Third, as pointed out above, the gain 
> in efficiency is really illusory.  I think it is really just 
> a gain in mental satisfaction that some packet universe might 
> somehow be more organized.
> >
> >> There are several compelling arguments against this mandate.
> Again, if it has nothing to do with protocols, then it just 
> does not belong in the specification.  And, the unique 
> encoding is _only_ of interest to fit Justin's model of TLVs 
> as a sort of variable assignment mechanism.  TLVs do not have 
> to fit that restrictive model.
> >
> enable me to define some two-dimensional understanding of 
> what you're talking about.  Perhaps you meant that the TLV 
> ordering structure is an array of intervals.
> What would the other axis be?  The scalar value for the value 
> to be assigned?
> 
> Anyway this is a very poor basis for discussing any sort of 
> ordering mandate...
> >
>  I think it is quite easy to see in practice.  Calculate the 
> energy expenditure from the radio interface, and compare it 
> to the expenditure from reading a string into memory.  
> Calculate the time spent from the bandwidth delay and compare 
> it to the CPU time expenditure by a processing unit made in 
> the last 50 years.  You can get a lot of martinis from me if 
> you find that the processing side is anywhere near similar.
> But then why isn't this in the OLSRv2 specification instead 
> of packetBB?
> 
> There is absolutely no resilience against DoS provided by 
> making this mandate.
> 
> >
> argument seems to mean that the parser can avoid allocating a 
> few most slots for storing the TLV structure data and avoid a 
> subroutine call for the higher-level protocol processing.
> all of these protocol restrictions and additional parsing 
> steps for protocols that have zero use for the restrictions?
> 
> >> And these are just the ones I remember right off the top 
> of my head.  
> >> For a full recapitulation ("rehash"), please ask and I will do the 
> >> seemingly thankless task of rehashing the rehashed arguments from 
> >> months ago.
> I hope my counterargument for your rebuttal will be of some interest.
> >
> >> Plus we have had several examples of good designs that would be 
> >> prohibited by these restrictions.
> >
> > I disagree.
> 
> Well, if it exists in protocol specification, simulation, and 
> code is it still hypothetical?
> 
>   I am still not seeing it, Thomas.  The efficiency gains are 
> either very small or else not even there at all.
> 
> I think that you have unfairly dismissed the non-IETFness of 
> this restriction and exaggerated the occasional benefits by 
> perhaps several orders of magnitude, while dismissing the 
> corresponding costs by pointing out that they are not to your taste.
>

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 07 Nov 2007 12:41:58 -0800

Hello Thomas,

I'll try again.

> previous email. I am sure that it is in the archives.
 It would be nice if you could help me find it.
> relevant to a specific problem-domain;

 Is this the problem domain of general [manet] protocols, or the problem
domain of something considerably more restrictive?
>     o     this encoding is made such that this information is 
> transmitted in a way that allows efficient and unique decoding;
 I guess my point has been that it is a mistake to impose the
efficiency argument on all protocols for the benefit of a few.
>     o    subsequent to the decoding, an unique data structure results;
 This is debatable as you have phrased it.  I think you meant that
a data structure results with the property that all variables have been
assigned a unique value.

>     o    this data structure can be used in a way which is to be 
> specified by a protocol specification.
This is a vey general statement, not at issue in the discussion.
>
> I do not understand what is meant by "meta-protocol"
In this context, it means a specification by which other
conformant protocols can be specified.
> and the like in your paragraph above -- however as has been explained 
> many times over, the constraints serve to ensure that the encoding can 
> be parsed into unique data structures (and that two nodes receiving 
> the same encoded information will be able to, despite being two 
> different implementations, decode identical data structures) linearly.
As stated, this can be done very well without the constraints at issue.

> consult previous emails, you will note that the efficiency goes beyond 
> "quick-abort" and has to do with the complexity of the parsing algorithm.

So now we have "quick-abort" [minor benefit] + parsing complexity.

>
> ...  I believe that the example I provided gives ample justification 
> for why a low parsing-overhead is beneficial, and why a little extra 
> effort on the sending side to achieve a gain on the receiver is 
> desirable. I am of the understanding that a low 
> per-packet-parsing-overhead is generally favoured.
 Of course.  But you can get even lower parsing overhead by omitting
the check entirely.  Your example only pertains when every receiver has
a strong reason to enforce the mandated behavior, and this is really
debatable.  More later...
> No, Charlie, ample arguments have been given in previous emails as to 
 Arguments have been given many times but they are are, I think,
summarizable as '"quick-abort" [minor benefit] + parsing complexity'
> No, the sender has to ensure that the encoding is done as specified
this is working harder...
> , whereby the recipient can parse it linearly.
>
> I thought you were agnostic to the cost of "processing"?
Agnostic is the wrong word here.  I'm much aware of it, being a
former assembly language programmer and all, sigh.

> You argue that processing by the receiver is insignificant, in which 
> case processing by the sender is even MORE insignificant -- and thus, 
> I do not understand why processing in the sender suddenly is important?
 I did not suggest that the sender processing complexity was the determining
factor here, only that it isn't obvious that, in general, the argument 
should be
tilted in favor of minimizing receiver processing for all protocols.
> Sorry, Charlie, but that does -- to reuse your phrase -- "not stand up 
> to logical scrutiny".

For flooding, I agree that sender-side processing complexity should be
increased to enable a decrease in receiver-side processing complexity.
I don't see where I have disagreed with this.  But even so, one can
reduce complexity on both ends by simply not doing the uniqueness
check.

You have dismissed my concern about non-IETFness, but you did not
present a good argument about why packetBB-conformant protocols
have special needs that are not present in other IETF protocols.  You
just pointed out that it might be possible for them to have special
needs.

> No, not at all since that no longer becomes something that can be done 
> at parse-time, but at a higher level -- which means that the work 
> (without the constraint, now no longer doable in O(n)) of parsing 
> already has been done. So this will clearly lead to inefficiencies.
 I think it means that you want to have not only a single meta-protocol
specification for all [manet] protocols, but even a single parser.
That's a bitter pill to swallow.  And we could even have a
single parser if the parser had the merest bit of type-dependent
protocol processing, easily loadable when the kernel is loaded.
That's just the first thing that comes to mind; I am sure there are
other handy ways to do it.

So I do not agree that this argument is clear.
> lower the lower the per-packet-parsing-overhead is. That was kind of 

Why, then, wouldn't a smart DoS-er make the nastygrams
to be packetBB-conformant?
> Other than that parsing can be done linearly in n nodes, of course.....

It still can, when needed, if the behavior is protocol-type-dependent.

>     - be generic, regardless of which protocol uses packetbb
 You can push this genericity entirely too far.  I could make a lot
of silly examples to prove my point, but my fingers are getting
tired already from massaging so many keys.  I believe that this
specification has already pushed it too far.
>     - be linear without backtracking,
If the indicated checking is needed at all, that is.

>     - ensure that the resulting data structure is unique, specifically
Here, again, I think you mean that the variables have unique
assignments.

>     - that two implementations will result in the same data structure 
 The constraints are definitely not needed to insure that.

> expressiveness is lost in doing so.

But, expressiveness is very clearly lost by imposing the single-assignment
model for all types of variables.

> dominated by protocols which, say, specify that a node (a source for a 
> traffic flow) issue a request to discover the network topology (say, a 
> Route Request), with this Route Request being flooded throughout the 
> network....? Since in that case, one node generates a message, which 
> is being retransmitted by n nodes in our n+1 large network.....

Yes, I think that route discovery should be a minor
part of the overall network traffic.  We should be
working towards making that happen.

> Yes, it belongs in the packetbb specification -- it does NOT belong in 
> a protocol specification using packetbb since this is already *in* 
> packetbb.
Well, I am writing this to ask you to take it out, so that it can be 
properly
introduced as a per-protocol detail for those protocols that need it.

> But, it should be fairly obvious why the TLVs are as they are if you 
 I did read it, several times.  It's obvious that the document authors are
very much favorable towards the single-assignment paradigm, and
do not seem to believe that other models could ever be useful in the
future.

> sometimes you have limited computational/storage capacity AND limited 

Here is a terrible exaggeration.  I never said infinite.  I believe that
for many cases of interest, both are limited.  However, that is why
you have to be careful against specifying for all cases something
that is of value for perhaps only a few cases.

If you want to be persuasive here, I think it would be valuable to
counter the commonly held belief that radio-transmission and
reception demands a lot more energy than processing.

This is why your cellphone dies a lot faster when you are
blabbering away for hours, compared to when the handset
is on standby.  This is also why when people first put WiFi
into the handsets, the batteries went to zero pretty darned
fast.

I think the relative tradeoffs here are dramatically clear.

And who is saying infinite?

>>> have a different environment in mind where this cost is not 
>>> negligible at all.
>> Please do tell!
>>
>
> Done above.

I did not see it.  Do you have an example?  Just to say
"limited processing power" is not very illuminating,
especially in comparison with the everyday experience
of what people use a lot.

> Was discussed at Paris and subsequent IETFs -- I believe that you were 
> party to that a long night in Vancouver too.

I clearly remember being told that you had inputs from
third parties requesting the sorting.  I asked who it was
and did not get any answer.  Besides that, the beer was
very good.

> "restrictions", no "additional parsing steps| for protocols.
 This is wrong.  One has to pay the following costs:
- Prohibition of designs that do not conform to the
    single-assignment paradigm for variable initialization
- Processing cost of sorting
- Packet enlargement for protocols that might otherwise
    be designed differently.

> greater details, since I feel that you have a misunderstanding on that 
> front.

Do you still think I misunderstand -- or do you instead
see that I am characterizing the benefits as not
justifying the costs on various levels?
> to ensure efficiency, genericity and unambiguity -- NOT on how a 
 What about for protocols that want to assign potentially
multiple values to variables in a way prohibited by packetBB?

> to ensure efficiency, genericity and unambiguity -- NOT on how a 
 Actually, it is my main point that some protocols cannot use it.
It is a second point that the claimed efficiencies are either not
important (in some cases), or never important enough to support
the universal mandate (in other cases).
> arguments such as "non-IETFness" or "dismissing based on taste".
 By the former, I mean to compare against the experience of
other working groups.  You should entertain that discussion.

We can dispense with any discussions based on tastefulness,
but I was responding to some particular wording in your note
about what would happen if you had your choice.

>   I further recent that you label my arguments as "occasional 
> benefits" and of "questionable nature"  when I present you with a 
> common example (a flooding.....which happens in AODV/OLSR/OLSRv2/DYMO 
> all the time) and point to the balance between in such a case having a 
 Hey, I'm not drunk!  But I maintain that we should strive
towards networks that are not dominated by flooding costs.
Nevertheless, I am all in favor of reducing the costs ascribed
to flooding.  Presumably you are also, and then we ought to
be talking about reducing packet size [ref: bloat].
> I suspect that you have misunderstood the purpose of packetbb.
 Well I hope by now you no longer ascribe my disagreement to
simple misunderstanding.

> Any constraints in there are only on how information is encoded, in 
> order to ensure efficiency, genericity and unambiguity -- NOT on how a 
> protocol can use it.
 But a protocol cannot use it, if the protocol operation already 
specifically
does not conform to the single-assignment paradigm for typed variables.

Regards,
Charlie P.