Subject: [Roll] Σχετ: Some comments about draft-zahariadis-roll-metrics-composition-01

From: [email-masked]
Date: Tue, 15 Nov 2011 16:59:46 +0100

Hello,

We are in a research team interested by routing metric composition in sensors network. We agree with the draft but have some comments :
Comment 1

In [draft-zahariadis-roll-metrics-composition-01] section 4.9 Composite metric MUST hold properties of isotonicity and monotonicity 

(paragraph just before figure 7) you claim:

Since the contribution of any path increases the non-negative composite metric value and one is minimizing along the non-decreasing paths, the metric satisfies the property of monotonicity.
 
This text can be understood as the composite metric <Latency + T> with ‘<’ as the composite metric order relation satisfies the property of monotonicity. When we examine figure 7, we can see that w(A,C,D) = 13 and w(A,C,D,E) = 13. Since w(A,C,D,E) is not greater than w(A,C,D), the monotonicity cannot hold. Worst if we change the node (E) Throughput to 1 (rather than 2), we compute w(A,C,D,E) = 12 (and then w(A,C,D,E) < w(A,C,D)), which decrease the path weight.

Comment 2

In [draft-zahariadis-roll-metrics-composition-01] section 2.2 Metric Operator (First paragraph) you claim:

According to [I-D.ietf-roll-routing-metrics], a metric can either be recorded or aggregated along the path. In the former case, the metric can be of maximum type (A=0x01) or minimum type (A=0x02), while in the latter case, a metric can be of additive type (A=0x00) or multiplicative type (A=0x03).
 
The referenced draft rather mention (section 2.1 DAG Metric Container Format, page 9 paragraph 3)

   The A field is only relevant for metrics and is
   used to indicate whether the aggregated routing metric is additive,
   multiplicative, reports a maximum or a minimum.

Reference that contradicts what you say. A field is relevant only when using aggregated metric, and must take one of the following values (A=0X00 additive, A=0x01 maximum A=0x02 minimum and A=0x00 multiplicative)

> Dear Nicolas,
> 
> Thanks for commenting this draft.
> We will soon update the draft taking into consideration your comments.
> See our reply below.
> 
> Best Regards,
> Panos Trakadas.
> 
> ----- Original Message ----- From: "Nicolas DEJEAN" <nicolas.dejean.ietf at googlemail.com>
> To: <zahariad at teihal.gr>; <trakadasp at adae.gr>
> Sent: Tuesday, October 04, 2011 6:00 PM
> Subject: Some comments about draft-zahariadis-roll-metrics-composition-01
> 
> 
> Hello,
> 
>.....

> Example 6 and Figure 7: I do not really understand the figure there.
> What are the local values (certainly L and T link properties)?
> Whar are the values advertised (i.e. the ones the potential successor
> have to take into account for computong their own)?
> 
> ->Panos: Correct. This is the only example that does not show link values, but node values, confusing the reader. We will modify it according to your comment.
> 
> I agree that with the 'bad' compound metric used, it seems that
> sub-optimal paths are used. However, in this example, practically the
> parent choice is the good one as the only available candidate for (E)
> is (D).
> Maybe a more complex example would show the selection of the wrong parent ...
> 
> ->Panos: Of course node E selects node D, as its only parent. What we are highlighting is that since the metric is not isotonic, >when node D is the source, it selects path (A,B,D), while when node D acts as a relay node, forwarding traffic of E, then it will >select path (A,C,D) which is not the optimal one.
> 

This seems to be a source routing mechanism that is not present in RPL (as our knowledge). 

Maybe the figure bellow is a better answer  that show how non isotonicity can lead to a sub-optimal path selection.

  +-------------------------------------------------------------------+
   |                   ------------ (A) <1 , 10>                       |
   |                  /             / \                                |
   |                 /             /   \                               |
   |                /             /     \                              |
   |               /             /       \                             |
   |              /             /         \                            |
   |             /             /           \                           |
   |            /             /             \                          |
   |  <6 , 8> (F)    <3 , 2> (B)             (C) <1 , 9>               |
   |           |              \             /                          |
   |           |               \           /                           |
   |           |                \         /                            |
   |           |                 \       /                             |
   |  <4 , 3> (G)                 \     /                              |
   |           |                   \   /                               |
   |           |                    \ /                                |
   |           |            <2 , 8> (D) w(A,B,D) = <6 , 2> = 8         |
   |           |                     |  w(A,C,D) = <4 , 8> = 12        |
   |            \                    |                                 |
   |             \                   |                                 |
   |              \         <6 , 2> (E) w(A,B,D,E) = <12 , 2> = 14     |
   |               \      ----------/   w(A,C,D,E) = <10 , 2> = 12     |
   |                \    /                                             |
   |                 \  /                                              |
   |         <1 , 1> (H) w(A,F,G,H) = <12 , 1> = 13                    |
   |                     w(A,B,D,E,H) = <13 , 1> = 14                  |
   |                     w(A,C,D,E,H) = <11 , 1> = 12                  |
   |                                                                   |
   +-------------------------------------------------------------------+

In this case we have modified the C node latency (from 2 to 1) and added nodes F to H.
As in the figure in the draft, first the node D propagates in DIO the lightest path toward A (A,B,D). Second the node E propagates the path toward A (A,B,D,E) with a weight of 14. At the other side, the path from H to A (A,F,G,H) has a weight of 13 and so will be choose by the node H. 

However the best path according to this metric composition is the one which pass through E and C (A,C,D,E,H). This example shows that the non isotonicity of such composition will lead to a non optimal routing. 

Emmanuel Nataf
Patrick Olivier Kamgueu

---

From: Panos Trakadas <[email-masked]>
Date: Wed, 16 Nov 2011 12:40:03 +0000 (GMT)

Dear Emmanuel,

Thanks for your comments.
See our answers in line (underlined).
A new version will be uploaded in the next few days, modifying the draft according to your comments.

Best Regards,
Panos.

________________________________
Απο: "[email-masked]" <[email-masked]>
Προς: [email-masked]
Κοιν.: Patrick Olivier Kamgueu <[email-masked]>
Στάλθηκε: 5:59 μ.μ. Τρίτη, 15 Νοεμβρίου 2011
Θεμα: [Roll]  Σχετ: Some comments about draft-zahariadis-roll-metrics-composition-01

Hello,

This text can be understood as the composite metric <Latency + T> with ‘<’ as the composite metric order relation satisfies the property of monotonicity. When we examine figure 7, we can see that w(A,C,D) = 13 and w(A,C,D,E) = 13. Since w(A,C,D,E) is not greater than w(A,C,D), the monotonicity cannot hold. Worst if we change the node (E) Throughput to 1 (rather than 2), we compute w(A,C,D,E) = 12 (and then w(A,C,D,E) < w(A,C,D)), which decrease the path weight.
Panos: According to section 4.9 of the draft, a routing metric is monotonic if and only if w(a)<=w(a&b) and w(a)<=w(c&a) (where ’&’ denotes the metric operator) for any paths a,b,c, while a routing metric is defined as strictly monotonicity if both w(a)<w(a&b) and w(a)<w(c&a) hold.The same statements apply to isotonicity and strict isotonicity. In other words, in case thatw(A,C,D) = 13= w(A,C,D,E), the metric is monotonic(although not strictly monotonic). The problem appears if we change the node (E) Throughput to 1 (rather than 2). In this case, monotonicity does not hold.

We have already identified the problem and we are now modifying the composite metric in or4der to provide an example where monotonicity holds but isotonicity does not. In this respect, we will make use of your example/figure but modified in order to fulfill monotonicity property requirements. The composite metric is defined as (L+(1/T)). By doing so, the composite metric is monotonic, but not always isotonic.

Comment 2

The A field is only relevant for metrics and is used to indicate whether the aggregated routing metric is additive, multiplicative, reports a maximum or a minimum.

Reference that contradicts what you say. A field is relevant only when using aggregated metric, and must take one of the following values (A=0X00 additive, A=0x01 maximum A=0x02 minimum and A=0x00 multiplicative)
Panos: This is correct. We have already changed the wording, according to Nicolas comment as well.

Panos: Utilizing recorded metrics is a "sense" of source routing, isn't it?

However the best path according to this metric composition is the one which pass through E and C (A,C,D,E,H). This example shows that the non isotonicity of such composition will lead to a non optimal routing. 
Panos: A bit more complicated example but, for sure, indicates in a better way the impact of non-isotonicity property. We will take into account this figure, although we have to modify the composite metric (L+T) in such a way that monotonicity property holds (L+(1/T)). 

Emmanuel Nataf
Patrick Olivier Kamgueu

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