Subject: Re: [Roll] Trickle clarification: (in)consistency

From: Phoebus Chen <[email-masked]>
Date: Tue, 01 Dec 2009 14:26:08 +0100

Hello,
	I've been following this mailing list for some time, and I thought I 
should chime in.  I'm hoping that the clarifications on Trickle in RPLv5 
will address my questions below, but please read on and give some comments.

I had a discussion with some other members in my research group on how
DAGs are constructed in RPL, and we were unclear about how the timing of
Trickle broadcasts would affect the choice of parents in the DAG.  As I
understand it, a node is suppose to choose the preferred parent from its
set of parents when it receives a RA-DIO message with a new DAG sequence
number.  This is because it needs to compute its rank to rebroadcast
(via Trickle) a new RA-DIO with it's new DAG rank.

Should the node choose a new preferred parent upon receiving the
*first* RA-DIO message with a new sequence number, or should it wait for
a prespecified amount of time for more RA-DIO messages with the same
sequence number from other potential parents?  Let me elaborate with 
three alternate approaches below.

1)
If the node chooses a preferred parent after hearing the first RA-DIO
message, it would be deciding on the preferred parent using cached data
(parents and associated metric + rank) associated with the previous
sequence number.  This seems to depart with the current line of
thinking, that inefficient DAGs (because of local routing loop repairs,
or a need to increase a node's rank so it has more parents, for example)
will be rebuilt cleanly when the DAG sequence number is incremented.

2)
If the node chooses to wait for a prespecified amount of time for more
RA-DIO messages from other potential parents, then the node's rank does
not need to depend on the ranks of neighboring nodes associated with an
older DAG sequence number.  However, this seems to depart from the way
Trickle was initially designed to operate.  Now, in addition to
Trickle's listen-only period, we would have another "silent" period
prepended to the first listen-only period of duration I_min/2.  This
silent period is another parameter to tune.  It would affect both the
performance of Trickle and the choice of parents in the DAG.  I would
also presume that all the nodes in the network should agree on one value
for the length of this silent period for this to work, and this length 
should also be carried within the DIO.

3)
Both alternatives described above assumes that for a given DAG sequence
number, a node cannot decide to change its rank after it has broadcast
an RA-DIO.  Another alternative is to allow a node to change its rank
multiple times (and reset the Trickle timer each time) during a single 
DAG iteration (the period of time when the DAG sequence number has not 
changed).  This seems to go against Pascal's recent suggestion on this 
thread, that the rank is not part of the consistency check for resetting 
the Trickle timer.  The consistency check would be against a cached 
value of the rank previously advertised by that neighbor for this DAG 
sequence number.

I tried looking at the CTP paper 
(http://sing.stanford.edu/pubs/sensys09-ctp.pdf) to see how they resolve
this, since it also runs into a similar situation when selecting the
best parent from all nodes it has heard before.  CTP does not use
sequence numbers, but "uses the routing cost gradient" (pg.3, Section
3.2) for consistency.  Thus, it seems most similar to the last approach
(approach #3, without sequence numbers).

I'm a bit nervous about this last approach, because now it sounds like
a node can increase its rank during the RA-DIO rebroadcasts in one DAG
iteration.  This could lead to loops... this was the whole purpose of
the DAG detach and merge mechanisms that were removed when going from 
RPLv3 to RPLv4.

Could someone comment on the three alternatives I described above? 
Which one is being used in the current RPL?  Is there another approach 
that I missed?  Or maybe this will all be clear in RPLv5? ;)

Phoebus Chen
Postdoctoral Researcher
Automatic Control Lab, KTH (Royal Institute of Technology)

> Hi Pascal, Jonathan,
> 
> Thanks for your answers. I think we agree that child and other nodes
> could play a role to detect a consistent situation. 
> Hence, we need to see how this affects the DIO processing rules as you
> actually typically don't process DIOs from node deeper than you in the
> DAG...
> I also agree with Pascal and Julien when they say that consistency
> should concentrate on global or common DAG information.
> 
> Best,
> Mathilde
> -----Original Message-----
> From: Pascal Thubert (pthubert) 
> Sent: lundi, 23. novembre 2009 08:55
> To: Julien Abeille (jabeille); 'Jonathan Hui'; Mathilde Durvy (mdurvy)
> Cc: 'roll at ietf.org'
> Subject: RE: [Roll] Trickle clarification: (in)consistency
> 
> Hi Julien
> 
> Seems to me that so far we are saying the same thing.
> 
> We'll be concentrating the DAG information in one option. That option
> should be consistent in an iteration. It should thus be subject to
> elision if it is redundant with C messages already heard during the
> trickle period. Other fields in the DIO might not be redundant though.
> My main concern is the routing information. My Rank is not my neighbor's
> Rank.
> 
> Pascal
> 
>>-----Original Message-----
>>From: Julien Abeille (jabeille)
>>Sent: dimanche 22 novembre 2009 22:55
>>To: Pascal Thubert (pthubert); Jonathan Hui; Mathilde Durvy (mdurvy)
>>Cc: roll at ietf.org
>>Subject: RE: [Roll] Trickle clarification: (in)consistency
>>
>>Hi Pascal,
>>
>>Not sure I understand your explanation. In a DIO there are informations
> 
>>that are global to the DAG and some that are node specific. We use 
>>trickle because we consider DIO sending a consitency problem, hence we 
>>focus on the global information. They come both from parents and
> childs, so I would also increment C when hearing from a child. Am I
> missing something?
>>
>>Julien
>>
>>> -----Original Message-----
>>> From: roll-bounces at ietf.org [mailto:roll-bounces at ietf.org] On Behalf 
>>> Of Pascal Thubert (pthubert)
>>> Sent: vendredi 20 novembre 2009 20:12
>>> To: Jonathan Hui; Mathilde Durvy (mdurvy)
>>> Cc: roll at ietf.org
>>> Subject: Re: [Roll] Trickle clarification: (in)consistency
>>>
>>> Hi Mathilde;
>>>
>>> I agree with Jonathan that we want to avoid redundancy.
>>>
>>> The rank of metric that a node advertises is an information about 
>>> self that cannot be inferred from the neighbors so it is *not* 
>>> redundant. If a number of nodes go down at the same time and one does
> 
>>> not advertise, then that node will look better and will attract the 
>>> traffic. It will also attract the neighbors that went down and that 
>>> will be tempted to reattach to that apparent survivor.
>>>
>>> The information in the DIO that relates to the DAG configuration will
> 
>>> be centralized in an option that IS redundant. We could add text that
> 
>>> a node that see C of it MAY filter it out from its DIO.
>>>
>>> Finally the new sequence is redundant. I proposed to use it to limit 
>>> the density of routers using trickle. When you hear C router 
>>> advertising a new sequence you are entitled to stop being a router 
>>> for that sequence (stop trickle timer). The trickle timer would then 
>>> be restarted upon a DIS to serve orphans, and upon a next sequence to
> 
>>> redistribute the load.
>>>
>>> Pascal
>>>
>>> >-----Original Message-----
>>> >From: roll-bounces at ietf.org [mailto:roll-bounces at ietf.org]
>>> On Behalf Of
>>> Jonathan Hui
>>> >Sent: vendredi 20 novembre 2009 16:41
>>> >To: Mathilde Durvy (mdurvy)
>>> >Cc: roll at ietf.org
>>> >Subject: Re: [Roll] Trickle clarification: (in)consistency
>>> >
>>> >
>>> >Hi Mathilde,
>>> >
>>> >On Nov 19, 2009, at 9:24 AM, Mathilde Durvy (mdurvy) wrote:
>>> >
>>> >>> - when do we increment C?
>>> >>
>>> >> The node MAY increment C when it hears another DIO.
>>> >>
>>> >> I think the spec says that a node MAY increment C each
>>> time it hears
>>> a
>>> >> "consistent DIO for this DAG from a DAG parent". What fields are 
>>> >> included in the consistency check? If only generic DAG information
>>> are
>>> >> checked you might want to look at DIO from non-DAG parents, no?
>>> >
>>> >You're right, this text in the draft is incorrect.  There's an 
>>> >important distinction to make here.  We want to quickly send DIO 
>>> >transmissions (reset the Trickle timer) whenever
>>> *inconsistencies* are
>>> >detected.  But you want to suppress DIO transmissions (increment C) 
>>> >whenever *redundancies* are detected.  While you can detect 
>>> >inconsistencies by listening to your DAG parent(s),
>>> redundancies will
>>> >probably come from your siblings/cousins.
>>> >
>>> >We are looking to update the text around incrementing C and
>>> make what
>>> >constitutes a redundancy more precise.
>>> >
>>> >--
>>> >Jonathan Hui
>>> >
>>> >_______________________________________________
>>> >Roll mailing list
>>> >Roll at ietf.org
>>> >https://www.ietf.org/mailman/listinfo/roll
>>> _______________________________________________
>>> Roll mailing list
>>> Roll at ietf.org
>>> https://www.ietf.org/mailman/listinfo/roll
>>>

---

From: Philip Levis <[email-masked]>
Date: Tue, 1 Dec 2009 09:50:01 -0800

On Dec 1, 2009, at 5:26 AM, Phoebus Chen wrote:

> Hello,
> 	I've been following this mailing list for some time, and I thought  
> I should chime in.  I'm hoping that the clarifications on Trickle in  
> RPLv5 will address my questions below, but please read on and give  
> some comments.
>
> for the length of this silent period for this to work, and this  
> length should also be carried within the DIO.
>
> 3)
> multiple times (and reset the Trickle timer each time) during a  
> single DAG iteration (the period of time when the DAG sequence  
> number has not changed).  This seems to go against Pascal's recent  
> suggestion on this thread, that the rank is not part of the  
> consistency check for resetting the Trickle timer.  The consistency  
> check would be against a cached value of the rank previously  
> advertised by that neighbor for this DAG sequence number.
>
>
> I tried looking at the CTP paper (http://sing.stanford.edu/pubs/sensys09-ctp.pdf 
> ) to see how they resolve
> the DAG detach and merge mechanisms that were removed when going  
> from RPLv3 to RPLv4.
>
> Which one is being used in the current RPL?  Is there another  
> approach that I missed?  Or maybe this will all be clear in RPLv5? ;)

We're hoping that the -05 text will clarify this.

The basic answer is none of the above. :) A node can decrease its Rank  
within an iteration at any time (following rank computation rules):  
the constraint is on when it can increase its Rank.

The rule is that all of a node's parent set must have the same  
sequence number. So after hearing one neighbor with a higher sequence  
number, a node may wait before becoming part of the next iteration, or  
could do so immediately. It's probably better to wait a little bit, as  
once the node has become part of the next iteration, it can't go back:  
having only one parent is a bit risky (unless it's the DODAG root   
with a high quality link).

Phil

---

From: Phoebus Chen <[email-masked]>
Date: Tue, 01 Dec 2009 20:14:31 +0100

Phil,

	(comments below)

> with a high quality link).

Thanks for responding.  Hmm, what you're describing sounds like
approach #2 that I outlined above, except you allow a node to decrease
rank at any time (oops, I forgot about that part of the draft) and that
you do not impose the restriction that all nodes wait for the same
prespecified 'silent period' before computing the rank (I can't think of
a better name for now, so I'll continue to refer to this as the 'silent
period' below).  Focusing on the second point, this sounds like it will
be tricky for a node to decide how long to wait before computing its
rank based on RA-DIO messages it has heard thus far --- The node doesn't
know how long the other nodes are waiting.  And you can't just wait till
all your neighbors compute their rank... some of them may want to be
your children.

I agree with you that there's a tradeoff between how long it takes to
build the next DAG and how good of a DAG you build.  Generally, a node
would want to wait longer to see if more of its neighbors join the DAG,
giving it a larger set of nodes ('potential parents') to choose parents
from.  I guess the DAG build time is less relevant if you can continue 
using your old DAG.

One approach to sidestep choosing a fixed "silent period" is for a node
to just wait till there are enough potential parents so that its metric
is "good enough", i.e. greater than a threshold. But this threshold
should probably drop over time. With a fixed threshold, you may have a 
situation where a group of nodes decide never to join the DAG because 
the first node in the group that joins would have a low or moderate 
metric. Determining how such a threshold drops over time is again a 
coordination and timing issue. Maybe I'm thinking too far ahead --- 
perhaps it's OK to have a fixed threshold and a partitioned network in 
these situations; if it's some sort of reliability or connectivity 
metric you can just deploy more relay nodes.

I'm wondering how Trickle performs differently if nodes could choose
their own 'silent period'... maybe RPL should bound how long nodes can
wait before computing their ranks?

Anyhow, I'll wait for RPLv5 to see how this all works out.  I wanted to
get my concerns on the table, in case this turns out to be an issue.

Phoebus Chen
Postdoctoral Researcher