[Olsr-dev] ETX mambo jambo

[Henning Rogge]

Am Montag 10 Mai 2010, 21:24:55 schrieb Mitar:
> Hi!
> 
> Probably a lot on this topic has already been written 
Yep... ;)

> but ETX is
> really badly conceptualized and it really does not properly influence
> routing decisions.
I would say the fact that the Freifunk networks work is a good evidence that 
ETX is not that bad.
 
> For example, we should have first two kind of links: full-duplex (or
> all in the neighborhood can talk with a very low cost at the same
> time) or half-duplex (or all in the neighborhood have to be quiet when
> one speaks).
Full duplex sounds like cable. At least I don't know a free available wireless 
medium for computer data that allows for full duplex. You would need a very 
complex TDMA radio system with multiple channels for wireless full duplex 
meshs.

> And then packet loss for those links. And then costs for
> routing decisions should take into account this. And if there is a
> full-duplex link without packet loss (like ethernet cable) there
> should be no cost associated with it).
Thats one of the reasons for etxff_eth (a variant of the etx routing metric 
most Freifunk networks use). It allows for the normal ETX costs (1.0 and 
higher) and a special cost (0.1) which is used for perfect links on interfaces 
that are tagged in the configuration as "mode ether".

> And this would be the reason
> why ethernet links would be less costly than one hop over half-duplex
> link. And not that we have a "special" flag for ethernet links.
Our problem (up to version 0.6.0, which will be there soon) is that we cannot 
really change our message format without breaking existing meshs. So allowing 
more flexible routing metrics will have to wait until we move the OLSRv2 (and 
the packetbb message format), which is planned for version 0.7.0.

> And then if OLSR would support asymmetric links it could take this
> half-duplex information and even better do routing.
See here to read the current draft for integrating generic metrics into 
OLSRv2. It will be in the OLSRv2 RFC.

http://tools.ietf.org/html/draft-dearlove-olsrv2-metrics-04

> Also hops does not really add much on full duplex links (except for
> latency which is not the main performance factor in comparison to
> others in wireless links) in comparison with half duplex links.
> 
> So a crude way would be to multiply ETX costs on full duplex links and
> add on half duplex (in comparison with just adding).
Doing this would mean you just lost the Dijkstra algorithm to do an efficient 
routing calculation. Efficiency is very important for larger meshs.

Multiplicative and additive metrics can be transformed into each other (just 
apply a logarithm/exponential-function).

> I really do not understand why ETX costs are summed in the first
> place. If we measure packet loss this is a probability of packet
> getting through over that particular hop and probability of packet
> getting through over the whole path is a product of all this
> probabilities for one hop.
ETX (expected transmission count) is some kind of "cost" function for wireless 
transmissions. If you have two hops, you need double the amount of "air time".

The MIC metric is a good idea to enhance an existing metric (for example ETX 
or ETT) by applying costs for the size of a collision domain. See
http://www.cs.ucdavis.edu/~prasant/WIMESH/p6.pdf

> The only reason why summing is reasonable is because there is a hidden
> cost of transferring packets over half-duplex (wireless) links to
> other links in vicinity which have to be quiet at that time. But all
> this is a bad probability model for what is happening and this is why
> discrepancies between the model and real world occur.
The cost is even worse than ETX suggests.

When one station wants to transmit any station within the interference range 
of the receiver has to be quiet. So you cost anyone in your neighborhood 
airtime.

> Because now, as we use a lot of ethernet links and VPN links, routing
> decisions are very bad sometimes.
I think most of the routing in mesh networks is done with wireless links.

> (And all this is without taking into the account bandwidth limits.)
> 
> More that I think now more I see it is a wrong approach. What routing
> protocols are? They are prediction tools which try to evaluate past
> behavior to predict behavior and performance of one route over
> another. As such first there should be a good model which would the
> networks be are talking about and what we would like to predict -
> performance (bandwidth, latency...) and what influences performance
> (packet loss, selected wifi link speed, limits on VPN tunnel) and how
> to get measurements which would be used for filling this model with
> data for prediction (with of course side-effects of active
> measurements on the performance).
I'm not sure it will be possible to model the effects on the wireless links in 
a large scale mesh network.
 
> And what are current routing protocols differ is how they measure data
> and how they compute shortest paths. I do not understand why exactly
> do we need new routing protocol for every this combination?
There are two types of routing protocols I know, distance vector and link-
state routing.

Within the categories you have multiple protocols because you want to optimize 
them for your use case. OLSR (and OLSRv2) is a linkstate routing protocol 
which is optimized for wireless mesh networks. Wireless networks have limited 
bandwith (compared to cable) and create an enviroment with quickly changing 
link characteristics.

> Why we
> cannot make a modular routing protocol where you would be able to
> define how to measure links (which messages you send and such) and
No problem on this part. The LQ-Plugin system of OLSRd allows this since 0.5.6 
I think. The core just works on a dimensionless "cost" value of each link, 
without knowing what kind of cost it is.

> then some prediction tool which you can vary to evaluate all this data
> (of which a good approach to its computation is just one part) and
> then what you do once you evaluate/predict paths performance - do you
> use it for L2 or L3 links, routes?
I don't think predicting path performance on 'generic links' (wireless, cable, 
laser, ...) is realistic. There is a reason why many simulations of wireless 
networks are bad... or just unrealistic (and simulators have perfect knowledge 
about their enviroment AND don't need to do anything in realtime).

> If all this would be modular we
> would be able to interchange things. Like if somebody makes a good L3
> module for adding/removing IPv4 and IPv6 routes once then everybody
> would be able to use it. Then we could play with different data
> collections and feed data into different predictive models. And if we
> collect data with OLSR or B.A.T.M.A.N. messages - it is not really
> important.
BATMAN is (in parts) comparable to a distance vector protocol (it use the 
message flow of it's 'pings' to measure the distance), so you cannot directly 
combine it with a linkstate protocol.

> Currently everybody is trying to make everything from the scratch.
I don't think so. Many routing protocols build uppon the experience of earlier 
protocols.

> Their way of measuring data, evaluating it and then pushing changes to
> network stack. This is crazy.

> Probably because most work originates
> from academia where author is concerned with testing/evaluating
> his/her own combination of things mentioned above.
Most routing protocols I care about have been developed in the IETF or by 
groups with lot's of practical experience. Yes, there are purely academic 
approaches to routing, but most of them are not very widely used.

> But if we would
> have such general "routing stack" it would be useful for everybody.
> For networks because we would be able to all work on same codebase
> (and have interchangeable modules) and for academia because they would
> only need to write a new, for example, prediction model and try it
> out.
Yes, it would be nice to have this "can do all routing problems" protocol, but 
I don't think it's really feasible. I think there is a reason why you apply 
different tools/protocols to different kind of problems/networks. Most 
'optimizations' are a tradeof between multiple (dis)advantages. An 
interstellar network of satellites would use a completely different routing 
strategy (google for DTRNG, it's a research groups of the IETF) than a huge 
sensor mesh of millimeter-sizes sensor-nodes. A free city mesh of mostly 
stationary node has other needs than a 100 gigabit/s cable network of a 
backbone provider.

If you have some concrete ideas how to model the cost of a link which behaves 
better than ETX/ETT, just tell us. We will be happy to talk about and and see 
if/how it could be applied to a WLAN link (which will stay our primary 
wireless technology in the near future I think). :)

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20100511/3e1fe534/attachment.sig>