Bugzilla – Bug 521
Ipv4 global routing inefficient
Last modified: 2010-01-23 15:29:44 EDT
You need to log in before you can comment on or make changes to this bug.
for large topologies, PopulateRoutingTables() is very slow. This is because it is performing, proactively, O(N^2) shortest path computations. It also requires full routing tables at each node. A different design (without requiring API change) would allow routes to be built and cached on-demand in a centralized place. This bug report is a placeholder for this issue; I expect it can be picked up as part of the early merge phase of ns-3.5.
Created an attachment (id=406) [details] patch for route computation This patch will speed up the routing computation for large topologies that have a lot of stub nodes connected to the routers by point-to-point links. Much more can be done but I am just providing this as an interim patch in case it helps any users for the moment.
We should start by coming up with a testcase which shows the problem and, adding it to our testsuite to track performance regressions in that code.
(In reply to comment #2) > We should start by coming up with a testcase which shows the problem and, > adding it to our testsuite to track performance regressions in that code. Agree. A version of the patch attached to this bug was previously committed. I would be OK with changing the title to "Performance regression test needed for global routing" or something like that, or else close this bug for now.
PopulateRoutingTables() is not only slow, it's eating RAM like a hungry voracious worm. Meaning 4000+ nodes can easily make your simulations jump to over 8G RAM. To be honest there's something wrong somewhere, as beside the computational part, I can't see why it needs so much memory. Once the paths are fixed, is really needed to keep everything ? I must confess I didn't study the code too much, but I think there should be a cleaner way to compute the route and fix it.