Subject: [Roll] FW: New I-D on composite routing metrics

From: "Theodore Zahariadis" <[email-masked]>
Date: Tue, 2 Aug 2011 09:55:40 +0300

Dear all,
My colleague Dr. Panos Trakadas and myself are working on an EC-funded
research project, called VITRO (Virtualized Distributed platform of Smart
objects - http://www.vitro-fp7.eu/), which has adopted RPL as the primary
routing protocol and we are currently performing some simulations and tests.

By monitoring roll, we have noticed that three (sorry if we have missed any)
I-D are discussed in the ROLL WG (draft-ietf-roll-minrank-hysteresis-of,
draft-ietf-roll-of0, draft-gnawali-roll-etxof), defining RPL Objective
Functions related to a single routing metric (either hop-count or ETX).

In VITRO, each sensor may be part of many virtual networks (even from
different administrative domains) and must be able to concurrently support
multiple user requests even with contradicting QoS characteristics. It is
obvious that in such cases, a composite routing metric is of great
importance.

In draft-zahariadis-roll-metrics-composition-00
(http://datatracker.ietf.org/doc/draft-zahariadis-roll-metrics-composition/)
, we aim at specifying the guidelines for designing efficient composite
routing metrics to be applied at RPL routing protocol.
 
We would be happy to receive your comments
 
Best Regards,
Theodore Zahariadis

------------------------------------
Ass. Prof. Theodore Zahariadis, PhD
Technological Educational Institute of Chalkida
Psachna, Chalkida, Greece
Tel: +30 22280 99550, +30 6932495045
Skype: theodore.zahariadis

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 3 Aug 2011 12:32:57 +0200

Hi Theodore:

I'm curious here: you did not explain why you have to build a single instance with composite metric as opposed to multiple instances each optimized for a certain flow.

In any fashion, you're correct, the OF framework is designed to allow you to have a mission specific logic with multiple criteria. We expect, though, that each metric you need is propagated separately and is not polluted by other metrics. Only the Rank mixes things together, and it is your OF's responsibility to define how that happens...

Cheers;

Pascal

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Theodore Zahariadis
> Sent: Tuesday, August 02, 2011 8:56 AM
> To: [email-masked]
> Cc: TRAKADAS PANOS
> Subject: [Roll] FW: New I-D on composite routing metrics
> 
> Dear all,
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: C Chauvenet <[email-masked]>
Date: Wed, 3 Aug 2011 08:46:35 -0700

Hi Theodore, 

I found your draft interesting and it gave me some useful guidelines for metric's design.

I've several comments on this : 

I fail to understand well the "Order Relation" you use in Table 1.
The definition of "metric order relation" given on page 4 doesn't really helped me.
Could you help me understand the Order Relation column in the table?

In this table in particular (Figure 1): 

	- Could you precise your view of the  Link-Color metric (Why is it in the integer domain, why the order relation in "minimum" ?).

	- As far as I understand the Order Relation, it seems that the LQL order relation should not be "maximum" but rather "minimum" (same relation as ETX, excluding the 0 value).

More generally, I would be happy to see in the document some formulas examples for metric computation, or maybe some guidelines.

Some example of metrics composition would also be great (You mention one in your draft with is ETX + RE (remainging Energy). Do you have some idea about other set of metric that would be interesting to bind ?

I finally think that it should be worth to add some content about the mechanisms that aim to deal with metric's dynamics (Multi Threshold, EWMA, Low pass Filters, ...). Some of them are mentioned at the end of the rpl metric draft.

Best,

Cédric.

---

From: "Theodore Zahariadis" <[email-masked]>
Date: Thu, 4 Aug 2011 09:49:24 +0300

Hi Pascal,

Thanks for your comments!
Probably our email caused a misunderstanding. It is not a matter of single
or multiple instances. Our draft tries to analyze and provide guidelines on
the design of proper OF's dealing with more than one routing metrics,
propagated separately and not polluted by other metrics, as you correctly
mentioned in your email.

For example:
Consider the case where the construction of a DODAG is based on two routing
metrics, namely Hop-Count (HC) and link reliability (LR) (the same also
holds for e.g. the pair of ETX and link-color), carried separately within
DAG Metric Container Object of the DIO message. HC is aggregated along the
path (C=0, O=0, A=0x00, R=0), while the LR is recorded along the path (C=0,
O=0, A=0x02, R=1).Furthermore, consider that node A receives DIO messages
from nodes B and C (being potential parents of node A). The pair of (HC, LR)
values advertized by nodes B and C are (3, 4) and (4, 2), respectively.

In the case that only the HC value is taken into account for parent
selection and Rank evaluation, then the selection of node A parent easily
leads to node B (node A Rank = 3).
On the contrary, if the LR value is considered, then node A will select node
C as its parent (node A Rank = 2). 

Of course the answer here could be: "Based on the application I would select
either HC or LR".
However, in more complex cases e.g. QoS requirement of an optimal path, the
selection of a metric may not be trivial.

One OF approach might be: "Each node selects as a parent the node that
advertizes the minimum value of HC and in case that there are two (or more)
advertizing the same HC value, then it selects the parent that advertizes
the path with the maximum LR." (draft's lexical approach).

Another OF might be: "Combine the pair of HC and LR values in the form of:
HC+LR (additive metric composition)". So, node A will select node C as its
preferred parent. It can be proved that this OF might lead to a construction
of a DODAG where the traversed paths are not optimal!

The intention of our draft is to present the properties that the routing
metrics must hold to assure that the construction of the DODAG (and
consequently the selection of the parent node) leads to optimal and
loop-free paths. So, it deals with OF design as you correctly mentioned in
your email: "it is your OF's responsibility to define how that happens".

This idea is not new. There are well-defined routing algebras that set the
conditions (routing metric properties) for achieving routing protocol
convergence, optimality and loop-freeness, mainly for Internet routing
protocols. Our goal is to "transfer" these routing metrics properties in
LLN's, providing guidelines for the design of efficient OF's.

Best Regards,
Theodore & Panos

-----Original Message-----
From: Pascal Thubert (pthubert) [mailto:[email-masked]] 
Sent: Wednesday, August 03, 2011 1:33 PM
To: [email-masked]; [email-masked]
Cc: TRAKADAS PANOS
Subject: RE: [Roll] FW: New I-D on composite routing metrics

Hi Theodore:

I'm curious here: you did not explain why you have to build a single
instance with composite metric as opposed to multiple instances each
optimized for a certain flow.

In any fashion, you're correct, the OF framework is designed to allow you to
have a mission specific logic with multiple criteria. We expect, though,
that each metric you need is propagated separately and is not polluted by
other metrics. Only the Rank mixes things together, and it is your OF's
responsibility to define how that happens...

Cheers;

Pascal

---

From: Panos Trakadas <[email-masked]>
Date: Fri, 5 Aug 2011 06:58:46 +0100 (BST)

Dear Cedric,

We believe that the definition of "order relation" is correct: the order relation is used by the OF to compare link/node weights along the path (equivalently, metric values) and select parent node. As an example, consider the case where the ETX is aggregated along the traversed path. If node A receives DIO messages from nodes B and C (potential parents) with ETX values of 2.5 and 3.2, respectively, then the order relation will help selecting node B (advertising the minimum value of ETX) as the parent of node A.
In this concept, your comment is right; the order relation of LQL must be minimum (and not maximum). Please consider it as a typo.

Regarding link-color comment: Apart from being used as a 10-bit flag field (e.g. for indicating the encrypted links, as described in rpl-metrics draft), link color may be used to indicate the number of nodes along the path transmitting at a specific radio channel; in this way interference can be reduced by selecting transmission in the "least occupied" channel. In this case, the order relation must be "minimum" and the domain is integer.

In general, we will re-format Table 1, following the metric description in rpl-metrics draft. Also, we will replace words "minimum"/"maximum" in the "order relation" column by "less-than" and "greater-than" in accordance to the order relation definition.

Before submitting this draft, there was a discussion on whether we should include examples and formulas in this initial version of the document; it seems that our decision was wrong... We will be happy to include examples and formulas to improve readability of this draft.

Finally, we think that "hysteresis" can provably improve RPL performance, and thus it will be included in this draft. To be honest, there is a "hidden" phrase: "...and if the first component values are equal *or differ less than a predefined threshold*..." (section 4.1, first sentence) indicating our effort to include hysteresis in this draft. We will give more emphasis on that point.

Thanks for your valuable comments,
Panos.

--- Στις Τετ., 03/08/11, ο/η C Chauvenet <[email-masked]> έγραψε:

Από: C Chauvenet <[email-masked]>
Θέμα: Re: [Roll] FW: New I-D on composite routing metrics
Προς: "[email-masked]" <[email-masked]>
Κοιν.: "TRAKADAS PANOS" <[email-masked]>, "[email-masked]" <[email-masked]>
Ημερομηνία: Τετάρτη, 3 Αύγουστος 2011, 18:46

Hi Theodore, 

Best,

Cédric.

---

From: C Chauvenet <[email-masked]>
Date: Sat, 6 Aug 2011 07:29:35 -0700

Hi,

See inline.

Le 5 août 2011 à 01:58, Panos Trakadas a écrit :

Dear Cedric,

We believe that the definition of "order relation" is correct: the order relation is used by the OF to compare link/node weights along the path (equivalently, metric values) and select parent node.

[C.C] I Agree with your definition.

As an example, consider the case where the ETX is aggregated along the traversed path. If node A receives DIO messages from nodes B and C (potential parents) with ETX values of 2.5 and 3.2, respectively, then the order relation will help selecting node B (advertising the minimum value of ETX) as the parent of node A.
In this concept, your comment is right; the order relation of LQL must be minimum (and not maximum). Please consider it as a typo.

[C.C] OK

[C.C] I think that the confusion is greatly due to the very wide range that the link color metric may cover. You example of the usage of this metric is interesting, but many others usage may be possible, and so an global order relation seems difficult to find for this metric.

[C.C] I agree that it would increase the readability.

[C.C] Nice. I think this would provide precious guidelines for readers, and speed up some RPL design.

[C.C] I noticed that reference, but it should be worth to explicitly speak about it. I also agree that the Hysteresis mechanism defined in the MRHOF draft greatly improve the stability of the topology and should be highly recommended. BTW, some guidelines about how to determine the good threshold value would be interesting.

Cédric.

--- Στις Τετ., 03/08/11, ο/η C Chauvenet <[email-masked]<mailto:[email-masked]>> έγραψε:

Από: C Chauvenet <[email-masked]<mailto:[email-masked]>>
Θέμα: Re: [Roll] FW: New I-D on composite routing metrics
Προς: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Κοιν.: "TRAKADAS PANOS" <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Ημερομηνία: Τετάρτη, 3 Αύγουστος 2011, 18:46

Hi Theodore,

Best,

Cédric.

Le 2 août 2011 à 02:55, Theodore Zahariadis a écrit :

> [email-masked]<http://gr.mc296.mail.yahoo.com/mc/compose?to=[email-masked]>

_______________________________________________
Roll mailing list
[email-masked]<http://gr.mc296.mail.yahoo.com/mc/compose?to=[email-masked]>
https://www.ietf.org/mailman/listinfo/roll