Subject: [Roll] DIS information filter

From: Philip Levis <[email-masked]>
Date: Fri, 2 Apr 2010 10:01:22 -0700

(Trying to restart the thread)

In -07, nodes always respond to DIS messages by resetting their Trickle timers. A few people on the list have pointed out that this is problematic. If an environment has multiple RPL instances, for example, when a node solicits information it must do so from *all* instances, even if it knows the one it wants to join.

The basic issue is that a node may wish to solicit DIOs from only a subset of nodes; it's wasteful to force a lot of nodes to reset their trickle timers unnecessarily.

I propose that we add a new suboption to RPL, which is only valid for DIS messages. The Solicited Information Filter suboption specifies a set of predicates; if a node satisfies the predicates, it MUST reset its timer in response to the message. If it does not satisfy the predicates, it MUST NOT reset its timer in response to the message.

The trick is to make this a simple, fixed-length suboption; forcing nodes to parse all kinds of suboptions is problematic in terms of code size. Similarly, we'd like the suboption to cover the compelling cases but not be so complete that it wastes space on useless fields. So the question is: what information do nodes want to filter on?

The one that immediately comes to mind is a DODAG Iteration: this would imply the RPLInstanceID, Sequence, and DODAGID. 

There have been a few mentions of Rank. I personally think it makes more sense to handle this through trickle suppression (you generally want low-Rank messages more than high-Rank ones), but this seems like a good point of discussion.

So my current proposal is that the Solicited Information Suboption has the following format:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |   Type = 5    |    Reserved   |   Sequence    | RPLInstanceID |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      +                                                               +
      |                            DODAGID                            |
      +                                                               +
      |                                                               |
      +                                                               +
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Furthermore, we should reserve values for Sequence, RPLInstanceID, and DODAGID as wildcards ("any value matches"). This would indicate that such values can't be used normally. Alternatively, the reserved region could have bits stating which of the three fields to match on.

Thoughts?

Phil

---

From: Jonathan Hui <[email-masked]>
Date: Fri, 2 Apr 2010 10:35:28 -0700

The assumption (which you stated) is that there are a number of  
instances and overlapping DODAGs.  If you have neither, then I'm not  
sure there is much value in scoping to a particular DODAG Iteration  
(instance, sequence, id).  For the highly constrained networks that  
I'm familiar with, the number of instances is small and the number of  
overlapping DODAG IDs is also small.  In many cases, both are 1.  In  
some cases, maybe 2.  Instead, the concern is usually with node density.

If large numbers of instances and overlapping DODAGs is a concern to  
some then I can see this useful.  Of course, an additional assumption  
here is that a node would prefer to stay within the same DODAG.  To  
complete the picture, we'd also need to think through how exactly to  
use the filter.  One obvious use case is for a node to start with a  
small scope, then expand the scope by setting wildcards when discovery  
fails.  The question is how best to indicate what is the intended  
behavior - does this need to be network-wide (e.g. through some config  
option in the DIO), something that is part of the OCP, or something  
completely node/implementation independent?

Minor comments: Type 5 is taken by the OCP option.  I'd prefer to use  
flags to indicate what parameters are in use.

--
Jonathan Hui

On Apr 2, 2010, at 10:01 AM, Philip Levis wrote:

> In -07, nodes always respond to DIS messages by resetting their  
> Trickle timers. A few people on the list have pointed out that this  
> is problematic. If an environment has multiple RPL instances, for  
> example, when a node solicits information it must do so from *all*  
> instances, even if it knows the one it wants to join.
>
> The basic issue is that a node may wish to solicit DIOs from only a  
> subset of nodes; it's wasteful to force a lot of nodes to reset  
> their trickle timers unnecessarily.
>
> I propose that we add a new suboption to RPL, which is only valid  
> for DIS messages. The Solicited Information Filter suboption  
> specifies a set of predicates; if a node satisfies the predicates,  
> it MUST reset its timer in response to the message. If it does not  
> satisfy the predicates, it MUST NOT reset its timer in response to  
> the message.
>
> The trick is to make this a simple, fixed-length suboption; forcing  
> nodes to parse all kinds of suboptions is problematic in terms of  
> code size. Similarly, we'd like the suboption to cover the  
> compelling cases but not be so complete that it wastes space on  
> useless fields. So the question is: what information do nodes want  
> to filter on?
>
> The one that immediately comes to mind is a DODAG Iteration: this  
> would imply the RPLInstanceID, Sequence, and DODAGID.
>
> There have been a few mentions of Rank. I personally think it makes  
> more sense to handle this through trickle suppression (you generally  
> want low-Rank messages more than high-Rank ones), but this seems  
> like a good point of discussion.
>
> Furthermore, we should reserve values for Sequence, RPLInstanceID,  
> and DODAGID as wildcards ("any value matches"). This would indicate  
> that such values can't be used normally. Alternatively, the reserved  
> region could have bits stating which of the three fields to match on.
>
> Thoughts?
>
> Phil
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Philip Levis <[email-masked]>
Date: Fri, 2 Apr 2010 12:19:43 -0700

On Apr 2, 2010, at 10:35 AM, Jonathan Hui wrote:

> 
> The assumption (which you stated) is that there are a number of instances and overlapping DODAGs.  If you have neither, then I'm not sure there is much value in scoping to a particular DODAG Iteration (instance, sequence, id).  For the highly constrained networks that I'm familiar with, the number of instances is small and the number of overlapping DODAG IDs is also small.  In many cases, both are 1.  In some cases, maybe 2.  Instead, the concern is usually with node density.

Agreed -- trickle suppression should handle the node density (until link-layer collapse). I think the intention is that this suboption is not necessarily used that often, but that there will be situations where it's helpful.

> 
> If large numbers of instances and overlapping DODAGs is a concern to some then I can see this useful.  Of course, an additional assumption here is that a node would prefer to stay within the same DODAG.  To complete the picture, we'd also need to think through how exactly to use the filter.  One obvious use case is for a node to start with a small scope, then expand the scope by setting wildcards when discovery fails.  

Makes sense. But let's also think about when a node might want to do this. When a node comes up, it can't really use the filters, as it doesn't know what values are in use (unless there's prior configuration, but that's going to be difficult given the nature of the fields). Things like pre-initialized keys (as is common for secure LLNs) can also scope the query/response.

The information filter is useful when a node that has been operating in RPL network needs additional DIOs from neighbors. E.g., its current parent set may all have issued NUDs so it wants to trigger discovery. I'd argue that exactly the order a node goes through in relaxing predicates isn't too important, and standardization probably isn't necessary. Some nodes might just default to all wildcards: others might try Sequence, DODAGID, then RPLInstance. 

> The question is how best to indicate what is the intended behavior - does this need to be network-wide (e.g. through some config option in the DIO), something that is part of the OCP, or something completely node/implementation independent?

I think implementation dependent is fine.

> 
> Minor comments: Type 5 is taken by the OCP option.  I'd prefer to use flags to indicate what parameters are in use.

Grazie.

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 5 Apr 2010 10:58:04 +0200

Hi Phil:

I'm in, agreement with everything you said below. But one thing where
you lost me.

I understood that you were advocating for simplicity and not using an
option for something that's really basic/core, thus my post on another
thread before I saw this where those parms make the DIS message itself.
I tend to prefer the simplicity in this case.

For me an option is good for: 
- something that's used only when an optional behavior applies. For
instance OF specific suboptions.
- something that does not need to be repeated in all messages. Like OF
parms.
- something that might be repeated multiple times in a message. For
instance I think that the target of a DAO should be an option so we can
have multiple of them in one message
- something that might be used in multiple types of messages. The target
I mentioned above could be useful in DIO for stimulated repair, incoming
request and P2P as already discussed in the ML.

So, I agree with accepting options in DIS, I'm just unclear whether your
proposal is an option or mostly the base DIS.

Votes?

Pascal

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
Of
> Philip Levis
> Sent: Friday, April 02, 2010 7:01 PM
> To: ROLL WG
> Subject: [Roll] DIS information filter
> 
Trickle
> timers. A few people on the list have pointed out that this is
problematic. If
> an environment has multiple RPL instances, for example, when a node
> solicits information it must do so from *all* instances, even if it
knows the
> one it wants to join.
subset of
> nodes; it's wasteful to force a lot of nodes to reset their trickle
timers
> unnecessarily.
> 
> I propose that we add a new suboption to RPL, which is only valid for
DIS
> messages. The Solicited Information Filter suboption specifies a set
of
> predicates; if a node satisfies the predicates, it MUST reset its
timer in
> response to the message. If it does not satisfy the predicates, it
MUST NOT
> reset its timer in response to the message.
> 
nodes to
> parse all kinds of suboptions is problematic in terms of code size.
Similarly,
> we'd like the suboption to cover the compelling cases but not be so
complete
> that it wastes space on useless fields. So the question is: what
information do
> nodes want to filter on?
would
> imply the RPLInstanceID, Sequence, and DODAGID.
> 
more
> sense to handle this through trickle suppression (you generally want
low-
> Rank messages more than high-Rank ones), but this seems like a good
point
> of discussion.
> 
> So my current proposal is that the Solicited Information Suboption has
the
> following format:
>       |
|
>       +
+
>       |                            DODAGID
|
>       +
+
>       |
|
>       +
+
>       |
|
> 
> Furthermore, we should reserve values for Sequence, RPLInstanceID, and
> DODAGID as wildcards ("any value matches"). This would indicate that
such
> values can't be used normally. Alternatively, the reserved region
could have
> bits stating which of the three fields to match on.
> 
> Thoughts?
> 
> Phil

---

From: JP Vasseur <[email-masked]>
Date: Mon, 5 Apr 2010 11:35:05 +0200

Hi,

There is golden rule for deciding this, mostly common sense. The  
reason why I would
argue for a sub-option in this case is that we may need other ones in  
the future. It
might not be needed in some cases, and we may need more in other  
cases, a good
reason for using options in my opinion.

Thanks.

JP.

On Apr 5, 2010, at 10:58 AM, Pascal Thubert (pthubert) wrote:

>> and

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 5 Apr 2010 11:43:29 +0200

JP:

I agree with allowing options and eventually suboptions (since we
migrated out of ND messages, the so-called suboptions are really
options, we need to fix that) in all RPL messages.

This does not mean that everything has to be options. Same goes for DIO,
would you make everything in the base header an option?

OTOH, in the current spec, the target in a DAO is not an option. This
prevents from packing multiple targets in a single DAO, which is really
sad in the stateful mode. 

I agree with good sense as long as it is really common. 

Pascal

> From: JP Vasseur [mailto:[email-masked]]
> Sent: Monday, April 05, 2010 11:35 AM
> To: Pascal Thubert (pthubert)
> Cc: Philip Levis; ROLL WG
> Subject: Re: [Roll] DIS information filter
> 
> Hi,
> 
reason why
> I would argue for a sub-option in this case is that we may need other
ones in
> the future. It might not be needed in some cases, and we may need more
in
> other cases, a good reason for using options in my opinion.
> 
> Thanks.
> 
> JP.
> 
> > instance I think that the target of a DAO should be an option so we
> > can have multiple of them in one message
> > - something that might be used in multiple types of messages. The
> > target I mentioned above could be useful in DIO for stimulated
repair,
> > incoming request and P2P as already discussed in the ML.
> >
> > So, I agree with accepting options in DIS, I'm just unclear whether
> > your proposal is an option or mostly the base DIS.
> >
> > Votes?
> >
> > Pascal
> >
> >
for
> >>      |   Type = 5    |    Reserved   |   Sequence    |
RPLInstanceID
> >> that

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 5 Apr 2010 11:53:12 +0200

Hi again JP:

What about this to clearly indicate that all RPL messages have the same
construct:

"
.  ICMPv6 RPL Control Message

   This document defines the RPL Control Message, a new ICMPv6 message.
   A RPL Control Message is identified by a code, and composed of a base
   that depends on the code, and a series of options.

   A RPL Control Message has the scope of a link.  The source address is
   a link local address.  The destination address is either all routers
   multicast address (FF02::2) or a link local address.

   In accordance with [RFC4443], the RPL Control Message has the
   following format:

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Type      |     Code      |          Checksum             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
                               Base                                    |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
                               Option(s)...
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                       Figure 5: RPL Control Message

   The RPL Control message is an ICMPv6 information message with a
   requested Type of 155.

   The Code field identifies the type of RPL Control Message.  This
   document defines three codes for the following RPL Control Message
   types:

   o  0x01: DODAG Information Solicitation (Section 5.1)

   o  0x02: DODAG Information Object (Section 5.2)

   o  0x04: Destination Advertisement Object (Section 5.3)
"

Then:
"
5.4.  RPL Control Message Options

   A RPL message is composed of a main body that depends on the message,
   and that may be followed by options.  All options but the Pad1 follow
   the same format:

        0                   1                   2
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -
       |  Option Type  |       Option Length           | Option Data
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -

                Figure 9: RPL message option Generic Format

Winter, et al.          Expires September 9, 2010              [Page 28]

Internet-Draft           draft-ietf-roll-rpl-07               March 2010

   Option Type:  8-bit identifier of the type of option.

   Option Length:  16-bit unsigned integer, representing the length in
         octets of the option, not including the option Type and Length
         fields.

   Option Data:  A variable length field that contains data specific to
         the option.

   When processing a RPL message containing an option for which the
   Option Type value is not recognized by the receiver, the receiver
   MUST silently ignore the unrecognized option and continue to process
   the following Options, correctly handling any remaining options in
   the message.

   RPL message options may have alignment requirements.  Following the
   convention in IPv6, options with alignment requirements are aligned
   in a packet such that multi-octet values within the Option Data field
   of each option fall on natural boundaries (i.e., fields of width n
   octets are placed at an integer multiple of n octets from the start
   of the header, for n = 1, 2, 4, or 8).

   This document defines the following RPL Message options:

   Pad1  1-octet padding, for use in all RPL messages.

   Padn  n-octets padding, for use in all RPL messages.

   Metric Container  To report path characteristics, for use in DIO
         messages.

   Destination Prefix  To indicate a internal or external prefix, for
         use in DIO messages.

   DODAG Configuration  To pass DODAG parameters, for use in DIO
         messages.

   This section describes the format of DIO options and the five options
   this document defines: Pad 1, Pad N, DAG Metric Container, DAG
   Destination Prefix, and DAG Configuration.
"
Cheers,

Pascal

> From: Pascal Thubert (pthubert)
> Sent: Monday, April 05, 2010 11:43 AM
> To: 'JP Vasseur'
> Subject: RE: [Roll] DIS information filter
> 
> JP:
> 
migrated
> out of ND messages, the so-called suboptions are really options, we
need to
> fix that) in all RPL messages.
> 
prevents
> from packing multiple targets in a single DAO, which is really sad in
the
> stateful mode.
> > reason why I would argue for a sub-option in this case is that we
may
> > need other ones in the future. It might not be needed in some cases,
> > and we may need more in other cases, a good reason for using options
in
> my opinion.
> > > I'm in, agreement with everything you said below. But one thing
> > > where you lost me.
> > >
> > > I understood that you were advocating for simplicity and not using
> > > an option for something that's really basic/core, thus my post on
> > > another thread before I saw this where those parms make the DIS
> > > message itself.
> > > - something that does not need to be repeated in all messages.
Like
> > > OF parms.
> > > repair, incoming request and P2P as already discussed in the ML.
> > >
> > >> So my current proposal is that the Solicited Information
Suboption
> > >> has
> > >>       0                   1                   2
3
> > >>       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0
> > >> 1
RPLInstanceID

---

From: Henning Rogge <[email-masked]>
Date: Mon, 5 Apr 2010 12:04:03 +0200

>    multicast address (FF02::2) or a link local address.
Just as a comment, the IANA has reserved a linklocal multicast address for 
manet routers (see RFC 5498), maybe this address (ff02::6d) would be useful in 
the Ripple context too.

Henning Rogge

-- 
1) You can't win.
2) You can't break even.
3) You can't leave the game.
— The Laws of Thermodynamics, summarized

---

From: Philip Levis <[email-masked]>
Date: Mon, 5 Apr 2010 10:11:47 -0700

> I agree with good sense as long as it is really common. 

Sure -- but there is zero evidence that these filters or flags that are in your proposal are very common fields that will almost-always be present or really commonly used. Seems like it increases complexity for a *possible* need. I think the possibility is great enough to call for including the suboption, but not so great to require it in all messages.

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 5 Apr 2010 20:31:42 +0200

Hi Henning:

Good to hear from you :)

Do you think we can safely share the MANET mcast address? Or maybe should we define all-rpl-routers?

Cheers,

Pascal

> From: Henning Rogge [mailto:[email-masked]]
> Sent: Monday, April 05, 2010 12:04 PM
> To: [email-masked]
> Cc: Pascal Thubert (pthubert); JP Vasseur
> manet routers (see RFC 5498), maybe this address (ff02::6d) would be useful
> in the Ripple context too.
> 
> Henning Rogge
> 
> --
> 1) You can't win.
> 2) You can't break even.

---

From: Henning Rogge <[email-masked]>
Date: Mon, 5 Apr 2010 21:35:41 +0200

> we define all-rpl-routers?
I don't see any problem using the address. In my oppinion Ripple is a MANET 
protocol, it has a different focus than stuff developed in the ietf manet 
group, but that's not really important.

The IANA allocation of the RFC I was talking about contains the multicast 
group (linklocal manet routers) and a port for packetbb. I don't see any 
reason why other similar protocols should not use the same IP but another 
port.

Henning Rogge

---

From: JP Vasseur <[email-masked]>
Date: Tue, 6 Apr 2010 12:15:05 +0200

Hi,

> would you make everything in the base header an option?

Sure, I do agree.

> I agree with good sense as long as it is really common.

Agree.

JP.

> where
> an

---

From: JP Vasseur <[email-masked]>
Date: Wed, 14 Apr 2010 10:21:29 +0200

So just to make sure that we came to a conclusion. There is a good  
consensus to say that there
are situations where such filter could be useful, thus the DIS format  
in rev-08 will be changed for
an empty body that could potentially carry TLV, with no TLV defined  
for the time being.

Cheers.

JP.