Subject: Re: [Roll] [roll] #53: How does an OF compute rank from metric values?

From: Mukul Goyal <[email-masked]>
Date: Thu, 17 Jun 2010 20:58:23 -0500 (CDT)

Hi Yoav

>Thanks for clarifying this.

>CU is a good idea, though I think different L1/2 technologies define
>different mappings for the same metric.

>Very fast delay metric for some technologies may be very slow for other
>technologies, so it's not just a question of metric. You also need a
>normalization method to accommodate for the technology (maybe by
>percentage from maximum capacity or something similar).

I guess I see the problem you are referring to. 

Suppose the delay metric defines the mapping as follows: 
1000ms or more => 1000 CU
x ms => x CU, if 1 <= x < 1000
less than 1ms => 1 CU 

Consider 3 link layer technologies: A, B and C.

Suppose the typical one hop latency value ranges associated with these technologies are 1s-10s, 1ms-10ms and 1us-10us respectively.

Suppose initially A is the predominant link layer technology in terms of deployment. As per the mapping, most links/paths will have CU value 1000 for latency, which is not acceptable. Similarly, if C is the predominant link technology, most links/paths will have CU value 1 for latency.  

So, I guess, rather than being part of metric definition, the metric to CU mapping could be:

1) a configuration parameter for RPL. The LLN administrator decides what the mapping should be and enforces this mapping throughout the LLN. I guess this is problematic for large LLNs because invariably there will be configuration inconsistencies throughout the LLN.
2) The other option is to make this mapping a part of DAG configuration to be periodically advertized by the DAG root in its DIO. 

In any case, an OF definition can assume that such mapping exists for each metric.    

Thanks
Mukul
 
>Taking this though one step further, IP routing can be expected as a
media-agnostic bridge between different L1/2 technologies. Do you see
your suggestion working in this case as well?

Regards,
Yoav

-----Original Message-----
From: Mukul Goyal [mailto:[email-masked]]
Sent: Thursday, June 17, 2010 9:36 AM
To: Yoav Ben-Yehezkel
Cc: [email-masked]
Subject: Re: [Roll] [roll] #53: How does an OF compute rank from metric
values?

Hi Yoav

I guess I did not express myself correctly. So, let me rephrase myself:

How about if we require a metric definition to provide a mapping to an
equivalent value in a common unit (lets call it CU).

So, the definition for latency metric will provide a mapping like:
latency 1s or more => 1000 CU
latency 700ms to 1s => 500 CU
.... latency 5ms or less => 1 CU

The definition for ETX will provide a mapping like:
ETX 100 or more => 1000 CU
ETX 50 to 100 => 500 CU
.... ETX 1 to 1.2 => 1 CU

Then, the job of objective function becomes easier; it just needs to
specify how to combine metric values expressed in CU's in to the rank
value. E.g. we
can have an OF for weighted sum: w_1*val_1 + w_2* val_2 + ....
Here, val_1 refers to the first metric in the metric container and so
on. And w_1, w_2 etc. are specified as the TLVs in a DIO option (lets
call it
the OF option).
So, the OF is specified in OCP field in the configuration object and the
argument/parameter values for the OF are specified in an OF option.

cheers
Mukul

Thanks
Mukul

----- Original Message -----
From: "Yoav Ben-Yehezkel" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>, [email-masked]
Sent: Thursday, June 17, 2010 1:10:38 AM
Subject: RE: [Roll] [roll] #53: How does an OF compute rank from metric
values?

Hi Mukul,

At least my understanding of the following is that the rank should not
necessarily be a direct mapping function of the metric. If it were,
there would have been no use for two different concepts (rank and
metric). Not
just for the sake of ranges and granularities.

"
3.6.2. Rank Properties

The rank of a node is a scalar representation of the location of that
node within a DODAG version. The rank is used to avoid and detect
loops, and as such must demonstrate certain properties. The exact
calculation of the rank is left to the Objective Function, and may
depend on parents, link metrics, and the node configuration and
policies.

The rank is not a cost metric, although its value can be derived from
and influenced by metrics. The rank has properties of its own that
are not necessarily those of all metrics:

Type: The rank is an abstract decimal value.

Function: The rank is the expression of a relative position within a
DODAG version with regard to neighbors and is not necessarily
a good indication or a proper expression of a distance or a
cost to the root.
"

If we decide to go your way - I see some potential for simplification
having just one number that determines both cost and position in the
DODAG.

Thoughts?

Regards,
Yoav

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Mukul Goyal
Sent: Thursday, June 17, 2010 8:33 AM
To: [email-masked]
Subject: Re: [Roll] [roll] #53: How does an OF compute rank from metric
values?

How about if we require a metric definition to provide a mapping to an
equivalent rank value. Then, the job of objective function becomes
easier; it just needs to combine equivalent values in the desired
manner.

Why wont this scheme work??

Thanks
Mukul

----- Original Message -----
From: "roll issue tracker" <[email-masked]>
To: [email-masked], [email-masked]
Cc: [email-masked]
Sent: Thursday, June 17, 2010 12:15:30 AM
Subject: [Roll] [roll] #53: How does an OF compute rank from metric
values?

#53: How does an OF compute rank from metric values?
--------------------------------+-------------------------------------------
Reporter: jpv@… | Owner: wintert@…
Type: defect | Status: new
Priority: major | Milestone:
Component: rpl | Version:
Severity: Active WG Document | Keywords:
--------------------------------+-------------------------------------------
We have different types of metrics with different ranges. Examples:
ETX is 16 bits. Latency is 24 bits. How do we convert these numbers to
rank in an OF? Does the range of rank depend on the range and size of
the metric?

-- Ticket URL: <http://trac.tools.ietf.org/wg/roll/trac/ticket/53>
roll <http://tools.ietf.org/wg/roll/>

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

---

From: JP Vasseur <[email-masked]>
Date: Fri, 18 Jun 2010 19:52:38 +0200

One comment in line.

On Jun 18, 2010, at 3:58 AM, Mukul Goyal wrote:

> Suppose the typical one hop latency value ranges associated with  
> these technologies are 1s-10s, 1ms-10ms and 1us-10us respectively.
>
> Suppose initially A is the predominant link layer technology in  
> terms of deployment. As per the mapping, most links/paths will have  
> CU value 1000 for latency, which is not acceptable. Similarly, if C  
> is the predominant link technology, most links/paths will have CU  
> value 1 for latency.
>
> 1) a configuration parameter for RPL. The LLN administrator decides  
> what the mapping should be and enforces this mapping throughout the  
> LLN. I guess this is problematic for large LLNs because invariably  
> there will be configuration inconsistencies throughout the LLN.
> 2) The other option is to make this mapping a part of DAG  
> configuration to be periodically advertized by the DAG root in its  
> DIO.
>

Just a comment ... if you look at other routing protocols, we do not  
standardize how the metrics are computed. In some IGP, network  
administrators choose to use a polynomial function of several metrics,  
thus ending up in a single metric that has to be used consistently of  
course. Note that this is not standardized. When you look at other  
parameters such as the reserved bandwidth (used as a constraint in  
MPLS Traffic Engineering for example), one can also under or overbook  
locally and there are very good reasons for doing so (still a matter  
of local policy, no standardization). In the case of inter-domain  
route (across AS), well, domains may use IGP using non consistent  
metrics. In this case, most of the RFC/IDs specifies that a metric  
normalization should be performed somewhere (PCE, ASBR, ...). These  
are just a few examples ... I understand that we do not want to  
require lots of configuration on routers within the LLN, but this does  
not necessarily translate into standardizing everything.
Makes sense ?

Thanks.

JP.

> -------------------------------- 
> +-------------------------------------------
> -------------------------------- 
> +-------------------------------------------

---

From: Philip Levis <[email-masked]>
Date: Sun, 20 Jun 2010 18:21:28 -0700

On Jun 18, 2010, at 10:52 AM, JP Vasseur wrote:

> 
> Just a comment ... if you look at other routing protocols, we do not standardize how the metrics are computed. In some IGP, network administrators choose to use a polynomial function of several metrics, thus ending up in a single metric that has to be used consistently of course. Note that this is not standardized. When you look at other parameters such as the reserved bandwidth (used as a constraint in MPLS Traffic Engineering for example), one can also under or overbook locally and there are very good reasons for doing so (still a matter of local policy, no standardization). In the case of inter-domain route (across AS), well, domains may use IGP using non consistent metrics. In this case, most of the RFC/IDs specifies that a metric normalization should be performed somewhere (PCE, ASBR, ...). These are just a few examples ... I understand that we do not want to require lots of configuration on routers within the LLN, but this does not necessarily translate into standardizing everything.
> Makes sense ?

It does, but I don't think the metaphor holds; the scale of LLN networks are such that inter-router normalization to preserve higher-level policies just isn't cost-effective. The issue we're facing is having devices from different vendors autonomously form an ad-hoc mesh within a single administrative domain. I'd argue this is a different problem than bringing up a new router in a standard IGP domain. Do you agree?

Phil