Subject: [manet] RE: Your comments in packetbb thread about #2 (ordering)

From: "Justin Dean" <[email-masked]>
Date: Tue, 21 Aug 2007 11:19:36 -0400

Ian thought it would be useful to post this and I agree as I feel there is
still some confusion on the benefits of some of the restrictions included in
packetbb.  I am sorry for the jumbled up presentation of information here,
it may be helpful to read bottom up (older message first)

Justin

Further comments are inline.

>Thanks for responding Justin.
>
>Comments inline.
>
>On 8/21/07, Justin Dean <[email-masked]> wrote:
>> Sending shouldn't be an issue, at least I haven't heard of any issues 
>> code wise or otherwise.
>>
>> The issue is on the receiving end when a protocols expects things to 
>> be ordered but are not.  The other way around works fine, receiving 
>> ordered but expecting unordered.  Your example of NHDP not ordering 
>> but OLSRv2 requiring ordering means that if OLSRv2 accepted a packet 
>> it could possibly process things wrong and skip over OLSRv2 tlvs 
>> because they were out of order with regards to the NHDP tlvs included 
>> in the message.  This makes it an all or nothing kind of thing when
mixing protocols.
>
>Ok, when mixing protocols in common messages - NHDP & OLSRv2. Got it.
>
>> The skipping over of tlvs is not the only advantage as it helps 
>> support the limiting of one tlv type per address without having to 
>> "store" in memory all of the tlvs used so far for a given address 
>> block.  Yes this restriction of one tlv per address may be relaxed but 
>> many protocols can and will reinsert this requirement (one tlvfulltype 
>> per address) making implementations work significantly harder to 
>> verify that messages are syntactically correct with out of order tlv 
>> types.  A third point is special tlvs when NEED to come before other 
>> tlvs of different types, on example of this being a fragmented message 
>> tlv type.  If the fragment tlv isn't included before other tlv types 
>> then incorrect parsing/action may have to be reversed when the tlv is
located.
>
>I thought fragmentation was removed? Also, why would a fragmentation TLV
need to be first?

It was but that doesn't mean that some fragmentation type tlv will never be
needed in the future.  The TLV might need to be first if the protocol using
this fragmentation type tlv only processes the message once the entire
message has been received.  If the tlv in question was at the end it would
make parsing work much harder to determine what the protocol should do with
the information contained in the message.  If the tlv was always at the
start the protocol would be able to store the message after reading the
first tlv and be done until the rest of the message showed up.

>
>Can you give me another case of a TLV needing to come first?
>
Any tlv which would "change" behavior of the following tlvs.  One example
would be a delay processing tlv.  This could pause the reception of a
message after it has been received.  Again if it was not in near the top
(fragmentation type makes sense to be before this kind of tlv), the entire
message would have to be read in order to decide on the correct behavior.

>> These issues can not be defined easily on a per protocol specification 
>> as conflicts will arise.  Ordering/not, two requiring tlv to be first 
>> if included.
>
>If we do not impose any ordering of TLVs, maybe we will have to include
some text in PacketBB saying that protocols cannot expect a particular order
for >TLVs. That is, trying to encode protocol specific information using the
order of TLVs should be discouraged.
Yes and this IMO reduces the flexibility of packetbb while adding nothing to
packetbb.  There is an advantage in not having to worry about ordering from
a document/IANA perspective but in terms of the protocol functionality
nothing is being added.

I would also like to point out that it allows for easy verification of one
TLV_fulltype per address.  Which I am still in favor of keeping after some
more thought.  The benefits are minimal and the possibility of incorrect
processing increases greatly when more than one TLV_fulltype can be on one
address.  An example is a protocol which rebuilds a packetbb packets and
includes it own information into the packet/message.  If this implementation
only ever expects one TLV_fulltype per address it may just throw out the
duplicates when rebuilding the packet.  Yes you could say that it shouldn't
do this but I would expect MANY implementations would do this as they
wouldn't ever use the more than one TLV_fulltype per address "feature".

>> Justin
>>
>> Ps if you think it would be helpful I will post this to the list.
>
>I think posting to the list would be good, if you've got some good
arguments to support ordering.

> -----Original Message-----
> From: Ian Chakeres [mailto:[email-masked]]
> Sent: Friday, August 17, 2007 10:52 PM
> To: Justin Dean
> Subject: Re:Your comments in packetbb thread about #2
>
> In regard to the overall concept, its still unclear to me why ordering 
> is so important. I'd like to understand this before I try to think 
> about protocols doing ordering.
>
> I'm also confused about the text below, is the problem during sending 
> or receiving? If a particular implementation/protocol does order 
> things, this would definitely be consumable by implementations that don't
order things.
> Therefore, if someone had NHDP and it didn't require ordering and 
> OLSRv2 which did require ordering, then the NHDP implementations 
> should have no problem communicating even if one NHDP implementation is
ordering tlvs.
>
> I understand the search problem, but I don't really think that is too 
> important.
>
> Ian
>
> On 8/18/07, Justin Dean <[email-masked]> wrote:
> > I thought I had with this message...
> >
> > "The reason I say protocols can not make ordering requirements on 
> > their own is for an envisioned system where two protocols are using 
> > the same packetbb "code engine".  This would save duplicate packets 
> > and become more efficent than both protocols opperating seperatly.  
> > If the first of these protocols requires ordering but the 2nd does 
> > not the first may make the wrong assumption that the tlv/address is 
> > not present when it is just out of order because the 2nd added some 
> > out of order tlv/address.  Actually nhdp/olsr nhdp/smf are an 
> > example of this and they would break if nhdp requires ordering but olsr
does not.
> >
> > Justin"
> >
> > I can reword it and resend to the list if you think that would be
helpful.
> >
> > -----Original Message-----
> > From: Ian Chakeres [mailto:[email-masked]]
> > Sent: Friday, August 17, 2007 12:17 PM
> > To: Justin Dean
> > Subject: Re: [manet] PacketBB Recent Discussion #1 - Allowing 
> > multipleTLVsofthe same type
> >
> > <private email>
> >
> > Justin, can you please reply to the other thread about ordering? It 
> > is still unclear to me why the ordering restriction is so important.
> >
> > Thanks.
> > Ian
> >
> > On 8/14/07, Justin Dean <[email-masked]> wrote:
> > > Well those were just two attributes which came to mind when 
> > > writing the example.  Having say link type of symmetric/asymmetric 
> > > as one type and then another orthogonal attribute lets say 
> > > willingness where most nodes have willingness of default and 2 are 
> > > never illustrates this with a more reasonable way.  They are 
> > > separate disjoint attributes apples to oranges yes and they should 
> > > be.  There is, however, value in having them associated with the 
> > > same address block and there is no clear way to order the 
> > > addresses to allow for aggregation of both sets of information within
the same address block.
> > >
> > > Having said that though the gains given in this example are minimal.
> > > In the current case the two fixed size tlvs can advertise all of 
> > > the first attributes.  The second tlv most likely would use a 
> > > single m-tlv to assign the mixed up attributes to all of the nodes.
> > > Relaxing this restraint would allow for some gains in terms of the 
> > > size of representation of the second attribute in some cases (not 
> > > all dependant on
> > how jumbled the values were).
> > >
> > >
> > > Size of current restrained packetbb = tlvoverhead*3+#addresses.
> > > (worst
> > > case) Optional size of unrestrained packetbb = 
> > > tlvoverhead*3+tlvoverhead*#ofdisjointattirbutes.
> > >
> > > There are many different ways to represent different attributes 
> > > with the current draft already.  And it isn't always clear on what 
> > > the best encoding scheme is for any given case as it is.  Relaxing 
> > > this restriction would allow another option to try and further 
> > > reduce overhead but only in the case where the second attribute is 
> > > mostly the same with small number of different values.  I don't 
> > > often think this will
> > be the case.
> > >
> > > Please correct me if I am wrong but I don't see a big issue with 
> > > allow derived protocols to decide on this behavior.  It doesn't 
> > > seem like it would break any further protocols by not having it in 
> > > packetbb.  So my question to you guys is, what are the tradeoffs 
> > > with changing the wording to more closely reflect the issues with 
> > > regard to multiple message/packet tlvfulltypes?
> > >
> > > The ordering restriction I am still very strongly in favor of keeping.
> > >
> > > Justin
> > >
> > > -----Original Message-----
> > > From: Dearlove, Christopher (UK)
> > > [mailto:[email-masked]]
> > > Sent: Tuesday, August 14, 2007 11:26 AM
> > > To: Stan Ratliff (sratliff); Ian Chakeres; manet
> > > Subject: RE: [manet] PacketBB Recent Discussion #1 - Allowing 
> > > multipleTLVsofthe same type
> > >
> > >
> > > I wouldn't regard that as a real use case - when was the last time 
> > > you actually wanted to declare a node as bright red?
> > >
> > > In addition I don't actually think it is a good example. What is 
> > > the relationship between bright and red?
> > >
> > > - If bright red is a colour, why not simply encode bright red,
> > >   bright blue, dark red etc. as separate colours in a single
> > >   value space? What's the advantage of separating them but also
> > >   regarding them as the same TLV - one with values including
> > >   red, blue, bright and dark, a definite apples and oranges
> > >   sort of value list?
> > >
> > > - If bright is something quite separate from red, we have two
> > >   TLVs, and putting them in a single value space makes no sense
> > >   at all.
> > >
> > > - If you consider bright to be a modifier of colour, then a
> > >   natural encoding is to use TLV subtypes, one for colour,
> > >   one for brightness. Note that you can have two TLVs of the
> > >   same type but different subtypes (i.e different full types)
> > >   associated with the same information.
> > >
> > >
> > > -----Original Message-----
> > > From: Stan Ratliff (sratliff) [mailto:[email-masked]]
> > > Sent: 14 August 2007 16:03
> > > To: Ian Chakeres; manet
> > > Subject: RE: [manet] PacketBB Recent Discussion #1 - Allowing 
> > > multiple TLVsofthe same type
> > >
> > >
> > >                *** WARNING ***
> > >
> > > This mail has originated outside your organization, either from an 
> > > external partner or the Global Internet.
> > >      Keep this in mind if you answer this message.
> > >
> > > Ian,
> > >
> > > I think that Justin provided a use case in his email:
> > >
> > > --------------------Included email---------------------- With 3 
> > > this was introduced to avoid confusion on which value should be used.
> > > I personally would be ok with wording this closer to 2 in 
> > > mandating that the tlv definitions explicitly disallow or allow.  
> > > There are issues with allowing this but there may also be an 
> > > advantages.  A hypothetical example; 10 addresses each of which is 
> > > either bright or dark and blue or red
> > > 1 bright red
> > > 2 bright blue
> > > 3 bright red
> > > 4 bright red
> > > 5 bright red
> > > 6 dark red
> > > 7 dark blue
> > > 8 dark red
> > > 9 dark red
> > > 10 dark red
> > >
> > > Under the current constraints it would require 1 indexed tlv for 
> > > bright
> > > 1
> > > indexed tlv for dark, then either a m-tlv for all the addressed or 
> > > a mixture of m-tlvs and indexed tlvs for the color.  If constraint 
> > > of more than one was lifted for the color tlv a m-tlv for all 
> > > nodes being red and then 2 single tlvs for the 2 blue nodes may 
> > > reduce
> overhead.
> > > -------------------End of inclusion----------------------
> > >
> > > Regards,
> > > Stan
> > >
> > >
> > > >-----Original Message-----
> > > >From: Ian Chakeres [mailto:[email-masked]]
> > > >Sent: Tuesday, August 14, 2007 8:23 AM
> > > >To: manet
> > > >Subject: [manet] PacketBB Recent Discussion #1 - Allowing 
> > > >multiple TLVs ofthe same type
> > > >
> > > >I'd like to focus the discussion around allowing multiple TLVs of 
> > > >the same type to be associated with the one entity in packetbb.
> > > >
> > > >If you have a good use case, please provide it and describe why 
> > > >it is useful.
> > > >
> > > >Ian Chakeres
> > > >
> > > >Note: I would like to quickly finish any remaining PacketBB 
> > > >discussion and move this document forward.
> > > >
> > > >
> > > >_______________________________________________
> > > >manet mailing list
> > > >[email-masked]
> > > >https://www1.ietf.org/mailman/listinfo/manet
> > > >
> > >
> > >
> > > _______________________________________________
> > > manet mailing list
> > > [email-masked]
> > > https://www1.ietf.org/mailman/listinfo/manet
> > >
> > >
> > > ******************************************************************
> > > ** This email and any attachments are confidential to the intended 
> > > recipient and may also be privileged. If you are not the intended 
> > > recipient please delete it from your system and notify the sender.
> > > You should not copy it or use it for any purpose nor disclose or 
> > > distribute its contents to any other person.
> > > ******************************************************************
> > > **
> > >
> > >
> > >
> > > _______________________________________________
> > > manet mailing list
> > > [email-masked]
> > > https://www1.ietf.org/mailman/listinfo/manet
> > >
> > >
> >
> >
>
>

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

---

From: "Ian Chakeres" <[email-masked]>
Date: Tue, 21 Aug 2007 20:54:42 +0530

Comments inline.

> first tlv and be done until the rest of the message showed up.

Why is it harder if it isn't first?

> Any tlv which would "change" behavior of the following tlvs.

I agree with you so far.

> One example

I believe the case above (delay processing) actually motivates for NOT
requiring a particular order.

> a document/IANA perspective but in terms of the protocol functionality

Why is a strict ordering better than any order?

> wouldn't ever use the more than one TLV_fulltype per address "feature".

I agree with the easier verification, but implementations will still
have to handle the case of a duplicate tlv's attached to the same
entity. So I don't consider this sufficient.

Here are some more issue with the ordering argument.

Who chooses the order? If it goes in IANA assigned order, how should
these TYPE values be allocated?

I plan to write the list to focus our attention on this issue again.
Please feel free to reply there.

Ian Chakeres

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Tue, 21 Aug 2007 16:35:53 +0100

> Who chooses the order?

Numerical, hence

> If it goes in IANA assigned order,

Yes

> how should

I think that for all the cases we have in timetlv/NHDP/OLSRv2/DYMO
we can allocate them as the documents go in. That would put the
timetlv ones in first.

I might suggest we don't allocate packet and message TLV types zero just
in case of a major need at some time in the future. Given that it has
subtypes, this will answer such as of Justin's point I think matters.
We have used address TLV type zero on something that deserves it.

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

---

From: "Justin Dean" <[email-masked]>
Date: Tue, 21 Aug 2007 11:54:57 -0400

Comments inline again. 

-----Original Message-----
From: Ian Chakeres [mailto:[email-masked]] 
Sent: Tuesday, August 21, 2007 11:25 AM
To: Justin Dean
Cc: [email-masked]
Subject: Re: Your comments in packetbb thread about #2 (ordering)

Comments inline.

On 8/21/07, Justin Dean <[email-masked]> wrote:
> Ian thought it would be useful to post this and I agree as I feel 
> there is still some confusion on the benefits of some of the 
> restrictions included in packetbb.  I am sorry for the jumbled up 
> presentation of information here, it may be helpful to read bottom up 
> (older message first)
>
> Justin
>
> >> Sending shouldn't be an issue, at least I haven't heard of any 
> >> issues code wise or otherwise.
> >>
> >> The issue is on the receiving end when a protocols expects things 
> >> to be ordered but are not.  The other way around works fine, 
> >> receiving ordered but expecting unordered.  Your example of NHDP 
> >> not ordering but OLSRv2 requiring ordering means that if OLSRv2 
> >> accepted a packet it could possibly process things wrong and skip 
> >> over OLSRv2 tlvs because they were out of order with regards to the 
> >> NHDP tlvs included in the message.  This makes it an all or nothing 
> >> kind of thing when
> mixing protocols.
> >
> >> block.  Yes this restriction of one tlv per address may be relaxed 
> >> but many protocols can and will reinsert this requirement (one 
> >> tlvfulltype per address) making implementations work significantly 
> >> harder to verify that messages are syntactically correct with out 
> >> of order tlv types.  A third point is special tlvs when NEED to 
> >> come before other tlvs of different types, on example of this being 
> >> a fragmented message tlv type.  If the fragment tlv isn't included 
> >> before other tlv types then incorrect parsing/action may have to be 
> >> reversed when the tlv is
> located.
> >
> It was but that doesn't mean that some fragmentation type tlv will 
> never be needed in the future.  The TLV might need to be first if the 
> protocol using this fragmentation type tlv only processes the message 
> once the entire message has been received.  If the tlv in question was 
> at the end it would make parsing work much harder to determine what 
> the protocol should do with the information contained in the message.  
> If the tlv was always at the start the protocol would be able to store 
> the message after reading the first tlv and be done until the rest of the
message showed up.

Because processing of the message as it is read can not occur if it isn't
first.  Then the TLVs would have to be internally ordered to see what action
would be required.  If the TLV is first then the message/packet can be
processed and parsed at the same time saving time and memory, with the nice
side benefit of easily checking for duplicate tlv_fulltypes.

I agree with you so far.

> message after it has been received.  Again if it was not in near the 
> top (fragmentation type makes sense to be before this kind of tlv), 
> the entire message would have to be read in order to decide on the correct
behavior.

Only if you think reading and "half" processing every tlv to see what action
should occur with the rest of the message is better than reading them in
order and deciding what is to be done with the rest.

> >> These issues can not be defined easily on a per protocol 
> >> specification as conflicts will arise.  Ordering/not, two requiring 
> >> tlv to be first if included.
> >
> some text in PacketBB saying that protocols cannot expect a particular 
> order for >TLVs. That is, trying to encode protocol specific 
> information using the order of TLVs should be discouraged.
> >
> Yes and this IMO reduces the flexibility of packetbb while adding 
> nothing to packetbb.  There is an advantage in not having to worry 
> about ordering from a document/IANA perspective but in terms of the 
> protocol functionality nothing is being added.

I think I have addressed that.  Processing and parsing can occur at the same
time as you go.  The entire message does not need to be read and stored so
that the protocol can "find" the "important" tlvs.

> I would also like to point out that it allows for easy verification of 
> one TLV_fulltype per address.  Which I am still in favor of keeping 
> after some more thought.  The benefits are minimal and the possibility 
> of incorrect processing increases greatly when more than one 
> TLV_fulltype can be on one address.  An example is a protocol which 
> rebuilds a packetbb packets and includes it own information into the 
> packet/message.  If this implementation only ever expects one 
> TLV_fulltype per address it may just throw out the duplicates when 
> rebuilding the packet.  Yes you could say that it shouldn't do this 
> but I would expect MANY implementations would do this as they wouldn't
ever use the more than one TLV_fulltype per address "feature".

I agree with the easier verification, but implementations will still have to
handle the case of a duplicate tlv's attached to the same entity. So I don't
consider this sufficient.

It's a one line check in code and in protocols to decide the behavior of
receiving a malformed packet.  Drop the tlv, drop the message, drop the
packet or override it.  I don't think packetbb should make a requirement as
to correct receiving behavior but should make a suggestion to drop the
message.

Who chooses the order? If it goes in IANA assigned order, how should these
TYPE values be allocated?

Ian Chakeres

I agree the ordering it not the easiest decision to make but I think it's
worthwhile endeavor. 
Justin

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Tue, 21 Aug 2007 17:05:54 +0100

Justin
> I agree the ordering it not the easiest decision to make but I think
it's

I think if you look at all of the TLVs required by OLSRv2 (including
NHDP) the order isn't critical.

Packet TLVs
- None

Message TLVs
- VALITITY_TIME
- INTERVAL_TIME
- WILLINGNESS
- MSG_SEQ_NUM
- INCOMPLETE

The first two are agreed common usage, and in an ID I expect will
get finished first (after packetbb) so I'm inclined towards putting
them first (skipping zero, just in case). After that if OLSRv2 gets
out before DYMO, they could go next (e.g. 3 to 5) but that's not a
deal-breaker.

Address Block TLVs
- Prefix Length - this is zero, defined in packetbb, and should be so.
- VALITITY_TIME - to be added to timetlv
- INTERVAL_TIME - if added to timetlv as address block TLV
- OTHER_IF
- LINK_STATUS
- OTHER_NEIGHB
- MPR           - might become more complicated if add metrics to OLSRv2
- GATEWAY
- LINK_METRIC   - (name TBD) if added

Similar comments.

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Wed, 22 Aug 2007 09:39:55 +0100

MSG_SEQ_NUM below should be CONT_SEQ_NUM. Doesn't
affect the argument.

-----Original Message-----
From: Dearlove, Christopher (UK) 
Sent: 21 August 2007 17:06
To: 'Justin Dean'; 'Ian Chakeres'
Cc: [email-masked]
Subject: RE: [manet] RE: Your comments in packetbb thread about #2
(ordering)

Justin

Packet TLVs
- None

Message TLVs
- VALITITY_TIME
- INTERVAL_TIME
- WILLINGNESS
- MSG_SEQ_NUM
- INCOMPLETE

Address Block TLVs

Similar comments.

---

From: "Ian Chakeres" <[email-masked]>
Date: Thu, 23 Aug 2007 11:32:39 +0530

If we take the argument about processing in IANA assigned order.

What happens if later, someone wants something that is processed
before one of these TLV types? Alternatively, how can we ensure that
the ordering we choose now is right for the future?

Ian

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Thu, 23 Aug 2007 09:45:13 +0100

There's absolutely no compulsion to process in the
order that you store in. Often there is no well-defined
processing order in any case.

If you consider OLSRv2, for example, INTERVAL_TIME is
optional - there's no compulsion to use it, and all its
uses are in things you may do. (For example one way to
track a poor link is to spot missing HELLO messages, if
you know when the next one is expected.) There's no fixed
position in when to use that. But even when not optional,
you use LINK_STATE and OTHER_IF of an address in a HELLO
message together (if both present). And I'm reasonably
sure I could organise the processing of a HELLO message
to use WILLINGNESS before or after VALIDITY_TIME (it's
written one way, but as long as you get the same effect,
the processing order doesn't matter. In any case I likely
would cache the two values (extracting and converting the
time value) while, or just after, parsing the message,
and then use them how I choose. (If a message had a long
block of information, I might cache a pointer to it
instead.)

-----Original Message-----
From: Ian Chakeres [mailto:[email-masked]] 
Sent: 23 August 2007 07:03
To: Dearlove, Christopher (UK)
Cc: Justin Dean; Thomas Heide Clausen (work); manet
Subject: Re: [manet] RE: Your comments in packetbb thread about #2
(ordering)

               *** WARNING ***

This mail has originated outside your organization,
either from an external partner or the Global Internet. 
     Keep this in mind if you answer this message. 

Ian