getting second best route from dikjstra's algorithm

[Vigneswaran R]

Hello,

Is there any way (API) to get the second best route to a destination
from dikjtra's algorithm (when multiple routes are available between
source and the destination)?

The idea is to write a plugin to get the second (third etc.,) best
routes (for destinations) and keep them in separate routing tables.
Later policy routing can be used to route different kinds of traffic
through different paths (which are unused otherwise).


Regards,
Vignesh

[Henning Rogge]

Post by Vigneswaran R
Hello,
Is there any way (API) to get the second best route to a destination
from dikjtra's algorithm (when multiple routes are available between
source and the destination)?

Difficult. I am not aware of such an algorithm.

Post by Vigneswaran R
The idea is to write a plugin to get the second (third etc.,) best
routes (for destinations) and keep them in separate routing tables.
Later policy routing can be used to route different kinds of traffic
through different paths (which are unused otherwise).

You don't want to use the second-best route for this anyways.

The second best route will be most likely the same as the best one, with
some small change (maybe one/two links different). You want a
second/third path that has a certain "distance" to the first one.

Theoretically you can do this by dijkstra again by adding "penalty"
costs to every link that touches the "best route". Not sure if it would
work out well.

Henning Rogge

[Teco Boot]

There is something around that uses 2nd best next hop in cases where best path doesn't work. To be used for L2 retransmit. Loop prevention needs attention.

Teco

Post by Henning Rogge

Post by Vigneswaran R
Hello,
Is there any way (API) to get the second best route to a destination
from dikjtra's algorithm (when multiple routes are available between
source and the destination)?

Difficult. I am not aware of such an algorithm.

Post by Vigneswaran R
The idea is to write a plugin to get the second (third etc.,) best
routes (for destinations) and keep them in separate routing tables.
Later policy routing can be used to route different kinds of traffic
through different paths (which are unused otherwise).

You don't want to use the second-best route for this anyways.
The second best route will be most likely the same as the best one, with some small change (maybe one/two links different). You want a second/third path that has a certain "distance" to the first one.
Theoretically you can do this by dijkstra again by adding "penalty" costs to every link that touches the "best route". Not sure if it would work out well.
Henning Rogge
--
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Fraunhofer Straße 20, 53343 Wachtberg, Germany
Telefon [phone], Fax [phone]
--
Olsr-users mailing list
https://lists.olsr.org/mailman/listinfo/olsr-users

[Vigneswaran R]

Post by Teco Boot
There is something around that uses 2nd best next hop in cases where best path doesn't work. To be used for L2 retransmit. Loop prevention needs attention.

Ok, will search for that. I agree that loop prevention needs to be taken
care. Thanks.


Regards,
Vignesh

Post by Teco Boot
Teco

Post by Henning Rogge

Post by Vigneswaran R
Hello,
Is there any way (API) to get the second best route to a destination
from dikjtra's algorithm (when multiple routes are available between
source and the destination)?

Difficult. I am not aware of such an algorithm.

Post by Vigneswaran R
The idea is to write a plugin to get the second (third etc.,) best
routes (for destinations) and keep them in separate routing tables.
Later policy routing can be used to route different kinds of traffic
through different paths (which are unused otherwise).

You don't want to use the second-best route for this anyways.
The second best route will be most likely the same as the best one, with some small change (maybe one/two links different). You want a second/third path that has a certain "distance" to the first one.
Theoretically you can do this by dijkstra again by adding "penalty" costs to every link that touches the "best route". Not sure if it would work out well.
Henning Rogge
--
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Fraunhofer Straße 20, 53343 Wachtberg, Germany
Telefon [phone], Fax [phone]
--
Olsr-users mailing list
https://lists.olsr.org/mailman/listinfo/olsr-users

[Vigneswaran R]

Post by Henning Rogge

Post by Vigneswaran R
Hello,
Is there any way (API) to get the second best route to a destination
from dikjtra's algorithm (when multiple routes are available between
source and the destination)?

Difficult. I am not aware of such an algorithm.

Post by Vigneswaran R
The idea is to write a plugin to get the second (third etc.,) best
routes (for destinations) and keep them in separate routing tables.
Later policy routing can be used to route different kinds of traffic
through different paths (which are unused otherwise).

You don't want to use the second-best route for this anyways.
The second best route will be most likely the same as the best one,
with some small change (maybe one/two links different). You want a
second/third path that has a certain "distance" to the first one.

True.. We are just thinking of a mesh kind of network where this may be
of help.

Post by Henning Rogge
Theoretically you can do this by dijkstra again by adding "penalty"
costs to every link that touches the "best route". Not sure if it
would work out well.

Good idea! Let us try.


Regards,
Vignesh

[Henning Rogge]

Post by Vigneswaran R

Post by Henning Rogge
Theoretically you can do this by dijkstra again by adding "penalty"
costs to every link that touches the "best route". Not sure if it
would work out well.

Good idea! Let us try.

I just remembered where I had heard about the idea:

http://interop.thomasclausen.org/Interops/2008_-_Papers.html

The "Implementation of Multipath and Multiple Description Coding in
OLSR" paper should be relevant for you.

Henning Rogge

[Vigneswaran R]

Post by Henning Rogge

Post by Vigneswaran R

Post by Henning Rogge
Theoretically you can do this by dijkstra again by adding "penalty"
costs to every link that touches the "best route". Not sure if it
would work out well.

Good idea! Let us try.

http://interop.thomasclausen.org/Interops/2008_-_Papers.html
The "Implementation of Multipath and Multiple Description Coding in
OLSR" paper should be relevant for you.

Thank you very much. I will go through them.

Regards,
Vignesh

[Vigneswaran R]

Post by Vigneswaran R
The idea is to write a plugin to get the second (third etc.,) best
routes (for destinations) and keep them in separate routing tables.
Later policy routing can be used to route different kinds of traffic
through different paths (which are unused otherwise).

Getting the a "second best" and "third best" routing table from the same
basic topology is dangerous IMHO. You have to be sure, that
a) everyone on a "second best" path agrees to use the "second best"
routing table for a given packet.

I agree. Same policy routing should be applied on all the routers.
(Otherwise, easily we get into routing loops).

b) the "x'nd best" routing table is monotonous throughout the
network. For Dijkstra and the best route, this is the case
(if there are no zero or negative costs involved). For a definition
of "second best" I wouldn't be so sure.

We are just thinking of a mesh where we may have 2 or 3 different paths
between one end to the other. Second best or third best is actually
alternate routes (could be of same cost or higher cost than the best path).

If nodes have different views on the network, or your routing table is
not monotonous, routing loops are likely to occur.

Ok.

How about not using the "second best route", but calculating a second
routing graph based on a different metric?

Ok. Though I am not sure how this can be done, we can do some thought
process on these lines. Thanks.


Regards,
Vignesh

[Henning Rogge]

Post by Vigneswaran R

b) the "x'nd best" routing table is monotonous throughout the
network. For Dijkstra and the best route, this is the case
(if there are no zero or negative costs involved). For a definition
of "second best" I wouldn't be so sure.

We are just thinking of a mesh where we may have 2 or 3 different paths
between one end to the other. Second best or third best is actually
alternate routes (could be of same cost or higher cost than the best path).

If nodes have different views on the network, or your routing table is
not monotonous, routing loops are likely to occur.

Ok.

How about not using the "second best route", but calculating a second
routing graph based on a different metric?

Ok. Though I am not sure how this can be done, we can do some thought
process on these lines. Thanks.

There is another problem you have to take care of.

Imagine a node A, which thinks that B,C,D,E,F is the "second best" path
through the network. Is there any guarantee that B will think that
C,D,E,F is the "second best" path? In fact I don't think so.

If not, you would have to use source routing, because your decision to
use "the second best" path will not be stable as a hop-by-hop decision.

Henning Rogge

[Vigneswaran R]

Post by Henning Rogge

Post by Vigneswaran R

b) the "x'nd best" routing table is monotonous throughout the
network. For Dijkstra and the best route, this is the case
(if there are no zero or negative costs involved). For a definition
of "second best" I wouldn't be so sure.

We are just thinking of a mesh where we may have 2 or 3 different paths
between one end to the other. Second best or third best is actually
alternate routes (could be of same cost or higher cost than the best path).

If nodes have different views on the network, or your routing table is
not monotonous, routing loops are likely to occur.

Ok.

How about not using the "second best route", but calculating a second
routing graph based on a different metric?

Ok. Though I am not sure how this can be done, we can do some thought
process on these lines. Thanks.

There is another problem you have to take care of.
Imagine a node A, which thinks that B,C,D,E,F is the "second best"
path through the network. Is there any guarantee that B will think
that C,D,E,F is the "second best" path? In fact I don't think so.

+---- J --------- K -------+
/ \
A --- B --- C --- D --- E ---- F
\ /
+-- M -- N -- O -- P-+


You're right. In the above scenario, A thinks that B,C,D,E,F is the
second best path. However, as far as B is concerned, M,N,O,P,F is the
2nd best path. When we apply policy routing uniformly on all the routers
to use 2nd best path (for a particular traffic), traffic from A to F
will flow through B,M,N,O,P,F instead of B,C,D,E,F (and which remains
unused).

Post by Henning Rogge
If not, you would have to use source routing, because your decision to
use "the second best" path will not be stable as a hop-by-hop decision.

Ok, will look into it. Thank you.


Regards,
Vignesh

[Henning Rogge]

Post by Vigneswaran R
+---- J --------- K -------+
/ \
A --- B --- C --- D --- E ---- F
\ /
+-- M -- N -- O -- P-+
You're right. In the above scenario, A thinks that B,C,D,E,F is the
second best path. However, as far as B is concerned, M,N,O,P,F is the
2nd best path. When we apply policy routing uniformly on all the routers
to use 2nd best path (for a particular traffic), traffic from A to F
will flow through B,M,N,O,P,F instead of B,C,D,E,F (and which remains
unused).

It might be even worse. Think about a network like this:

B---C---D
/ \ / \ / \
A X X H
\ / \ / \ /
E---F---G

A might decide that A-B-C-D-H is the best path and A-E-F-G-H is the
second best one.

But E decides that E-F-G-H is the best one and E-C-D-H is the second
best one, pushing the traffic back onto the best path from A to H.

Henning Rogge

[Teco Boot]

The trick is to converge to something that works well. L2 feedback may play an important role. Give the 2nd best route a chance and find out its L2 behaviour makes sense. Before the 2nd best route is taken, we must make sure there isn't a micro-loop.

Teco

Post by Henning Rogge

Post by Vigneswaran R
+---- J --------- K -------+
/ \
A --- B --- C --- D --- E ---- F
\ /
+-- M -- N -- O -- P-+
You're right. In the above scenario, A thinks that B,C,D,E,F is the
second best path. However, as far as B is concerned, M,N,O,P,F is the
2nd best path. When we apply policy routing uniformly on all the routers
to use 2nd best path (for a particular traffic), traffic from A to F
will flow through B,M,N,O,P,F instead of B,C,D,E,F (and which remains
unused).

B---C---D
/ \ / \ / \
A X X H
\ / \ / \ /
E---F---G
A might decide that A-B-C-D-H is the best path and A-E-F-G-H is the second best one.
But E decides that E-F-G-H is the best one and E-C-D-H is the second best one, pushing the traffic back onto the best path from A to H.
Henning Rogge
--
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Fraunhofer Straße 20, 53343 Wachtberg, Germany
Telefon [phone], Fax [phone]
--
Olsr-users mailing list
https://lists.olsr.org/mailman/listinfo/olsr-users

[Vigneswaran R]

Post by Teco Boot
The trick is to converge to something that works well. L2 feedback may play an important role. Give the 2nd best route a chance and find out its L2 behaviour makes sense. Before the 2nd best route is taken, we must make sure there isn't a micro-loop.

Thank you for your points. I need to read about how to make use of L2
feedback. As of now, I am not able to think of how it can be implemented.


Regards,
Vignesh

Post by Teco Boot
Teco

Post by Henning Rogge

Post by Vigneswaran R
+---- J --------- K -------+
/ \
A --- B --- C --- D --- E ---- F
\ /
+-- M -- N -- O -- P-+
You're right. In the above scenario, A thinks that B,C,D,E,F is the
second best path. However, as far as B is concerned, M,N,O,P,F is the
2nd best path. When we apply policy routing uniformly on all the routers
to use 2nd best path (for a particular traffic), traffic from A to F
will flow through B,M,N,O,P,F instead of B,C,D,E,F (and which remains
unused).

B---C---D
/ \ / \ / \
A X X H
\ / \ / \ /
E---F---G
A might decide that A-B-C-D-H is the best path and A-E-F-G-H is the second best one.
But E decides that E-F-G-H is the best one and E-C-D-H is the second best one, pushing the traffic back onto the best path from A to H.
Henning Rogge
--
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Fraunhofer Straße 20, 53343 Wachtberg, Germany
Telefon [phone], Fax [phone]
--
Olsr-users mailing list
https://lists.olsr.org/mailman/listinfo/olsr-users

[Teco Boot]

L2 traffic may help to get link metric feedback. OLSR uses multicast only, so it provides some signal quality (e.g. RSSI) and loss ratio stats (ETX) only. With user traffic (or probing), data rate and retransmit ratio is provided. With Minstrel, BestThroughput is provided (at transmitter side).

There is an experimental LQ NL80211 plugin available, using more than ETX. It is in src/linux/lq_plugin_ffeth_nl80211. I think the description is not in git. Bad. Here a copy Frank de Brabander posted in March 2012..

Teco

[Vigneswaran R]

Post by Teco Boot
L2 traffic may help to get link metric feedback. OLSR uses multicast only, so it provides some signal quality (e.g. RSSI) and loss ratio stats (ETX) only. With user traffic (or probing), data rate and retransmit ratio is provided. With Minstrel, BestThroughput is provided (at transmitter side).
There is an experimental LQ NL80211 plugin available, using more than ETX. It is in src/linux/lq_plugin_ffeth_nl80211. I think the description is not in git. Bad. Here a copy Frank de Brabander posted in March 2012..

Oh, yes. I have seen this plugin earlier. However, haven't yet tried
(since I am using Ethernet links for test setup, not wireless). Thanks
for reminding. Let me see, how it can help us.


Regards,
Vignesh

Post by Teco Boot

Post by Teco Boot
The trick is to converge to something that works well. L2 feedback may play an important role. Give the 2nd best route a chance and find out its L2 behaviour makes sense. Before the 2nd best route is taken, we must make sure there isn't a micro-loop.

Thank you for your points. I need to read about how to make use of L2 feedback. As of now, I am not able to think of how it can be implemented.
Regards,
Vignesh

Post by Teco Boot
Teco

Post by Henning Rogge

Post by Vigneswaran R
+---- J --------- K -------+
/ \
A --- B --- C --- D --- E ---- F
\ /
+-- M -- N -- O -- P-+
You're right. In the above scenario, A thinks that B,C,D,E,F is the
second best path. However, as far as B is concerned, M,N,O,P,F is the
2nd best path. When we apply policy routing uniformly on all the routers
to use 2nd best path (for a particular traffic), traffic from A to F
will flow through B,M,N,O,P,F instead of B,C,D,E,F (and which remains
unused).

B---C---D
/ \ / \ / \
A X X H
\ / \ / \ /
E---F---G
A might decide that A-B-C-D-H is the best path and A-E-F-G-H is the second best one.
But E decides that E-F-G-H is the best one and E-C-D-H is the second best one, pushing the traffic back onto the best path from A to H.
Henning Rogge
--
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Fraunhofer Straße 20, 53343 Wachtberg, Germany
Telefon [phone], Fax [phone]
--
Olsr-users mailing list
https://lists.olsr.org/mailman/listinfo/olsr-users

--
Olsr-users mailing list
https://lists.olsr.org/mailman/listinfo/olsr-users

[Vigneswaran R]

Post by Henning Rogge

Post by Vigneswaran R
+---- J --------- K -------+
/ \
A --- B --- C --- D --- E ---- F
\ /
+-- M -- N -- O -- P-+
You're right. In the above scenario, A thinks that B,C,D,E,F is the
second best path. However, as far as B is concerned, M,N,O,P,F is the
2nd best path. When we apply policy routing uniformly on all the routers
to use 2nd best path (for a particular traffic), traffic from A to F
will flow through B,M,N,O,P,F instead of B,C,D,E,F (and which remains
unused).

B---C---D
/ \ / \ / \
A X X H
\ / \ / \ /
E---F---G
A might decide that A-B-C-D-H is the best path and A-E-F-G-H is the
second best one.
But E decides that E-F-G-H is the best one and E-C-D-H is the second
best one, pushing the traffic back onto the best path from A to H.

Oh, yes. It just saves B from getting some traffic by routing through E.
However, after that the remaining path is same (C,D,H).


Regards,
Vignesh

[Vigneswaran R]

Post by Vigneswaran R
Is there any way (API) to get the second best route to a destination
from dikjtra's algorithm (when multiple routes are available between
source and the destination)?

There's been quite a lot of work done on multipath routing in
link-state protocols. As Henning notes, the tricky bit is ensuring
that the two routes are actually disjoint.
I don't have my bibliography handy, but the following paper should
http://gyroweb.inria.fr/~viennot/publis/articles/sirocco10multipath.pdf

Ok.

Post by Vigneswaran R
The idea is to write a plugin to get the second (third etc.,) best
routes (for destinations) and keep them in separate routing tables.

There's an experimental (unpublished) branch of babeld that does
something very similar, except that we use the *source* address of
packets to choose the route. This puts the responsibility for
splitting traffic in the application, which can choose a given path by
picking a source address. (We should be able to publish the code next
week, you'll know everything if you follow babel-users.)

I didn't know about this branch. I will check this out.

Since we're manipulating routing rules in order to achieve that, it
should be possible to use different ways to choose the path. What
exactly do you have in mind?

As of now I don't have anything specific regarding implementation. We
are looking into the suggestions made on this thread. Thanks for your
inputs.


Regards,
Vignesh

[Vigneswaran R]

Post by Vigneswaran R

I don't have my bibliography handy, but the following paper should
http://gyroweb.inria.fr/~viennot/publis/articles/sirocco10multipath.pdf

Ok.

Feel free to get in touch with Laurent (the author of the paper), he's
a very friendly guy. He's a theorist, but he'll certainly be able to
give you some good pointers.

Ok.

Post by Vigneswaran R

There's an experimental (unpublished) branch of babeld

I didn't know about this branch. I will check this out.

It's top secret right now ;-) We're cleaning it up, I'll drop you
a note when we make it public.

Sure, Thank you :-).


Regards,
Vignesh