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

From: Mukul Goyal <[email-masked]>
Date: Tue, 21 Jul 2009 03:55:27 -0500 (CDT)

Hi Jonathan

If we were to compare the loop-avoidance strategy I proposed, when applied to RPL, with the RPL approach, we can find more subtle differences:

1. Even though you have not mentioned it, one has to assume that a newly detached node tells its neighbors (including its erstwhile children) about its detachment so that they can update their routing metrics eliminating this node from consideration. So, in effect, the detached node is advertising an infinite cost, which may cause a large number of its descenadants to advertise infinite cost as well (if they also detach from the original DAG). Now, can we call such nodes, detached from their original DAG, route-less since such nodes can't forward packets to their old parents and don't have new parents yet? If so, there may be serious implications for packet forwarding. Thus, detaching nodes from the DAG seems an overly-conservative loop-avoidance strategy. (The "loop correction" strategy I proposed is based on detecting explicitly the nodes in-loop and requiring only "in-loop" nodes to advertise infinite cost; still a much milder strategy than what RPL has.) In comparison, the loop-avoidance strategy I proposed involves nodes maintaining their old routes during the "loop avoidance" state. These old routes may not be best but are still better than no routes at all.

2. There are issues with putting neighbors in "held-up" state versus putting the node itself in "loop avoidance" state:
a) Need to maintain potentially several per-neighbor timers.
b) The "held-up" timer duration for a neighbor depends on the neighbor's depth. As you mentioned, if all neighbors have large depths, the "held-up" states of the neighbors can last for a long time during which the node has to stay detached, i.e. potentially route-less.
c) Since the node selects the first neighbor coming out of "held-up" state as the parent, a node would perhaps select its minimum depth neighbor as its only parent. This is not necessarily a good thing. This policy discourages multiple parents. On the other hand, if the node were to go to a fixed duration "loop-avoidance" state itself, it may have good chances of selecting multiple parents including the minimum depth one.

Thanks
Mukul

----- Original Message -----
From: "Jonathan Hui" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Monday, July 20, 2009 9:18:23 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] A simple loop avoidance mechanism for use in P2P DV routing not using DAGs

Hi Mukul,

On Jul 20, 2009, at 6:02 PM, Mukul Goyal wrote:
> I am not sure how does the "Held-up" mechanism cover the loop  
> avoidance scheme I described. I seem to be missing some thing. Here  
> is my understanding of the "held-up" mechanism described in RPL:
>
> Section 5.3.3.1 in RPL draft states two purposes for the "Held-Up"  
> state:
>
> 1. "Delay the reattachment of a sub-DAG that has been forced to
>      detach.  This is not as safe as the use of the sequence, but  
> still
>      covers that when a sub-DAG has detached, the Router Advertisement
>      - DAG Information Option that is initiated by the new DAG root  
> has
>      a chance to spread outward along the sub-DAG so that two  
> different
>      DAGs have formed."
>
> I did not understand the text quoted above at all. Please clarify. I  
> did not find any additional text in RPL draft that further describes  
> the use of "held-up" state in this context.

It's clear that loops may occur if a node needs to increase its cost.  
In the current draft, a node detaches from the DAG if a node cannot  
use any neighbor as a feasible successor without increasing its cost.  
If a node must increase its cost, it must put the candidate successor  
in the held-up state for a period of time before it becomes a feasible  
successor. The held-up state is a loop-avoidance mechanism to allow  
new routing information to propagate to the candidate node. The held- 
up period is currently specified to approximate the worst-case - a  
value based on the depth of the candidate node and the expected time  
to communicate information at each hop.

I don't see any real difference between the "held-up" state and your  
proposed "loop-avoidance" state.
A subtle difference is rather than a node placing itself in the "held- 
up/loop-avoidance" state, RPL places the *candidate* in the "held-up/ 
loop-avoidance" state. That's why the RPL loop-avoidance mechanism  
does not require a flag in the advertisement - any joining nodes will  
wait for the held-up period for new routing information to propagate  
to the candidate node. Am I missing something else?

We'll try to improve the text in the next revision. Among other  
things, we need to use common terminology (the current draft is a mix  
of existing drafts and new text).

--
Jonathan Hui

> 2. The second purpose of the "held-up" state, which I think I  
> understand clearly, is to delay a node's joining of a new DAG to try  
> to ensure that:
> a) a node joins the new DAG at the minimum possible depth;
> b) among the neighbor/nearby nodes trying to join the new DAG, the  
> nodes join the new DAG roughly in order of their depth in the new DAG.
> To achieve these objectives, a node keeps a potential parent in the  
> new DAG in the "held-up' state for a time duration proportional to  
> the potential parent's depth in that DAG. For every new potential  
> parent, the node starts a new "held-up" state timer (the hop timer).  
> The node joins the new DAG via the first potential parent coming out  
> of the "held-up" state.
>
> On the other hand, the loop avoidance mechanism I described puts a  
> node in the "loop avoidance" state when the current nexthop/parent  
> is no longer good enough. Rather than immediately choosing a  
> different parent (based on potentially erroneous costs currently  
> being advertised by neighbors), the node advertises (via special  
> _marked_ advertisements) its new cost through the current parent for  
> the duration it is in the "loop avoidance" state. On receiving these  
> _marked_ advertizements, the node's children enter the "loop  
> avoidance" state as well and further propagate the new cost  
> information. The idea is that, by the time the node comes out of the  
> "loop avoidance" state, hopefully all its neighbors would have  
> corrected their cost estimates if the previous estimates were based  
> on the old costs. So, on coming out of the "loop avoidance" state,  
> when the node selects its new parents, it does not cause a routing  
> loop or a "count to infinity" situation.
>
>> 2) What is the effect of packet loss?
>> - If node B is a descendant of A and B misses the advertisement from
>> its parent, then A may attach to B or any of its descendants. In a
>> sufficiently dense network, there's a fairly high probability that
>> some node B will miss the advertisement from A (even with
>> retransmissions). On the flip side, those that properly hear the new
>> cost values are likely not to be involved in any loops. In summary,
>> Count-to-Infinity still exists but arguably with only a subset of  
>> nodes.
>
> I agree. The efficacy of the solution depends on the probability of  
> _neighbor_ descendants (i.e. descendants that are neighbors as well)  
> receiving the new cost information and updating their cost  
> advertisements based on this information. This probability in turn  
> depends on parameters like the probability of advertisement loss,  
> the duration of the "loop avoidance" state, the number of times a  
> node sends out advertisements while in this state, the children tree  
> topology etc.
>
> Regards
> Mukul
>
>
>
> On Jul 14, 2009, at 4:46 AM, Mukul Goyal wrote:
>
>> Hi all
>>
>> Here is a simple loop avoidance mechanism that can be used in a P2P
>> routing solution that does not use DAGs.
>>
>> Thanks
>> Mukul
>>
>> In DV protocols, the routing loops are triggered when the cost to
>> reach a destination via the current next hop increases so much that
>> a new next hop needs to be selected.
>>
>> Suppose, a node, B, determines that its current next hop, A, for a
>> destination, X, may no longer be the best ("minimum cost") neighbor
>> to forward packets to. Such determination could be based on an
>> increase in the link cost to node A or the receipt of a new
>> advertisement from node A showing an increased cost to reach the
>> destination X.
>>
>> In case of such an event, node B should not choose a new next hop
>> immediately. This is because the current cost advertisements by its
>> neighbors, as well as any new advertisements generated in the
>> immediate aftermath of the event, may be based on node B's erstwhile
>> cost to reach the destination. Immediate selection of a new next hop
>> based on the current or new cost advertisements by the neighbors may
>> lead to a routing loop and a "count to infinity" situation.
>>
>> Rather, node B should initiate the propagation of new cost
>> information down the tree (of nodes for whom it currently lies on
>> the route to X)and wait for some time before calculating its new
>> next hop. The hope is that by the time the node calculates its new
>> next hop, its increased cost along the current next hop is known to
>> all its neighbors and they have generated new advertisements if
>> their previous advertisements were based on the old cost of node B
>> to reach X.
>>
>> So, when node B determines that its current next hop A for
>> destination X is no longer the best neighbor to forward packets to,
>> it generates a new specially _marked_ advertisement that lists node
>> B's new cost to reach X via A, the current next hop.
>>
>> The generation of a _marked_ advertizement regarding destination X
>> puts the node in the "loop avoidance" state for a time period during
>> which the node can neither change its next hop to destination X nor
>> generate a regular advertisement for the destination X.
>>
>> All nodes that receive node B's _marked_ advertisement regarding
>> destination X update their cost to reach X via B. If a node
>> currently considers node B as its next hop to destination X, it
>> additionally does the following:
>> 1. it enters the "loop avoidance" state and hence consequently keeps
>> node B as its next hop to X
>> 2.  originates a _marked_ advertizement listing its new cost to
>> destination X via node B
>>
>> Once a node exits the "loop avoidance" state, it is allowed to
>> select a new next hop to X and generate a regular advertisement
>> listing its new cost to X.
>>
>> Here is an example showing the efficacy of this proposal:
>>
>>                  X
>>                  |
>>                  A
>>                 / \
>>                 B-C
>>                / \
>>                D E
>>                \ /
>>                 F
>>
>> X is the destination.
>>
>> Suppose all unidirectional link costs are 1 except the following: B-
>>> C:5, B->D:5 and E->B:5
>>
>> Accordingly, the routes are as follows: C->A->X and E->F->D->B->A->X
>>
>> and node B's perceived cost to reach X via each neighbor is as
>> follows:
>> via A:2, via C:7, via D:8, via E:6
>>
>> Suppose the cost of link B->A changes to 100.
>>
>> In a simple DV protocol, B's cost to reach X via A becomes 101 and
>> hence it immediately chooses E as the next hop (declaring its new
>> cost to X as 6), thereby creating routing loop B->E->F->D->B and a
>> "count to infinity" situation.
>>
>> Under the proposed protocol, B would generate a _marked_
>> advertisement listing its cost to X as 101 and enter the "loop
>> avoidance" state. This _marked_ advertisement is received by A, C, D
>> and E. Since D considers B as its next hop to X, it enters the "loop
>> avoidance" state as well and generates its own _marked_
>> advertisement listing its cost to X as 102.
>>
>> On receiving this advertisement, node F enters the "loop avoidance"
>> state and generates its own _marked_ advertisement listing its cost
>> to X as 103.
>>
>> On receiving this advertisement, node E enters the "loop avoidance"
>> state and generates its own _marked_ advertisement listing its cost
>> to X as 104.
>>
>> If node B comes out of the "loop avoidance" state only after the
>> receipt of this advertisement from E, B would correctly choose node
>> C as its new next hop to X and generate a new advertisement listing
>> its cost to X as 7. When nodes D, F and E come out of the "loop
>> avoidance" state, they would ultimately  update their cost to X to
>> 8, 9 and 10 respectively without any loops.
>>
>> This policy does cause a delay in convergence. Suppose B->C cost is
>> 1 in the example above. B enters the "loop avoidance" state when
>> cost of link B->A changes to 100. Node B would not select C as next
>> hop (and advertize a cost 3 to X) until it comes out of the "loop
>> avoidance" state.
>> _______________________________________________
>> Roll mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll
>

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 21 Jul 2009 07:55:20 -0700

Hi Mukul,

While there are subtle differences, both are based on the same  
principle - if there's a possibility of a loop, communicate new  
routing information to children, wait for a while for routing  
information to propagate before finalizing decisions.

The larger issue is the efficacy of such an approach in real-world  
deployments. There is a level of discomfort in the WG because this  
(and other) mechanisms haven't yet been widely deployed. As identified  
by myself, you, and others in this thread, there are still some issues  
that we need to weigh against the perceived benefits. I'd like to get  
input from others on the basic mechanism before we get into a deep  
discussion on the details.

Couple quick comments to your email below:

On Jul 21, 2009, at 1:55 AM, Mukul Goyal wrote:
> If we were to compare the loop-avoidance strategy I proposed, when  
> applied to RPL, with the RPL approach, we can find more subtle  
> differences:
>
> 1. Even though you have not mentioned it, one has to assume that a  
> newly detached node tells its neighbors (including its erstwhile  
> children) about its detachment so that they can update their routing  
> metrics eliminating this node from consideration. So, in effect, the  
> detached node is advertising an infinite cost, which may cause a  
> large number of its descenadants to advertise infinite cost as well  
> (if they also detach from the original DAG). Now, can we call such  
> nodes, detached from their original DAG, route-less since such nodes  
> can't forward packets to their old parents and don't have new  
> parents yet? If so, there may be serious implications for packet  
> forwarding. Thus, detaching nodes from the DAG

Detachment only means that a node advertises itself as being in a  
floating DAG - the routing structure isn't really dissolved.

> seems an overly-conservative loop-avoidance strategy. (The "loop  
> correction" strategy I proposed is based on detecting explicitly the  
> nodes in-loop and requiring only "in-loop" nodes to advertise  
> infinite cost; still a much milder strategy than what RPL has.) In  
> comparison, the loop-avoidance strategy I proposed involves nodes  
> maintaining their old routes during the "loop avoidance" state.  
> These old routes may not be best but are still better than no routes  
> at all.
>
> 2. There are issues with putting neighbors in "held-up" state versus  
> putting the node itself in "loop avoidance" state:
> b) The "held-up" timer duration for a neighbor depends on the  
> neighbor's depth. As you mentioned, if all neighbors have large  
> depths, the "held-up" states of the neighbors can last for a long  
> time during which the node has to stay detached, i.e. potentially  
> route-less.
> c) Since the node selects the first neighbor coming out of "held-up"  
> state as the parent, a node would perhaps select its minimum depth  
> neighbor as its only parent. This is not necessarily a good thing.  
> This policy discourages multiple parents. On the other hand, if the  
> node were to go to a fixed duration "loop-avoidance" state itself,  
> it may have good chances of selecting multiple parents including the  
> minimum depth one.

Minimally, the wait time should be the time it takes to propagate  
routing information from a node to the candidate successor - this can  
be approximated by the required increase in depth to use the candidate  
successor. The draft uses depth from the root because it serves the  
dual purpose of trying to better coordinate the propagation of DV  
information - with the hope of better convergence times in some cases.

Again, these pretty detailed issues in the protocol design. I think we  
first need to have the larger discussion of whether a broadcast-wait- 
choose or a different mechanism should be included in the core protocol.

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 21 Jul 2009 11:59:20 -0400

Hi Jonathan,

   From: Jonathan Hui <[email-masked]>
   Date: Tue, 21 Jul 2009 07:55:20 -0700

I think that this approach has a number of weaknesses:

 - It is resource intensive in that it requires two separate
   downward information flows.  The first to test for a loop
   and the second to propogate the successful return to a
   known loop-free state.

 - 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.

 - Checking for a loop using broadcasts to propagate
   information down the DAG is slow and expensive.

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.
                                  -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 21 Jul 2009 09:08:52 -0700

Hi Richard,

Your primary concerns are the same as mine, especially (i) relying on  
information to actually be communicated and (ii) broadcasts. Given the  
proposals on the table, I'm much more comfortable with loop-detection  
than loop-avoidance. I am influenced by the fact that I have much more  
experience with the former than the latter, but I suspect the same  
goes for others in the WG.

--
Jonathan Hui