Subject: Re: [Roll] I-D Action:draft-ietf-roll-rpl-04.txt

From: Sung Lee <[email-masked]>
Date: Thu, 29 Oct 2009 12:08:58 -0400

Tim and WG members,

I was reviewing v04 and have some concerns about current proposal.
In particular, the restriction on 2 sibling hops in a row.

> 5.11.4.  Sibling Loop Avoidance
>
>   When a packet is forwarded along siblings, it cannot be checked for
>   forward progress and may loop between siblings.  Experimental
>   evidence has shown that one sibling hop can be very useful but is
>   generally sufficient to avoid loops.  Based on that evidence, this
>   specification enforces the simple rule that a packet may not make 2
>   sibling hops in a row.

I recall that the experiment result was presented at the interim meeting.
However, it was also pointed out that if the selected sibling is not the
right one, then you risk a packet loss.
If the network topology is simple enough, this may be sufficient
restriction to avoid sibling loops.
Without much coordinated effort of trying to figure out the "right" next
hop sibling, this simple restriction will cause many packet drops if the
network topology is complicated.

My understanding is that ROLL is targeting for a large scale network.
And I have concerns about this.
I would like to hear about what others think about this.

Regards,
Sung

>
> Message: 3
> Date: Tue, 27 Oct 2009 09:31:21 -0400
> From: Tim Winter <[email-masked]>
> Subject: Re: [Roll] I-D Action:draft-ietf-roll-rpl-04.txt
> Cc: [email-masked]
> Message-ID: <[email-masked]>
> Content-Type: text/plain; charset=ISO-8859-1
>
> WG,
>
> In this revision we did incorporate much of the recent feedback from the
> list, including
> 	- Remove recommendations for DAG splitting/merging (detach/float/reattach)
> 	- Remove Held-Up state and related procedures
> 	- Remove Held-Down state and related procedures
> 	- Clarified that a DAG Instance is in support of a single application
> objective / optimization, and that RPL specifies operation in a single DAG
> Instance
> 	- ICMPv6 message type proposed to carry DIO/DAO message + DIO/DAO revised
> (OCP now comes from Metric Container)
> 	- Updated DIO suboptions to be consistent with metrics draft (16 bit length)
> 	- Added use of flow label to specify DAG Instance and allow for loop detection
> 	- Misc. editorial changes
>
> We are still working to provide an FSM presentation of RPL.
>
>
> Regards
>
> -RPL Authors
>
> [email-masked] wrote:
>
>> A New Internet-Draft is available from the on-line Internet-Drafts directories.
>> This draft is a work item of the Routing Over Low power and Lossy networks Working Group of the IETF.
>>
>>
>> 	Title           : RPL: IPv6 Routing Protocol for Low power and Lossy Networks
>> 	Author(s)       : T. Winter, et al.
>> 	Filename        : draft-ietf-roll-rpl-04.txt
>> 	Pages           : 82
>> 	Date            : 2009-10-26
>>
>> Low power and Lossy Networks (LLNs) are a class of network in which
>> both the routers and their interconnect are constrained: LLN routers
>> typically operate with constraints on (any subset of) processing
>>
>
>
>> power, memory and energy (battery), and their interconnects are
>> characterized by (any subset of) high loss rates, low data rates and
>> instability.  LLNs are comprised of anything from a few dozen and up
>> to thousands of LLN routers, and support point-to- point traffic
>> (between devices inside the LLN), point-to-multipoint traffic (from a
>> central control point to a subset of devices inside the LLN) and
>> multipoint-to- point traffic (from devices inside the LLN towards a
>> central control point).  This document specifies the IPv6 Routing
>> Protocol for LLNs (RPL), which provides a mechanism whereby
>> multipoint-to-point traffic from devices inside the LLN towards a
>> central control point, as well as point-to-multipoint traffic from
>> the central control point to the devices inside the LLN, is
>> supported.  Support for point-to-point traffic is also available.
>>
>> A URL for this Internet-Draft is:
>> http://www.ietf.org/internet-drafts/draft-ietf-roll-rpl-04.txt
>>
>> Internet-Drafts are also available by anonymous FTP at:
>> ftp://ftp.ietf.org/internet-drafts/
>>
>> Below is the data which will enable a MIME compliant mail reader
>> implementation to automatically retrieve the ASCII version of the
>> Internet-Draft.
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> Roll mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll
>>
>
>
> ------------------------------
>
> Message: 4
> Date: Tue, 27 Oct 2009 12:57:46 -0400
> From: Sung Lee <[email-masked]>
> Subject: Re: [Roll] RPL Metric ID
> To: [email-masked]
> Message-ID: <[email-masked]>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> Philip,
>
> Sorry for my late response. I have been quite swamped with work and
> travels.
> I read your paper and I liked it. I like your concept of using
> information from all three layers.
> Although our approach is not as "formalized" as yours, I think
> fundamentally we do share some similarity.
> I would say that one difference is that we try to reflect the existence
> of loop in the estimation. Since we do actively check for loop
> existence, we reflect that into the estimation value by penalizing it.
> But please note that we do not actively try to remove the loop when we
> find it. Our experience is that by reflecting the existence of loops in
> the estimation/metric, it sorts itself out over time.
>
> Thanks for sharing your paper.
> Best regards,
> Sung
>
> [email-masked] wrote:
>
>> Message: 2
>> Date: Thu, 15 Oct 2009 09:05:23 -0700
>> From: Philip Levis <[email-masked]>
>> Subject: Re: [Roll] RPL Metric ID
>> To: Sung Lee <[email-masked]>
>> Cc: [email-masked]
>> Message-ID: <[email-masked]>
>> Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
>>
>>
>> On Oct 15, 2009, at 7:20 AM, Sung Lee wrote:
>>
>>
>>
>>> JP and WG members,
>>>
>>> This may be considered link reliability.
>>> But in our experience, we found the following information very helpful
>>> in improving the stability of network and also (and you could say) in
>>> avoiding loops as well.
>>>
>>> We use what we call 'W' (weight).
>>> When we forward data packet, we require per-hop ACK.
>>> When we receive ACK, we adjust the new W to be old W -1 (W_new =
>>> W_old - 1).
>>> When we don't receive ACK, we adjust the new W to be old W + 1
>>> (W_old =
>>> W_old +1).
>>> When we detect a loop, we adjust the W value to MAX.
>>>
>>> We have experimented MAX value based on real system, MAX value of 10
>>> seems to be a good value to start with.
>>>
>>> Now this can be combined with other metric values you are all
>>> discussing. We have experimented quite a lot with combing several
>>> metrics with the above weight in determining the path, which so far
>>> seems to work in our system.
>>> For instance, the other metric values you are discussing (such as link
>>> quality, RSSI, and/or everything else - please note this can be as
>>> simple as hop count, RSSI, or whatever the WG determines) can be used
>>> with along with W value to determine.
>>>
>>> I am interested in what the WG thinks of using this 'W' as part of
>>> metric for RPL.
>>>
>>>
>> Sung,
>>
>> I think the general approach of directly measuring the datapath is a
>> great way to have fast and accurate link estimation. CTP's 4-bit link
>> estimator (4B) has some similarities to what you describe, although it
>> smoothes estimates much more: I'd be concerned about excessive
>> instability in the above algorithm, as note that you can't measure a
>> link you're not using.
>>
>> Have you read the 4-bit paper? You can find it at http://sing.stanford.edu/singpubs.html
>>
>> Phil
>>
>>
>>
>>
>>
>>
>
>
> ------------------------------
>
> Message: 5
> Date: Tue, 27 Oct 2009 14:00:55 -0400
> From: Michael Richardson <[email-masked]>
> Subject: Re: [Roll] I-D Action:draft-ietf-roll-rpl-04.txt
> To: [email-masked]
> Message-ID: <[email-masked]>
>
>
>
>>>>>> "Tim" == Tim Winter <[email-masked]> writes:
>>>>>>
>     Tim> - Added use of flow label to specify DAG Instance and allow for loop detection
>
>   Thanks, I think this will help people link things together.
>
> --
> ]       He who is tired of Weird Al is tired of life!           |  firewalls  [
> ]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
> ] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
>    Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
> 	               then sign the petition.
>
>
> ------------------------------
>
> Message: 6
> Date: Tue, 27 Oct 2009 19:22:33 +0100
> From: Alexandru Petrescu <[email-masked]>
> Subject: Re: [Roll] I-D Action:draft-ietf-roll-rpl-04.txt
> To: Michael Richardson <[email-masked]>
> Cc: [email-masked]
> Message-ID: <[email-masked]>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> Michael Richardson a ?crit :
>
>>>>>>> "Tim" == Tim Winter <[email-masked]> writes:
>>>>>>>
>>     Tim> - Added use of flow label to specify DAG Instance and allow for loop detection
>>
>>   Thanks, I think this will help people link things together.
>>
>
> I think calling it a "flow label" may collide with the flow label field
> of IPv6 base header.
>
> Let me tell you why I say so.  I recently went through an implementaiton
> exercise where Route Lifetime and Router Lifetime were mistaken one for
> the other, because they're close enough.
>
> Just a remark.
>
> Alex
>
>
>
>
> ------------------------------
>
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>
>
> End of Roll Digest, Vol 21, Issue 82
> ************************************
>

---

From: JP Vasseur <[email-masked]>
Date: Thu, 29 Oct 2009 17:18:26 +0100

> I would like to hear about what others think about this.

You're quite right that the results were for a limited topology size.  
I would vote for making it
configurable 3-bit flag that could be adjusted according to the  
network topology.

Thoughts ?

JP.

>>   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE 
>> >
>> 	               then sign the petition.
>>
>>

---

From: Sung Lee <[email-masked]>
Date: Thu, 29 Oct 2009 13:14:32 -0400

Tim and WG members again,

 > 5.11.5.  DAO Inconsistency Loop Detection and Recovery
 >
 >   A DAO inconsistency happens when router that has an outwards DAO
 >   route via a child that is a remnant from an obsolete state that is
 >   not matched in the child.  With DAO inconsistency loop recovery, a
 >   packet can be used to recursively explore and cleanup the obsolete
 >   DAO states along a sub-DAG.

Based on our experience, the state of the network is constantly
changing. We previously attempted to correct and maintain the accurate
state upon loop discovery. However, we found that overall performance is
better if we reflect the knowledge of loop existence (we do so into the
weight we use to determine which route to take) and attempts to delivery
the packet via different route.

We are for attempting to recursively deliver the packet via different
route, but we do have concerns about cleaning up the obsolete state.

I am willing to share the details of what we do in regard to loop
detection/correction. However, as I was working through that I realized
that I may need some in depth discussion with editors of this spec, if
WG is interested in what we can bring to the group.

Would you please let me know how we can proceed?
Thank you,
Sung

Sung Lee wrote:
> However, it was also pointed out that if the selected sibling is not
> the right one, then you risk a packet loss.
> Without much coordinated effort of trying to figure out the "right"
> next hop sibling, this simple restriction will cause many packet drops
> if the network topology is complicated.
>
>>    Kyoto Plus: watch the video
>> <http://www.youtube.com/watch?v=kzx1ycLXQSE>
>>                    then sign the petition.
>>
>>