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

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 9 Oct 2009 14:55:27 +0200

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.

Opinions? (fire at will)

Pascal

---

From: Philip Levis <[email-masked]>
Date: Fri, 9 Oct 2009 10:20:05 -0700

On Oct 9, 2009, at 5:55 AM, Pascal Thubert (pthubert) wrote:

> mechanism associated to the packets. This approach had been  
> validated in CTP and DADR.
>
> 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
> 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?
>
> 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.
> 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.
>
> 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
> 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.
>
> 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.
>
> 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  

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

---

From: Richard Kelsey <[email-masked]>
Date: Fri, 09 Oct 2009 16:21:50 -0400

From: Philip Levis <[email-masked]>
   Date: Fri, 9 Oct 2009 10:20:05 -0700

A can safely forward the packet to its current, N+1, parent.
No looping can occur.

   Overall, the edge cases were complex, required a good deal of code,  
   and had a lot of tricky edge cases.

I don't follow you.  As I understand and use the sequence
number algorithm, a node only needs to maintain one parent
(tree) or set of parents (DAG).  The only requirement is
that a node not advertise a sequence number more recent than
any of its parents.  Packets are forwarded to any current
parent.  Where do the tricky edge cases come in?

To take the example above, all of A's parents must be at
N+1 or higher.  Transitively, all of A's ancestors must be
at N+1 or higher.  Because B is at N, B cannot be an
ancestor of A.

I pretty much agree with you, except that I think 1) is the
better approach.
                                   -Richard Kelsey

---

From: Philip Levis <[email-masked]>
Date: Sat, 10 Oct 2009 12:11:54 -0700

> A can safely forward the packet to its current, N+1, parent.

Node A is version N.
Node B is version N.
Node A forwards a packet to node B.
Node A receives a beacon with N+1.
Node A sends a beacon with N+1, which node B hears.
Node B forwards the packet to node A.

Assuming that the sequence number space is stable, the problem will of  
course work itself out. But in some initial tests, we found that loops  
such as these (note this is just two nodes, when using sequence number  
increments you can have routes with very high stretch while the  
network reconfigures) could significantly increase the cost  
(transmissions/delivery). A couple of heuristics can help. E.g., if  
you have sequence number N when you receive a packet, then you should  
forward that packet as if you were still number N.

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 12 Oct 2009 08:53:58 -0400

From: Philip Levis <[email-masked]>
   Date: Sat, 10 Oct 2009 12:11:54 -0700

   Node A is version N.
   Node B is version N.

Personally, I wouldn't call this a loop.  At no time
is there a loop in the directed graph formed by the
routing tables.  In a network where links are changing,
packets are going to backtrack across links on occasion.

   (transmissions/delivery).

Hmm.  We have never had a problem with this.  Normally we
see the sequence number updates travel faster along the
better routes, which are the faster/more reliable paths,
which in turn causes the updates to settle quickly.
I would guess that the difference comes down to timing.
The longer the intervals between RA-DIO transmissions, the
longer it will take things to settle down.  Out of curiosity,
what was the minimum trickle delay in your tests?

I can see that it would be more of a issue with a metric
that is unrelated to latency or reliability.  This would
remove any correlation between the paths taken by the
sequence number updates and the desired paths.  Note that
this is specific to the sequence number updates; any
gradient protocol where the routing information propogates
differently than the data packets is going to have problems
with churn.

   A couple of heuristics can help. E.g., if you have sequence number
   N when you receive a packet, then you should forward that packet as
   if you were still number N.

I think that this would be a mistake.  What if the old path
is broken?  The point to doing the update is to create
newer, more reliable paths.  Better would be to delay
transmitting a packet if its gradient is in flux, similar to
what CTP does.
                                   -Richard Kelsey

----------------
This message and the information it contains are the proprietary
and confidential property of Ember Corporation and may be privileged.
If you are not the intended recipient, please do not read, copy,
disclose or distribute its contents to any party, and notify the
sender immediately.

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 12 Oct 2009 22:09:48 -0700

> what was the minimum trickle delay in your tests?

Using sequence numbers to establish an event-horizon is, of course,  
not new in the wireless space.  DSDV proposed using sequence numbers  
for the purpose of avoiding loops 15 years ago.  The difference in  
opinion here may come from subtle differences in how we view the  
sequence number propagation - these differences can have a fairly  
significant change in the overall behavior.  In particular, one of the  
criticisms often associated with the use of sequence numbers it that  
they encourage long, unstable links.  This, of course, does occur when  
naively using the first received beacon of the latest sequence number  
to select the primary parent.  Doing so often chooses routes that  
utilize long but intermittent links - possibly resulting in high  
stretch and/or churn.  Conservatively allowing sequence numbers to  
only propagate along "good" links but not "okay" links may produce  
more stable paths, but requires other mechanisms to utilize the "long"  
links.

I do think sequence numbers can be powerful for loop avoidance and  
dealing with the count-to-infinity issue, but I also think that  
sequence number state must be refreshed periodically for the mechanism  
to remain simple and work well (a significant cost for some  
networks).  I do believe count-to-infinity is a significant issue we  
should be concerned about, more so because of the energy cost rather  
than convergence time.  So far, the loop detection/recovery mechanisms  
don't really solve the count-to-infinity problem.

--
Jonathan Hui