[Xorp-hackers] Computing shortest path trees

[Bruce Simpson]

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