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: Wed, 22 Jul 2009 00:51:49 -0500 (CDT)

Even if those 1-2 bytes need to be added to every packet?? I know the shrinking payload size in packets is already a major concern. E.g. in IEEE 802.15.4, taking 1-2 bytes off from about 80 bytes of payload is significant. And this number - 80 bytes - is optimistic since other information (IPv6 headers etc.) is going to cause additional shrinking of allowed payload on a packet.

Having a special packet for loop-detection purpose allows you control over how frequently you want to originate this packet. Secondly, path accumulation allows explicit loop detection, which in turn may allow better/efficient loop correction.

Thanks
Mukul

> 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

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 22 Jul 2009 00:26:39 -0700

Hi Mukul,

On Jul 21, 2009, at 10:51 PM, Mukul Goyal wrote:
> Even if those 1-2 bytes need to be added to every packet?? I know  
> the shrinking payload size in packets is already a major concern.  
> E.g. in IEEE 802.15.4, taking 1-2 bytes off from about 80 bytes of  
> payload is significant. And this number - 80 bytes - is optimistic  
> since other information (IPv6 headers etc.) is going to cause  
> additional shrinking of allowed payload on a packet.

In many cases, yes, 1-2 bytes in every packet can be much more  
efficient than sending an explicit control message every X packets.  
Specific to 802.15.4 250 kbps, 1 byte adds 32us of transmission time -  
that's it. Compare that to the cost of CCA (order ms), preamble (128  
us), RX-TX turnaround (192 us), ack (352 us). If the radio is duty- 
cycled, then consider radio start/stop times (order ms) and the guard  
times - around 2 ms total when synchronized or, in the worst-case,  
hundreds of milliseconds to seconds when completely unsynchronized  
(e.g. an extended preamble in a low-power listening protocol).

Also note that transmitting a large datagram as X fragments is often  
more efficient than communicating the same information in Y  
unfragmented datagrams. Fragmented datagrams only carry the L3/L4  
headers in the first fragment and there are a number of optimizations  
that can be applied at the link to reduce the transmission of  
subsequent fragments (e.g. reduced guard times, reduced/removal of  
CCA, etc.).

Finally, hop-by-hop information doesn't accumulate as you get towards  
the more burdened nodes closer to the root - the overhead per datagram  
is fixed. Path accumulation also operates on IPv6 addresses, whereas  
hop-by-hop only communicates routing cost. To make path accumulation  
more viable, we'd have to start discussing address compression  
techniques and/or defining new namespaces.

> Having a special packet for loop-detection purpose allows you  
> control over how frequently you want to originate this packet.  
> Secondly, path accumulation allows explicit loop detection, which in  
> turn may allow better/efficient loop correction.

Note that I do support sending of path accumulation datagrams - it's  
used in the RPL drafts for building source-route information at  
ancestor nodes. The same packets can be helpful for loop detection as  
well. The difference is that I would not rely solely on path  
accumulation datagrams for loop-detection. They are significantly more  
expensive to communicate (compared to hop-by-hop) and, as a result,  
should be communicated infrequently. When loops exist, they are  
costly, and I'd want to detect them quickly when datagrams are flowing.

--
Jonathan Hui

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 22 Jul 2009 02:49:13 -0500 (CDT)

Very good explanation! Thanks.

Cheers
Mukul
----- Original Message -----
From: "Jonathan Hui" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Wednesday, July 22, 2009 2:26:39 AM 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

Hi Mukul,

--
Jonathan Hui

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 22 Jul 2009 08:25:07 -0500 (CDT)

We had a good discussion about relative merits of hop-by-hop loop detection versus path accumulation approach. There is a sound claim that frequent origination of a special control packet is much more expensive than putting "cost" information in each packet (the hop-by-hop approach). One problem with hop-by-hop approach is that it fails to identify the in-loop nodes explicitly and hence any loop correction mechanism based on the knowledge of in-loop nodes can not be used.   

So, I am thinking of the following loop detection and correction approach for the alternative (to RPL) routing scheme:

1. Use hop-by-hop approach to detect the possibility of a loop.
2. The node detecting the loop originates the control packet that would do path accumulation and identify the in-loop nodes. This node then initiates loop correction using this knowledge.

Now, path accumulation packets are originated when we know there is a problem.

Thanks
Mukul
 
----- Original Message -----
From: "Mukul Goyal" <[email-masked]>
To: "Jonathan Hui" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Wednesday, July 22, 2009 2:49:13 AM 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

Cheers
Mukul
----- Original Message -----
From: "Jonathan Hui" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Wednesday, July 22, 2009 2:26:39 AM 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

Hi Mukul,

--
Jonathan Hui

> tradeoffs between both approaches.

_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll