[Olsr-dev] Some reflections on link state routing and metrics

[Henning Rogge]

Am Monday 09 February 2009 04:00:17 schrieb Harald Geyer:
> Hi!
>
> After some private discussion with Henning I think I should share
> a few observations with this list. Basically the question I'm pondering
> is: Will OLSR work with good metrics?
I think so... ;)

> Of course there are metrics trying to optimize very different aspects
> of connection qualitiy, but for the purpose of the e-mail I'll
> assume that any good metric will need a big range of values to provide
> a proper model for a divers real world mesh like freifunk/funkfeuer.
Yes, you have to be careful how to combine different measurements into a 
single metric.

> So the question above boils down to "Will OLSR work with wide-range
> metrics?"
>
> Of course there is the fundamental criticism of most wide-range metrics,
> that they can't properly handle links with unicast package loss (i.e.
> they prefer lossy links just because they have some other good
> property - which of course is a bad thing to do in general). But I won't
> discuss this today, as this has nothing to do with OLSR.
Unicast loss (or link loss) is definitely an important point in OLSR metrics.

> BTW: Does anybody know results about a metric that solely concentrates on
> unicast package loss? It's that obvious that it sure has been studied
> extensively, but I don't know anything about that myself. So if you have
> any references, please share them with me!
ETT can be thought as a package loss metric, especially if you just directly 
take the unicast bandwith from the mac-layer and put it through a smoothing 
process.

(see 
http://linuxwireless.org/en/developers/Documentation/mac80211/RateControl/minstrel 
)

> Ok, back to topic. OLSR was designed with the hop count metric (link costs
> can only be 1 or infinite) in mind - and it work's well there. Since
> hop count has some nasty properties we went on and started using ETX where
> link costs are basically in the range (1-5). Any link with cost above 5
> is pretty much useless, as you have to expect big unicast package loss
> there.
Yes, as soon as you get higher unicast packet loss things get ugly.

> Anyway OLSR works with ETX at least reasonably. Seems that now
> people are becoming discontent with ETX too, so how will the funkfeuer
> OLSR mesh behave with a metric that has link costs in some very big range?
A metric change does not need necessarily mean a very big range.

> OLSR is designed under the assumption that it takes only a short time
> for the routing to converge. Before the routing has converged loops
> are likely and the time to converge is a function of the diameter of
> the mesh and the broadcast package loss. To keep the chance of loops
> at a minimum topology information is distribute frequently - faster
> than the link costs can change significantly.
>
> But if we introduce large link costs, we also need to allow for
> fast absolute changes: In a given fixed time interval the link costs
> must be able to change by some relativ amount (say 10%) otherwise
> the link costs would lag behind reality too much to be useful.
> (I hope this point is clear, if not: Please speak up.)
Markus and me discussed a lot about "smoothing" of metric values. Even if you 
have a perfect link at the moment the link might be worthless if it drops to 
50% unicast loss every 500 milliseconds. So it might make sense to sample 
metric values of the past and combine them into a link metric. Stable links 
(with static values) should get a lower final metric cost than wildly 
fluctuating links.

> So now if the absolute change of link costs is fast:
I don't think it's a really good idea to allow a link to change its metric 
multiple times in a short timeframe. If it goes up, down and up within a few 
seconds keep the metric cost high until the link stabilizes.

> Will the routing
> ever converge? In the presence of package loss on low cost links probably
> not. - So I claim as a way out any link state routing protocol that
> wants to use wide-range metrics will need some mechanism to ensure
> good synchronisation on links with low cost.
If the link metric cost will have a higher range than ETX we might be forced 
to drop fisheye and develop some cost-change based link interval system.

> Some additional remark: This is much worse for funkfeuer like networks
> (with centralistic uplink organisation) than for freifunk like networks
> (with O(n) uplink gateways) because funkfeuer tends to have long routes,
> where it is much more likely to hit a loop. I guess that also explains
> why so many olsrd bugs have been found in Vienna.
Sorry, you got it exactly the wrong way. Vienna with it's 5 Ghz backbone to 
the central uplink(s) have a short average hopcount compared to networks like 
Berlin od Leipzig.

Henning Rogge

*************************************************
Diplom Informatiker Henning Rogge
Forschungsgesellschaft für
Angewandte Naturwissenschaften e. V. (FGAN) 
Neuenahrer Str. 20, 53343 Wachtberg, Germany
Tel.: 0049 (0)228 9435-961
Fax: 0049 (0)228 9435-685
E-Mail: (spam-protected)
Web: www.fgan.de
************************************************
Sitz der Gesellschaft: Bonn
Registergericht: Amtsgericht Bonn VR 2530
Vorstand: Prof. Dr. rer. nat. Maurus Tacke (komm. Vors.), Prof. Dr.-Ing. 
Joachim Ender (Stellv.)

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20090209/fcf91f1b/attachment.sig>