Subject: [manet] packetbb constraints

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Fri, 14 Sep 2007 09:39:03 +0100

With the current contraints in packetbb you can
so two things:

- Linearly pass through a TLV block verifying its
  correctness, without the need to store the
  information therein. All you need to carry from
  one step to the next is the TLV is the last
  TLV full type and stop index.

- Linearly pass through an address TLV block, without
  backtracking, extracting the information of a
  certain type to apply to the addresses in the
  associated address block, in order. (You even get
  to stop when you are past it, without proceeding
  to the end of the block.)

These are not true without the constraints. For
example consider if we have (mixed in among all
the other TLVs, but in this order)

- TLV type X applying to index 2
- TLV type X applying to index 1

Now for index 1 we go on to the second of these,
but for index 2 we how need to go back to the first.
It gets worse however, now consider

- TLV type X applying to indexes 2 to 4
- TLV type X applying to indexes 1 to 5

Now for index 1 we go on to the second of these,
but for index 2 we need to go back to the first
to spot that it's there twice. And which do we
use? And if you say the first, we now use some
but not all information in the second TLV, but
some is over-ridden by the first. If you say
"take the best/worst value" then we end up using
a mixture of values from both TLVs.

No matter how you resolve this, this is more
complicated. That means that the claim that
the additional complexity in the receiver
without the constraints is less than the
additional complexity in the transmitter with
the constraints (which is simply insertion
in order) is not true. The key point that makes
things difficult, and why experience with other
TLV mechanisms isn't all you need, is the address
indexes.

********************************************************************
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

---

From: "Stan Ratliff \(sratliff\)" <[email-masked]>
Date: Fri, 14 Sep 2007 12:47:38 -0400

>-----Original Message-----
>From: Dearlove, Christopher (UK) 
>[mailto:[email-masked]] 
>Sent: Friday, September 14, 2007 4:39 AM
>To: manet
>Cc: Thomas Heide Clausen (work)
>Subject: [manet] packetbb constraints
>
[snip]
>TLV mechanisms isn't all you need, is the address

I respectfully disagree. First off, TLV's can simply 
be processed in the order received. This removes 
the ambiguity, and doesn't add processing 
complexity. 

Secondly, if TLV ordering is important, it should be
something imposed at the protocol level (e.g. OLSR,
NHDP) instead of at the packetbb level, IMO. 

Regards,
Stan

---

From: "Justin Dean" <[email-masked]>
Date: Fri, 14 Sep 2007 14:28:48 -0400

TLVs can be processed in the order they are received yes and in fact can be
processed in any way independent on ordering within the packet.  That being
said there may be TLVs which invalidate the processing of other TLVs.  There
are two issues as I see it. Finding relevant TLVs to the protocol doing the
processing and checking TLVs which may cause the message to be ignored.  

ANY kind of ordering helps with both of these issues.  Having no order
doesn't break anything it may just require implementations to read/store
more information than would be needed with ordering.  Imposing an order
later within a protocol specification would allow for "perfect" ordering
unlike the current type value ordering but it would not allow differing
protocols to share the same message space without explicit rules as to the
integrating orders of the TLVs.  If these rules on ordering were not
explicit enough there is an increased danger of protocols breaking if they
were expecting a specific order which was not present.  This could be fixed
by reading all TLVs in before any processing but why have ordering at all
then?  By imposing AN order on TLVs, while it may not end up being perfect,
would allow ALL protocols derived from packetbb the opportunity to quickly
search/process relevant TLVs.

Possible future TLVs which may cause a message to be ignored:
A protocol TLV which lists the protocols contained within the message(s).
A security TLV which may cause the packet/message to be ignored if it fails.
A checksum TLV which may cause the packet/message to be ignored if it fails.

Again I would like to stress that the ordering within the packet does not
preclude the functioning of any of these types of TLVs.  If they were placed
in order (and hopefully with lower assigned type values) they could be more
easily verified before other less fundamental TLVs are even read in.  If the
order isn't perfect the situation degrades to reading all TLVs in before
processing which is the same as if there were no order imposed at all.

Justin

> From: Stan Ratliff (sratliff) [mailto:[email-masked]] 
> Sent: Friday, September 14, 2007 12:48 PM
> To: Dearlove, Christopher (UK); manet
> Subject: RE: [manet] packetbb constraints
> 
>  
> 
> >No matter how you resolve this, this is more complicated. That means 
> >that the claim that the additional complexity in the 
> receiver without 
> >the constraints is less than the additional complexity in the 
> >transmitter with the constraints (which is simply insertion 
> in order) 
> >is not true. The key point that makes things difficult, and why 
> >experience with other TLV mechanisms isn't all you need, is 
> the address 
> >indexes.
> >
> 
> I respectfully disagree. First off, TLV's can simply be 
> processed in the order received. This removes the ambiguity, 
> and doesn't add processing complexity. 
>

---

From: "Stan Ratliff \(sratliff\)" <[email-masked]>
Date: Fri, 14 Sep 2007 15:17:04 -0400

>From: Justin Dean [mailto:[email-masked]] 
>Sent: Friday, September 14, 2007 2:29 PM
>To: Stan Ratliff (sratliff); 'Dearlove, Christopher (UK)'; 'manet'
>Cc: 'Thomas Heide Clausen (work)'
>ANY kind of ordering helps with both of these issues.  

Not sure I agree in all cases. Let's assume that we're ordering TLV's.
Also, 
let us assume that there exists some TLV with the lowest possible value.
Then 
let us assume that the TLV that invalidates the lowest-possible-value
TLV is 
assigned the highest possible value -- because it wasn't assigned at the
same 
time, was contained in new functionality, etc etc.   In this case,
having the TLV's 
ordered sill causes the perusal of all TLV's in order to find the
"invalidating event". 

Addition of new TLV's (complete with the possibility of invalidating
previous, 
existing TLV's) is the case I'm most concerned about when TLV ordering
is 
discussed. It places potential constraints on the numbering of future
TLV's, 
and that seems like an extremely difficult (if not impossible) thing to
manage 
to me. 

Regards,
Stan

>Having no order

---

From: "Justin Dean" <[email-masked]>
Date: Fri, 14 Sep 2007 17:31:03 -0400

Comments in line. 

> Sent: Friday, September 14, 2007 3:17 PM
> To: Justin Dean; Dearlove, Christopher (UK); manet
> >are two issues as I see it. Finding relevant TLVs to the 
> protocol doing
> the
> let us assume that the TLV that invalidates the 
> lowest-possible-value TLV is assigned the highest possible 
> value -- because it wasn't assigned at the same 
> ordered sill causes the perusal of all TLV's in order to find 
> the "invalidating event". 
> 
Yes having the "worst" order causes the same problems which arise from
having no order, all TLVs need to be read in before being processed.  I
would argue though that the wg could assign numbers with sufficient space
between initial tlv values where the "worst" order would not happen it just
would not be optimal.  

> Addition of new TLV's (complete with the possibility of 
> invalidating previous, existing TLV's) is the case I'm most 
> concerned about when TLV ordering is discussed. It places 
> potential constraints on the numbering of future TLV's, and 
> that seems like an extremely difficult (if not impossible) 
> thing to manage to me. 
> 
Invalidating previous TLVs with new non-similar ones would indeed cause
headaches.  An idea would be to have a order mapping to all TLV types.
Where this order mapping list would reside I do not know.  Also how to
update the ordering while continuing protocol functionality with previous
lists becomes an issue.  I don't think I like this idea as much as having
direct ordering on the types but I feel it would be better than having no
ordering or allowing protocols to decide ordering independently.  

Justin

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 14 Sep 2007 15:27:14 -0700

Hello Justin,

I have to report that I just do not see the
need for this TLV ordering constraint.

I have one sort of "nonexistence" proof.
I think I have been to _every_ [manet] meeting.
I have heard about dozens of protocols, most
of which you are probably also familiar.  The
four experimental routing protocols did not
exhibit the need for this ordering.  The dozens
of other protocols did not exhibit the need.
It was never raised as an issue for _years_.

So how come it's so important all of a
sudden to be _mandated_ for all future
[manet] protocols?

Well, the answer in my mind is that it is
_not_ so important as to be mandated in
the way that the packetbb authors are
claiming.

And, it is not important for any of the other
protocols in other working groups that use
such extensions.  There have been a lot of
them.  There is nothing that makes [manet]
protocols so different in this respect.  If it
is needed, why isn't is specified for DHCP
extensions or Mobile IP or OSPF or any
other IETF protocol??  Surely we cannot
claim to be so far ahead of every other
working group, to finally now see the need
for such processing constraints.

In fact, it does not even seem to be needed
for OLSR.  At least, when I looked at
RFC 3626, I did not find any text to impose
this mandate (or even recommend its use).

Regards,
Charlie P.

ext Justin Dean wrote:
>>> TLVs can be processed in the order they are received yes and in fact
>>>       
>> can be
>>     
>>> processed in any way independent on ordering within the packet.  That
>>>       
>> being
>>     
>>> said there may be TLVs which invalidate the processing of other TLVs.
>>>       
>> There
>>     
>>> processing and checking TLVs which may cause the message to 
>>>       
>> be ignored.
>>

---

From: "Justin Dean" <[email-masked]>
Date: Mon, 17 Sep 2007 10:40:42 -0400

IPv6 option headers do have ordering constraints.

IPv6 relevant text
   The
   contents and semantics of each extension header determine whether or
   not to proceed to the next header.  Therefore, extension headers must
   be processed strictly in the order they appear in the packet; a
   receiver must not, for example, scan through a packet looking for a
   particular kind of extension header and process that header prior to
   processing all preceding ones.

   The exception referred to in the preceding paragraph is the Hop-by-
   Hop Options header, which carries information that must be examined
   and processed by every node along a packet's delivery path, including
   the source and destination nodes.  The Hop-by-Hop Options header,
   when present, must immediately follow the IPv6 header.  Its presence
   is indicated by the value zero in the Next Header field of the IPv6
   header.

   If, as a result of processing a header, a node is required to proceed
   to the next header but the Next Header value in the current header is
   unrecognized by the node, it should discard the packet and send an
   ICMP Parameter Problem message to the source of the packet, with an
   ICMP Code value of 1 ("unrecognized Next Header type encountered")
   and the ICMP Pointer field containing the offset of the unrecognized
   value within the original packet.  The same action should be taken if
   a node encounters a Next Header value of zero in any header other
   than an IPv6 header. 

We are trying to do something a little bit different and more flexible than
this but they do mandate an order.  We are not mandating processing take
place in order, which will allow us to have imperfect ordering within the
packet.  Also deciding what to do with the packet when encountering an
unknown TLV is up to derived protocols.  

Justin

> From: Charles E. Perkins [mailto:[email-masked]] 
> Sent: Friday, September 14, 2007 6:27 PM
> To: ext Justin Dean
> Cc: 'manet'
> Subject: Re: [manet] packetbb constraints
> 
> 
> Hello Justin,
> 
> I have to report that I just do not see the need for this TLV 
> ordering constraint.
> 
> I have heard about dozens of protocols, most of which you are 
> probably also familiar.  The four experimental routing 
> protocols did not exhibit the need for this ordering.  The 
> dozens of other protocols did not exhibit the need.
> Well, the answer in my mind is that it is _not_ so important 
> as to be mandated in the way that the packetbb authors are claiming.
> 
> And, it is not important for any of the other protocols in 
> other working groups that use such extensions.  There have 
> been a lot of them.  There is nothing that makes [manet] 
> protocols so different in this respect.  If it is needed, why 
> isn't is specified for DHCP extensions or Mobile IP or OSPF 
> or any other IETF protocol??  Surely we cannot claim to be so 
> far ahead of every other working group, to finally now see 
> the need for such processing constraints.
> 
> In fact, it does not even seem to be needed for OLSR.  At 
> least, when I looked at RFC 3626, I did not find any text to 
> impose this mandate (or even recommend its use).
> 
> Regards,
> Charlie P.
> 
> 
> 
> ext Justin Dean wrote:
> > Comments in line. 
> >
> >   
> lowest-possible-value 
> >> TLV is assigned the highest possible value -- because it wasn't 
> >> assigned at the same
> > having no order, all TLVs need to be read in before being 
> processed.  
> > I would argue though that the wg could assign numbers with 
> sufficient 
> > space between initial tlv values where the "worst" order would not 
> > happen it just would not be optimal.
> >
> >   
> invalidating 
> >> previous, existing TLV's) is the case I'm most concerned 
> about when 
> >> TLV ordering is discussed. It places potential constraints on the 
> >> numbering of future TLV's, and that seems like an 
> extremely difficult 
> >> (if not impossible) thing to manage to me.
> >>
> >>     
> > Invalidating previous TLVs with new non-similar ones would indeed 
> > cause headaches.  An idea would be to have a order mapping 
> to all TLV types.
> > update the ordering while continuing protocol functionality with 
> > previous lists becomes an issue.  I don't think I like this idea as 
> > much as having direct ordering on the types but I feel it would be 
> > better than having no ordering or allowing protocols to 
> decide ordering independently.
> >
> > Justin
> >
> >
> >

---

From: Brian Haberman <[email-masked]>
Date: Mon, 17 Sep 2007 11:10:46 -0400

Justin,
      I am a little confused with your text below.  You start by 
mentioning IPv6 Option Headers and immediately quote text on extension 
headers.  The interesting text on extension headers is found in Section 
4.1 or RFC 2460, which states:

    When more than one extension header is used in the same packet, it is
    recommended that those headers appear in the following order:

            IPv6 header
            Hop-by-Hop Options header
            Destination Options header (note 1)
            Routing header
            Fragment header
            Authentication header (note 2)
            Encapsulating Security Payload header (note 2)
            Destination Options header (note 3)
            upper-layer header

Please note the use of recommended in this text.  It is not a hard and 
fast rule.

Further along, the section points out the following:

    If and when other extension headers are defined, their ordering
    constraints relative to the above listed headers must be specified.

This allows future extensions to be added and their position described 
relative to the recommended order.  The most interesting point, IMHO, is 
the last part of the section which states:

    IPv6 nodes must accept and attempt to process extension headers in
    any order and occurring any number of times in the same packet,
    except for the Hop-by-Hop Options header which is restricted to
    appear immediately after an IPv6 header only.  Nonetheless, it is
    strongly advised that sources of IPv6 packets adhere to the above
    recommended order until and unless subsequent specifications revise
    that recommendation.

This rule allows IPv6 to be liberal in what it receives in order to 
support implementations that did not follow the recommended ordering 
mentioned earlier.

Regards,
Brian

---

From: "Stan Ratliff \(sratliff\)" <[email-masked]>
Date: Mon, 17 Sep 2007 11:17:42 -0400

With the exception of the Hop-by-Hop header, 
I don't see this as an ordering constraint. With the
exception of that header, the text says that options
MUST be processed in whatever order they've 
been placed into the packet. It doesn't mandate 
ascending sequence of options. 

I don't see this as precedent for what is being 
proposed in packetbb.

Regards,
Stan

>Sent: Monday, September 17, 2007 10:41 AM
>To: 'Charles E. Perkins'
>Cc: 'manet'

---

From: "Justin Dean" <[email-masked]>
Date: Mon, 17 Sep 2007 12:36:29 -0400

I agree with a lot of what you have said here.  I posted the example more to
point out that there are protocols which have ordering (and with hop-by-hop
options mandated ordering) considerations and not to make a direct
comparison.  Although since they were raised a few comments in line. 

> From: Brian Haberman [mailto:[email-masked]] 
> Sent: Monday, September 17, 2007 11:11 AM
> To: Justin Dean
> Cc: 'Charles E. Perkins'; 'manet'
>       I am a little confused with your text below.  You start 
> by mentioning IPv6 Option Headers and immediately quote text 
> on extension headers.  The interesting text on extension 
> headers is found in Section
> Please note the use of recommended in this text.  It is not a 
> hard and fast rule.
> 
I actually suggested having an ordering independent of the type value fields
much the same way IPv6 proposes.  Ordering is not hard and fast rule with
IPv6 and processing in order is mandated.  I would rather mandate ordering
and allow for any kind of processing. 

> This allows future extensions to be added and their position 
> described relative to the recommended order.  The most 
> interesting point, IMHO, is the last part of the section which states:
> 

I am warming to this method for ordering although in my opinion it has the
need for the following restriction.

>     recommended order until and unless subsequent 

This rule is really required when ordering is not mandated or can be changed
by later specifications.  I my opinion this is drawback to IPv6's method as
all orders must be accepted, limiting processing optimizations.  Receivers
don't actually KNOW a TLV isn't there until the end of the TLV block.

> This rule allows IPv6 to be liberal in what it receives in 
> order to support implementations that did not follow the 
> recommended ordering mentioned earlier.
> 
> Regards,
> Brian
> 

In summary if we were to do a packetbb ordering setup similar to IPv6 I
would not be in favor of forced processing and any ordering but the exact
opposite or any processing and a fixed order.

   Therefore, extension headers must

Justin