Subject: Re: [Roll] The need for multiplicative metrics and other comments on draft-ietf-roll-routing-metrics-05

From: JP Vasseur <[email-masked]>
Date: Tue, 13 Apr 2010 09:34:32 +0200

Hi Mukul,

Thanks for your comments on the draft. See below.

On Mar 28, 2010, at 8:36 AM, Mukul Goyal wrote:

> Here are some comments on draft-ietf-roll-routing-metrics-05. Not  
> sure if people have already identified these issues.
>
> 1) I am concerned about the fact that the metrics draft does not  
> currently allow a metric to be declared "multiplicative" in nature.
>
> The natural way to aggregate the link-level reliabilities into a  
> path-level reliability is by multiplication.
>
> Quoating from section 4.3.1 ("Link Quality Level Reliability  
> Metric") in the metrics draft:
>
> "Aggregated LQL Value: when used an an additive metric (A=0x00), the
>  aggregated LQL value reports the sum of all the LQL values for all
>  links along the path.  When used to report a minimum (A=0x02), the
>  field reports the minimum LQL value of all links along the path."
>
>
> Aggregating the "Link Quality Levels" by adding them together does  
> not make any sense. This allows two routes, with very different end- 
> to-end reliabilities, to have same aggregated LQL values.
>

Two comments:
1) There are situations where indeed adding metrics is just not  
meaningfull, this is why we introduced the concept of recorded metrics
2) But there are cases, where adding LQL is just good enough.

To you second point, using logs/exponential you could concert additive  
into multiplicative metric.
Should you still want "multiplicative" to avoid too much computation  
on the nodes, let's add a flag value here for multiplcative metric (in
the next revision).

> 2) The beginning text in Section 4.3 (Link Reliability) identifies  
> external and multipath interefence as the reasons for poor link  
> reliability. I think that external interference should be described  
> a little more. For CSMA based MAC layers, too much contention for  
> channel access is also a major cause for high packet loss rates,  
> which should be mentioned as well.
>
> 3) There are two typos in the draft:
>
> 1. At the beginning of section 4.3.1:
>
> "The Link Quality Level (LQL) object is used to quantify the link
>  reliability using a discrete value, from 0 to 3 where 0 indicates
>  that the link quality level is unknown and 1 reports the highest link
>  quality level."
>
> 1 should be replaced by 3.
>

This was not a typo and a fairly common choice in protocol to assign  
the lowest value to higher preference (e.g. link metric for IGP,
router preference). That helps lowest path costs.

> 2. Towards the end of 4.3.2:
>
> "The ETX object may be used as a constraint or a path metric.  For
>  example, an Objective Function may indicate that the ETX must not be
>  below some specified value."
>
> Should be: ETX must not be more than some specified value.
>

Good catch, will fix it.

Thanks.

JP.

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

---

From: JP Vasseur <[email-masked]>
Date: Tue, 13 Apr 2010 09:34:39 +0200

Hi,

On Mar 28, 2010, at 6:31 PM, Yoav Ben-Yehezkel wrote:

> Hi,
>
> Just a quick question, is 1 reports the highest or lowest link  
> quality level?
>

1 is the Highest.

> It seems contradicting in the text.
>
> "
> 4.3.1.  The Link Quality Level Reliability Metric
>
>    The Link Quality Level (LQL) object is used to quantify the link
>    quality level.  The mechanisms and algorithms used to compute the  
> LQL
>    is implementation specific and outside of the scope of this  
> document.
> "
>
>
> Whereas in the following text it says:
>
> "
>    The format of the LQL Type 1 sub-object is as follows
>
>      0 1 2 3 4 5 6 7
>     +-+-+-+-+-+-+-+-+
>     |Val| Counter   |
>     +-+-+-+-+-+-+-+-+
>
>     Figure 12: LQL Type 1 sub-Object format
>
>    Val: LQL value from 0 to 3 where 0 means undetermined and 1  
> indicates
>    the lowest link quality.
>
>    Counter: number of links.
> "
>

=> the latter is a typo (thanks!), will fix it.

> So – which is it?
>
> Anyway, WRT to reliability and LQL - there’s a problem with long  
> good paths (in the following assume 1 indicates the good link). The  
> multiplication of any number of good links will remain 1, where in  
> fact the reliability will drop significantly after a few hops. Also  
> the value 0 indicating unknown will immediately cause the  
> multiplication to be 0 – i.e. unknown (which could make some sense,  
> though in summation it should do no difference to the aggregation).  
> Could there be a problem with the definitions?
>

Should you want to multiply LQL, 0 must be avoided indeed. Note that  
the intent was more for recorded metric.

> Just a nice trick - to get the same results as in option 1 (counting  
> 1/2/3), one can make a multiplication of primes (say 2, 3, 5), and  
> aggregate (using multiplication or summation of logs) the divisors  
> of the aggregated value would be the counters of 2,3,5 which maps to  
> 1/2/3 counters, respectively. I don’t think this is the intent though.
>

Thanks.

JP.

> Thoughts?
>
> Yoav
>
>
> From: [email-masked] [mailto:[email-masked]] On Behalf  
> Of Robert Cragie
> Sent: Sunday, March 28, 2010 5:48 PM
> To: [email-masked]
> Subject: Re: [Roll] The need for multiplicative metrics and other  
> comments on draft-ietf-roll-routing-metrics-05
>
> Hi Mukul,
>
> Multiplicative metrics make sense if the metric is a probability. If  
> the metric is on a logarithmic scale, the sum amounts to a product  
> anyway so it may be sufficient to keep it as an additive metric. In  
> the scale from 1 to 3, perhaps it would be necessary to define what  
> 2 represents, so maybe 4.3.1 needs to be clarified.
>
> Robert
> Robert Cragie (Pacific Gas & Electric)
>
> Gridmerge Ltd.
> 89 Greenfield Crescent,
> Wakefield, WF4 4WA, UK
> +44 (0) 1924 910888
> http://www.gridmerge.com
>
>
> On 27/03/2010 11:36 PM, Mukul Goyal wrote:

---

From: Henning Rogge <[email-masked]>
Date: Tue, 13 Apr 2010 10:02:12 +0200

> into multiplicative metric.
You can do this the other way around to (converting a multiplicative metric 
into an additive one).

> on the nodes, let's add a flag value here for multiplcative metric (in
The advantage I see with additive metrics is that they are easier to implement 
in integer arithmetic. Doing a multiplicative metric in integer arithmetic is 
often a source for subtle bugs.

Henning Rogge

-- 
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Neuenahrer Straße 20, 53343 Wachtberg, Germany
Telefon +49 228 9435-961,   Fax +49 228 9435 685
mailto:[email-masked] http://www.fkie.fraunhofer.de
GPG: E1C6 0914 490B 3909 D944 F80D 4487 C67C 55EC CFE0

---

From: Omprakash Gnawali <[email-masked]>
Date: Tue, 13 Apr 2010 09:44:21 -0700

On Tue, Apr 13, 2010 at 12:34 AM, JP Vasseur <[email-masked]> wrote:
...
>> Should be: ETX must not be more than some specified value.

The ETX Objective Function proposes a threshold. While I was working
on ETXOF, the difficulty was coming up with the "right" threshold for
both link ETX and path ETX. This might be a configuration parameter
but it is not clear what the default value should be. It will be great
to get feedback from the WG on what the default should be.

- om_p

---

From: JP Vasseur <[email-masked]>
Date: Wed, 28 Apr 2010 13:06:24 +0200

Hi,

> to get feedback from the WG on what the default should be.

It is application dependent, and does not need to be standardized.  
This is not a protocol
parameter either, so no need to suggest a default value.

Thanks.

JP.

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Wed, 28 Apr 2010 21:20:27 +0300

Hi,

Sorry for coming up with this comment after this release... It came up to
me only when reviewing the diffs between new and previous version :)

I think there a small issue in the following para.:

"
4.3.1.  The Link Quality Level Reliability Metric
...
     0               1
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |      Aggregated LQL Value     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Figure 13: LQL Type 2 sub-Object format

   Aggregated LQL Value: when used an an additive metric (A=0x00), the
   aggregated LQL value reports the sum of all the LQL values for all
   links along the path.  When used to report a minimum (A=0x02), the
   field reports the minimum LQL value of all links along the path.

"

In case the LQL on any link is unknown 0, and the metric is multiplicative
(A=0x03), using a multiplication by 0 would reset the aggregated LQL
value, whereas if the metric is additive, the aggregated LQL value will
remain unchanged. So I suggest to update the above para. to:

"
...
   Aggregated LQL Value: when used an an additive metric (A=0x00), the
   aggregated LQL value reports the sum of all the LQL values for all
   links along the path.  When used to report a minimum (A=0x02), the
   field reports the minimum LQL value of all links along the path. When
   used to report a multiplication (A=0x03), and the LQL
   field of one of the links along the path is undetermined (LQL=0),
   the undetermined LQL will be ignored and not aggregated (i.e. no
   reset to Aggregated LQL Value field).
"

Thanks,
Yoav

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of JP
Vasseur
Sent: Wednesday, April 28, 2010 2:06 PM
To: Omprakash Gnawali
Cc: roll
Subject: Re: [Roll] The need for multiplicative metrics and other comments
on draft-ietf-roll-routing-metrics-05

Hi,

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Wed, 28 Apr 2010 20:23:35 +0200

Hi,

Good comments, which we agreed upon some time ago, I forgot to  
incorporate it.
OK that will be in the next revision for sure.

Cheers.

JP.

On Apr 28, 2010, at 8:20 PM, Yoav Ben-Yehezkel wrote:

> When
> Of JP

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 29 Apr 2010 15:03:28 +0300

While you're at it, I think I found a few more related small editorial
comments:
"
2.  Object Formats
...
   o  A Field: The A field is used to indicate whether a routing metric
      is additive, reports a maximum or a minimum.
"
Should be:
"   o  A Field: The A field is used to indicate whether a routing metric
      is additive, multiplicative, reports a maximum or a minimum.
"

Another one in section 2:
"
   Example 1: A DAG formed by RPL where all nodes must be main powered
   and the link metric is the link throughput.  In this case the DAG
   Metric container carries two routing objects: the link metric is the
   link throughput (C=0, O=0, A=00, G=1, R=0) and the node constraint is
   power (C=1, O=0, A=00, G=0, R=0).  Note that in this example, the
   link throughput is a global additive aggregated link metric.  An RPL
   implementation may use the metric to report a minimum (A=01).  In
   this case, when the link throughput metric is processed each node
   updates it is the link throughput is less than the value reported by
   the link throughput metric.
"

The text: "An RPL implementation may use the metric to report a minimum
(A=01)."
Should be changed either to:
"An RPL implementation may use the metric to report a minimum (A=02)." OR
"An RPL implementation may use the metric to report a maximum (A=01)."

Question regarding the following in 4.3.1:

"  When used to report a minimum (A=0x02), the
   field reports the minimum LQL value of all links along the path."

This means that an undetermined value (0) beats best value (1) being the
minimum of the two. Is this really the intent? Suggested replacement text
if not:

"  When used to report a minimum (A=0x02), the
   field reports the minimum LQL value of all links along the path,
   ignoring undetermined LQLs (Aggregated LQL Value = 0)."

Also, why does this para. describe only LQL for additive and minimum?
Shouldn't it also describe multiplicative (suggested in previous thread
message) and maximum as well?

I think there are some inconsistencies in section 9.2 and maybe also 9.3:
"
   Codespace of the A field (NSA Object)
    Value  Meaning                              Reference

      0    Routing metric is additive           This document
      2    Routing metric reports a maximum     This document
      3    Routing metric reports a minimum     This document
      4    Routing metric is multiplicative     This document
"
Should the values be inconsistent with the values in the text?

Also:
"   Codespace of the Flag field (Routing common header)
     Bit      Description              Reference

      8       Constraint/metric        This document
      7       Optional Constraint      This document
      5-6     Additive/Max/Min         This document
      4       Global/Local             This document
      3       Recorded/Aggregated      This document
"

Should it be?
"5-6     Additive/Max/Min/Mult    This document"

What does the term "flag field" mean (for example, "NSA Object flag
field")? Does it mean flags/fields?

That's it for now :)

Yoav

-----Original Message-----
From: JP Vasseur [mailto:[email-masked]]
Sent: Wednesday, April 28, 2010 9:24 PM
To: Yoav Ben-Yehezkel
Cc: Omprakash Gnawali; roll
Subject: Re: [Roll] The need for multiplicative metrics and other comments

Hi,

Cheers.

JP.