[Babel-users] ETX metric for bandwidth limited links

Juliusz Chroboczek Juliusz.Chroboczek at pps.jussieu.fr
Tue May 11 15:06:29 UTC 2010


> our wlan ljubljana open wireless network (http://wlan-lj.net/)

Cool.  (For anyone who doesn't understand Venedic, you can see the list
of nodes is on the page titled « Pregled točk », and a few cool photos
on the page « Spletne strani točk ».)

> models [...] are quite simple and very often just a search for
> shortest path in a graph.

You're right, but you're confusing two things.

There's the metric computation, and the route selection.  Metric
computation is about defining which route is "shortest", while metric
selection is about choosing which route you'll use.  What you don't seem
to realise is that the protocol designer can often choose where to put
the smarts -- into metric computation or route selection.  Choosing the
shortest path is the simplest route selection policy, but it doesn't
mean there's no intelligence -- intelligence can be hidden within the
metric computation.

Where you are right is that more work needs to be done on both metric
computation and route selection.

> From my experience I find this quite unsatisfactory as in a network
> with different kind of links (WiFi, ethernet, tunnels) packet loss
> itself is far from only factor influencing path performance.

You forget about multiple radio frequencies, which is what I am working
on right now.

> But in both OLSR and Babel ETX are summed together. Which does not
> have really a theoretical reason/model behind it (except of
> a similarity to (historical) routing protocols which are minimizing
> hops)? Or it does?

You're wrong -- ETX is an additive metric for very good theoretical
reasons.  Please read the ETX paper:

  Defcouto, D., Aguayo, D., Bicket, J., and R. Morris, “A high-throughput
  path metric for multi-hop wireless networks,” Proc. MobiCom 2003, 2003.

> I find it that it mostly works because we are using WiFi links where
> there is a hidden cost added to using a given link: that neighboring
> nodes have to stay quiet. It is in some way a half-duplex link. And
> this is why every hop "costs" (except for latency it also introduces).

Your intuitions are very close to what I am currently working on with
Zoobab.

> - links where packet loss is a function of bandwidth use

Careful with that, that's a positive feedback loop.  If not done
carefully, this can lead to massive instabilities.

> So I would like to know if there are any plans/ideas (or maybe there
> is already this) for such ETX metrics in Babel?

Yes, I'm working on taking route diversity into account; Zoobab has
shown that it can lead to a 6-fold increase in throughput.  I am also
thinking about load balancing (which you allude to above).

> As I understand Babel specially treats ethernet links but this is not
> something which would be just a special case of determining link
> quality/nature?

See above about routing metrics.

> How does it determine if a link is an ethernet link?

It asks the kernel.

> Babel does not do load balancing routes?

Not yet.

> Does it support asymmetric links?

Yes.

> As I understand currently it is possible to define your own ETX
> metrics but I do not see a clear way of adding bandwidth information
> to ETX without also changing the way (not just shortest path) routes
> are calculated.

What you are raising are open reasearch problems.

Babel is known to work well with shortest route selection for any
strictly monotonic, isotonic metric (see Section 3.5.2 of the Babel
draft).  Whether Babel works well with non-isotonic metrics is an open
research problem.  It is also not known what is the class of route
selection policies that Babel works well with.

Careful, though: most of the things you suggest above are naturally
non-isotonic.

                                        Juliusz



More information about the Babel-users mailing list