Direction des Relations Européennes et Internationales (DREI)

Programme INRIA "Equipes Associées"

 

I. DEFINITION

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

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 (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

3. Impact :

4. Divers : toute autre information que vous jugerez utile d'ajouter.



II. BILAN 2005

 

Rapport scientifique pour l'année 2005

Nous avons poursuivi nos travaux sur les problèmes de réseaux dorsaux et sur les réseaux radio.

Nous avons obtenu de nouveaux résultats sur le problème du groupage de trafic dans les réseaux dorsaux, en particulier dans le cas où le réseau est un chemin orienté BBC05. Nous nous sommes également intéressés au problème de la construction incrémentale de séquences de graphes KLPT05.
Enfin, l'article sur la protection par cycles pour le cas où le graphe des demandes est le graphe complet et le réseau physique un tore a été accepté pour publication dans Networks BeYu06.

Concernant les réseaux radio, nous avons poursuivi les travaux initiés dans BCY05 sur le problème de "gathering" de messages répartis dans les sommets du chemin vers un sommet déterminé sous contraintes que:

  1. Un sommet recoit une communication si l'émetteur est à une distance inférieure à d et qu'il n'y a pas d'interférences
  2. Une transmission interfère avec la réception d'une autre si l'émetteur de la première est à une distance inférieure à b du récepteur de la deuxième.
Dans ce contexte, on cherche à minimiser le nombre d'étapes d'un tel protocole (ou à utiliser au mieux la division du spectre radio). Nous avons résolu le case de la grille BePe05, montré la complexité du problème dans le cas de trafic stationnaire KMP04 et BGK+06.


  1. J-C. Bermond, R. Corrêa, and J. Yu. Gathering in Radio networks, the one-dimensionnal case.
    Note: Manuscript, 2005.

  2. J-C. Bermond, L. Braud, and D. Coudert. Traffic Grooming on the Path. In 12th International Colloquium on Structural Information and Communication Complexity -- SIROCCO, Le Mont Saint-Michel, France, pages 34-48, May 24-26 2005. LNCS 3499. [PDF]

  3. J-C. Bermond and J. Peters. Efficient Gathering in Radio Grids with Interference.. In ALGOTEL, pages 103-106, 2005. [PDF]

  4. J.-C. Bermond and M-L. Yu. Vertex disjoint routings of cycles over tori. Networks, to appear, 2006. [POSTSCRIPT]

  5. J-C. Bermond, J. Galtier, R. Klasing, N. Morales, and S. Perennes. Hardness and approximation of Gathering in static radio networks. In submitted to FAWN06, Pisa,Italy, 2006. [POSTSCRIPT]

  6. 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.
    Note: Submitted to Algorithmic Operations Research. [PDF] [POSTSCRIPT]

  7. R. Klasing, N. Morales, and S. Perennes. On the Complexity of Bandwidth Allocation in Radio Networks with Steady Traffic Demands. Technical report, INRIA Research Report RR-5432 and I3S Research Report I3S/RR-2004-40-FR, December 2004. [PDF] [POSTSCRIPT]

 

Rapport financier 2005

1. Dépenses EA (effectuées sur les crédits de l'équipe associée)
 
Budget EA alloué
Montant dépensé
Accueil   11000€
Missions   5000€
Total
(a) 16000€ (b) 16000€
Taux d'utilisation des crédits EA alloués (b/a %)
100%

 

2. Dépenses externes (soutenues par des financements hors EA)
 
Budget alloué
Montant dépensé
Nom de l'organisme 1 (*): MASCOTTE
Accueil   4000€
Missions   3000€
Total
  7000€
Nom de l'organisme 2 (*) : SFU
Accueil   6000€
Missions    
Total
  6000€

Total des financements externes

alloués : (c)

dépensés : 13000€

(*) Ajouter ou supprimer des lignes au tableau ci-dessus de façon à faire figurer tous les organismes ayant contribué au financement de l'équipe associée

Total des financements EA et externes

alloués : (d)

dépensés : 29000€


Taux de co-financement (c /d %)

56%


Bilan des échanges effectués en 2005


1. Seniors

Nom
statut (1)
provenance
destination
objet (2)
durée (en semaines)
Coût (EA)
Coût (externe)
R. Klasing CR Sophia Antipolis SFU Visite 2 3000€ (Mascotte)
S. Perennes CR Sophia Antipolis SFU Visite 4 5000€
P. Hell Pr SFU Sophia Antipolis Visite 2 2000€ (SFU)
J. Peters Pr SFU Sophia Antipolis Visite 21 7000€ 4000€ (Mascotte)
3000€ (SFU)
J. Yu A-Pr SFU Sophia Antipolis Visite 13 4000€ 1000€ (SFU)

Total des durées en semaines
 42
(1) DR / CR / professeur
(2) colloque, thèse, stage, visite....

2. Juniors

(1) post-doc / doctorant / stagiaire
(2) colloque, thèse, stage, visite....

 



III. PREVISIONS 2006

Programme de travail

 

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.

Le dimensionnement d'un réseau dorsal consiste à définir des routes pour chaque flux à transporter puis affecter les ressources pour réaliser ces routes. La définition des routes est contrainte par des hypothèses qui sont liées soit à la technologie ou au protocole, soit à des paramètres de qualité de service imposés.

Nous détaillons ci-dessous des problèmes issus des réseaux dorsaux que nous comptons étudier.

  1. Routage par longueurs d'onde

    Voir [GuTa00] [GuPe99] [GuPe03a] [CFK+01a] [BGP+00] [BPT99] [Bea00] [Bea99] [HaZe02] [BBGH+97] [CoRi02] [GHP01] [BHP98] [BCL+03]

    Lorsqu'on effectue un routage par longueurs d'ondes dans un réseau WDM, un chemin dans le réseau et une longueur d'onde doivent être attribués à chaque requête de communication, de manière à ce que deux chemins partageant un même lien aient des longueurs d'onde différentes. A routage fixé, cela peut se modéliser par des problèmes de coloration de graphes, éventuellement avec contraintes. Si l'on cherche à déterminer le routage en même temps que les longueurs d'onde, on peut utiliser une modélisation en multiflots.

  2. Groupage

    Voir [HPS02] [BPS02] [BDPS03] [BCY03] [BeCe03] [BeCo03] [BCM03]

    Le groupage est la technique qui consiste à agréger des flux de trafic élémentaire pour les transporter ensemble sur un même canal optique. Cela permet à la fois une économie d'échelle et une simplification de la gestion des réseaux. C'est le principal problème étudié sur les anneaux SONET/WDM. Des résultats optimaux pour certaines tailles de groupage et d'anneaux ont été obtenus en utilisant des résultats connus de la théorie des design.

  3. Plongement de réseaux

    Voir [StVr00] [LLSS01a] [LLPS+01b] [HPS96] [GHSV] [BMPP03] [Cho02]

    Etant donnée un réseau physique, on cherche un réseau logique qui une fois plongé sur le réseau physique optimise certains paramètres (nombre de sauts, charge, ...).

    Ce problème s'applique en particulier pour les réseaux ATM mais concerne plus généralement tous les empilements de réseaux quelconques. L'instance de communication est réalisée sur le réseau virtuel. Une mesure de la qualité de service est la longueur du chemin associé à une requête et en particulier le diamètre du réseau virtuel.

    Une autre application est l'utilisation de ``spanners''. Le spanner d'un réseau G est un réseau ayant les mêmes noeuds dans lequel la distance entre deux noeuds approxime celle dans G. Un de leurs intérêts tient au fait que si un réseau est coûteux, lui substituer un spanner, léger et donc beaucoup moins cher, n'augmente que légèrement les coûts de communication. Nous sommes intéressés par l'existence plusieurs spanners liens-disjoints de certains graphes. Cela correspond à partitionner un système distribué pour plusieurs utilisateurs ou processus différents sans diminuer la performance de chacun des réseaux virtuels.

  4. Sécurisation

    Voir [GuPe99] [MaSt99] [BDD02] [BCCT01a] [Cou01b] [BCY03]

    Dans le cas où une panne (de noeuds ou de liens) intervient dans un réseau, il est nécessaire de pouvoir assurer la continuité du trafic. Ceci se fait par un re-routage du trafic affecté par la panne, soit en utilisant des ressources prédéterminées et dédiées (off-line), soit en utilisant les ressources disponibles au moment de la panne (on-line).

    Des mécanismes de sécurisations apparaissent dans toutes les couches des réseaux (couche paquet, couche physique,..) et plusieurs mécanismes peuvent être utilisés simultanément, parfois de manière redondante. Aussi il est important de mettre en place un plan de commande unifié permettant d'optimiser le coût des ressources de sécurisation. Nous allons aborder ce problème dans le cadre de l'ACI-SI PRESTO, en collaboration avec l'ENST Paris et le LIMOS de Clermont-Ferrand, et l'expérience de nos collègues canadiens se révèlera utile.

  5. Réseaux sans fil

    Voir [Hav01] [GvPe01] [GaOl01] [FGPR01] [FeKr01] [HaYu02] [HaZe02] [CHRV03]

    Les réseaux sans fil (en particulier Ad-Hoc) sont des réseaux de communications composés uniquement d'entités mobiles sans infrastructure. Le rayon de transmission limité et la mobilité continue de ces entités rend le routage dans les réseaux Ad-Hoc beaucoup plus compliqué que dans les réseaux filaires. Avec l'arrivée massive sur le marché d'équipements munis d'une technologie sans fil (Bluetooth, carte 802.11), les problèmes de routage et d'utilisation de la bande passante dans les réseaux Ad-Hoc sont devenus des enjeux majeurs. L'expertise commune en réseaux satellitaires sera utile.

    Une approche pour le développement d'algorithmes de routage efficaces dans les réseaux Ad-Hoc consiste à utiliser le ``clustering'' de graphes afin de simplifier le routage. Cela nécessite la recherche d'un ensemble dominant dans un réseau. Un problème important est alors de pouvoir maintenir un tel ensemble lorsque la topologie change.

    D'autres problèmes seront aussi considérés concernant l'allocation de fréquences analogues aux cas des réseaux radio de téléphonie cellulaire (problèmes utilisant des outils théoriques semblables à ceux utilisés par l'affectation de longueur d'onde dans les réseau WDM).



Budget prévisionnel 2006

1. Co-financement

ESTIMATION PROSPECTIVE DES CO-FINANCEMENTS
Organisme
Montant
MASCOTTE 15000€
SFU 10000€
Total
25000€

2. Echanges

ESTIMATION DES DEPENSES
Montant
 
Nombre
Accueil
Missions
Total
Chercheurs confirmés 8 20000€ 20000€ 40000€
Post-doctorants
       
Doctorants        

Stagiaires

       
Autre (précisez) :
       
Total
8 20000€ 20000€ 40000€
   
- total des co-financements
25000€
  Financement "Equipe Associée" demandé 15000€


Remarques ou observations :

 

 

 

© INRIA - mise à jour le 20/10/2005