||Topology generation through network design heuristics
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
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).
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.
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
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
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.
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.
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
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
project. IGen is also partly supported by the European
Commission within the E-Next
Network of Excellence.
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.