Direction des Relations Internationales (DRI)

Programme INRIA "Equipes Associées"
(Dossier de renouvellement)

I. DEFINITION

EQUIPE ASSOCIEE RESEAUXCOM
sélection
2004
Renouvellement
2009

Equipe-Projet INRIA: MASCOTTE, commun INRIA, I3S, CNRS, Univ. Nice Sophia Organisme étranger partenaire: Network Modelling Group, Simon Fraser University
Centre de recherche INRIA: Sophia Antipolis - Méditerranée
Thème INRIA : Com B
Pays : Canada
 
Coordinateur français
Coordinateur étranger
Nom, prénom Bermond, Jean-Claude Peters, Joseph
Grade/statut Directeur de recherches Professeur
Organisme d'appartenance
(précisez le département et/ou le laboratoire)
CNRS Simon Fraser University
Adresse postale Projet Mascotte, commun I3S(CNRS/UNSA)-INRIA
INRIA Sophia-Antipolis
2004, route des Lucioles -- B.P. 93
06902 Sophia-Antipolis Cedex
France
School of Computing Science
Faculty of Applied Sciences
Simon Fraser University
Burnaby, British Columbia V5A 1S6
Canada
URL http://www-sop.inria.fr/mascotte/ http://www.cs.sfu.ca/research/groups/NML/
Téléphone +33 (0)4 92 38 76 79 +1 778 782 3780
Télécopie +33 (0)4 92 38 79 71 +1 778 782 3045
Courriel Jean-Claude.Bermond@sophia.inria.fr peters@cs.sfu.ca

La proposition en bref
Titre de la thématique de collaboration (en français et en anglais):
Réseaux de Communications / Communication Networks
Thématique de la collaboration :

L'objectif de cette collaboration est de factoriser les connaissances des deux équipes pour la modélisation et la résolution des problèmes issus des télécommunications, dont un grand nombre sont issus de nos partenariats industriels (Orange labs, Alcatel-Lucent Bell, ...).
Nous souhaitons principalement nous concentrer sur deux types de réseaux, les réseaux dorsaux et les réseaux sans fil. En particulier nous étudions conjointement les problèmes de groupage de trafic et de tolérance aux pannes dans les réseaux dorsaux, de concentration de données dans les réseaux sans fils et d'algorithmes distribués pour l'ordonnancement d'appels.

Abstract :

The goal of this collaboration is to share the expertise of both teams to model and solve telecommunication problems. Many problems are motivated by our industrial partners (Orange labs, Alcatel-Lucent Bell,...).
We plan to concentrate mainly on backbone networks and wireless networks. In particular, we intend to work together on traffic grooming and survivability issues in backbone networks, gathering problems in wireless networks, and distributed algorithms for call scheduling.


Présentation détaillée de l'Équipe Associée

1. Objectifs scientifiques de la proposition

This collaboration is a continuation of our productive associate team. We will continue to share the expertise of the two teams to model and solve telecommunication problems. In the next three years, we will concentrate most of our efforts on three subjects, two in wireless networking, and one in WDM networks as described below. The first subject has been studied intensively during the last four years and we now have the tools and ideas to make important progress. The second subject is new and very promising; papers from researchers in ATT are starting to appear, and it is the subject of the thesis of D. Mazauric who will continue to work in collaboration with J. Peters. We began working on the third subject during the most recent visit of David Coudert and J-C. Bermond to SFU. During the next three years, we will also finish our work on UPP DAG's and peer-to-peer systems (see report of 2008) and perhaps do further research on these subjects as many questions remain open.

2. Présentation des partenaires

Network Modelling Group, School of Computing Science at Simon Fraser University
MASCOTTE

Historique de la collaboration
Les membres de MASCOTTE et de l'école d'informatique de SFU (Simon Fraser University) à Vancouver ont des collaborations très suivies depuis plusieurs années.

Visites de chercheurs de MASCOTTE: J-C. Bermond a passé une année sabbatique (1988) et effectué une dizaine de visites dont un mois en 2003, 2004 et 2005, 2 semaines en 2006 et 3 semaines en 2008, A. Ferreira a effectué plusieurs visites de plus d'un mois, M. Syska y a passé un mois en 1992, 1996, 2004 et 2006 ainsi qu'un séjour post-doctoral de janvier à aout 1993, S. Pérennes y a passé 4 mois en 1998, un mois en 2005 et en 2007, R. Klasing y a passé un mois en 1999, 2004 et 15 jours en 2005 (il est maintenant au LABRI), F. Havet y a passé un mois en 2001, D. Coudert y a passé un mois en 2004 et en 2008, M. Cosnard y a passé un mois en 1994 et en 2007, et D. Mazauric y a effectué un stage de 2 mois en 2008.

Symétriquement J. Peters a passé son année sabbatique 1990-1991 chez nous, 1 mois en 1998 et 2003, 2 mois en 2004, 3 mois en 2005, et 1 mois en 2006, 2007 et 2008. Certaines visites ont été suivie de la visite d'autres laboratoires en France. P. Hell passe régulièrement chaque année environ 1 mois (ou 2 mois comme en 2002) au titre de professeur ou chercheur invité. M.-L. Yu est venu de nombreuses fois comme chercheur invité CNRS ou INRIA ou UNSA. Il a passé 9 mois ici en 2001, 3 mois en 2002, en 2003, en 2004, en 2005, en 2007 et en 2008, et 1 mois en 2006. L. Stacho est venu 3 semaines en 2006 et 2 semaines en 2007. D'autres visites plus courtes ont aussi eu lieu.

Une collaboration officielle a été financée par un PICS CNRS-CANADA de 1992 à 95 (le premier PICS franco-canadien du CNRS).

Plusieurs membres de MASCOTTE ont participé à des jurys de thèse à Vancouver (J-C. Bermond et A. Ferreira ont dirigés des thèses) et réciproquement les chercheurs de SFU ont été rapporteurs et/ou membres de plusieurs jurys d'étudiants de MASCOTTE. J. Peters a été membre du comité d'évaluation du programme 1A de l'INRIA en 1999.

Enfin nous avons aujourd'hui plus de 30 articles en commun avec eux (voir plus bas).

La collaboration passée a eu pour objectif principal d'appliquer une expertise commune en mathématiques discrètes, et en particulier en théorie des graphes, aux problèmes de conception de réseaux (principes reliant le degré d'un réseau, son diamètre et son nombre de sommet BHQ92, propriétés structurelles BHY90a BHY90b BeHe93 et aux questions liées à la diffusion de l'information dans les réseaux BHLP92a BHLP92b BFP95 BHLP97 FPP98 FrPe01 GHP01. Sur le plan théorique, elle a contribué a comprendre les phénomènes de diffusion et d'échange total. Sur un plan plus pratique, elle a mis en perspective l'importance des hypothèses de modélisation (commutation de paquets, routage wormhole, réseaux par bus PeSy96 BMY00 BBGH+97 avec comme domaine d'applications le parallélisme.

Les deux projets ont à peu près en même temps réorienté leurs thématiques vers la modélisation et la résolution des problèmes issus des réseaux de télécommunications et investi plus dans les relations industrielles. Au sein de l'école d'informatique de SFU a été crée en septembre 2001 un nouveau groupe (projet) qui travaille de fait sur les mÊmes sujets que MASCOTTE. Si durant ces dernière années MASCOTTE a eu tendance à collaborer plus avec des partenaires industriels et des partenaires européens, l'équipe de SFU reste par la qualité de ses chercheurs et les thématiques développées comme la plus voisine de nous et un excellent partenaire pour une équipe associée.

Depuis la création de l'équipe associée (2004) la collaboration a été fructueuse et nous souhaitons la poursuivre et demandons donc son renouvellement pour 2009.

Articles en commun

2008 2007 2006 2005 2004 2003 2002 2001 2000
1998 1997 1996 1995 1994 1993 1992 1991 1990

2008
  1. J.-C. Bermond, R. Correa, and M.-L. Yu. Optimal Gathering Protocols on Paths under Interference Constraints. Discrete Mathematics, 2008, to appear.
    Note: A preliminary version has been presented at CIAC06. [WWW] [PDF]
  2. F. Havet and M.-L. Yu. (p,1)-total labelling of graphs. Discrete Mathematics, 308(4):496--513, February 2008. [PDF]
  3. J.-C. Bermond and M-L. Yu. Optimal gathering algorithms in multi-hop radio tree networks with interferences. In ADHOC-NOW 2008, volume 5198 of Lecture Notes in Computer Science, pages 204-217, September 2008. Springer-Verlag. [PDF]
  4. J-C. Bermond, D. Coudert, and J. Peters. Online multihop traffic grooming on the path with bounded number of ADMs per node.
    Note: Manuscript, 2008.
  5. J-C. Bermond and J. Peters. Optimal Gathering in Radio Grids with Interference.
    Note: manuscript to be submitted, 2008.
  6. D. Mazauric Conception et analyse d'algorithmes distribués d'ordonnancement des transmissions dans les réseaux sans-fil. Master's thesis. Ecole Doctorale STIC - Master Recherche Réseaux et Systèmes Distribués (RSD).
    Note: Supervised by Jean-Claude Bermond and Philippe Nain. Part of this work was done with J. Peters at SFU, 2008.
  7. S. Perennes and J. Peters. Modelling Peer-Assisted Content Distribution Systems.
    Note: Manuscript, 2008.
2007
  1. J.-C. Bermond, A. Ferreira, S. Pérennes, and J. Peters. Neighbourhood Broadcasting in Hypercubes. SIAM Journal on Discrete Mathematics, 21(4):823-843, 2007. [PDF]
  2. J.-C. Bermond and M.-L. Yu. Vertex disjoint routings of cycles over tori. Networks, 49(3):217-225, 2007. [PDF]
  3. J-C. Bermond, R. Correa, and M-L. Yu. Optimal Gathering Protocols on Paths under Interference Constraints. Technical report inria-00168162, HAL, August 2007. [WWW] [PDF]
2006
  1. R. Klasing, C. Laforest, J. Peters, and N. Thibault. Constructing Incremental Sequences in Graphs. Algorithmic Operations Research, 1(2), 2006.
  2. J-C. Bermond, R. Correa, and M-L. Yu. Gathering algorithms on paths under interference constraints. In 6th Conference on Algorithms and Complexity, Roma,Italy, pages 115-126, May 2006. [PDF]
2005
  1. J-C. Bermond and J. Peters. Efficient Gathering in Radio Grids with Interference.. In ALGOTEL, pages 103-106, 2005. [PDF]
  2. R. Klasing, C. Laforest, J. Peters, and N. Thibault. Constructing Incremental Sequences in Graphs. Technical report, INRIA Research Report RR-5648 and I3S Research Report I3S/RR-2005-22-FR, 2005. [PDF] [POSTSCRIPT]
2004
  1. J-C. Bermond, C.J. Colbourn, A. Ling, and M-L. Yu. Grooming in unidirectional rings : K_4 -e designs. Discrete Mathematics, Lindner's Volume, 284(1-3):57-62, 2004. [POSTSCRIPT]
  2. J-C. Bermond, A. Ferreira, S. Perennes, and J. Peters. Neighbourhood Broadcasting in Hypercubes. Technical report, SFU-CMPT-TR 2004-12, 2004.
    Note: Submitted to SIAM JDM. [PDF]
2003
  1. R. Balakhrishnan, J-C. Bermond, P. Paulraja, and M.L. Yu. On Hamilton cycle decompositions of the tensor product of complete graphs. Discrete Mathematics, 268:49-58, 2003.
  2. J-C. Bermond, D. Coudert, and M-L. Yu. On DRC-covering of K_n by Cycles. Journal of Combinatorial Designs, 11(3):100-112, 2003. [PDF] [POSTSCRIPT]
2002
  1. F. Havet and M-L. Yu. On (d,1)-total labelling of graphs. Rapport de recherche INRIA RR-4650, Projet MASCOTTE, Sophia Antipolis, November, 2002.
2001
  1. L. Gargano, P. Hell, and S. Pérennes. Coloring All Directed Paths in a Symmetric Tree, with an Application to Optical Networks. Journal of Graph Theory, 38(4):183--196, 2001.
2000
  1. J-C. Bermond, S. Marshall, and M.-L. Yu. Improved bounds for gossiping in mesh-bus networks. Journal Of Interconnection Networks, 1(1):1-19, 2000.
1998
  1. B. Beauquier, P. Hell, and S. Pérennes. Optimal wavelength-routed multicasting. Discrete Appl. Math., 84(1-3):15--20, 1998.
  2. S. Fujita, S. Pérennes, and J.G. Peters.. Neighbourhood Gossiping in Hypercubes. Parallel Processing Letters, 8:189--195, 1998.
1997
  1. L. Gargano, P. Hell, and S. Pérennes. Colouring paths in directed symmetric trees with applications to WDM routing. In Automata, languages and programming (Bologna, 1997), volume 1256 of Lecture Notes in Comput. Sci., pages 505--515. Springer, Berlin, 1997.
  2. J-C. Bermond, H. A. Harutyunyan, A. L. Liestman, and S. Pérennes. A Note on the Dimensionality of Modified Knödel Graphs. International Journal of Foundations of Computer Science, 8(2):109--116, 1997.
  3. B. Beauquier, J-C. Bermond, L. Gargano, P. Hell, S. Pérennes, and U. Vaccaro. Graph problems arising from wavelength--routing in all--optical networks. In WOCS97, April 1997.
1996
  1. J.G. Peters and M. Syska. Circuit-Switched Broadcasting in Torus Networks. IEEE Trans. on Parallel and Distributed Systems, 7(3):246--255, 1996.
1995
  1. J.-C. Bermond, P. Fraigniaud, and J.G. Peters. Antepenultimate broadcasting. Networks, 26(3):125--137, 1995.
1994
  1. M. Cosnard, A. Ferreira, and J. Peters, editors. Parallel and Distributed Computing -- Theory and Practice, volume 805 of Lecture Notes in Computer Science. Springer-Verlag, 1994.
1993
  1. J.-C. Bermond and P. Hell. On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs. Journal of Graph Theory, 17(5):647--655, 1993.
1992
  1. J.-C. Bermond, P. Hell, A.L. Liestman, and J.G. Peters. Broadcasting in bounded degree graphs. SIAM Journal on Disc. Math., 5(1):10--24, 1992.
  2. J.-C. Bermond, P. Hell, A.L. Liestman, and J.G. Peters. Sparse broadcast graphs. Disc. Appl. Math., 36:97--130, 1992.
  3. J-C. Bermond, P. Hell, and J-J. Quisquater. Construction of large packet radio networks. Parallel Processing Letters, 2(1):3-12, 1992.
1991
  1. A. Ferreira and J. Peters. Finding the smallest path in a rectilinear polygon on a hypercube multiprocessor. In Proceedings of the Third Canadian Conference on Computational Geometry -- CCCG'91, Vancouver (Ca), pages 162-165, 1991.
1990
  1. B. Alspach, J-C. Bermond, and D. Sotteau. Decomposition into cycles. I. Hamilton decompositions. In Cycles and rays (Montreal, PQ, 1987), volume 301 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 9--18. Kluwer Acad. Publ., Dordrecht, 1990.
  2. J-C. Bermond, K. Heinrich, and M-L. Yu. On resolvable mixed path designs. European J. Combin., 11(4):313--318, 1990.
  3. J.-C. Bermond, K. Heinrich, and M.-L. Yu. Existence of resolvable path designs. European J. Combin., 11(3):205--211, 1990.

3. Impact

4. Divers

II. BILAN 2008

Changements majeurs survenus concernant l'Equipe Associée (modifications des objectifs scientifiques, des chercheurs impliqués)

Rapport scientifique de l'année 2008

Le programme de travail initialement prévu fin 2007 pour l'année 2008 est disponible sur la page RESEAUXCOM2008 Nous avons en particulier obtenu les résultats suivants sur les 3 thématiques annoncées et démarré un nouveau sujet.
  1. Wireless Gathering Problem

    We have conducted joint research during the preceding years (see reports) on the Wireless Gathering Problem which consists of finding a schedule for data gathering in a wireless static network (call scheduling). Some of the motivation for this research comes from the problem (proposed by France Telecom) of designing efficient strategies to provide Internet access using wireless devices. Typically, several houses in a village wish to access a gateway (a satellite antenna) and have to use multi-hop wireless relay routing to do so. Similar problems arise in sensor networks where a base station has to collect data or distribute tasks for sensor nodes. In particular, we address the problem of gathering information into a specific node (or sink) of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most dT in the graph, but when doing so it generates interference that does not allow nodes at distance up to dI to listen to other transmissions. Time is synchronous and divided into time steps in each of which a round (set of non-interfering radio transmissions) is performed.

    • We have finished the case of toroidals grids for dT=1 with J. Peters. In particular we have used tools developed for the weighted routing problem by other members of Mascotte R. Klasing, N. Morales, and S. Perennes. Indeed, the weighted routing problem can be viewed as a relaxed version of the problem where we don't care about the scheduling of the calls but just want to insure that there are enough calls on each arc to route the messages using this arc. Using duality, we have obtained lower bounds for our problem that match the number of rounds obtained by the protocols. A final version will be submitted soon to a journal (BePe08). We have also obtained lower bounds for the case of hexagonal grids and are currently designing the protocols matching them.
    • We have completely solved the problem for trees for the case dT=dI with J. Yu (a specific case widely considered in the literature under the name of primary interference node or avoiding collisions). In fact we considered the analogous problem of personalized broadcasting where a source wants to send different messages to the nodes of the network (for example web pages). The results appeared in the proceedings of the conference AdHoc Now 08 (BeYu08), a conference where J-C Bermond presented a general invited talk covering the whole problem. Also the article BCY08 concerning the case of paths has been accepted for publication and will be published soon.

    We are currently using these ideas to obtain results for the weighted routing problem for trees with general dI where we expect to obtain polynomial algorithms.
    Finally we have started (internship of Dorian Mazauric Maz08 done both in Mascotte and S.F.U.) to design distributed algorithms for the call scheduling problems with probabilistic traffic (joint work with P. Nain, MAESTRO). This new topic will be emphasized in the future.

  2. How to retrieve a large file stored in a peer-to-peer overlay network ?

    The manuscript PePe08 was written during the visit of S. Pérennes to SFU in 2007.

    We have persued our research on the problem of streaming a large file (for example a video stream) stored in multiple locations in an overlay network.
    In this problem we considered a peer-to-peer overlay network in which a set of receivers want to stream a file (media object) which is replicated and stored in different server nodes. The file consists of a large number of frames that are partitioned into equal-sized chunks. Each receiver needs to receive all of the chunks approximately in the order that they need to be used. A chunk can arrive at a receiver before the time that it is needed and will be buffered. Our main goal 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 is used (played back or listened to) to avoid jitter during playback.

    We have proved that the general problem is NP-hard when the frames cannot be split. However, we have also established that certain cases of practical importance can be solved efficiently. In particular, we have shown that the steady state case, in which a streaming process must be maintained over a long period of time, can be solved efficiently. We have proved a few reults for the realistic scenario in which the peer-to-peer network is dynamic (peers can join and leave the network) using statistical methods.

  3. WDM DAG Networks

    As announced in the program last year, we have continued our research on DAG's (Directed Acyclic Graphs) without internal cycles. An internal cycle is an oriented cycle such that all of the vertices have at least one predecessor and one successor. We have found a simpler proof that if a DAG has no internal cycles, then the minimum number of colors (wavelengths) needed to color the paths associated with requests is equal to the load. In particular, we have studied more deeply the class of DAGs with a unique path between any pair of vertices (called UPP graphs). We have shown for this class of graphs that if a graph has an internal cycles, then there exists a family of dipaths with load 2 that needs as many wavelengths as we want. The proof uses a new concept of good labeling for the conflict graph and a recent probabilistic result on coloring of B. Reed. An article is in preparation with M. Cosnard who is supposed to finish it during his "free time" ...

  4. Online traffic grooming

    In a WDM network, routing a request consists of assigning it a route and a wavelength in the physical network. If each request uses at most 1/C of the bandwidth of the wavelength, we say that the grooming factor is C. This means that we can groom (group) at most C requests into the same wavelength on a given edge of the network. With this constraint, the objective is either to minimize the number of wavelengths (related to the transmission cost) or to minimize the number of Add Drop Multiplexers (i.e. ADMs) used in the network (related to the cost of the nodes).
    During their visit to Vancouver in August 2008, J-C. Bermond and D. Coudert began joint work with J. Peters on online traffic grooming on the path. In this context, we have to design the network according to a given routing algorithm (or for all possible routing algorithms) to satisfy any set of requests such that at most k requests start from and finish at a given a node. Our parameters are: the length N of the path, the grooming factor C, the number W of wavelengths to which a node is connected, and the neighborhood pattern (i.e. each node u is connected to nodes u+l1,u+l2,...,u+lr). We have already obtained significant results including upper and lower bounds and a manuscript is in preparation.

Bilan des échanges effectués en 2008

Nom
statut
provenance
destination
objet
durée (en semaines)
Coût (EA)
Coût (Mascotte)
Coût (SFU)
J-C. Bermond DR CNRS Sophia Antipolis SFU Visite 3   3000€ 1400€
D. Coudert CR INRIA Sophia Antipolis SFU Visite 5   2000€ 2000€
D. Mazauric Doctorant Sophia Antipolis SFU Stage 9 2000€ 2600€  
J. Peters Pr SFU Sophia Antipolis Visite 4 2000€   2000€
J. Yu A-Pr SFU Sophia Antipolis Visite 12 4000€   3000€
Totaux 33 8000€ 7600€ 8400€
Total des dépenses 24.000€
Ratio financement EA/Total 33%


III. PREVISIONS 2009

Programme de travail

We describe below what we intend to do in 2009 on the three topics of the proposal. We refer to Section I for the motivation and statements of the problems.

Programme d'échanges avec budget prévisionnel

1. Echanges
Les échanges prévus pour l'année 2009 ont vocation à effectuer du travail en commun:
 1. ESTIMATION DES DÉPENSES EN MISSIONS INRIA VERS LE PARTENAIRE Nombre de personnes Coût estimé
Chercheurs confirmés 3 12.000€
Post-doctorants    
Doctorants 1 4.000€

Stagiaires

   
Autre (précisez) :
   
Total 4 16.000€

 

 2. ESTIMATION DES DÉPENSES EN INVITATIONS DES PARTENAIRES Nombre de personnes Coût estimé
Chercheurs confirmés 3 14.000€
Post-doctorants
   
Doctorants    

Stagiaires

   
Autre (précisez) :
   
Total 3 14.000€

2. Cofinancement
Ces dernières années, l'équipe associée a bénéficiée, en plus du soutien de l'INRIA, d'autres soutien: ressources propres du projet MASCOTTE et grant NSERC des partenaires. La part de du programme Equipe Associée de l'INRIA varie entre 30% et 50% du budget total.

3. Demande budgétaire
Commentaires Montant
A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...) 30.000€
B. Cofinancements utilisés (financements autres que "Equipe Associée") 20.000€
Financement "Équipe Associée" demandé (A.-B.) (maximum 10 K€) 10.000€


© INRIA - mise à jour le 15/08/2008