Subject: Re: [manet] Metric encoding for OLSRv2

From: Henning Rogge <[email-masked]>
Date: Thu, 1 Jul 2010 14:35:21 +0200

On Wed June 30 2010 00:33:45 Teco Boot wrote:
> Your alternative and the "- 15" option do not differ that much.
> So it is acceptable for me.
The "infinite" metric is not that important (it's a nice to have I think), as 
long as we can encode a cost of zero.
 
> 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.
value = (a + 2^m)*2^b - 2^m
0 <= value <= 1015792

What would be a good default link value for this encoding ?
I would suggest (a=0,b=15) = 524272 or (a=0,b=14) = 262128.

This would give us lot's of range for metrics better than hopcount and some 
space for links worse than 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: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Thu, 1 Jul 2010 14:25:25 +0100

The current proposal is in the middle of the range
logarithmically, rather than arithmetically (I would
prefer a=0,b=15 to a=0, b=14). I can (otherwise we
wouldn't have proposed it) see some logic to that.

There is another value worth considering, and that
is the maximum value. This has the potential advantage
of clarity over that there are two different default
concepts

- The "don't need to signal a metric thus saving
  octets" value, and

- The "I haven't been able to work out what a good metric
  valus is yet, so let's use this" value.

The latter should almost certainly be the maximum value.
The former really only has two purposes

- If there is an often used value.

- For hop count.

Note that for pure hop count it is irrelevant what the default
value is. If you are going to have cases where e.g you signal
double hops then maximum is the worst value - and the best
value is probably the minimum value (excluding zero, if zero
is included). And that is another candidate.

Incidentally inclusion of zero makes a change to OLSRv2.
It means that you MUST pick the fewest hop route among those
with the same metric. Without it, that becomes a SHOULD,
or even a MAY.

-- 
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: Henning Rogge [mailto:[email-masked]] 
Sent: 01 July 2010 13:35
To: Teco Boot
Cc: Dearlove, Christopher (UK); [email-masked]
Subject: Re: [manet] Metric encoding for OLSRv2

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: Teco Boot <[email-masked]>
Date: Fri, 2 Jul 2010 08:17:50 +0200

> The latter should almost certainly be the maximum value.

This depends on the configuration.
The default for 10/100/1000/10000 Ethernet, where
rate is not known, should not be the max value, I think.

In general, we are in a discussion on guidelines, on what
cost value to use for what class / state of a link.
I think it is helpful to have an informational document,
with examples of (at a minimum) 802.3 and 802.11.

> with the same metric. Without it, that becomes a SHOULD,

As far as I understand, nobody asked for zero for OLSR.
The idea was having a generic coding scheme, and some
protocols do require a zero value (Henning says so ...).
The OLSRv2-metrics document could specify that zero MUST NOT
be used. 
Same could be specified for a max value = DoNotUse. This
leaves 254 codepoints for OLSRv2.

Teco.

---

From: Henning Rogge <[email-masked]>
Date: Fri, 2 Jul 2010 08:31:59 +0200

> protocols do require a zero value (Henning says so ...).
Using a link quality of 1 with a multiplicative metric seems to be a normal 
thing. We cannot do something equivalent with our metrics if we do not allow 
cost ZERO for additive metrics.

> The OLSRv2-metrics document could specify that zero MUST NOT
I see no reason for this. Dijkstra can handle zero-cost edges easily. It do 
not even add much cost to the implementation, a tie-breaker for deciding which 
zero-cost link should be used (e.g. based on originator address) is enough.

> leaves 254 codepoints for OLSRv2.
That was the idea behind the "infinite" value.

We have some people writing "roaming" plugins for the OLSR.org codebase, that 
allow a to handover mobile clients without forcing them to run OLSR. They just 
associate to the local router and the routers create HNA entries for them on 
the fly. It might be useful to have "subtractive" partial TCs for this usecase 
in OLSRv2.

A different way (a hack) to implement this would be to send out partial TCs 
with a minimal VTime, just repeat them with different ANSNs and the same 
sequence number a few times to be sure. But I really don't like this, it's not 
really stable.

Henning Rogge

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Fri, 2 Jul 2010 09:37:35 +0100

> As far as I understand, nobody asked for zero for OLSR.

The draft being discussed is one intended to be rolled
into OLSRv2. While in theory I am in favour of separate
drafts for separate things, the IETF process has been
painful enough that I'm limiting my interest and intentions
to that.

---

From: "Günes, Mesut" <[email-masked]>
Date: Thu, 8 Jul 2010 14:27:50 +0200

Dear all,

we are proud to announce the release of the routing framework DES-SERT.

The DES-Simple and Extensible Routing-Framework for Testbeds (DES-SERT) [2]
is a framework for underlay routing in user space. The goal of DES-SERT is
to simplify the development of reactive and proactive routing protocols for
mobile ad-hoc networks (MANET), wireless mesh networks (WMN), wireless
sensor networks (WSN), and similar wireless multi-hop networks. The focus is
on the experimentally driven research of these networks with experimental
facilities, i.e., a wireless multi-hop testbed. DES-SERT is implemented for
Linux and runs on the current kernel.

DES-SERT is currently being used in the hybrid, multi-transceiver multi-hop
DES-Testbed at Freie Universitaet Berlin [1], which consists of more than
100 nodes.

We implemented several routing protocols based on DES-SERT. Among them are:
  - ARA (Ant Routing Algorithm)
  - AODV
  - B.A.T.M.A.N, several variants
  - DSR, several (multi-path) variants
  - Gossip routing, several variants
  - OLSR

Some advantages of DES-SERT are:
  - Abstraction from the Linux operating system
  - Support of packet handling
  - Low operating system interference
  - High-level language and data structures
  - Run-time configuration

The software is provided under the GPLv3 and is available over [3]. An older
version (0.87) is also in Debian unstable and the current version (0.93)
submitted and waiting to be included. A manual/tutorial with some code
examples can be found here [4].

If you have got any questions, feel free to contact us [5]. We are very
interested in getting some feedback.

Best regards,

DES-SERT Team

------------------------------------------------------------------
[1] https://www.des-testbed.net/
[2] Blywis et al., DES-SERT: A Framework for Structured Routing Protocol
Implementation, IFIP Wireless Days 2009, Paris, France (2009)
[3] https://www.des-testbed.net/DES-SERT/
[4] http://www.des-testbed.net/libdessert/doc/0.93/
[5] [email-masked]

---

From: Henning Rogge <[email-masked]>
Date: Wed, 28 Jul 2010 17:06:36 +0200

> leaves 254 codepoints for OLSRv2.
Another option I thought about on the IETF meeting to support "do not
use/infinite" distanced addresses in TCs (without wasting a metric
coding point) would be to add an additional tlv value for the
NBR_ADDR_TYPE tlv ("not_connected" ?).

We just need a similar thing for the gateways, to mark an attached
gateway (for example the internet uplink) as "not there anymore".

Henning Rogge

-- 
"Wo kämen wir hin, wenn alle sagten, wo kämem wir hin, und niemand
ginge, um einmal zu schauen, wohin man käme, wenn man ginge." (Kurt
Marti)