Research activities: past projects

mascopt has been made possible through the joint support of INRIA (Bruno Bongiovanni, junior R&D engineer Oct. 2001 - Oct. 2002), University of Nice - Sophia Antipolis (Jean-François Lalande, phd/ATER, Sept. 2001 - Aug. 2005), I3S-CNRS (Yann Verhoeven, Post-Doc ARACNE and CRESCCO, Apr. 2003 - Aug. 2004), and both INRIA and I3S-CNRS (from Oct. 2004 to Dec. 2009, Fabrice Peix, ACI PRESTO and IST FET AEOLUS).

Mascopt (Mascotte Optimization) is a Java library 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 last public distribution of Mascopt appeared under the name of the openGVE project, Mascopt being one implementation of the bridge graph interface (see http://opengve.inria.fr/bridge-graph-interface/apidocs/fr/inria/opengve/bridge/interfaces/Graph.html ). The objective is to allow easy integration of different implementations. The applications already written are not be affected. They will have different choices of internal implementation which may lead to better performances for specific issues such as large graphs processing.

The main objective of the Mascopt project is to ease software development in the field of network optimization. Examples of problems include routing, grooming, survivability, and virtual network design. Mascopt helps 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 implementations of existing algorithms or linear programs (e.g. shortest paths or integral multicommodity flow).

A key feature of Mascopt is to provide a generic linear programming object interface which allows users to program the same way whether the target solver is IBM ILOG CPLEX, GLPK (GNU Linear Programming Kit) or CLP/CBC (accessed through JNI).

Mascopt has been intensively used in the past within Mascotte industrial cooperation programs for experimentation and validation purposes as for example with Alcatel Space Technologies and Orange Labs. Today, the library is used within the framework of the ANR AGAPE to implement FPT algorithms (work done at LIFO).

The code of mascopt 1.1 has been protected by a deposit at the APP institute. We received the Inter Deposit Digital Number IDDN.FR.001.100002.000.S.P.2004.000.31235.

See also the web page: Mascopt

Documents	Description	Importance
RT mascopt 04/2004	First technical report about mascopt	High
mascoptDoc-1.3.1.pdf 2003	First documentation about mascopt	Med
Séminaire Mascotte du 26/10/2006	Slides of the talk about mascopt presented at the Mascotte meeting in ST Raphael	Low
Café Logiciel Inria Sophia du 14/12/2005	Slides of the talk about mascopt presented at cafés logiciels InTech'Sophia, but without the demo	Med.
Tutorial Mascotte du 09/01/2004	Slides of the tutorial about mascopt presented at Inria	Low

SPREADS is the acronym for Safe P2p-based REliable Architecture for Data Storage. It is a common research project between UbiStorage, I3S/INRIA/Mascotte, Eurecom/NSTeam, LIP6/INRIA/REGAL and LACL/SC. The project started in Sept. 2007 with a funding from the French National Research Agency (ANR) with an additional sponsorship from the SCS pole of competitivity. The other people in the Mascotte team working on this project are Olivier Dalle, Philippe Mussi, and Stéphane Pérennes.

My involvement in this project (40%) focus on the study of protocols and algorithms, analytical modeling, and performance metrics definition.

Documents	Description
spreads-techannex.pdf	Description of the SPREADS project

I have set up the GenOpt INRIA COLOR in collaboration with DISI : Dipartimento di Informatica e Scienze dell'Informazione - Università di Genova. 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.

Along with this COLOR, I am also involved in the Leonardo da Vinci ITISFORM placement programme in which I have supervised two master students :

• Marco Servetto (Mar. - Sept. 2007) on a graph generator tool that allow to generate appropriated experimental data sets for network optimization
• Paolo Pastorelli (Jul. - Nov. 2006) on Bipartite graphs and Traffic grooming using mascopt

My main involvement in AEOLUS consisted in being representative of CNRS at the Technical Committee, including for instance the installation and maintenance of 4 nodes of the overlay computer testbed in collaboration with the 21 others participants. I also have participated to the deliverables listed below.

Documents	Description
D221.pdf	Critical resource sharing: State-of-the-art survey and algorithmic solutions

I was a member of the RESEAUXCOM INRIA associated team between Mascotte and the Network Modeling Research Group of School of Computing Science, Simon Fraser University.

During my stay in SFU (May 16th to June 16th 2006), I have started working with J. Peters on the problem of retrieving a large file (for example a video stream) stored in multiple locations in an overlay network. This work has been pursued with L. Stacho in Sophia Antipolis (visit of J. Peters and L. Stacho - July 2006), with J-C. Bermond during his stay in SFU (September 2006) and more recently with S. Pérennes and J. Peters (visit of S. Pérennes at SFU, June 10th to July 10th 2007).

In this problem we consider a peer-to-peer overlay network in which a set of receivers want to stream some file (media object) which is replicated and stored in different servers nodes. The file is partitioned into a large number of equal-sized chunks. Each receiver requests to receive all the chunks in order. A chunk can arrive at a receiver before the time that it is needed and will be buffered. Our main constraint is to avoid gaps between chunks. In other words, a chunk must arrive no later than the time that the previous chunk in the sequence has been used (played back or listened to) to avoid jitter during playback. The objective is to minimize the makespan: time at which all the receivers have completed the reception of the last chunk of the sequence.

A first solution based on graph matching has been implemented with the mascopt optimization library. Experimental results proved that the critical point is the buffer space allowed at receiver nodes and we keep on working on the algorithm.

In 2007, we worked on the streaming problem; we discarded the network flow approach and made some changes to the model. We regarded the network itself as a black box and analyzed what is essentially a streaming version of BitTorrent.

We hope the current results will be improved with the help of simulation, as we will use this approach in the context of the new ANR SPREADS: Safe P2p-based REliable Architecture for Data Storage.

CRESCCO

Documents	Description
Deliverable D4.1 (aug. 2002)	Survey on optical network co-authored with B. Beauquier and S. Pérennes
Deliverable D4.2 (jan. 2003)	Author : M. Syska
Workshop 02/03/2003	Presentation by M. Syska at the workshop in Cyprus (from ICC2002)
Evaluation 01/31/2003
ALGOTEL 03	Article on grooming published in ALGOTEL 03
Talk_Syska_Oberseminar_18_05_2004.pdf	Talk at CAU Kiel

PRESTO

PORTO

Documents	Description
sfu_10_09_2004.pdf	Detailed presentation and demo at the Network Modeling Research Group (SFU), sep. 10 2004
ecotel2002-env28_10_02.pdf	Talk at the fifth winter school on telecommunications / software and telecommunication, dec. 2-6 2002, Golfe Juan, France