Subject: Re: [Roll] A simple loop avoidance mechanism for use in P2P DV routing not using DAGs

From: Mukul Goyal <[email-masked]>
Date: Wed, 22 Jul 2009 03:06:07 -0500 (CDT)

Richard,

> - The absence of a change is interpreted as a successful
   result.  The presence of a loop is indicated by seeing a
   change in a prospective parent's RA.  No change implies
   no loop.  These networks are lossy.  I would be much
   happier if there were a positive acknowledgement of a
   loop-free path.

Please expand your comment. I did not undetstand "The presence of a loop is indicated by seeing a change in....". Also please explain what do you mean by "positive acknowledgement of a loop free path".

> A loop can be detected by sending information either upward
or downward.  In an RPL DAG the upward branching factor will
usually be significantly less than the downward one.  It is
likely to be cheaper and faster to detect loops by sending
probes upwards.  We might even be able to use unicasts
instead of broadcasts.

Again, not sure what you mean. Loop detection, whether using RPL approach or path accumulation approach, works by sending probes "upwards". In loop-avoidance approach I mentioned, there is "downwards" flow of information to make sure that "neighbor descendants" update their cost estimates while the node is in "loop avoidance" state.

Thanks
Mukul

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 22 Jul 2009 11:46:20 -0400

Mukul,

   Date: Wed, 22 Jul 2009 03:06:07 -0500 (CDT)
   From: Mukul Goyal <[email-masked]>

   RK> The absence of a change is interpreted as a successful
   RK> result.  The presence of a loop is indicated by seeing a
   RK> change in a prospective parent's RA.  No change implies
   RK> no loop.  These networks are lossy.  I would be much
   RK> happier if there were a positive acknowledgement of a
   RK> loop-free path.

   Please expand your comment. I did not undetstand "The
   presence of a loop is indicated by seeing a change
   in....".

In draft-dt-roll-rpl-01 the method for moving down the DAG
to a parent with a greater depth is:
 1. detach
 2. wait while the detached state propagates downward
 3. reattach to any grounded node
The assumption is that any node still grounded after the
waiting period is not a descendent of the moving node and
thus can be used as a parent.  This depends on the reliable
distribution of the detached status.  Any communication
failure is interpreted as the absence of a loop.

   Also please explain what do you mean by "positive
   acknowledgement of a loop free path".

Picking a parent with a more recent DAG sequence number
would be a positive acknowledgement.  Sending a message to
the root, or at least far enough up the DAG, and receiving a
response would also be a positive acknowledgement of the
absence of a loop.

   RK> A loop can be detected by sending information either upward
   RK> or downward.  In an RPL DAG the upward branching factor will
   RK> usually be significantly less than the downward one.  It is
   RK> likely to be cheaper and faster to detect loops by sending
   RK> probes upwards.  We might even be able to use unicasts
   RK> instead of broadcasts.

   Again, not sure what you mean. Loop detection, whether using RPL
   approach or path accumulation approach, works by sending probes
   "upwards".

For detached nodes, RPL propagates the detached status
down the DAG, not up.  The detached status is used for
detecting loops.
                                  -Richard Kelsey