Scientific description of the project

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.