[OLSR-users] Bellman-Ford instead of Dijkstra?

Cedric Krier (spam-protected)
Tue Jun 13 15:20:46 CEST 2006


I think that there is a problem with this kind of configuration.

For example, look if A wants to connect to F.
There is  2 possible routes with the same weight :
A-B-F and A-E-F

So if A choose the first, there is no problem because for B the shortest
path to F is the ethernet interface.
But if A choose E, then the shortest path for E to join F is :
E-A-B-F
So E will resend the packet to A, etc...

There will be a loop in the routing. I don't know if there is a way to
be sure that A will take the good route to prevent the loop.


C├ędric


On 13/06/06 14:52 +0200, Benjamin Henrion wrote:
> Thomas Lopatic <(spam-protected)> [060613]:
> > Hey Benjamin,
> > 
> > I thought through your idea again and - although you already explained
> > it to me and I thought that I understood it - I am not quite sure any
> > longer whether I really get it. Let me try to put it into my own words
> > and see whether I understand what you're trying to accomplish.
> > 
> > You're trying to establish two links between a node A and a node B. For
> > this you have two interfaces per node, say A1 and A2 on node A as well
> 
> Two interfaces per node (typically one ethernet and one wireless), here
> I make a schematics of 8 nodes where A1 is wireless and A2 is ethernet:
> 
> A1===(10)===1B1===(10)===1C1===(10)===1D
> 2            2            2            2
> |            |            |            |
> (-2)        (-2)         (-2)         (-2)
> |            |            |            |
> 2            2            2            2
> E1+++(10)+++1F1+++(10)+++1G1+++(10)+++1H
> 
> where:
> 
> === wireless chan1
> +++ wireless chan13
> | ethernet
> () weights on interfaces
> 
> > as B1 and B2 on node B. Say, A1 talks to B1, A2 talks to B2.
> 
> Nope, see here over. A1 talks to B1 through wireless, but if A2 wants to
> talk to B2, it has to go trough A2E2E1F1F2B2
> 
> > You would now like to use the A1/B1 link for packets from A to B. You
> > would like to use the A2/B2 link for the opposite direction, i.e. for
> > packets from B to A. In this way we would have a full-duplex connection
> > between A and B, packets could flow in both directions at the same time.
> 
> Let's take the example of host A wanting to reach node D.
> 
> In my schematics, the fastest road would be in terms of not reusing the
> same channel:
> 
> ABFGCD
> 
> Right now, OLSR takes the route ABCD.
> 
> > What this boils down to is an asymmetric scenario, doesn't it? From A's
> > point of view, we want to leave the A1/B1 link at its original link
> > quality and we want to make the A2/B2 link artificially bad, so that
> > A1/B1 gets prefered when node A sends packets to B. On B, we'd like to
> > make A1/B1 artificially bad and leave A2/B2, so that A2/B2 gets prefered
> > when B sends packets to A.
> 
> No, I just want the route to be choosen in function of weights on
> interfaces. I consider that the radios of chan1 and chan13 have the same
> SNR and link quality.
> 
> > What this means is that A has another notion of the link quality of link
> > A1/B1 and link A2/B2 than B. For A the former is good and the latter is
> > bad, for B it's the other way around.
> > 
> > Based on this, let me ask two questions that came to my mind when
> > thinking through the scenario again.
> > 
> >  * We calculate our routing metric as follows: ETX = 1 / (NLQ x LQ). NLQ
> > is the quality of a link as reported by our neighbour (e.g. 0.7 if the
> > neighbour sees 70% of our packets), LQ is the quality of a link as
> > measured by us. So, I am not sure whether we can use ETX with asymmetric
> > routing as described above. The "LinkQualityMult" directive affects the
> > link quality that we measure (and then report to our neighbourhood). So,
> > if we use "LinkQualityMult" on a given link, then this link becomes
> > better or worse for us and for our neighbours. There currently isn't any
> > way to make us think that a link is good and at the same time our
> > neighbours think that the same link is bad - which is the basis for the
> > above asymmetric scenario, unless I am missing something here. Maybe the
> > solution is to simply announce the modified link quality to our
> > neighbours and ourselves use the original unmodified link quality. Hmm.
> > 
> >  * Why would the "LinkQualityMult" value have to be negative? Can't we
> > stick to Dijkstra, i.e. isn't 0 "bad" enough a multiplier? Hmmm. Could
> > you outline the scenario that you have in mind a little further?
> 
> LinkQualityMult = weight in olsrd.conf?
> 
> I need to think what happens if wireless links are assymetric in the
> schema hereover if you also use negative weights on interfaces.
> 
> > Hmmm. As I (mis)understand the whole thing now, it rather looks like an
> > "asymmetric" kind of challenge and not that much a problem of negative
> > weights, or?
> > 
> > -Thomas
> > 
> > _______________________________________________
> > olsr-users mailing list
> > (spam-protected)
> > https://www.olsr.org/mailman/listinfo/olsr-users
> 
> -- 
> Benjamin Henrion <(spam-protected)>
> http://bh.udev.org
> <<<                      INSPIRE Directive will close                >>>
> <<<            Public access to State-collected Geographic Data      >>>
> <<<                            All over Europe                       >>>
> <<<                        http://publicgeodata.org                  >>>
> 
> _______________________________________________
> olsr-users mailing list
> (spam-protected)
> https://www.olsr.org/mailman/listinfo/olsr-users
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: not available
URL: <http://lists.olsr.org/pipermail/olsr-users/attachments/20060613/42c05a3a/attachment.sig>


More information about the Olsr-users mailing list