Programme INRIA "Equipes Associées"

EQUIPE ASSOCIEE	RESEAUXCOM
sélectionnée en	2004

Projet INRIA : MASCOTTE, commun CNRS-I3S-INRIA	Organisme étranger partenaire : Network Modelling Group, Simon Fraser University
Unité de recherche INRIA : Sophia Antipolis Thème INRIA : Com B	Pays : Canada

 

	Coordinateur français	Coordinateur étranger
Nom, prénom	Coudert, David	Peters, Joseph
Grade/statut	Chargé de recherches	Professeur
Organisme d'appartenance (précisez le département et/ou le laboratoire)	INRIA	Simon Fraser University
Adresse postale	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 79 81	+1 604 291 3780
Télécopie	+33 (0)4 92 38 79 71	+1 604 291 3045
Courriel	David.Coudert@sophia.inria.fr	peters@cs.sfu.ca

Mots-clés : Optimisation combinatoire, algorithmique, réseaux de télécommunications

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 (France Telecom, Alcatel, ...). Nous souhaitons principalement nous concentrer sur deux types de réseaux, les réseaux dorsaux et les réseaux sans fil. Cependant les problématiques soulevées par ceux-ci se retrouvent généralement pour d'autres types de réseaux.

Présentation de l'Equipe Associée

1. Présentation du coordinateur étranger

Joe Peters (né en 1951) a eu son PhD en 1984 à l'université de Toronto (Informatique). Il est en poste à S.F.U. (Simon Fraser University) à la School of Computing Science à Vancouver depuis 1984 (Full professor depuis 1996). Il travaille dans le domaine de l'algorithmique des télécommunications (antérieurement sur l'algorithmique parallèle et distribuée). Il a écrit une trentaine d'articles sur ce sujet dans les dix dernières années et dirigé une quinzaine de thèses. Il a aussi un grand nombre de responsabilités au sein de S.F.U. Il a été membre de plusieurs comités de programme. Il a effectué de nombreux séjours en France (années sabbatiques à Sophia-Antipolis et Grenoble,visites à Bordeaux et Orsay); il a été rapporteur de plusieurs thèses et membre du comité d'évaluation du programme 1A de l'INRIA en 2000.

2. Historique de la collaboration

• 2.1. entre les équipes :

  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, A. Ferreira a effectué plusieurs visites de plus d'un mois, M. Syska y a passé un mois en 1992 et en 1996 ainsi qu'un séjour post-doctoral de janvier à aout 1993, S. Pérennes y a passé 4 mois en 1998, R. Klasing y a passé un mois en 1999 et y passera le mois de février 2004 et F. Havet y a passé un mois en 2001. Symétriquement J. Peters a passé son année sabbatique 90-91 chez nous, 1 mois en 1998, 2 mois en 2003 et vient 4 mois dès avril 2004. 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, 3 mois en 2003 et vient 3 mois en 2004. 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 a dirigé une thèse) 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 plus de 20 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. Plusieurs chercheurs de MASCOTTE (en particulier ceux recrutés récemment) souhaitent aller régulièrement à Vancouver et de manière réciproque plusieurs chercheurs canadiens souhaitent profiter d'années sabbatiques pour venir ici.

  
  
  

  Articles en commun 2003 2002 2001 2000 1998 1997 1996 1995 1994 1993 1992 1991 1990 2003 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. J-C. Bermond, D. Coudert, and M-L.Yu. On DRC-covering of $K_n$ by Cycles. Journal of Combinatorial Designs, 11:100-112, 2003. 2002 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 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 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 B. Beauquier, P. Hell, and S. Pérennes. Optimal wavelength-routed multicasting. Discrete Appl. Math., 84(1-3):15--20, 1998. S. Fujita, S. Pérennes, and J.G. Peters.. Neighbourhood Gossiping in Hypercubes. Parallel Processing Letters, 8:189--195, 1998. 1997 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. J-C. Bermond, H. A. Harutyunyan, A. L. Liestman, and S. Pérennes. A Note on the Dimensionality of Modified Kno"del Graphs. International Journal of Foundations of Computer Science, 8(2):109--116, 1997. 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 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 J.-C. Bermond, P. Fraigniaud, and J.G. Peters. Antepenultimate broadcasting. Networks, 26(3):125--137, 1995. 1994 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 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 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. J.-C. Bermond, P. Hell, A.L. Liestman, and J.G. Peters. Sparse broadcast graphs. Disc. Appl. Math., 36:97--130, 1992. J-C. Bermond, P. Hell, and J-J. Quisquater. Construction of large packet radio networks. Parallel Processing Letters, 2(1):3-12, 1992. 1991 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 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. J-C. Bermond, K. Heinrich, and M-L. Yu. On resolvable mixed path designs. European J. Combin., 11(4):313--318, 1990. J.-C. Bermond, K. Heinrich, and M.-L. Yu. Existence of resolvable path designs. European J. Combin., 11(3):205--211, 1990.

  
  
  
• 2.2. entre l'INRIA et l'organisme partenaire :
  
  

3. Impact :