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

From: Mukul Goyal <[email-masked]>
Date: Sat, 10 Oct 2009 09:57:07 -0500 (CDT)

Philip

I agree with you. Loop avoidance/prevention/detection should not be in the base specs. Another positive implication of your approach would be that 'rank', rather than being a loop avoidance mechanism, would simply be the cost to reach the dag root under the routing metrics being used. Lets agree that we dont want to solve "count to infinity" problem in base specs.

Thanks
Mukul

----- Original Message -----
From: "Philip Levis" <[email-masked]>
To: "Pascal Thubert (pthubert)" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Friday, October 9, 2009 12:20:05 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] A proposal for Traffic Loop avoidance, detection and recovery

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

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 15:09:36 +0200

Hi Mukul,

On Oct 10, 2009, at 4:57 PM, Mukul Goyal wrote:

> Philip
>
> I agree with you. Loop avoidance/prevention/detection should not be  
> in the base specs. Another positive implication of your approach  
> would be that 'rank', rather than being a loop avoidance mechanism,  
> would simply be the cost to reach the dag root under the routing  
> metrics being used. Lets agree that we dont want to solve "count to  
> infinity" problem in base specs.
>

We just do not want to look simple by having another simplistic core  
spec augmented with a number of other mechanisms defined in other  
specs. I think that we should adopt one approach and document all of  
its aspects in the core spec.

Thanks.

JP.