Subject: Re: [Roll] DAG hop timers

From: Mukul Goyal <[email-masked]>
Date: Sat, 10 Oct 2009 11:32:02 -0500 (CDT)

Pascal

Now that we agree on having just one DAG hop timer, here is a further suggestion:

Right now, the DAG hop timer is scheduled to fire after a delay that is proportional to the rank of the candidate parent (lets call it rank) whose RA-DIO triggers the starting of the timer.

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.

So, node A can expect to receive an RA-DIO from a neighbor within few multiples of I_min if that neighbor was in its sub-DAG. So, I would think that DAG hop timer value should be a safe multiple of I_min (independent of the dag rank of the candidate parent).

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

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.

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.

What do folks think?

Thanks
Mukul

PS: I am not implying that DAG hop timers should be in base specs. I believe that this feature is a useful OPTION. 

----- 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: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 12 Oct 2009 09:21:31 +0200

Hi Mukul:

>Right now, the DAG hop timer is scheduled to fire after a delay that is proportional to the rank of the
>candidate parent (lets call it rank) whose RA-DIO triggers the starting of the timer.

Correct, though another consequence of making the rank decimal should be that the timer should really depend on self's final rank.

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

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.

>So, node A can expect to receive an RA-DIO from a neighbor within few multiples of I_min if that neighbor was
>in its sub-DAG. So, I would think that DAG hop timer value should be a safe multiple of I_min (independent of
>the dag rank of the candidate parent).
>

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

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

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

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.

Cheers,

Pascal