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

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 2 Sep 2009 10:11:59 +0200

Hi Jonathan and Richard:

My understanding seems to match that of Richard here. I fail to clearly understand Jonathan's point that a new sequence in a DIO invalidates the states built from the old sequence. It should in fact add new possibilities. The draft does not currently use old sequences as a method to remove parents. We basically expect that either NUD or failure to receive RAs (ala RFC 3775) are the indication that a parent is gone. It appears that we need to clarify this.

The only case that I had in mind for a sequence to invalidate an older one was for the DAOs back, in the context of trees as opposed to DAGs. Along a tree, there can be only one next hop to a destination. IF we receive a same DAO from 2 children, that means that the destination has moved within the subdag and the newer sequence wins. Along a DAG, that property cannot be enforced.

Clearly this is a very interesting and deep thread. I'd urge anyone on the list to read this through and participate if required.

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of Richard Kelsey
>Sent: mardi 4 août 2009 21:32
>To: Jonathan Hui
>Cc: [email-masked]
>Subject: Re: [Roll] cost of incrementing the DAG sequence number
>
>
>   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.
>
>   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.
>
>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.
>
>   > 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.
>
>   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.
>
>   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.
>
>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.
>
>   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?
>
>Joining or leaving a DAG would definitely still need to
>reset the trickle timer.  There may be other cases as
>well.
>                              -Richard Kelsey
>_______________________________________________
>Roll mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/roll