[OLSR-users] Bellman-Ford instead of Dijkstra?
Benjamin Henrion
(spam-protected)
Tue Jun 13 17:09:49 CEST 2006
Cedric Krier <(spam-protected)> [060613]:
>
> 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.
Maybe this idea would help to fix the problem you point:
http://carlstrom.com/stanford/quals/mirror/swig.stanford.edu/pub/summaries/networks/bellman_ford.html
> 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
> _______________________________________________
> 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 >>>
More information about the Olsr-users
mailing list