Topology generation through network design heuristics
Brief introduction
Description Download Authors Contacts

Description

 IGen is a network topology generator. Unlike GT-ITM and BRITE, IGen does not rely on probabilistic methods to generate network topologies. Since real networks are the outcome of a careful network design, IGen implements various network design heuristics such as MENTOR, MENTour, Delaunay triangulation and Two Trees for the purpose of building network topologies.

IGen is written in Perl/Tk and is provided under the LGPL license. The text of the LGPL license is available here and more information can be obtained from the Free Software Foundation.

Other topology generators are available such as BRITE, GT-ITM and Inet. Methods to infer topologies at the AS-level have been proposed by Subramanian et al (University of Berkeley) and by University of Roma. Methods to infer the router-level Internet topology have been proposed by Rocketfuel (University of Washington) and D. Magoni (University of Strasbourg).

Brief introduction

 There are two ways of using IGen. The first one is through its graphical interface. In order to run IGen in this mode, just move to the IGen directory and run ./igen-gui.pl. A window similar to the one shown in Fig.1 should appear.


Fig.1 Screen shot of IGen with an interdomain topology loaded.
(click to enlarge)

IGen makes possible to import/export the graph of an existing network written in various file formats (GML, BRITE, TOTEM XML...). Import is done through the menu item 'Graph'/'Import'. It is also possible to generate a random set of points using the 'Graph'/'Generate' menu item. The generation method is currently limited to a uniform distribution within a geographical area.

Based on the imported network or on the generated set of points, it is possible to generate another network topology using various network design heuristics. This is done through the 'Build' menu item. The easiest method is to rely on the 'Intradomain network' method which will drive you through all the steps of building a two-levels network with a backbone and access networks. The currently implemented network design heuristics are MENTOR which builds a hybrid MST-SPT, MENTour which builds a tour using a TSP heuristic, Delaunay triangulation which connect the set of routers using triangles and Two-trees which builds two disjoint MSTs.

In addition, IGen allows the user to perform some measurements on the imported/generated networks through the 'Measure' menu item. The supported metrics consider performance (distribution of shortest path lengths, link utilization) as well as pure graph properties (distribution of node degree, edge-connectivity).

Finally, it is also possible to run IGen in command-line without the GUI interface. It is possible to load a network, a traffic matrix, perform measurements, and so on. For instance ./igen-gui.pl --no-gui --in-net=abilene.gml --measure=node-degrees will load the topology from file abilene.gml and measure the distribution of node degrees.

Download

 Latest release:

igen-0.15.tar.gz March 5th, 2010 127.17 K


IGen requires a recent version of Perl (version 5.8.4 or above suggested) compiled with threads support. IGen also requires Perl/Tk available from CPAN. Finally, the following CPAN modules need to be installed: Graph (version 0.20105) as well as the Statistics/Basic and Statistics/Descriptive modules. Note that if you encounter installation problems, you might find some help in Gilles Bertrand's tutorial
.
Subversion:

The source code repository is hosted by SourceForge. You can use the following svn command to retrieve the current version: 
svn co https://igen.svn.sourceforge.net/svnroot/igen igen
Documentation:

There is currently no documentation available for IGen. We had a paper at the 21st International Teletraffic Conference in 2009 that describes the methodology behind IGen. The paper is available here as well as the slides of the ITC talk.
igen-tech-report.pdf March 5th, 2010 1.03 M
itc21-igen-bqu.pdf March 5th, 2010 133.67 K
itc21-igen-bqu-slides.pdf March 5th, 2010 1.39 M


Available topologies:

abilene.gml March 5th, 2010 2.18 K
belnet.gml March 5th, 2010 3.20 K
geant-20041125.gml March 5th, 2010 5.21 K
internet.pops.bz2 March 5th, 2010 2.97 M


Small experimental Internet-like topology:

This is an example interdomain topology built using IGen. The topology contains 5 domains, one for each continent. The routers in these domains where generated using a uniform distribution. The list of routers is provided in the net-continents-5.pops file.
Each domain is divided in 10 PoPs using k-medoids. Each PoP contains 2 backbone routers, the other routers being access routers. Each access router is connected to the two backbone routers in its PoP. The backbone routers in a PoP are connected in full-mesh. In addition, all the backbone routers are connected using a Delaunay triangulation. The IGP weights are assigned based on the mileage of the links. The capacities are assigned using a single scheme where backbone links have a 10G capacity and access links have a 155M capacity.
The interdomain links are based on business relationships between the domains. These relationships were defined manually in the following way: North_America, Australia and Europe_Asia have Peer-Peer relationships and South_America and Africa are customers of North_America and Europe_Asia. The net-continents-5.relation file contains these business relationships. Each business relationship is implemented using 3 interdomain links. These links are not assigned a capacity nor an IGP weight. The net-continents-5.rig file contains the generated topology.
Finally, a C-BGP script has been generated in order to compute the intradomain and interdomain routes in this network.

net-continents-5.pops March 5th, 2010 8.56 K
net-continents-5.relation March 5th, 2010 249.00
net-continents-5.rig March 5th, 2010 38.63 K
net-continents-5-cbgp.cli.bz2 March 5th, 2010 9.73 K
net-continents-5-cbgp-policies.cli.bz2 March 5th, 2010 9.81 K
net-continents-5-cbgp_1_1_21.cli.bz2 March 5th, 2010 4.73 K
net-continents-5-cbgp_1_1_21-policies.cli.bz2 March 5th, 2010 4.92 K


Authors

 IGen is written and maintained by Bruno Quoitin (CSE Department, Université de Mons (UMons), Belgium).
Jean Lepropre from the Research Unit in Networking of University of Liège (ULg) also contributes to this project.

We thank Cristel Pelsser (UCL) and Stefano Iasi (Politecnico di Torino) for testing some of the functionalities of IGen.

This work was supported by the Belgian Walloon Government under the WIST TOTEM project. IGen is also partly supported by the European Commission within the E-Next Network of Excellence.

Contacts

 IGen is developed by the networking group at the CSE Dept. of University of Louvain-la-Neuve. If you want to contact the authors, you can write to this address.