Subject: Re: [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: Fri, 17 Jul 2009 19:37:49 -0500 (CDT)

Phil,

The way I understand CTP operation, it seems that it provides no loop correction mechanism other than reducing trickle timers to their smallest value so that any "count to infinity" takes place quickly. So, I am not sure if any claim that loops are repaired "with in a few packet times" is valid. The loop correction times, under CTP, depend on the severity of "count to infinity" situation, the minimum trickle times and the length of the loop.

The loop correction strategy I proposed is not impeccable either. It works if an in-loop node stays in the "loop correction" state long enough to allow all neighbors to advertise new costs excluding from consideration all in-loop nodes. Otherwise, it does not work and the in-loop nodes would have to resort to "count to infinity".
 
Whether adding the transmitting node's cost value to each packet, as in CTP, is a more desirable loop detection mechanism than using a separate control packet, that accumulates the route it travels over, is debatable as well.

CTP mechanism will certainly result in faster loop detection but requires dedicating bytes in every packet, which would result in reduction in the payload of each packet. If only a fraction of packets carry the transmitting node's cost, CTP's advantage in terms of the loop detection times is lost. 

Using a separate control packet for loop detection allows the nodes involved in the loop to be explicitly identified (useful if this information can be used to correct loops). There is no need to sacrifice bytes in every packet. The application can generate these control packets based on its loop tolerance characteristics. A source node can choose to originate such a control packet after every 'x' data packets or use a trickle-like strategy to originate them (originate more frequently if loops are likely, e.g. after a upheaval in the topology or routing metrics values, otherwise originate infrequently). One major limitation is if the complete path is too big to be carried in a single control packet. In such cases, I guess, the earliest nodes in the path would have to be forgotten on the assumption that shorter loops are more likely than longer loops.     

I guess the floor is open for further debate.

Thanks,
Mukul

----- Original Message -----
From: "Philip Levis" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Friday, July 17, 2009 12:15:12 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] A loop correction mechanism Re: A simple loop avoidance mechanism for use in P2P DV routing not using DAGs

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

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

---

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

Hi Mukul,

On Jul 17, 2009, at 5:37 PM, Mukul Goyal wrote:
> The way I understand CTP operation, it seems that it provides no  
> loop correction mechanism other than reducing trickle timers to  
> their smallest value so that any "count to infinity" takes place  
> quickly. So, I am not sure if any claim that loops are repaired  
> "with in a few packet times" is valid. The loop correction times,  
> under CTP, depend on the severity of "count to infinity" situation,  
> the minimum trickle times and the length of the loop.

I think Phil's "few packet times" claim is for a CTP node that has  
alternate parents not a part of the loop.

> Whether adding the transmitting node's cost value to each packet, as  
> in CTP, is a more desirable loop detection mechanism than using a  
> separate control packet, that accumulates the route it travels over,  
> is debatable as well.

It's important to note that generating another datagram is  
significantly more expensive than adding 1-2 bytes to a packet. For  
many radio links in use, each packet has the overhead of acquiring the  
channel, sender/receiver sync, RX-TX turnaround, and acknowledgement.  
With duty-cycled radios, add the overhead of starting/stopping the  
radio and any guard times for synchronization and/or preambles for low- 
power listening. Depending on the link protocol, a new datagram can be  
1-3 orders of magnitude more expensive than adding 1-2 bytes to an  
existing packet.

Having these relative costs in mind is helpful in evaluating the  
tradeoffs between both approaches.

--
Jonathan Hui