[olsr-dev] Differing metrics for route decision

[William Conroy]

* On Mon Feb 27 08:50:02 CET 2006 Thomas Lopatic wrote:
*
**
Yes, I believe it would. However, one of the things that we'd need to
think through for this is the following. Metrics come in a couple of
variants. They differ in how the metric of a multi-hop path is derived
from the metrics of the individual hops. I think that we have three
different kinds.

  * Additive metrics. Simply add the metrics of the individual hops to
obtain the metric of the full path. An example for this is ETX. If we
have a two-hop path from node A via node B to node C, the ETX for the
path from A to C is the sum of the ETX between A and B and the ETX
between B and C.

  * Multiplicative metrics. Packet loss is multiplicative, I'd say. If
50% of the packets make it from A to B and 40% make it from B to C then
the probability of a successful packet transmission on the path A -> B
-> C is 50% * 40% = 20%.

  * Minimum metrics. If we look at the bandwidth of a path then the hop
that has the lowest bandwidth is the bottleneck and dictates the
bandwidth of the complete path. The bandwidth of A -> B -> C then is
minimum(bandwidth(A -> B), bandwidth (B -> C)).

These are also the metrics I'm aware of, and I can't think, nor have I read
that any other types exist (although 'minimum metric' is often referred to
as 'concave metric' in the literature). The problem is (and I hope I'm not
teaching any grannies to suck eggs here, apologies in advance if I am :P )
is that, as soon as you start combining metrics, the problem becomes
horrificly expensive to solve. The following paper describes this issue:
http://www-inst.eecs.berkeley.edu/~ee290t/sp04/lectures/rdr_paper34.pdf

Which shows that if we have n additive and m multiplicative metrics, and n+m
=> 2, then our problem is NP-Complete, which as far as I know, basically
means its too expensive to feasably calculate :) (I got this from reading
http://qolsr.lri.fr/papers/qolsr-selection-lritr04.pdf, page 5, section B as
well as a bit of wikipediaing)
**
*On Mon Feb 27 08:50:02 CET 2006 Thomas Lopatic wrote:*

For additive metrics the Dijkstra algorithm applies. But does it also
apply to the other two types? What about combinations of metrics of
different kinds, e.g. something based on ETX and the bandwidth? Hmmm.
Anyone?

-Thomas

 It does indeed seem as though most attempts at providing some QoS to an
ad-hoc protocol are attempting to simplify the multiple metric problem, to
that of a single metric problem, rather than attempting to solve the full,
NP-Complete problem...

For example

http://qolsr.lri.fr/papers/qolsr-multimetric-mwcn03.pdf

Considers at one point (page one, 'The DBCLH Problem') hop-count, delay and
bandwidth as metrics. They use a method based on lagrangian relaxation. As
far as I understand, this means that the constraints are changed based on
the understanding of the problem area. In this case they reason that

"The delay has two basic

components: queuing delay and propagation delay. The

queuing delay is more dynamic and traffic-sensitive, thus

bandwidth is often more critical for most multimedia

applications. If there is no sufficient bandwidth, queuing

delay and probably the loss rate will be very high. So,

we define the precedence as bandwidth and then the

propagation delay. Our strategy is to find a path that

satisfies the bandwidth constraint, and when there is more

than one, we choose the one with shortest hop and under

the delay constraint."

So I translate this as 'Rather than consider all the metrics individually,
simplify it all into one metric. Check bandwidth first, then if there are
multiple paths with the same bandwidth, then look at propagation delay. We
do this because bandwidth is usually most important, and thus this will give
you a near optimal route most of the time'.... I could be wrong though, I'm
not very good at translating academiaese :) I think I've read of this
idea in other places as the 'widest-shortest algorithm'.... There are some
other research papers discussing heuristics flying about too, but I haven't
had the time to digest them yet.
... In any case, I'm not sure the consideration of the seperate metrics in
some kind of framework for a plugin is as important as having one single
hooking point for the current (ETX) heuristic metric. It would be nice to
see this heuristic with only one hook into the code-base, as this would
allow easy swapping with other heuristics, and would open the code up to
others to allow them to start experimenting easier in this respect :)
Although having not looked at the code base much, I'm not sure how feasable
this is :S

I also have a question regarding what data (to be used for metrics) is
available directly from different technologies? For example, what raw
network data can be gathered from, for example, 802.11b, or ethernet? I'm
aware through ETX that we can get packet loss.... But how about throughput?
Is this data easily obtained? How about delays (transmission/queueing)? Do
drivers provide this information?

Anyway, thats my 2c on the situation. Sorry if any of my
questions/statements seem a bit dumb, this network stuffs quite a new topic
for me :) And great project chaps! I've looked at a lot of ad-hoc
implementations to use, and this definitely seems to be the one for me :D

Best regards

Liam Conroy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20060302/67dd79b1/attachment.html>