[Olsr-dev] ETX mambo jambo
Tue May 11 21:12:28 CEST 2010
Am Montag 10 Mai 2010, 21:24:55 schrieb Mitar:
> Probably a lot on this topic has already been written
> 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
> 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.
> 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
> 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
> 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-
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
> 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
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
> 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
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
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). :)
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...
Size: 198 bytes
Desc: This is a digitally signed message part.
More information about the Olsr-dev