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

From: Mukul Goyal <[email-masked]>
Date: Sun, 28 Mar 2010 13:21:31 -0500 (CDT)

Hi Robert

Link reliability is indeed a probability. I see LQL as a mapping from this probability to a discrete value space (in this case: 1, 2, 3).

Yes, rather than multiplying reliabilities, we can simply add their log values. But, the LQL value space is too small to represent the log value with fine-enough granularity. 

Here is one mapping that I tried:

Here, col 1 is the reliability, col 2 is ln(rel), col 3 is 3.1+ln(rel) and col 4 is the LQL
0.99	   -0.010050336	       3.089949664   3
0.9        -0.105360516        2.994639484   3
0.8        -0.223143551        2.876856449   3
0.7        -0.356674944        2.743325056   3
0.6        -0.510825624        2.589174376   3
0.5        -0.693147181        2.406852819   2
0.4        -0.916290732        2.183709268   2
0.3        -1.203972804        1.896027196   2
0.2        -1.609437912        1.490562088   1
0.1        -2.302585093        0.797414907   1

So, the mapping is:

rel. range (0.6 and higher) => LQL 3
rel. range (between 0.2 and 0.6) => LQL 2
rel. range (0.2 and lower) => LQL 1

Suppose that we were to use this mapping. Suppose there is a path with 3 links with rel. values 0.1, 0.1 and 0.1. The sum of the log values is 3*(-2.3) = -6.9. But, if rel. 0.1 is mapped to LQL value 1, the addition of 3 LQLs is 3. When I receive a DIO with aggregated (summed) LQL 3, I dont know that this value is sum of 3 link-level LQLs 1, 1 and 1. If I were to "record", rather than aggregate, link-level LQL values, I will be able to determine e2e rel. reasonably accurately. But, summing LQL values does not help me. Summed up LQL value 3 does not tell me if the e2e rel. is 0.99 or 0.001.

Now, if I were to declare "reliability" as a "multiplicative" metric and specify a mapping between rel. and LQL, I can aggregate the LQL values in the following manner:

1. Suppose I receive aggregated LQL value 3 in a DIO. 
2. I map it back to the reli. range 0.6-1.0.  
3. I multiply my local rel. (say 0.7) to upper/lower ends of this range (so I get range 0.42-0.7) which I map to LQL value 2 and put this value in the DIO that I send out.   

Thanks
Mukul

----- Original Message -----
From: "Robert Cragie" <[email-masked]>
To: [email-masked]
Sent: Sunday, March 28, 2010 9:47:53 AM GMT -06:00 US/Canada Central
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: 

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.

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.

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.

Thanks
Mukul

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