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

From: Mukul Goyal <[email-masked]>
Date: Thu, 16 Jul 2009 20:13:15 -0500 (CDT)

Om,

This proposal does not "guarantee" loop-free routing. It is a loop "avoidance" strategy rather than a loop "prevention" mechanism (RPL's DAG seems to me as a loop "prevention" mechanism). There is an obvious dependence on the advertisements not getting lost. This dependence can be lessened by allowing a node to repeat its _marked_ advertisement during its sojourn in the "loop avoidance" state.

Thanks
Mukul
  
----- Original Message -----
From: "Omprakash Gnawali" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Thursday, July 16, 2009 7:15:07 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] A simple loop avoidance mechanism for use in P2P DV  routing not using DAGs

On Tue, Jul 14, 2009 at 4:46 AM, Mukul Goyal<[email-masked]> 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.

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

- om_p

---

From: Philip Levis <[email-masked]>
Date: Thu, 16 Jul 2009 18:17:36 -0700

On Jul 16, 2009, at 6:13 PM, Mukul Goyal wrote:

> Om,
>
> This proposal does not "guarantee" loop-free routing. It is a loop  
> "avoidance" strategy rather than a loop "prevention" mechanism  
> (RPL's DAG seems to me as a loop "prevention" mechanism). There is  
> an obvious dependence on the advertisements not getting lost. This  
> dependence can be lessened by allowing a node to repeat its  
> _marked_ advertisement during its sojourn in the "loop avoidance"  
> state.
>
> Thanks
> Mukul

I think Om's question is more about what happens to all of the data  
packets a node is asked to forward while it "waits for some time."  
Note that these devices have very limited queue sizes. In this  
scheme, any time a node wants to choose a new parent, it will  
possibly drop a burst of dropped packets as well as cause a big jump  
in RTT. Both of these pose issues for TCP.

Phil