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

[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?

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.

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.

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!

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

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

So now if the absolute change of link costs is fast: 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.


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.

Hope you find this interesting.
Harald