[Xorp-hackers] Computing shortest path trees

[Victor Faion]

On Fri, Feb 27, 2009 at 18:34, Atanu Ghosh <atanu at icir.org> wrote:
> Hi,
>
> The Spt interface was designed to support incremental updates. You
> should be able to create a single Spt instance and every time the
> topology changes apply the deltas then call compute which should
> generate just operations required. This requires the caller to track
> the topology changes and apply them to the Spt interface.
>
> Behind the scenes the Spt interface does not perform an incremental
> computation but the code is structured to support this. If we see a
> performance issue we can add it without changing the interface.
>
> Currently the code that uses the Spt interface does not use its
> incremental feature. For correctness it is simpler to compute the
> whole graph and "diff" the results.
>
>      Atanu.
>
> On Thu, Feb 26, 2009 at 4:12 PM, Bruce Simpson <bms at incunabulum.net> wrote:
>> Victor Faion wrote:
>> ...
>>>  I don't understand how to use the result given by
>>> Spt::compute (a list of RouteCmd<IPv4>).
>>>  Are these operations that
>>> must be performed on the whole graph (i.e. everything I've added to
>>> the Spt object on which I call the compute function), and if so is
>>> there a function that does this? Or does the compute function itself
>>> prune the graph?
>>
>> Spt::compute() yields a collection of RouteCmd objects. These are just
>> an abstraction of  'given the shortest paths in this graph, here are
>> some abstract route commands to populate a flat FIB-style forwarding table'.
>> It doesn't perform any operations which would modify the Spt itself, and
>> it doesn't compute any deltas as such. It's entirely up to the developer
>> to compute deltas.
>>
>> The XORP consumers of Spt just repopulate the Spt every time at the
>> moment for this very reason. I did look at Boost's BGL for doing this,
>> and quite frankly, the performance sucked.
>>
>> Have a look at OLSR's RouteManager::recompute_all_routes() method, for
>> another consumer of Spt::compute(). See RouteManager::begin() and
>> RouteManager::end() for a transaction-based approach to deriving deltas
>> from running Dijkstra's algorithm on the graph, and only pushing those
>> to the RIB.
>>
>> When I implemented OLSR last year for XORP, I found and fixed some
>> memory leaks in Spt itself. It could no doubt do with further attention.
>> A potential win for something such as OLSR or DYMO where the topology
>> varies more dynamically than OSPF, and may contain hundreds of nodes,
>> would be to refactor Spt to support Incremental SPT.
>>
>> thanks
>> BMS
>>
>> _______________________________________________
>> Xorp-hackers mailing list
>> Xorp-hackers at icir.org
>> http://mailman.ICSI.Berkeley.EDU/mailman/listinfo/xorp-hackers
>>
>

Thank you for the help. If I understand correctly, is the Spt class
just a container for the shortest path tree as computed by the
developer and Spt::compute() just produces a list of RouteCmds which
can be used to populate a forwarding table? I thought the deltas would
be computed by Spt::dijkstra(). I'm not too worried about the
incremental feature, recomputing the whole graph on a topology change
is fine. I just don't understand how to use the implementation of
Dijksta's algorithm; does it give you a shortest path tree or should I
be computing this myself and adding it into my Spt object?

Victor