On Fri, Feb 27, 2009 at 18:34, Atanu Ghosh <[email protected]> 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 <[email protected]> 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 >> [email protected] >> 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 _______________________________________________ Xorp-hackers mailing list [email protected] http://mailman.ICSI.Berkeley.EDU/mailman/listinfo/xorp-hackers
