Subject: [manet] Metric encoding for OLSRv2

From: Henning Rogge <[email-masked]>
Date: Tue, 15 Jun 2010 13:37:15 +0200

Hello,

I would like to start a discussion about how to encode a metric for the coming 
OLSRv2 RFC. The current proposal from Christopher Dearlove is:
(see http://tools.ietf.org/html/draft-dearlove-olsrv2-metrics-04#section-4.6)

metric value = 16 * (1 + a/16) * 2^b
                    = (16 + a) * 2^b
a,b element of [0;15]

This creates a metric range between 16 (a=b=0) and 1.015.808 (a=b=15).
The default_metric value is defined as 4096 (a=8, b=0).

----------------
I think this representation could be improved in some ways.

First it would be good to have a metric representation for cost 0.
When migrating from a multiplicative metric to an equivalent additive one (by 
using a logarithm on the link cost before transmitting) we will need the value 
0 for representing the multiplicative factor 1.0 (which is used by a few 
routing protocols with multiplicative metrics I know).

Second I would like to have a special metric representation for cost 
"infinite/lost". This would allow OLSR to invalidate links in the TCs without 
transmitting a full TC update. Some kind of "explicit lost link" notification.

The third problem I see with the current draft is the choice of the 
default_metric value. A default linkcost is a link without cost measurement, 
which is the equivalent to an OLSRv2 running hopcount metric. There might be a 
few links which are worse than hop count (links that you only want to use as a 
backup for the rest of the network), but most metrics want to mark links 
better than hopcount. Because of this I think it make sense to put the 
default_metric value near the upper end of the total metric range.

Teco Boot mentioned a fourth disadvantage of the constants. The range between 
minimum and maximum metric is only a factor of ~ 2^16. If we want to keep the 
option to calculate all metric operations with 32 bit integer, 2^16 is still 
much lower than the maximum single hop metric of (2^32-1)/255 ~= 2^24.

I think it is time to talk about this arguments before we start to include the 
metric draft into the OLSRv2 draft. What do you think about it ?

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-961,   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: "Justin Dean" <[email-masked]>
Date: Tue, 15 Jun 2010 10:52:23 -0400

It has expired as it may have been a bit premature at the time but have a
look at

http://tools.ietf.org/html/draft-dean-manet-metriclv-01

It explicitly says not to include 0 or infinity values but that could be
changed easily enough.  This draft was not meant to be used specifically for
OLSRv2 but as a general metric container for use in/by multiple protocols.

Justin

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
> Of Henning Rogge
> Sent: Tuesday, June 15, 2010 7:37 AM
> To: [email-masked]
> Cc: Dearlove, Christopher (UK)
> Subject: [manet] Metric encoding for OLSRv2
> 
> Hello,
> 
> When migrating from a multiplicative metric to an equivalent additive
> one (by using a logarithm on the link cost before transmitting) we will
> need the value 0 for representing the multiplicative factor 1.0 (which
> is used by a few routing protocols with multiplicative metrics I know).
> 
> "infinite/lost". This would allow OLSR to invalidate links in the TCs
> without transmitting a full TC update. Some kind of "explicit lost
> link" notification.
> 
> default_metric value. A default linkcost is a link without cost
> measurement, which is the equivalent to an OLSRv2 running hopcount
> metric. There might be a few links which are worse than hop count
> (links that you only want to use as a backup for the rest of the
> network), but most metrics want to mark links better than hopcount.
> Because of this I think it make sense to put the default_metric value
> near the upper end of the total metric range.
> 
> Teco Boot mentioned a fourth disadvantage of the constants. The range
> between minimum and maximum metric is only a factor of ~ 2^16. If we
> want to keep the option to calculate all metric operations with 32 bit
> integer, 2^16 is still much lower than the maximum single hop metric of
> (2^32-1)/255 ~= 2^24.
> 
> I think it is time to talk about this arguments before we start to
> include the metric draft into the OLSRv2 draft. What do you think about
> it ?
> 
> Henning Rogge
> 
> --
> Kommunikationssysteme (KOM) Neuenahrer Straße 20, 53343 Wachtberg,
> Germany

---

From: Teco Boot <[email-masked]>
Date: Tue, 15 Jun 2010 16:53:53 +0200

> routing protocols with multiplicative metrics I know).

Hmmm.
Is there a need for 1.0000001 and 1.001?
Why not convert the cost before using as multiplicative factor?

> transmitting a full TC update. Some kind of "explicit lost link" notification.

Discussed before. 
Sending complete TC without this link has same effect.
Having a DoNotUse metric value would support incomplete TC messages for
revoking usage of the link.

> default_metric value near the upper end of the total metric range.

I'm neutral on this one.

> much lower than the maximum single hop metric of (2^32-1)/255 ~= 2^24.

My argument is that in a single MANET, links with very, very different 
characteristics could be used. Could be > 1Gbps or << 64kbps, delay ns to s, 
loss 0% to 99,99%.
There is a need for selecting best links with same link type (needs fine 
granularity) and multi-hop paths over high capacity links instead of a low 
capacity link (needs the broad range). And the combination of those: use
an additional hop over high capacity link to make use of a somewhat better, 
high costs link.

Regards, Teco

---

From: Henning Rogge <[email-masked]>
Date: Tue, 15 Jun 2010 17:33:34 +0200

> http://tools.ietf.org/html/draft-dean-manet-metriclv-01
I will read it.

> changed easily enough.  This draft was not meant to be used specifically
> for OLSRv2 but as a general metric container for use in/by multiple
> protocols.
Okay.

For OLSRv2 it might be a good thing to limit the options for linkcost 
transmission to make the implementation easier (I would like to be able to 
implement OLSRv2 without floating point variables ^^).

Henning Rogge

-- 
1) You can't win.
2) You can't break even.
3) You can't leave the game.
— The Laws of Thermodynamics, summarized

---

From: Henning Rogge <[email-masked]>
Date: Tue, 15 Jun 2010 17:37:54 +0200

Am Dienstag 15 Juni 2010, 16:53:53 schrieb Teco Boot:
> > When migrating from a multiplicative metric to an equivalent additive one
> > (by using a logarithm on the link cost before transmitting) we will need
> > the value 0 for representing the multiplicative factor 1.0 (which is
> > used by a few routing protocols with multiplicative metrics I know).
> 
> Hmmm.
There are multiplicative metrics in use, many of them consider some links as 
"1.0" multiplier, which would translate into linkcost 0.0 if you use an 
additive metric.
I would like to defuse the argument "multiplicative metrics are much better" 
by having the necessary linkcost range to emulate them with additive metrics.

> > without transmitting a full TC update. Some kind of "explicit lost link"
> > notification.
> 
> Discussed before.
Yes.

> characteristics could be used. Could be > 1Gbps or << 64kbps, delay ns to
> s, loss 0% to 99,99%.
Would you think a range of 0 to ~16 millions would be enough ? If not we need 
more than 32 bit integer arithmetic.

Henning Rogge

---

From: David Young <[email-masked]>
Date: Tue, 15 Jun 2010 14:34:16 -0500

> default_metric value near the upper end of the total metric range.

I think you are right that the default metric should be near (at?) the
upper end of the metric range.  The same goes for the initial metric.
In my experience, a router that joins the network with low initial
metrics is quickly added to least-cost paths where it does not belong.
At least for a while, it is a "blackhole" on those paths.

Dave

-- 
David Young             OJC Technologies
[email-masked]      Urbana, IL * (217) 278-3933

---

From: Teco Boot <[email-masked]>
Date: Wed, 16 Jun 2010 10:05:54 +0200

> more than 32 bit integer arithmetic.

I also prefer the 32 bit integer arithmetic for path cost calculations.
Using a 2^24-1 (or less) for max link cost, and a maximum of 255 of such links 
will do. ISIS TE extensions uses this scheme (RFC5305). TE Default Metric is 
a 24-bit TLV. 

For MANETs, lowering overhead using (modified) exponential encoding is useful.  
I suggested using (16 + a) * 2^b - 15, this results in range 1 to 1015793.
Using (16 + a) * 2^b - 16, a zero value is supported and max-costs is 1015792.

Regards, Teco

---

From: Henning Rogge <[email-masked]>
Date: Wed, 16 Jun 2010 12:57:09 +0200

On Wed June 16 2010 10:05:54 Teco Boot wrote:
> Using a 2^24-1 (or less) for max link cost, and a maximum of 255 of such
> links will do. ISIS TE extensions uses this scheme (RFC5305). TE Default
> Metric is a 24-bit TLV.
> 
> For MANETs, lowering overhead using (modified) exponential encoding is
> useful. I suggested using (16 + a) * 2^b - 15, this results in range 1 to
> 1015793. Using (16 + a) * 2^b - 16, a zero value is supported and
> max-costs is 1015792.

I still don't like that we loose a factor of 16, but it's okay. If we reserve 
one value for infinite (a=15, b=15), we still have a range of 0 to 983024.

We could set ETX=1.0 to 32752 (a=0, b=11), which would give us pretty good 
representation up to ETX 30.0 (which will be at a=14, b=15). I would suggest 
putting the "default metric" to 262128 (a=0, b=14) or ETX8, which gives us up 
to a factor of 4 for links worse than hopcount.

I will try to play with a few different exponents, maybe we will find 
something better. Even if there is no good algorithm to convert between the 1-
byte compress representation and the expanded 3-byte one, we could just use a 
sorted lookup table and a binary search for conversion. Will just cost 1 kbyte 
of memory.

Henning Rogge

---

From: Teco Boot <[email-masked]>
Date: Wed, 16 Jun 2010 16:59:19 +0200

> to a factor of 4 for links worse than hopcount.

This is useful input for a default configuration for ETX implementation.
I suggest using a config option, where the link ETX is multiplied by a
configured factor (32752 in your suggestion), or conversion table.

Granularity is important here, what is the next better ETX? ETX1.01?
Then we need a value of 33079. Next cost value is 34800, which would be ETX1.06.
The stepsize is ~ 3 to 7% (at costs > 20). With rounding, loss of accuracy 
is in general less than 3%, which is OK for averaged RSSI. But for ETX, 6% loss
is far in the grey zone. I think coding between ETX1 and ETX1.25 should be the 
focus. More than 20% loss at lowest data rate is a bad link.
Your proposal use only five codepoints for this.
I assume non-symmetric implementation, this is not the funkfeuer-manet-olsrv2-
etx-01 draft. There: L_in_metric := ETX_PERFECT_METRIC * L_METRIC_r_etx *
L_METRIC_d_etx. (link cost is square of 1/loss_ratio)

Configuration is strongly related to other transmission facilities in the network,
e.g. duplex 40GB links (or better). Or lousy, expensive satcom links.
I would configure a WiFi 1Mbps link (or better for nearby nodes) in the 1000 to 
200000 range.
I would not use a hopcount based box in my network. So I prefer a (a=15, b=15) 
default :-)
// to be serious: I am neutral on the default //

> we could just use a 

This is useful for ETX to cost conversion.
Then, you can create the fine granularity at the lower loss ratios.

Having devices with more info (RSSI, data rate), can use this for costs where
ETX is 1 or somewhat above. These nodes are not in the grey zone and should have 
lower link costs. But actual link cost can vary a lot for these!

Regards, Teco

---

From: Marcello Caleffi <[email-masked]>
Date: Thu, 17 Jun 2010 10:41:30 +0200

> lower link costs. But actual link cost can vary a lot for these!

Or you can use a more detailed delivery ratio estimator. We made a study about this topic, and we find that the way in which you estimate the delivery ratio has a strong impact on the ETX performances.

Marcello

---

From: Henning Rogge <[email-masked]>
Date: Tue, 29 Jun 2010 08:15:41 +0200

Hello,

I have done some experiments with the metric formula and found some constants 
that might give us a better range of metric values.

The proposal keep a 4 bit mantissa (a) and a 4 bit exponent, but calculates 
the metric value slightly different. The two highest encodings (254/255) are 
reserved for "existing link with very high cost" and "infinite cost".

metric value = round_down((16 + a) * 2.42^b - 16)

The range of the function is 0 (a=0, b=0) to 16581662 (a=13, b=15). It 
contains 16 linear ranges of values, distributed exponentially over the whole 
range (the first one is 0,1,2,3,...,15).

The easiest way to implement this formula would be storing the 256 metric 
values in a integer array (would just need 1 kByte of memory), but it should 
be possible to just store the 16 exponential functions and calculate the rest 
on the fly.

What do you think ? Is this a good way to spread the range of our metric 
encoding closer to the range of 0 to ((2^32-1) / 255) ?

Henning Rogge

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Tue, 29 Jun 2010 09:46:36 +0100

I've not been engaging in this discussion, as right now I've
other fish to fry, but any formula with an arbitrary number
like 2.42 in it is just plain horrible. 

A long time back, I posed the fundamental question that if
your minimum metric is X, what should be your next minimum
metric. The current formula is X and a bit. Any formula
where that is the case loses some dynamic range. The
obvious alternative is 2X. If picking that, I had a formula
(dig into records to find it) that's fairly clean - much
more so than -15 or -16 based solutions.

-- 
Christopher Dearlove
Technology Leader, Communications Group
Networks, Security and Information Systems Department
BAE Systems Advanced Technology Centre
West Hanningfield Road, Great Baddow, Chelmsford, CM2 8HN, UK
Tel: +44 1245 242194  Fax: +44 1245 242124

BAE Systems (Operations) Limited
Registered Office: Warwick House, PO Box 87,
Farnborough Aerospace Centre, Farnborough, Hants, GU14 6YU, UK
Registered in England & Wales No: 1996687

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Henning Rogge
Sent: 29 June 2010 07:16
To: [email-masked]
Subject: Re: [manet] Metric encoding for OLSRv2

Hello,

Henning Rogge

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Tue, 29 Jun 2010 13:20:27 +0100

Following myself up.

If we have m mantissa bits and e exponent bits (with m+e = 8)
then we have encodings of (a,b) where 0<=a<2^m and 0<=b<2^e.
The current encoding is

(a + 2^m).2^b

This has minimum value 2^m and maximum value 2^(E+m) - 2^(E-1)
where E = 2^e. Dynamic range (ratio of maximum to minimum)
is 2^E - 2^(E-m-1).

An alternative candidate is

(a + 1 + 2^m).2^b - 2^m

(Where did that come from? Essentially it's what you get with
differences of 1 2^m times, then 2 2^m times, then 4 2^m times,
starting from 1. It's essentially still got a mantissa and
exponent part, but modified.)

This has minimum value 1 and maximum value 2^(E+m) - 2^m, which is
therefore also its dynamic range.

For m = e = 4:
Current:      Minimum 16  Maximum 2^20 - 2^15  Ratio 2^16 - 2^11
Alternative:  Minimum  1  Maximum 2^20 - 16

If we were to try to use m = 3, e = 5 then even single metric values
wouldn't fit in 32 bits.

The other issue is mapping from a metric value x to (a, b). With
the current metric a suitable (a, b) can be found, assuming
x < 2^(E+m) - 2^(E-2), by:

   1.  Find the integer b such that 2^(b+m) <= x < 2^(b+m+1)

   2.  Set a := (x / 2^b - 2^m), rounded to the nearest
       integer.

   3.  If a = 2^m, then set b := b + 1 and set a := 0.

For the alternative, assuming x < 2^(E+m) - 2^m

   0.  Set y := x + 2^m.

   1.  Find the integer b such that 2^(b+m) < y <= 2^(b+m+1).

   2.  Set a : = y / 2^b - 2^m - 1, rounded to the nearest
       integer.

   3.  If a = 2^m, then set b := b+1 and set a := 0.

Of course a lookup table is also possible, but it's good to have
an integer arithmetic option also.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Henning Rogge
Sent: 29 June 2010 07:16
To: [email-masked]
Subject: Re: [manet] Metric encoding for OLSRv2

Hello,

Henning Rogge

---

From: Henning Rogge <[email-masked]>
Date: Tue, 29 Jun 2010 14:42:28 +0200

> An alternative candidate is
I would like to drop the "+1" in the formula, so that we can encode the cost 
"zero" in the metric.

> exponent part, but modified.)
My formula with the fractional exponent used the same strategy, I just tried 
to "tune" the range of the exponent to fill the whole range of 0 to 2^24-1.
 
> Alternative:  Minimum  1  Maximum 2^20 - 16
(a + 2^m)*2^b - 2^m
Minimum  0  Maximum ~= 2^20 -2^15 (1.015.792).

If we use the a=15, b=15 encoding for "infinite", we have a range of 0 to 
983040 left.

Not great, but better than a range of factor 2^16.

> If we were to try to use m = 3, e = 5 then even single metric values
Yes, that's made me looking for fractional exponents.
 
> an integer arithmetic option also.
A lookup table for the exponent (which would have 16 entries) would be enough 
even for a fractional exponent.

Henning Rogge

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Tue, 29 Jun 2010 15:27:32 +0100

> I would like to drop the "+1" in the formula, so that we can encode
the cost 

I am not convinced by zero, but I agree (and nearly said so)
that this approach can be adopted to include zero quite
cleanly, in fact in a number of ways it's easier without the
zero, and OLSRv2 can be made to work either way. I do not
however agree with infinity.

Part of the reason for that is that without infinity, the
choice of metric mapping is orthogonal to the rest of the
protocol. With infinity, that is no longer the case, and
there are various nasties to deal with. One of these is
that infinity really means "do not use". So don't, in fact,
change your Link Set, hence Neighbor Set etc. But, you may
say, this allows a "negative delta" to remove a link
without advertising everything else. We could have done that
in OLSRv2 without the need for infinite metrics, but it was
a deliberate decision not to do that.

---

From: Teco Boot <[email-masked]>
Date: Wed, 30 Jun 2010 00:33:45 +0200

Your alternative and the "- 15" option do not differ that much.
So it is acceptable for me.

Having a coding scheme with a maximum near to 2^24 - 1 would be nice, but a 1 to 10^6 ratio would be good enough for almost all scenarios.
 
Teco.

Op 29 jun 2010, om 14:20 heeft Dearlove, Christopher (UK) het volgende geschreven:

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