[Olsr-users] getting second best route from dikjstra's algorithm

[Vigneswaran R]

On 06/14/2013 11:23 AM, Henning Rogge wrote:
> On 06/14/2013 06:36 AM, Vigneswaran R wrote:
>>> 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).

> 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