Subject: [Roll] Delays involved in various DAG operations

From: Mukul Goyal <[email-masked]>
Date: Wed, 30 Sep 2009 16:21:21 -0500 (CDT)

Hi all,

I did an analysis of delays involved in various DAG operations making certain assumptions. I hope this is useful. I will be thankful if you could point out errors in the analysis.

Thanks
Mukul

Time required for a node to join a DAG:
---------------------------------------
If the node chooses candidate parents after an evaluation period: 
The time required for a node to evaluate a neighbor node and elevate it to candidate parent status is policy-dependent. Once the node has identified a bunch of candidate parents, it can choose some of them as parents and hence join the DAG immediately.

If the node chooses the candidate parents without any evaluation and DAG hop timers are used: 
As soon as the node comes to know of a neighbor advertizing the DAG it wants to join, it elevates the neighbor to candidate parent status and starts a DAG hop timer for this neighbor. If the neighbor's rank in the DAG is 'd', the DAG hop timer is set to fire some time between d*DAG_Delay and (d+1)*DAG_Delay. While this timer is running, the node starts additional DAG hop timers for any additional candidate parents it encounters. The node joins the new DAG as soon as one of the DAG hop timers fire. The hope is that the DAG hop timer for the candidate parent with minimum rank will fire first.

If the node chooses the candidate parents without any evaluation and DAG hop timers are not used: 
As soon as the node comes to know of a neighbor advertizing the DAG, it joins the DAG via this neighbor.

Time required for a node in the DAG to reach its minimum rank:
--------------------------------------------------------------

Assuming that:
1) neighbors are elevated to candidate parents status as soon as their RA-DIOs are received
2) DAG rank increments are 1
3) redundancy counter in trickle timer does not affect RA generation

If DAG hop timers are not used: 

A node will join the DAG as soon as it hears its first RA from a neighbor. It also schedules an RA to be sent after time ra_delay in {I_min/2, I_min} range. As it hears from a neighbor with a better rank, it improves its own rank and again schedules to send its RA after time ra_delay in {I_min/2, I_min} range. Now, suppose that the DAG root originates its RA at time 0. The level 1 nodes will achieve their minimum rank (1) at time 0 on receiving the RA from the DAG root. Level 1 nodes will generate their RAs at times between I_min/2 and I_min and hence level 2 nodes will achieve their minimum rank (2) at a time uniformly distributed between I_min/2 and I_min. Thus, a level 'n' node will achieve its minimum rank in the DAG at a time t(n) that is sum of (n-1) random variables (ra_delay) where each ra_delay is independent and uniformly distributed in range {I_min/2, I_min}:

t(1) = 0
t(n) = sum_{over i = 1 to n-1}(ra_delay),  for n > 1

If DAG hop timers are used: 

Level 1 nodes receive their RAs from DAG root at time 0 and join the DAG after DAG hop delay between 0 and DAG_delay. Then, they schedule RA to be sent after some time between I_min/2 and I_min. Thus, at each level the delay is DAG hop delay + delay in generating the RA. Let dag_hop_delay(i) be the dag hop delay for the node at level i+1. Then dag_hop_delay(i) is a random variable uniformly distributed between {i*dag_delay, (i+1)*dag_delay}. Let ra_delay be a random variable unformly distributed in range {I_min/2, I_min}. Then, a node at level 'n' will achieve its minimum rank in the DAG at a time t(n) that is sum of (2n-1) random variables - n dag hop delays and (n-1) ra_delays:

t(1) = dag_hop_delay(0)
t(n) = sum_{over i = 0 to n-1}(dag_hop_delay(i)) + sum_{over i = 1 to n-1}(ra_delay), for n > 1

Time required for a node to decrease its rank in a DAG:
------------------------------------------------------
No delay

Time required for a node to increase its rank in a DAG:
------------------------------------------------------
Wait for the candidate parent(s) to increase the sequence number. Optionally wait for the DAG hop timer to fire in order to join the parent with minimum rank. RPL specs leaves it to DAG root to decide when to increment the sequence number.

Time required for a node to know of a change above:
---------------------------------------------------
Suppose the change causes each node to reset its trickle timer. Thus, each node will generate its RA ra_delay after detecting the change. Suppose the change is first detected by a node at time 0. So, if a node is at level 'n' in the sub-DAG of the node that detected the change first, it will detect the change (on receiving the RAs from its parents) at time t(n) that is sum of n random variables uniformly distributed in range {I_min/2,I_min}:

t(n) = sum_{over i = 1 to n}(ra_delay)

Time required for a node to know of a change below:
---------------------------------------------------
Any change in the prefix reachability in the sub-DAG is intimated to the node via NA-DAOs.
RPL draft specifies two ways of triggering NA-DAOs:
1) A node can send an RA-DIO to its children with the `D' destination advertisement bit set. This would cause the children to send it NA-DAOs after the DelayNA delays.
2) If the node's RA-DIOs have the Destination Advertisement Supported (A) bit set, then children send it NA-DAOs: a) once it has been added to the DA parent set; b)when the list of advertised prefixes has changed; c) (optionally) when the PathDigest of the node's RA-DIO message has changed. It is not clear from the draft whether these NA-DAOs are sent immediately or after DelayNA delay.

So, every change in the set of advertized prefix would trigger NA-DAO to be sent to the selected parent nodes. 

Now, lets consider the specific case of the loss of a prefix. A node can detect the loss of a prefix by two methods:
1) life time of the prefix, as specified in the DAO (or no-DAO), expires;
2) the node times out the prefix (presumably with infinite/large life time). This time out requires the node to count how many RA-DIOs it has generated without receiving any NA-DAO about this prefix. Once the number of such RA-DIOS reaches a threshold (say m), the node starts the RemoveTimer and the firing of this timer causes the prefix to be moved to the Unreachable list.

So, the time required for a node to detect the loss of a prefix is min(lifetime, time required to send 'm' RIOs + the time for RemoveTimer to fire). The time required to send 'm' RIOs depends on trickle timer values etc. Lets assume that no-DAO method is generally successful and the timeout method is rarely required.

Once the loss of prefix has been detected by a node 'n' levels below me, I will receive the no-DAO about it:
1) within a short time if the intermediate nodes do not use DelayNA delays before sending the no-DAO upwards; or
2) after (1/k)*DEF_NA_LATENCY*(1/(d+1) + 1/(d+2) +...+ 1/(d+n)) where 'd' is my DAG rank and 'k' is the multiple used in deciding DelayNA delay (=DEF_NA_LATENCY/(k*rank)).

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 30 Sep 2009 22:03:53 -0500 (CDT)

Under "Time required for a node in the DAG to reach its minimum rank" where DAG hop timers are used, the identified time delay is really the best case delay when a DAG hop timer for a non-minimum rank neighbor does not fire before the DAG hop timer for the minimum rank neighbor. If that happens, the node will have to wait for the next RA from the minimum rank neighbor. 

Thanks
Mukul
----- Original Message -----
From: "Mukul Goyal" <[email-masked]>
To: "roll" <[email-masked]>
Sent: Wednesday, September 30, 2009 4:21:21 PM GMT -06:00 US/Canada Central
Subject: [Roll] Delays involved in various DAG operations

Hi all,

Thanks
Mukul

Assuming that:

t(1) = 0

t(1) = dag_hop_delay(0)

_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll