Subject: Re: [Roll] DAG hop timers

From: Mukul Goyal <[email-masked]>
Date: Mon, 5 Oct 2009 09:56:31 -0500 (CDT)

Pascal

This sounds good.

Cheers
Mukul
----- Original Message -----
From: "Pascal Thubert (pthubert)" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Monday, October 5, 2009 9:33:27 AM GMT -06:00 US/Canada Central
Subject: RE: DAG hop timers

Hi Mukul,

Yes, that is conceptually identical. There's a real need for one timer per DAG that the node might want to jump onto. 

When a timer elapses, the node joins the best position that it knows of in the new DAG. That can be done because regardless of the candidate parent for which the timer fired that just elapsed, the node is now allowed to join that DAG. Since moving inwards can be done without delay the node can pick the best position it sees right away.

Pascal

>-----Original Message-----
>From: Mukul Goyal [mailto:[email-masked]]
>Sent: samedi 3 octobre 2009 20:45
>To: Pascal Thubert (pthubert)
>Cc: roll
>Subject: DAG hop timers
>
>Hi Pascal
>
>Current RPL specs require a separate DAG hop timer for each neighbor in held_up state. All these timers are
>stopped as soon as one of the timers fires. There is no guarantee that the timer for the neighbor with minimum
>rank will fire first. If the timer for some other neighbor fires first, the node will have to wait for next RA
>from minimum-rank neighbor to include it as a parent.
>
>How about running just one timer. When a neighbor with lower rank is discovered, the current timer is stopped
>and restarted with a delay proportional to this lower rank. This ensures that the neighbor with lowest rank
>will be chosen as parent. Also, only one timer will be required.
>
>Thanks
>Mukul

---

From: Mukul Goyal <[email-masked]>
Date: Mon, 12 Oct 2009 14:49:31 -0500 (CDT)

Hi Pascal,

Please see inline.

>>DAG hop timer value = random number between rank*DagDelay and (rank+1)*DagDelay
>>
>>If DAG hop timer is expected to help in loop avoidance, the node (say A) should generate a new RA-DIO
>>advertising its own floating DAG when it starts the DAG hop timer. All the children nodes will hopefully
>>receive this RA-DIO and decide whether to kick node A out of the parent set or leave the current DAG and join
>>A's floating DAG. As soon as they make this decision, they will generate their RA-DIO either immediately or
>>within I_min interval, where I_min is the minimum trickle timer value. So, the nodes at level 'n' in A's sub-
>>dag are expected to generate new RA-DIOs within n*I_min interval.

>I suspect that could be done but I'm unsure what is improved by the proposed change. Do you think >that this would save churn or battery? 

I am suggesting making DAG hop time independent of the dag rank of the nodes. It will allow DAG rank increase operations (if you dont want to depend on new seqno from root) to take place in a shorter and more predictable time frame. But, I am not trying to reduce churn or increase the battery life.

>With the current spec, if the node A still has a forwarding path along the current DAG, it is >UNSTABLE and refrains from saying anything. So packets keep flowing along the current DAG whereas >detaching also would mean no packet forwarding till jump. When it jumps, A advertises its new >position and node in the sub-DAG that wish to follow can do so immediately and without a loop. One >could think of having a timer there too but one rationale is (again) to avoid packet loss so the >slight risk of churn is accepted.

I think there is some communication gap here. If node A does not detach itself from the dag before increasing its rank, it may end up choosing a node in its sub-dag as its parent, thereby creating a loop. So, it seems to me that detaching from the dag is must before increasing one's rank (unless rank is increased on receiving a newer seqno).

But the need to quickly increase the rank is another justification to make DAG hop time independent of the rank.
   
>>I understand that the decision to make DAG hop timer value proportional to candidate parent's rank was
>>influenced by the desire to:
>>1) make a node join the DAG at minimum possible rank and
>>2) allow nodes at lower rank to join before the nodes at higher rank

>Correct. As a side effect, it also covers the (trickled) spreading of a detaching RA, at least >over line of sight.

Not sure what you meant. Please elaborate.

>>If we are not resetting the DAG hop timer every time we come to know of a lower ranked candidate, we already
>>agreed to give up on the second objective above.

>I'm not seeing you here. We agreed that there's a practical need for only one timer per target DAG >though the spec describes that as one timer per parent. If the a new candidate pops up that would >be get this node to a shorter rank with a shorter timer, an implementation that uses only one >timer must emulate that by shortening the existing timer duration.

OK. So I misunderstood you earlier. You were indeed supporting that a node restart its DAG hop timer on finding a candidate with smaller rank.

>>
>>If we make DAG hop timer value a safe multiple of I_min (independent of the dag rank of the candidate parent
>>that cause the timer to start), objective (1) above is still achievable to roughly the same degree as with
>>current way of setting up DAG hop timer.
>>

>This might be true. I could buy that this works independently of the discussion above. 
>But keep in mind that the main objective is to reduce churn. Your points 1) and 2) are the >strategy to remove the churn, not the goal to be achieved.

>With the timer, the new shape of the resulting DAG spreads out like a wave. 

Again, please explain in more details what you mean by "DAG spreads out like a wave". Sorry for asking for too many explanations!

>You're in a great position to simulate the churn with and without the dag hop timer. 
>I think that this would be a key data to enable an informed decision for the running poll.

I am going to simulate the following 3 ways of joining a new DAG (which also covers the case where a node detaches from the old dag in order to join it at a higher rank):

1) wait for new seqno from root
2) do not wait for new seqno but use dag hop timer:
a) where dag hop time is proportional to candidate's rank (and dag hop timer restarts when a node comes to know of a lower rank candidate)
b) where dag hop time is fixed (few multiples of I_min)

Performance metrics would be number of control messages (RA-DIOs) generated by the node and its children in the old sub-dag and the overall delay in the process. I have to think more carefully about the simulation scenarios.

Thanks
Mukul