Involvement in research projects

This document is intended to be pasted in various activity reports. It describes my personnal participation in the research activities of the Mascotte team.
En construction - Dernière modification le 24/10/2007

Mascopt (2001 - )

Since 2001, after having completed the PORTO software, I have started a new project with as a main objective to ease experimental work on network optimization. The result consists in mascopt (which stands for Mascotte Optimization), a free 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 mascopt library is dedicated to software development in the field of combinatorial network optimization. Examples of targeted problems include routing, grooming, survivability, and virtual network design. mascopt help with 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).

When writing linear programs, mascopt provides the user an adapted interface, especially when decision variables are derived from graph data structures. The interface allows the use of many different solvers, provided that a Java interface exists (this restriction could be removed using techniques such as JNI).

The new public distribution of mascopt is scheduled for the end of october 2007.

mascopt has also been made possible through the joint support of INRIA (Bruno Bongiovanni, junior R&D engineer oct. 01 - oct. 02), University of Nice - Sophia Antipolis (Jean-François Lalande, phd/ATER, sept 01 - aug. 05), I3S-CNRS (Yann Verhoeven, Post-Doc ARACNE and CRESCCO apr. 03 - aug 04), and both INRIA and I3S-CNRS (since oct. 04, Fabrice Peix ACI PRESTO and IST FET AEOLUS).

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.

We believe the current success of mascopt will keep growing with the new released stable version made available these days. We already proved the efficiency of mascopt in most of the research projects being yield in the Mascotte team and partners, but also in master class teaching (Master 2 MDFI in Marseille and RSD in Nice). The maturity of the code today allows us to distribute and support the use of mascopt in the national (GDR ASR ResCom) and international (AEOLUS, Associated team INRIA ReseauxCom) network optimization communities.

Documents Description Importance
RT mascopt 04/2004 First technical report about mascopt High
mascoptDoc-1.3.1.pdf 2003 First documentation about mascopt Med
mascopt's web site (under updating process) Home page of mascopt High
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 (2007-2010)

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 has just 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%) will focus on the study of protocols and algorithms, analytical modeling, and performance metrics definition.

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

GenOpt (2007)

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 - sep 2006) 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
Documents Description
Paolo_Pastorelli.pdf Paolo_Pastorelli.pdf

AEOLUS (2005 - 2009)

My main involvement in AEOLUS consists 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

RESEAUXCOM (2004 - 2007)

I am 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 play back. 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 (2002 - 2005)

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 (2003 - 2006)

Porto (1998 - 2001)

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