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

[Harald Geyer]

> > 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/m
> instrel 
> )

Good point. But that's a rather indirekt relationship in this case.
 
> > 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.

Hm, most new metrics that I've heard of seem to imply a range that is
quite bigger than ETX. Do you have any particular counter example in
mind?
 
> > 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.

Yes, I agree this is a good idea. But to trigger the issue I'm discussing
you don't need fluctuating links. Just two alternativ high cost links
that are both changing at low relativ rate in the same direction.
 
> > 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.

See above, why this isn't enough.

> > 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.

ACK. fisheye is one of those nasty things, that don't make all this easier.

> > 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.

Sorry, I have been (too) short: What I wanted to write was: "funkfeuer tends
to have long *default* routes compared to freifunk". I don't have any
actual data about freifunk networks but I would be very surprised if this
was wrong. And loops in the default route is, what people usually 
notice ...

Harald