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

From: Mukul Goyal <[email-masked]>
Date: Thu, 16 Jul 2009 21:56:40 -0500 (CDT)

Hi All

Along the same lines as the loop avoidance mechanism described in an earlier email, here is the outline of a mechanism to correct loops once they have been detected:

Periodically, a source node sends a control packet towards the destination X. This packet accumulates the path it travels over. When a node A receives such a packet, it checks the accumulated path. If the node finds itself listed in the accumulated path (i.e. a loop has been detected), it takes the following steps:
1. Identify the nodes involved in the loop and discard the packet.
2. Enter the "loop correction" state, which involves the following actions:
   2.1 Reset the cost of all the neighbors to reach destination X as infinity. Note that the cost of all neighbors is reset to infinity and not just the neighbor identified as being involved in a loop. This is done because the currently advertized cost of other neighbors may be tainted by the costs advertized by the nodes in the loop. 
   2.2 Immediately generate an advertisement listing an infinite cost to reach destination X and including the list of nodes identified to be in the loop. The node may generate additional such advertisements during its sojourn in the "loop correction" state.

The sojourn in the "loop correction" state lasts for a certain pre-configured time interval. While in the "loop correction" state, the node can not add any new next hop for destination X. Thus, while a node is in the "loop correction" state, it simply buffers or drops packets going to destination X. A node in the "loop correction" state updates the neighbors cost to reach X based on the received advertisements. But, as mentioned before, it can not choose a next hop and it continues to advertise its own cost to reach X as infinity.

When a node B receives an advertisement from node A that identifies it to be involved in a routing loop for destination X, node B notes the IDs of nodes involved in the loop and enters the "loop correction" state taking the actions identified above.

Thus, all nodes involved in the loop will enter the "loop correction" state and advertise infinite cost to destination X. The neighbors of these nodes will generate new advertisements for destination X that exclude previously in-loop nodes from consideration. Assuming that:
1. a path, excluding in-loop nodes, does exist from the node to destination X and
2. the "loop correction" state lasts long enough to allow the node to receive new advertisements from all its neighbors based on such a path,
the node would select one such out-of-loop neighbor as a next hop for destination X when it comes out of the "loop correction" state. Immediately, the node generates a new advertisement listing its new cost to destination X.

Thus, all previously in-loop nodes, when they come out of the "loop correction" state, advertise any paths they may have to destination X that do not include previously in-loop nodes. These advertisements would allow these nodes to determine new optimal, and loop-free, paths to destination X.

Thanks
Mukul
   
----- Original Message -----
From: "Mukul Goyal" <[email-masked]>
To: "roll" <[email-masked]>
Sent: Tuesday, July 14, 2009 6:46:01 AM GMT -06:00 US/Canada Central
Subject: [Roll] A simple loop avoidance mechanism for use in P2P DV routing not using DAGs

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: Philip Levis <[email-masked]>
Date: Fri, 17 Jul 2009 10:15:12 -0700

On Jul 16, 2009, at 7:56 PM, Mukul Goyal wrote:

> Hi All
>
> Along the same lines as the loop avoidance mechanism described in an  
> earlier email, here is the outline of a mechanism to correct loops  
> once they have been detected:
>
> Periodically, a source node sends a control packet towards the  
> destination X. This packet accumulates the path it travels over.  
> When a node A receives such a packet, it checks the accumulated  
> path. If the node finds itself listed in the accumulated path (i.e.  
> a loop has been detected), it takes the following steps:
>   2.1 Reset the cost of all the neighbors to reach destination X as  
> infinity. Note that the cost of all neighbors is reset to infinity  
> and not just the neighbor identified as being involved in a loop.  
> This is done because the currently advertized cost of other  
> neighbors may be tainted by the costs advertized by the nodes in the  
> loop.
>   2.2 Immediately generate an advertisement listing an infinite cost  
> to reach destination X and including the list of nodes identified to  
> be in the loop. The node may generate additional such advertisements  
> during its sojourn in the "loop correction" state.
>
> The sojourn in the "loop correction" state lasts for a certain pre- 
> configured time interval. While in the "loop correction" state, the  
> node can not add any new next hop for destination X. Thus, while a  
> node is in the "loop correction" state, it simply buffers or drops  
> packets going to destination X. A node in the "loop correction"  
> state updates the neighbors cost to reach X based on the received  
> advertisements. But, as mentioned before, it can not choose a next  
> hop and it continues to advertise its own cost to reach X as infinity.

What is the advantage of such an approach rather than detecting loops  
as soon as their occur and repairing them within a few packet times?

One of the key lessons from CTP was that it's a bad idea to make  
routing failure detection independent of the data rate. Preconfigured  
time intervals are very difficult for interoperability and lead to  
high packet losses. Of course, one could say that these periodic  
control packets are bound to the data rate (e.g., every tenth packet),  
but in low-power MACs it's usually much more efficient to add a bit of  
data to an existing packet than source entirely new packets.

Phil