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

From: Mukul Goyal <[email-masked]>
Date: Tue, 14 Jul 2009 06:46:01 -0500 (CDT)

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.

---

From: Omprakash Gnawali <[email-masked]>
Date: Thu, 16 Jul 2009 17:15:07 -0700

> 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 n…

What kind of packet loss assumptions are necessary to guarantee
loop-free routing under this proposal?

- om_p

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 20 Jul 2009 08:07:20 -0700

Hi Mukul,

I think the mechanism you outlined is captured by the "Held-Up"  
mechanism in Section 5.3.3.1 of the RPL draft. Please clarify if you  
are thinking of something different.

That said, I do think it is good to discuss the "Held-Up" state a bit  
more. There's a couple of questions that come to mind:

1) How long does a node stay in the Held-Up state?
- The RPL draft says that it is a function of the candidate's depth.  
For deep networks, that can be a fairly long time before a node can  
successfully find a new feasible successor.

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.

We need to weigh the benefits of utilizing the "Held-Up" state with  
the potential downsides raised by the two questions above. The answer  
is not clear to me yet.

--
Jonathan Hui

On Jul 14, 2009, at 4:46 AM, Mukul Goyal wrote:

> 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:
> 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.
>
> Suppose all unidirectional link costs are 1 except the following: B- 
> >C:5, B->D:5 and E->B:5
>
> 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