[Ns-developers] Topology generators and simulations with 4000+ nodes

[Tommaso Pecorella]

On 24/gen/2010, at 00.36, Tom Henderson wrote:

> On 1/22/10 6:40 PM, Tommaso Pecorella wrote:
>> Hi all,
>> 
>> some time ago I was trying to run some simulations for a wide-area scenario and I found myself failing bad. The simulator I was using wasn't able to understand simple concepts like "internet-like topology". Darn.
>> 
>> Now I'm working with ns-3 and I honestly don't want to find myself in need again, especially because I plan to do some simulations about P2P-like networks, so a large-scale network is a must. 10.000 nodes or so. Well, "if there isn't, do it", right ?
>> 
>> So, I'm working on a simple interface to read the major topology generators output. To be honest it's already almost finished, I'll submit it in a few. However first I'd like to ask if anyone have some suggestions about the topology generators that *must* be supported.
>> 
>> So far we have a rather simple and modular code to read Inet 3.0 and Orbis 0.7 outputs. I checked Tiers 1.1 but I must confess that all I got is a segmentation fault. Rather old code indeed. I'll take a look at gt-itm but that one too seems to be rather old. BRITE is not anymore developed, but someone might use it still. I don't know if coding it as well is worth tho. Note that those are the ones that was supported ns-2.
>> 
>> Any suggestions ?
> 
> I don't think there are any "must" topology generators.  Anything that you're able to contribute will be welcome.
> 
> Some of the ones previously used in ns-2 (which you seem to already know about) are listed here:
> http://www.isi.edu/nsnam/ns/ns-topogen.html

Aye, I got already those covered up to the best possible extent.

> There is a relatively new one that looks interesting:
> RealNet:  http://portal.acm.org/citation.cfm?id=1395414

That one is new to me, I'll take a look.

> George Riley has some plans to support BRITE with ns-3 in the future.

I'll write to George, maybe we should get in sync then.

> You might find some other tools by poking around CAIDA's site; e.g.
> http://www.caida.org/data/active/ipv4_routed_24_topology_dataset.xml

Done, Orbis is from CAIDA's work for real. It can crunch Archipelago's data as a matter of fact. Archipelago's data alone aren't really of much use, unless you want to really recreate the snapshot of Internet as it is right now, and I doubt someone want to do that in a "normal" simulation.

>> By the way, my actual code is able to munch 4000+ nodes in a snap. The only drawback is about the routing. Ipv4GlobalRoutingHelper::PopulateRoutingTables () simply... fails. nixRouting rocks.
>> 
>> Let me a bit more clear. PopulateRoutingTables with 4000+ nodes (and about the same number of links) works, but the simulations takes hours to start and like 10G RAM to run. I didn't debug the code, but my guess is that the code isn't designed for that number of nodes. Still I can't figure out why so much memory is needed, unless for a huge memory leak somewhere.
>> On the other hand with nixRouting the simulations ends in 20 seconds. probably because only 2 of the 4000 nodes are sending datas. I'll try with an increasing number of senders to check how much memory is needed.
>> 
>> 
> This is becoming a more frequent complaint.  Basically, the code is a non-optimized port of the quagga ospf SPF computation; only a small amount of optimization to prune some leaf nodes during the computation has been added.  If you could post a test case program to bug 521, I would be happy to look at it and I am pretty sure it can be improved. However, NixVector is probably going to still outperform it, since NixVector just builds routes with a breadth-first search as it needs them.  For what you describe (a really large topology but a really sparse traffic matrix), it may be preferable to defer the SPF computations until they are really needed.


I'll update bug 521 as soon as my code is available to everyone, as it can be used to benchmark other routing protocols as well. It's an ugly code, but it's a worst-case. All the IP numbers are assigned to node interfaces in a dumb way, without really checking anything. It's a pure flat network made of simple PointToPoint links. The dumbest thing one can think about indeed, but the fastest one to do. And I am interested in checking the topology readers, not in using them in a smart way (yet).

Anyway, I did a more stressing test. I wanted to see the TTL distribution between a random node and the rest of the network. It's just a ping, but all the nodes are pinging a given node now. Result is: SimpleRouting is simply... well, it didn't change. NixRouting took a bit more to end the simulation. Instead of the usual 20 seconds, now it needs 1-2 minutes.

Note that now Nix have to (sooner or later) map all the paths from one node to the whole network. Sure, it's still 1/4000 of the work needed by SimpleRouting, but the memory seems stable.

Again, tomorrow more tests, this time I will measure the memory used for real with increasing number of routes computed.

The real question, however, is: do SimpleRouting needs to be smarter or not ? I'm more and more convinced that maybe it doesn't need to be really smarter. On the other hand ns-3 users need to be aware that it's not smart at all. According to Josh's tests (reported in another mail) a decent choice of IP numbers seems to solve the issues, so the real point is to make sure to warn for possible memory issues related to dumb IP number assignments. Unless you want to simulate an extremely large number of AS of course. But then again, in that case you should use BGP and not OSPF with only one area, isn't it ?

Regards,

Tommaso

--------------------------------------------------------------

The nice thing about standards is that there are so many to choose from.
And if you really don't like all the standards you just have to wait another year until the one arises you are looking for.
-- A. Tanenbaum, "Introduction to Computer Networks"

--------------------------------------------------------------

Tommaso Pecorella - Ph.D.

Assistant professor
Dpt. Elettronica e Telecomunicazioni
Università di Firenze

CNIT - Università di Firenze Unit

via di S. Marta 3
50139, Firenze
ITALY

email: tommaso.pecorella at unifi.it
       tommaso.pecorella at cnit.it

phone : +39-055-4796412
mobile: +39-320-4379803
fax   : +39-055-494569