Subject: Re: [Roll] A proposal for Traffic Loop avoidance, detection and recovery

From: Sung Lee <[email-masked]>
Date: Mon, 12 Oct 2009 13:27:06 -0400

I am with Philip.
Our experience also shows that
    2) Allow routing through nodes of higher rank

  with loop detection and repair in the data path works pretty well.

Regards,
Sung

[email-masked] wrote:
> Message: 2
> Date: Fri, 9 Oct 2009 10:20:05 -0700
> From: Philip Levis <[email-masked]>
> Subject: Re: [Roll] A proposal for Traffic Loop avoidance,	detection
> 	and recovery
> To: Pascal Thubert (pthubert) <[email-masked]>
> Cc: roll <[email-masked]>
> Message-ID: <[email-masked]>
> Content-Type: text/plain; charset=WINDOWS-1252; format=flowed;
> 	delsp=yes
>
>
> On Oct 9, 2009, at 5:55 AM, Pascal Thubert (pthubert) wrote:
>
>
>> Hi:
>>
>> It seems widely accepted in this group that Loop avoidance in the
>> control place should be kept simple but completed by a detection
>> mechanism associated to the packets. This approach had been
>> validated in CTP and DADR.
>>
>> After a number of discussions, here is a proposal. The proposal uses
>> some info that is placed in the packet in the flow label.
>> It assumes that the flow label is reserved for the purpose of RPL
>> and node interaction. In the flow label we place:
>>
>> Outwards            : 1 bit
>> Sibling                   : 1 bit
>> Rank_error         : 1 bit
>> DAO_Error          : 1 bit
>> Rank                      : 8 bit
>> Instance ID         : 8 bit
>>
>> Instance forwarding
>> Instance IDs is used to avoid loops between DAGs from different
>> origins.
>>
>> InstanceID is placed by the source in the flow label. It MUST
>> matched the DAG instance onto which the packet is placed by a
>> router. The router MAY either change the instanceID to match the DAG
>> that it is using for this packet or discard the packet. That
>> decision is policy based. Default policy TBD.
>>
>> Idea?
>>
>> DAG inconsistency loop detection
>> The DAG is inconsistent is the packet direction does not match the
>> rank relationship.
>>
>> A host MUST set the rank to FF. A router MUST place its rank in the
>> flow label.
>> A node emitting a packet must reset the Rank_error bit and the
>> Outwards bit.
>> A router MUST also reset the Outwards bit if it is using the default
>> route inwards, either via a sibling or a parent, and set the bit if
>> it is using a DAO route, either via a sibling or a child.
>>
>> A receiver detects an inconsistency if it receives a packet going
>> inwards from a source with a lesser Rank, or outwards with a higher
>> rank.
>>
>> Upon inconsistency, if the Rank_error bit was not set then the
>> Rank_error bit is set. If it was set the packet is discarded. This
>> is done to cover a rare re-sequencing of the DAG.
>>
>> Sibling loop avoidance
>> A simple rule is that a packet may not make 2 sibling hops in a row.
>>
>> When a host sends a packet or a router forwards to a non sibling,
>> the Sibling bit must be reset.
>> When a router forwards to a sibling: if the Sibling bit was not set
>> then the Sibling bit is set. If it was set then the packet is
>> discarded.
>>
>> DAO inconsistency loop detection
>> A ?parent? has an outwards DAO route that is a remnant from an
>> obsolete DAO via a ?child? but the ?child? does not have a matching
>> DOA state.
>>
>> In a general manner, a packet that goes outwards should never go
>> inwards again. So rather than routing inwards a packet with the
>> Outwards bit set, the router MUST discard the packet. If DAO
>> recovery is in place, then the router MAY send it back to the source.
>>
>> DAO inconsistency loop recovery
>> A Router that supports recovery uses a packet to recursively explore
>> and cleanup the obsolete paths.
>>
>> The ?child? router that detects the DAO inconsistency SHOULD set the
>> DAO_Error bit and return the packet to the parent that passed it.
>>
>> Upon a packet with a DAO bit set, the parent MUST remove the routing
>> states that caused forwarding to the child that passed it, clear
>> DAO_Error bit and send the packet again.
>>
>>
>
> I advocate taking a more extreme approach: remove the current sequence
> number loop prevention mechanisms from the draft.
>
> Currently, RPL is trying to have it both ways. It's using sequence
> numbers to prevent (not just avoid) loops caused by increasing in
> rank. However, by allowing nodes to choose siblings, RPL still
> requires a loop detection mechanism in data packets. If there is a
> mechanism to detect loops with data packets, then there is no need to
> have rules on when nodes can increase rank: the decision of whether to
> do so or not is a performance design choice.
>
> When we started designing CTP, we tried using sequence numbers as DSDV
> does. The logic to handle all of the edge cases was non-trivial. In
> particular, if node A has move to sequence number N+1, but its child B
> is still on sequence number N, then on receiving a packet from child
> B, A must forward it with tree N. That is, A must maintain two trees.
> Overall, the edge cases were complex, required a good deal of code,
> and had a lot of tricky edge cases. Furthermore, the prospect of being
> floating until a sequence number increment created a difficult tension
> between the longest interval a DAG could be floating and the cost of
> periodically flooding DAG sequence number updates.
>
> If there is a way to detect and repair loops in the data path, then
> this tension disappears. Loops become an efficiency problem, due to
> the extra messages they send. Correspondingly, may protocols have an
> inventive to follow the loop prevention guidelines in -03, if doing so
> leads to overall better efficiency. But such algorithms and policies
> are RECOMMENDED or OPTIONAL performance optimizations on top of a
> specification, not part of the specification itself (e.g., think RFC
> 2581).
>
> In summary, I'd argue, that for the sake of simplicity in required
> mechanisms, and flexibility in future implementation designs, that RPL
> should either:
>
> 1) Disallow routing through siblings
> 2) Allow routing through nodes of higher rank
>
> I personally think 2) is a better approach, based on my experiences,
> as it can remove the need for periodic sequence number increments. But
> I think that the current half-way position is worse than either 1) or
> 2): it has the worst of both worlds.
>
> If we make sequence number-based DAG control OPTIONAL, then I'd argue
> we should elide it from the main RPL document. Keep the core
> specification simple.
>
> Phil
>
> ------------------------------
>
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>
>
> End of Roll Digest, Vol 21, Issue 21
> ************************************
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 13 Oct 2009 16:56:48 +0200

Hi Sung and Phil;

Option 2) is close in spirit to what the current draft is doing. 
 
Routing through higher rank has the same risk as moving to higher rank;
maybe a loop, maybe not; loop detection will help figure. 

The draft actually allows moving to a higher rank but there's a catch.
Whereas a node can reattach right away to obtain a better rank, it needs
to play a little dance that includes detach, wait & see before it can
attach at a higher rank. 

The dance is not aimed at avoiding loops completely. 

It just tries to bend the stats and lowers the odds of using the wrong
guy, by marking proactively some unsafe landing spots before making a
risky move. This is done by poisoning the route via self over the self's
subDAG. A side effect is to reduce the traffic that will take a risky
path and the chances to count to infinity. Route poisoning is completed
by the rule that a parent that goes down should be eliminated. 

RPL as it stands today certainly does not provide the level of guarantee
that DUAL would over a rather fixed topology.  So at the end of the day,
we do end up routing through nodes of higher ranks and do need a loop
detection. The question is where we place the bar, and I am one of those
of think that the poisoning brings along more benefit on the battery
than cost in missed forwarding opportunities.

We might be less conservative when we have a better description of our
loop detection mechanism. To get there, it is especially important that
the two of you comment on the proposal from original thread on detection
and recovery.

Thanks in advance,

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Sung Lee
>Sent: lundi 12 octobre 2009 19:27
>To: [email-masked]
>Subject: Re: [Roll] A proposal for Traffic Loop avoidance,detection and
recovery