Bug 521

Summary:	Ipv4 global routing inefficient
Product:	ns-3	Reporter:	Tom Henderson <tomh>
Component:	routing	Assignee:	Tom Henderson <tomh>
Status:	NEW ---
Severity:	normal	CC:	mathieu.lacage, ns-bugs, tommaso.pecorella
Priority:	P4
Version:	ns-3-dev
Hardware:	All
OS:	All
Attachments:	patch for route computation

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.