IGen - Topology generation through network design heuristics

Topology generation through network design heuristics

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 distribution:

igen-0.11.tar.gz

April 12th, 2006

119.42 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
.
Documentation:

There is currently no documentation available for IGen. However, the basic motivations and techniques are briefly described in the short abstract accepted at the Co-Next'05 conference.

sw88-quoitin.pdf	April 12th, 2006	45.47 K
igen-tech-report.pdf	September 7th, 2007	1.03 M

Available topologies:

abilene.gml	April 12th, 2006	2.18 K
belnet.gml	April 12th, 2006	3.20 K
geant-20041125.gml	April 12th, 2006	5.21 K
internet.pops	April 12th, 2006	9.58 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	April 12th, 2006	8.56 K
net-continents-5.relation	April 12th, 2006	249.00
net-continents-5.rig	April 12th, 2006	38.63 K
net-continents-5-cbgp.cli	April 12th, 2006	515.31 K
net-continents-5-cbgp-policies.cli	April 12th, 2006	529.19 K
net-continents-5-cbgp_1_1_21.cli	April 12th, 2006	47.25 K
net-continents-5-cbgp_1_1_21-policies.cli	April 12th, 2006	60.92 K

Authors

IGen is written and maintained by Bruno Quoitin (CSE Department, Université Catholique de Louvain, 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.