Subject: [Roll] cost of incrementing the DAG sequence number

From: Richard Kelsey <[email-masked]>
Date: Mon, 03 Aug 2009 10:44:22 -0400

ROLLers,

At the session in Stockholm both Jonathan and Pascal
described incrementing the DAG sequence number as a costly
operation.  I don't think that this is necessarily the case.

The cost of incrementing the sequence number depends on
whether or not seeing a new sequence number resets the
trickle timer.  If it does, then the cost may indeed be
high.  If not, there is essentially no cost to incrementing
the sequence number.  With the exception possibly resetting
the trickle timer, no action is required upon receiving a
new sequence number in a DIO.

I would argue that seeing a new sequence number in a
parent's DIO should not reset the trickle timer.  In
addition to reducing the cost of incrementing, it also
increases the utility of doing so.  The sequence numbers are
more useful if they propagate slowly than if they propagate
quickly.  Incrementing the sequence number reasonably often
increases nodes' ability to react to topography changes.  At
the extreme, once all nodes in the DAG have the same
sequence number the sequence number is no help at all.  We
shouldn't be in a hurry to get there.

                                -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 3 Aug 2009 12:58:23 -0700

Hi Richard,

> shouldn't be in a hurry to get there.

Being able to use the sequence number to cause more frequent RAs is a  
useful mechanism for network management or for other protocol-specific  
reasons down the line. There is also benefit to have the new sequence  
number propagate quickly throughout the network. While the sequence  
number is propagating, special care needs to be taken as to when a  
node should actually make the flip from the old topology to the new  
topology - once you flip to new, you can only use routes in the new  
topology and you cannot go back. Flip too early, and the node may  
advertise higher costs and other routing information carried in DAOs -  
causing additional unneeded churn in the routing structure later in  
time. Taking longer to flip obviously impacts the time it takes to  
react to topological changes. This issue is well-known with DSDV.  
Specifying actual values for the time delays is difficult because they  
depend on link-layer parameters, etc.

The actual cost of sending an RA and propagating new sequence numbers  
will depend on the specific link-layer being used and the application  
requirements. I imagine some scenarios where it is completely fine to  
send RAs every 10s of seconds all the time (broadcasts are cheap and  
energy is relatively plentiful). I also imagine some scenarios where  
you really want to keep the RA transmission to 10s of minutes if  
possible (broadcasts are extremely expensive and energy is scarce). In  
the latter case, you'd really like to have some mechanisms for  
increasing the RA transmission frequency when topology changes do  
occur - in other words, spend some extra resources when changes occur,  
but otherwise spend as little as possible. When there is this tradeoff  
in resource consumption vs. responsiveness, then it's beneficial to  
utilize mechanisms that only require actions by the affected nodes -  
rather than mechanisms that affect all nodes within the network.

This is my rationale for providing both sequence number and DAG  
detatching mechanisms for resolving topology changes. They each have  
their pros/cons - how they are used is, ideally, guided by the  
specific application.

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 04 Aug 2009 10:21:35 -0400

From: Jonathan Hui <[email-masked]>
   Date: Mon, 3 Aug 2009 12:58:23 -0700

Jonathan,

   > shouldn't be in a hurry to get there.

   Being able to use the sequence number to cause more
   frequent RAs is a useful mechanism for network management
   or for other protocol-specific reasons down the line.

Can you be more specific?  

   There is also benefit to have the new sequence  
   number propagate quickly throughout the network. While the sequence  
   number is propagating, special care needs to be taken as to when a  
   node should actually make the flip from the old topology to the new  
   topology - once you flip to new, you can only use routes in the new  
   topology and you cannot go back.

Propagating a new sequence number doesn't necessitate
any change in the topology.  There is no requirement,
or even suggestion, that a new sequence number alone
cause any changes in routes.  The new sequence number
gives nodes the opporunity to pick better routes; there
is no need for them to pick worse ones.

   Flip too early, and the node may advertise higher costs
   and other routing information carried in DAOs - causing
   additional unneeded churn in the routing structure later
   in time. Taking longer to flip obviously impacts the time
   it takes to react to topological changes.

As does taking longer to increment the sequence number.
You can have infrequent fast propagation or frequent
slow propagation.  The latter seems less disruptive
and no worse at reacting to changes.

   [...] When there is this tradeoff  
   in resource consumption vs. responsiveness, then it's beneficial to  
   utilize mechanisms that only require actions by the affected nodes -  
   rather than mechanisms that affect all nodes within the network.

Exactly.  If incrementing the sequence number does not reset
the trickle timer, then a new sequence number allows regions
that need route improvements to make those improvements
while allowing everyone else to keep their current routes at
no additional cost.
                                -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 4 Aug 2009 08:21:41 -0700

Hi Richard,

> Can you be more specific?

If the network generally operates with a slow RA transmission period,  
speeding it up can help convergence times. We've found it useful for  
when something in the network changes more quickly than expected (e.g.  
unexpected node movement, unexpected network failures, network  
maintenance, etc.). Sequence number is also useful for building  
routing state from a clean slate - which is what it does by building a  
new DAG.

> is no need for them to pick worse ones.

A nice property of propagating a new sequence number is that it can  
move deeper in the DAG if it wishes without forming cycles. The  
problem is that, in many cases, the first nodes you hear advertising a  
new sequence number will have higher cost than your current cost in  
the existing (soon-to-be deprecated) DAG. RAs propagate quicker along  
paths with shorter hops - not necessarily ones with lower cost. If the  
node uses routes from the new DAG, it can no longer use routes from  
the old DAG (otherwise there is no guarantee of loop freedom). So the  
question is - when does a node decide to use the new DAG and when can  
it start advertising routes for the new DAG? How long does it wait if  
some of the old routes have not yet communicated a new sequence  
number? And does the loss of a few broadcast transmissions provide a  
good indicator that unicast transmissions is also failing to the same  
degree?

> and no worse at reacting to changes.

Right - but if you can provide other mechanisms that can fix the  
majority of problems locally while using the sequence number to fix  
harder problems globally - then we can move towards a nice tradeoff  
between slow and fast. My wish is to have a protocol that operates  
well while transmitting RAs every 10s of minutes the majority of the  
time - while allowing local adaptations to occur in only a few minutes  
at most. If I'm missing something, please elaborate.

> while allowing everyone else to keep their current routes at

It seems that you are arguing for a fixed RA transmission period for  
all nodes. What are some cases where you would reset the Trickle  
timer? or more generally transmit RAs more frequently than you would  
like for a limited period of time?

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 04 Aug 2009 15:31:53 -0400

From: Jonathan Hui <[email-masked]>
   Date: Tue, 4 Aug 2009 08:21:41 -0700

Jonathan,

First off, I want to make it clear that I am not sold
on the desirability of slowing down the propagation of
sequence numbers.  I do think it is worth a bit of
examination.

I agree with you on this.  On startup, or when things are
really broken, you have to reset the trickle timer.  If we
were to slow down sequence number propagation there would
have to be a mechanism for speeding up the propagation
when required.

   A nice property of propagating a new sequence number is that it can  
   move deeper in the DAG if it wishes without forming cycles.

Exactly.

   The problem is that, in many cases, the first nodes you hear advertising a  
   new sequence number will have higher cost than your current cost in  
   the existing (soon-to-be deprecated) DAG.

I think that one of our differences is that you see a new
sequence number as creating a new DAG.  It doesn't have to.
With a slow propagation of sequence numbers there may be
several sequence numbers in use at the same time.  The root
and nearby nodes will have the highest number, with previous
numbers used by nodes in bands more-or-less ordered by
depth.

Most of the time this all has no effect on anything, as
nodes wait until all of their parents' have updated before
updating themselves.  The routes stay the same.  If a node's
parents become unreachable, then there may already be, or
may soon appear, alternate parents available that have a
higher sequence number.

   RAs propagate quicker along paths with shorter hops - not
   necessarily ones with lower cost. If the node uses routes
   from the new DAG, it can no longer use routes from the
   old DAG (otherwise there is no guarantee of loop
   freedom). So the question is - when does a node decide to
   use the new DAG and when can it start advertising routes
   for the new DAG? How long does it wait if some of the old
   routes have not yet communicated a new sequence number?

Use a timer similar to the DAG Hop timer in the current
draft.  If you first hear a new sequence number from node
N, then you wait (local_depth - node_N_depth) * some_delay.
The delay should be long enough to allow for occasional
missed RAs.

   And does the loss of a few broadcast transmissions
   provide a good indicator that unicast transmissions is
   also failing to the same degree?

The goal would be to set the delay long enough to
allow for some missed broadcast transmissions without
forcing routes to change.

I agree with you.  Slow propagation of DAG sequence numbers
isn't a replacement for fast local repair, it is an
improvement on bursty global repair.  The two advantages of
slow propagation are:

A) Reducing the peak bandwidth used for DAG maintenance.
Fast construction of a new DAG can consume a lot of
bandwidth, leaving little for application traffic.

B) Eliminating the need to report routing problems back to
the root in order to trigger a new sequence number.  By
reducing the cost of new sequence numbers the root can
produce them on a continual basis rather than as needed.

Joining or leaving a DAG would definitely still need to
reset the trickle timer.  There may be other cases as
well.
                              -Richard Kelsey