Proposal for COLOR 2007 project : GenOpt

The goal of the GenOpt project is to design and implement new graph algorithms, especially in the fields of network optimization and graph representation.

The objective is to use advanced techniques in combinatorial optimization and graph theory to improve the existing solutions to these problems, while implementing the resulting algorithms in the Mascopt library developed at Mascotte team.

The duration of the project is one year.

Mascotte & DISI - Università di Genova

DISI: Dipartimento di Informatica e Scienze dell'Informazione - Università di Genoa

DISI is the Department of Computer Science of the University of Genoa and was established in 1992, while the University of Genoa is one of the oldest Italian Universities and dates its origin in the Middle-Age. Nearly sixty people are engaged in research, with a teaching staff of about thirty; it supports the teaching activity of the programs in Computer Science: Laurea (undergraduate, three years), Master (postgraduate or near), Laurea Specialistica (postgraduate, two years); since 1993 it hosts a PHD program in Computer Science.

The main research areas are: databases and information systems, image processing, machine learning, artificial intelligence, geometric modeling and computer graphics, software development methods, parallel and distributed systems, programming languages, computational logic, computer algebra; research is performed in collaboration with national and international research centres and universities and industry.

In the first ten years of activity DISI ha established collaborations with over a hundred of research institutes in Europe and US. In the last five years 70% of our fund resources came from collaborations with external institutes and companies: EC projects (IV, V, VI framework; ESPRIT, BRITE, HCM, SCIENCE, CRAFT, IST) and MURST/MIUR, CNR, INFM, Parco Scientifico e Tecnologico Regione Liguria and companies (e.g. TXT e-solutions, Elsag, Marconi, Ferrovie dello Stato).

Mascotte - joint team INRIA Sophia - Antipolis, CNRS I3S and University of Nice - Sophia Antipolis

Mascotte is a joint team between Inria and the laboratory I3S (Informatique Signaux et Systèmes Sophia Antipolis) which itself belongs to Cnrs (Centre National de la Recherche Scientifique) and Unsa (University of Nice - Sophia Antipolis). Furthermore Mascotte is strongly associated with the center of research and development of France Telecom at Sophia-Antipolis via the CRC CORSO (the first Contrat de Recherche Collaborative Inria with France Telecom).

Its research fields are Simulation, Algorithmic, Discrete Mathematics and Combinatorial optimization with applications to telecommunication, global computing and transportation networks.

In particular, Mascotte has developed in the last four years both theoretical and applied tools for the design of heterogeneous networks or networks using various technologies like wavelength division multiplexing (WDM), synchronous digital hierarchy (SDH), Asynchronous Transfer Mode (ATM), fixed, mobile or satellite wireless networks, ...

In this project we would like to share the expertise of the two teams on specific graph or network design algorithms. We would also take advantage of the existing Mascopt library in order to implement the results of common research.

On one hand, we have already initiated collaboration on network design problems, for example with the internship of Paolo Pastorelli (master student from Genoa) in Mascotte from June to November 2006. Another master student is going to come in Mascotte in the cadre of the Leonardo Project Itisform. Here the problem is to study new strategies for traffic grooming in multi-layer networks.

On the other hand, Gianluca Quercini, PhD student in Genoa has started working with Bruce Reed on the subject of data visualization and graph clustering and drawing.

On both hands we want to study new algorithms and implement them with Mascopt. The objective is twofold : first, we want to test the practical efficiency of the algorithm by running experimentation with real data. Second, we want to improve the distribution of Mascopt by adding more "ready to use" classes in the interface of the library.

In the following we describe more precisely the Mascopt library and the problems we would like to work with.

Implementing Graph Algorithms with Mascopt

Mascopt is a free Java library developed within Mascotte team and distributed under the terms of the LGPL license which is dedicated to graph and network processing. Mascopt includes a collection of Java interfaces and classes that implement fundamental data structures and algorithms.

The main objective of Mascopt (Mascotte Optimization) project is to ease software development in the field of network optimization. Examples of problems include routing, grooming, survivability, and virtual network design. Mascopt help implementing a solution to such problems by providing a data model of the network and the demands, classes to handle data and ready to use implementation of existing algorithms or linear programs (e.g. shortest paths or integral multicommodity flow). A new release of Mascopt has been developed since 2005 in order to allow Mascopt users to program to an interface, not an implementation. Indeed, basic Mascopt users may simply use the existing API, but more advanced users may like to use different implementations of some features. The applications already written will not be affected, they will not have to be rewritten but will have different choices of internal implementation. This may lead to better performances for specific issues. The Mascopt interface was defined in collaboration with Ricardo Correa (Universidade Federal do Ceara, Brazil) to make it compatible with the Parego library implementation to start with. The interface also enables the transparent use of different solvers when writing linear programs.

Mascopt was intensively used within Mascotte industrial cooperation programs for experimentation and validation purposes: with Alcatel Space Technologies on the design of fault-tolerant on-board network satellites, on the optimization of the access layer and planning of satellite communication and with France Telecom on the design of telecommunication backbone networks.

The last version of Mascopt will be publicly available on gforge.inria.fr in January 2007 (user documentation in progress).

Network Design : Traffic Routing and Grooming

Optical networks using WDM are widely deployed in carrier networks. One important problem is the design and planning of such networks. Given a traffic matrix of demands between all node pairs, and given capacity constraints on the links, the problem is to find the best traffic routing that minimizes the cost of the network. The dominant cost when building the network appears to be the cost of the equipment of the nodes: optical crossconnects (OXC s), optical add/drop multiplexers (OADM s) or add/drop multiplexers (ADM s) that play the interface between the optical and electronical network. Traffic grooming is the optimization problem that aims to reduce that cost.

In this project we want to study the influence of routing algorithms over the performance of grooming. Indeed, the physical paths assigned to the demands are usually computed in the first step of the optimization process. Hence the set of paths used as an input of the grooming problem may not lead to an optimal solution of the general problem (routing and grooming). However, the optimization process may be done in several steps over subsets of demands (for instance by sorting them according to their sizes) and the physical paths could have been fixed by the manager of the network on some geographical or protection purposes.

In this project we will explore different strategies for routing that may improve the grooming process. We will try to use linear programming decomposition techniques but also heuristics.

Data Visualization and Graph Clustering and Drawing: Issues and Applications

Graphs are among the most studied and used mathematical tools to visualize data and their relationships. The increasing number of applications exploiting their descriptive power makes graph representation a key issue in modern graph theory and computer science. Beside classical applications, particularly exciting and challenging are relatively new fields, such as virtual reality and information visualization. Virtual reality introduces new representations of relationships, based on a metaphor of the real world, requiring approaches that are different from traditional graph drawing. Moreover, in information visualization a huge quantity of information has to be visualized and some knowledge should be extracted from them; therefore data representation has to be not only pleasant, but also meaningful.

Some examples are cartograms, where the area of each region represents a particular statistical value (such as population) associated to it, and communication networks, that are traditionally difficult to manage and update, especially when they are very large.

Graph drawing has been dealing with graph representation for almost thirty years, proposing many solutions and newer issues to be tackled. Works in graph drawing pay a major attention on aesthetic criteria, that, however, are very useful as a good drawing is the first condition for a representation to be functional. The aim of this project is to investigate new directions in graph representation, starting from a technique, rectangular dualization, that has not been well exploited yet for this purpose.

As stated before, we already have initiated some collaboration. More precisely, the plan is the following:

• Gianluca Quercini will visit Mascotte (internship) to work with Bruce Reeds on graph representation. Bruce Reed will use his expertise in graph tree-width and probabilistic methods.
• Massimo Ancona, Vittoria Gianuzzi and Michel Syska will define directions for research for internship students in network optimization
• Michel Syska will supervise the implementation of algorithms in the Mascopt library
• All the listed people will meet and organize seminars in Genoa and Sophia as well