Bug 521 - Ipv4 global routing inefficient
Ipv4 global routing inefficient
Status: NEW
Product: ns-3
Classification: Unclassified
Component: routing
ns-3-dev
All All
: P4 normal
Assigned To: Tom Henderson
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2009-03-12 00:38 EDT by Tom Henderson
Modified: 2013-04-26 15:12 EDT (History)
3 users (show)

See Also:


Attachments
patch for route computation (9.61 KB, patch)
2009-03-29 14:46 EDT, Tom Henderson
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Tom Henderson 2009-03-12 00:38:34 EDT
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.
Comment 1 Tom Henderson 2009-03-29 14:46:21 EDT
Created attachment 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.
Comment 2 Mathieu Lacage 2009-11-23 09:27:14 EST
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.
Comment 3 Tom Henderson 2009-11-24 00:15:54 EST
(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.
Comment 4 Tommaso Pecorella 2010-01-23 15:29:44 EST
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.
Comment 5 Tom Henderson 2010-04-16 18:45:55 EDT
I think this should be marked down from P2 for this release as it is a performance optimization and workarounds exist (NixVector) for many scenarios.