Subject: Re: [Roll] [roll] #20: Question on Metric ID

From: MiJeom Kim <[email-masked]>
Date: Wed, 3 Mar 2010 14:28:26 +0900

Hi,

It’s time to summarize.

- ETX >= 1, and 100 is enough for Max ETX since more than 10 ETX is
close to infinity.
- 8 bits are enough but need to avoid floating point format.  good to
multiply with a constant factor (C) like 256

I think Henning’s suggestion is good. But we don’t need a big range
for ETX, but precision needs to be increased. So we can adjust it with
5 bit mantissa and 3 bit exponent.

So, we can represent (ETX * C) as (32 + a) * 2^b where 0 <= a <= 31
and 0 <= b <= 7. If C is 128, the max possible ETX is 63 and if C is
64, the max ETX is 126. So let’s try C = 64 and if ETX is bigger than
126, we can just make it the possible max which is 126.

All the numbers can be adjustable again, so please settle down the
issue with your ideas.

I can’t understand the Overloading ETX thing. Nobody suggests
overloading ETX, I think. What do you mean by that in this thread,
Omprakash?

Mijeom.

On Wed, Feb 24, 2010 at 2:00 AM, Omprakash Gnawali
<[email-masked]> wrote:
> On Tue, Feb 23, 2010 at 2:22 AM, Henning Rogge
> <[email-masked]> wrote:
> ....
>>> Does your bad experience related to metric representation from running
>>> OLSR network have to do with metric precision?
>> No, we discovered that we could not represent ethernet links (connecting
>> multiple devices) better than a "perfect" wireless link in our metric
>> encoding, so our routing agent prefers a single wireless link with some packet
>> loss over an ethernet-hop plus a perfect wireless link, which is BAD.
>>
>> It's a good idea to keep a little bit room for "better links".
>>
>> We use 1 byte for LQ with a factor of 255 to shift the floating point value
>> (0.0 - 1.0) into a pure integer one. It's very difficult to change the encoding
>> of the routing metric later without reinstalling the whole network at once.
>
> Thanks for sharing this insight. We need to be aware of similar
> scenarios also on LLNs.
>
> I think RPL's approach is to have different objective functions that
> maximize/minimize or constrain different metrics, and even apply a
> series of objective functions for path selection if desired. That
> seems like a better approach than overloading many meanings to ETX.
> Does OLSRv2 support different metrics such as data rates and energy?
> If it does, are there still advantages to overloading ETX?
>
> - om_p
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: Henning Rogge <[email-masked]>
Date: Wed, 3 Mar 2010 08:05:20 +0100

> multiply with a constant factor (C) like 256
As soon as you move to ETT or MIC you need a higher range. Either you use a 
32-bit integer or floating point, otherwise Ripple will be unable to run with 
better metrics.

> overloading ETX, I think. What do you mean by that in this thread,
I suggest not to design your protocol for a single routing metric. That would 
make Ripple inflexible and force you to change the message format later when 
you want to move to something better.

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-263,   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: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 3 Mar 2010 10:33:26 +0100

Hi:

The latest version of the draft accommodated the Rank in 2 bytes, in particular to enable the granularity that latency would require.

We have a min increment that acts as the location of the floating point. This is very generic, but it also makes the text, and probably the code that goes with it, a lot more complex than need be, in particular with the use of divisions and floor().

We could probably live with Richard's original proposal, that is to generalize the minimum increment to what's proposed here, 256. IOW use the first byte as the floor to determine siblings etc... and use the secnd byte to carry finer grained information that becomes seful when things add up.

I suggest we make an issue on the draft to figure that out. Ideas?

Pascal

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Henning Rogge
> Sent: Wednesday, March 03, 2010 8:05 AM
> To: MiJeom Kim
> Cc: [email-masked]
> Subject: Re: [Roll] [roll] #20: Question on Metric ID
> 
> > - 8 bits are enough but need to avoid floating point format. è good to
> make Ripple inflexible and force you to change the message format later
> when you want to move to something better.
> 
> Henning Rogge
> 
> --
> Kommunikationssysteme (KOM) Neuenahrer Straße 20, 53343 Wachtberg,
> Germany

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 03 Mar 2010 13:20:20 -0500

> Date: Wed, 3 Mar 2010 10:33:26 +0100
> From: "Pascal Thubert (pthubert)" <[email-masked]>
> 
> We have a min increment that acts as the location of the floating
> point. This is very generic, but it also makes the text, and probably
> the code that goes with it, a lot more complex than need be, in
> particular with the use of divisions and floor().

I don't think it adds significant implementation complexity.
For any given metric the rank is a fixed-point number.

                                    -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 4 Mar 2010 08:21:19 +0100

Richard:

With the current text, one could make a min increment that is say, 103.
The division should be something that can be achieved at worst  by a
simple shift.
Making the position of the dot a variable destroys the generic aspect of
the Rank, and for example the capability to extend the network with OF0.
I think that is very wrong.
So while I agree to use a second byte to reflect fined grained metrics
increments, I do not see the value of the added complexity of making the
min increment anything. 
Do  you have a use case that justifies that?

My take is that this deserves a ticket.

Pascal

> From: Richard Kelsey [mailto:[email-masked]]
> Sent: Wednesday, March 03, 2010 7:20 PM
> To: Pascal Thubert (pthubert)
> Cc: [email-masked]; [email-masked]; [email-masked]

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 04 Mar 2010 07:55:02 -0500

> Date: Thu, 4 Mar 2010 08:21:19 +0100

Pascal,

> The division should be something that can be achieved at worst  by a

We have to trust the writers of objective functions to do
something sensible.

> the Rank, and for example the capability to extend the network with OF0.

The current draft requires that non-leaves understand the
objective function:

 In the case where a node is unable to encounter a suitable RPL
 Instance using a known Objective Function, it may be configured to
 join a RPL Instance using an unknown Objective Function - but in that
 case only acting as a leaf node.

Ranks from different objective functions are not comparable.

> min increment anything.  Do you have a use case that justifies that?

This needs to be determined by the objective function, not
by RPL.  There is added complexity only if the objective
function mandates it.  I don't see why we should limit the
authors of objective functions in this way.

                                        -Richard

---

From: Omprakash Gnawali <[email-masked]>
Date: Fri, 5 Mar 2010 12:58:33 -0800

> overloading ETX, I think. What do you mean by that in this thread,

It was the suggestion that not all ETX=1 links are the same so we
should leave room in the metric to differentiate preferred ETX=1 link
from the other ETX=1 links. The example that was used was, wired ETX=1
link vs wireless ETX=1 link. If we make minimum ETX value to be 1,
then there is no room for such differentiation based on just the ETX
metric.

- om_p

---

From: MiJeom Kim <[email-masked]>
Date: Mon, 8 Mar 2010 10:38:19 +0900

Thank you for clearing the issue.

So, we don't need the overloading ETX, then.
How do you think about my suggestion:

we can represent (ETX * C) as (32 + a) * 2^b where 0 <= a <= 31 and 0
<= b <= 7. If C is 128, the max possible ETX is 63 and if C is 64, the
max ETX is 126. So let’s try C = 64 and if ETX is bigger than 126, we
can just make it the possible max which is 126.

Other better ideas?
let's close the ticket soon.

Mijeom.

On Sat, Mar 6, 2010 at 6:04 AM, Marcello Caleffi
<[email-masked]> wrote:
> If the delivery ratios are correctly estimated, there is no difference among 1ETX links, wired wireless or anything else.
> The issue is in correctly estimating the delivery ratios, but this does not need additional bits in the header.
>
> Marcello
>
>
> Il giorno 05/mar/2010, alle ore 21.58, Omprakash Gnawali ha scritto:
>
>> manet mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/manet
>
>

---

From: Matteo Paris <[email-masked]>
Date: Mon, 8 Mar 2010 09:40:34 -0500

I'd prefer using a 16-bit fixed point value for ETX, with 4 bits of 
fractional part.  It's very simple, and easily covers the desirable 
ranges.

I don't think the ETX value field is the right place to try to save 
one byte.  If we need to shave bytes, there are other good 
candidates.  For example we could reduce the length fields of DIO 
suboptions and routing metric common headers from 2 bytes to 1 byte. 
We could also eliminate the byte of flags from the routing metric 
common header since that information is redundant if you know the 
Objective Function, and unused if you don't.

Matteo

At 10:38 AM +0900 3/8/10, MiJeom Kim wrote:
>max ETX is 126. So let's try C = 64 and if ETX is bigger than 126, we
>>  If the delivery ratios are correctly estimated, there is no 
>>difference among 1ETX links, wired wireless or anything else.
>>  The issue is in correctly estimating the delivery ratios, but this 
>>does not need additional bits in the header.
>>
>>  Marcello
>>
>>
>>>>  It's time to summarize.
>>>>  - 8 bits are enough but need to avoid floating point format. ? good to
>>>>  I think Henning's suggestion is good. But we don't need a big range
>>>>  64, the max ETX is 126. So let's try C = 64 and if ETX is bigger than
>>>>  I can't understand the Overloading ETX thing. Nobody suggests

---

From: Marcello Caleffi <[email-masked]>
Date: Fri, 5 Mar 2010 22:04:55 +0100

Marcello

---

From: MiJeom Kim <[email-masked]>
Date: Wed, 10 Mar 2010 11:21:11 +0900

Hi, Matteo,

I think we don't need two bytes since 1 byte can manage it as I
suggested. 1 byte can be enough for ETX according to what we have
discussed until now. Even using 2 bytes, we need more bits for
fractional part. Anyway, what's your proposal to express fractional
part using 4 bits?

Mijeom.

On Mon, Mar 8, 2010 at 11:40 PM, Matteo Paris <[email-masked]> wrote:
> fractional part.  It's very simple, and easily covers the desirable ranges.
>
> I don't think the ETX value field is the right place to try to save one
> byte.  If we need to shave bytes, there are other good candidates.  For
> example we could reduce the length fields of DIO suboptions and routing
> metric common headers from 2 bytes to 1 byte. We could also eliminate the
> byte of flags from the routing metric common header since that information
> is redundant if you know the Objective Function, and unused if you don't.
>
> Matteo
>
>
>>>  If the delivery ratios are correctly estimated, there is no difference
>>> among 1ETX links, wired wireless or anything else.

---

From: "roll issue tracker" <[email-masked]>
Date: Wed, 17 Mar 2010 01:58:04 -0000

#20: Question on Metric ID
--------------------------------+-------------------------------------------
 Reporter:  jpv@…               |        Owner:  mjkim@…     
     Type:  defect              |       Status:  closed      
 Priority:  major               |    Milestone:              
Component:  routing-metrics     |      Version:              
 Severity:  Active WG Document  |   Resolution:  fixed       
 Keywords:                      |  
--------------------------------+-------------------------------------------
Changes (by mjkim@…):

  * status:  new => closed
  * resolution:  => fixed

Comment:

 After long discussion, we concluded as follows:

 - Throughput: 32 unsigned integer in unit of microsecond

 - Latency: 24 unsigned integer in unit of bytes per second

 - ETX: 1 byte to present (ETX * C) as (32 + a) * 2^b
   where C = 64, 0 <= a <= 31 and 0 <= b <= 7.
   If ETX >= 126, we can assume ETX is infinity.
  (First 5 bits for a and the rest 3 bits for b.)

 Thanks,
 Mijeom.

-- 
Ticket URL: <https://svn.tools.ietf.org/wg/roll/trac/ticket/20#comment:1>
roll <http://tools.ietf.org/wg/roll/>

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 17 Mar 2010 08:36:31 -0400

> From: "roll issue tracker" <[email-masked]>
> Date: Wed, 17 Mar 2010 01:58:04 -0000
> 

I applaud the decision not to use floating point for
throughput and latency.  Can we please do the same for ETX?
Many of the same arguments apply to it as well (e.g.
http://www.ietf.org/mail-archive/web/roll/current/msg03104.html).
Make it ETX * 64 as a 16-bit unsigned integer.

                               -Richard Kelsey

---

From: Philip Levis <[email-masked]>
Date: Wed, 17 Mar 2010 08:18:49 -0700

> Make it ETX * 64 as a 16-bit unsigned integer.

+1

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 17 Mar 2010 18:07:08 +0100

How about using RTT too?

RTT Round Trip Time is inherent in protocols such as TCP, and is 
typically measured by ping available on many platforms.

RTT could be accurately measured and compared between different 
implementations.

Alex

Le 17/03/2010 02:58, roll issue tracker a écrit :
>     where C = 64, 0<= a<= 31 and 0<= b<= 7.
>     If ETX>= 126, we can assume ETX is infinity.

---

From: Omprakash Gnawali <[email-masked]>
Date: Wed, 17 Mar 2010 18:41:59 -0700

>> Make it ETX * 64 as a 16-bit unsigned integer.

+1 for not using floating point for ETX.

- om_p

---

From: MiJeom Kim <[email-masked]>
Date: Fri, 19 Mar 2010 13:59:36 +0900

Okay, then.
Let make ETX * 128 as a 16 bit unsigned integer. (With 16 bits, the
range can be up to 65535 so we may use a bigger number (like 256) as
the Constant C. But, let's just leave it for now.)
And let's round off to the nearest whole number.
For example, if ETX = 3.569, the metric value will be 457.
If ETX > 511.9921875, let make the metric vale the maximum which is 65535.

Mijeom.