SAMOVAR UMR 5157

  • Accueil
  • Accueil
  • Accueil
  • Accueil

CNRS

Rechercher




Accueil > Équipes > METHODES > Bilan scientifique 2008-2013 > Axes de recherche

Evaluation de performances dans les réseaux

  • Enseignants-chercheurs : Tülin ATMACA, Monique BECKER, Walid BEN-AMEUR, Hind CASTEL-TALEB, Tijani CHAHED, Michel MAROT.
    • Thèses soutenues : 19
    • Thèses en cours : 10

Evaluation de performances par méthodes mathématiques

Vue la complexité des réseaux et des services d’aujourd’hui (en terme de nombre de noeuds, d’événements : pannes/réparations, arrivées/services), il devient difficile d’effectuer une analyse quantitative complète de ces systèmes. Cette complexité peut être réduite grâce aux méthodes de bornes stochastiques pour calculer des mesures de performance bornantes à partir de systèmes plus simples à analyser.

Un algorithme d’agrégation a été défini. L’approche proposée par les méthodes de bornes a l’avantage de borner aussi bien les distributions de probabilité stationnaires que transitoires. Le point fort des agrégations bornantes est de proposer des systèmes dont la taille dépend d’un paramètre qu’on peut ajuster pour avoir un compromis entre qualité et complexité de calcul. Ce travail a été réalisé dans le cadre du projet ANR Checkbound et a donné lieu à un certain nombre de publications, dans des conférences internationales, et des revues dont Theoretical Computer Science [648] et The Computer Journal [348].

Un travail a été mené pour utiliser les méthodes de bornes stochastiques pour analyser des modèles imparfaitement connus. Un exemple pratique est donné par le trafic dans un réseau. La définition d’un modèle représentant le trafic d’une manière fidèle est extrêmement difficile surtout dans le cadre de trafic variable tel que le trafic autosimilaire.
Des histogrammes bornants et agrégés permettant d’analyser les réseaux de communications avec des profils de trafic généraux ont été proposés. Des résultats ont été obtenus sur des mesures de performance (délais, probabilité de perte), à partir de matrices de trafics réels. Ce travail se déroule dans le cadre du projet MARINA de Digiteo.

Un autre aspect de incertitude du trafic est pris en compte à travers le paradigme d’optimisation robuste. La matrice de trafic varie dans un ensemble d’incertitude (un polytope par exemple). L’équipe qui est à l’origine de ce modèle d’incertitude, continue ses travaux sur le problème du routage robuste. Plusieurs stratégies allant du statique vers le dynamique en passant par l’affine ou le multipolaire ont été proposées [363, 501, 658, 330].

L’équipe s’est également intéressée aux réseaux OFDMA, et notamment au concept de modulation hiérarchique qui est une manière de superposer deux signaux provenant de deux usagers sur une même sous-porteuse, et ce en utilisant des constellations différentes pour chacun de ces deux usagers. Dans notre travail, nous avons modélisé le système au niveau flux, via une Chaîne de Markov à Temps Continu, dont les états représentent le nombre d’usagers présents dans le réseau et qui varie de manière dynamique avec les arrivées et les départs des usagers. Nous avons quantifié le gain en performance en termes de plusieurs métriques telles que les temps moyens de transfert de fichiers ainsi que la probabilité de blocage. Nous avons aussi démontré qu’avec la modulation hiérarchique, des mécanismes d’ordonnancement simples, de type round robin, génèrent des gains plus importants que les mécanismes opportunistes sophistiqués de type Propotional Fair. Enfin, nous avons étudié la modulation hiérarchique dans un réseau OFDMA avec relais et proposé des mécanismes d’ordonnancement joint entre modulation hiérarchique et relayage, coopératif et non coopératif, permettant des gains significatifs par rapport à un mécanisme de relayage simple. Ces travaux ont fait l’object de plusieurs articles de revue [345, 344, 360]. Cette recherche s’inscrit dans le cadre du projet ANR WINEM.

Une alternative aux réseaux OFDMA serait l’utilisation de la technique SC-FDMA. Nous avons étudié le problème d’affectation des canaux dans les réseaux SC-FDMA en intégrant la contrainte de contiguité des canaux. Des algorithmes exacts, des heuristiques avec garantie de performances ainsi que des résultats d’inapproximabilité en temps polynomial ont été établis [332]. Ce travail s’inscrit dans le cadre du projet WISDOM de Digiteo.

Nous avons aussi travaillé sur le transport fiable dans les réseaux tolérants aux délais (DTN) où une solutionclassique provenant des réseaux filaires, tel que TCP, ne pourrait pas fonctionner compte tenu des délais trop importants introduits par ce type de réseaux. Nous avons donc proposé un nouvel algorithme basé sur l’utilisation du codage réseau et des acquittements afin de garantir la fiabilité dans le transport des données, nous l’avons modélisé en utilisant une approche de modèle fluide, et nous l’avons optimisé afin de minimiser le temps moyen de transfert de bout-en-bout entre source et destination [450]. Nous avons aussi étudié des solutions pour l’estimation du niveau de propagation dans ce type de réseaux basée sur le déploiement d’un certain nombre d’observateurs, avec une approche basée sur la diffusion pour modéliser la dynamique du système et les mesures ainsi que l’application d’un filtre de Kalman. Ces solutions permettent de mieux contrôler le routage et la dépense d’énergie [428]. Un financement de l’IMT a aidé à la réalisation de ce travail, via le recrutement d’un post-doc.

L’équipe a également démarré un travail de recherche autour de la question de transport du trafic de télévision en direct dans le contexte de systèmes hybrides, composés de réseaux LTE et DVB (Digital Video Broadcast). Ce travail a déjà donné lieu à un article dans IEEE Transactions on Wireless Communications [321].

L’équipe mène également des travaux sur la structure topologique des réseaux. Des recherches effectuées en collaboration avec l’équipe R3S portent sur l’amélioration de la dissémination dans les réseaux sans-fils. Des modèles de type "Small World" et des modèles bio-inspirés se sont révélés riches. Ils ont permis de choisir les noeuds du réseau pour lesquels on applique le "beam-forming" qui permet à des liens nouveaux de relier des nœuds éloignés et de relier ainsi deux clusters qui ne l’étaient pas. Ce travail a été publié dans [353] The Computer Journal . Actuellement l’équipe étudie des modèles de type épidémiologiques et résout les systèmes d’équations différentielles qui permettant de modifier la structure du réseau afin d’améliorer la dissémination. Une technique d’inondation directionnelle (utilisant le "beam-forming") a également été étudiée dans le cadre des réseaux véhiculaires. Une approche géométrique pour caractériser l’ensemble des véhicules qui participent à la transmission a été proposée. Les probabilités d’atteindre la destination sont également calculées. Ce travail se fait en collaboration avec l’équipe R3S [425, 576, 575, 409].

Enfin, l’équipe a porté un effort sur les problèmes de réduction d’énergie dans les réseaux mobiles en proposant des nouvelles techniques pour la gestion du réveil des stations de base qui sont responsables à elles seules d’environ 80% de la facture énergétique dans les réseaux mobiles. Notre travail a porté spécifiquement sur la proposition, la modélisation via les Markov Decision Processes (MDPs), et l’analyse d’algorithmes de contrôle en ligne et hors ligne dans les réseaux cellulaires [405] et dans les HetNets, composés de stations de base macro et de petites cellules : Femto et Pico [352]. Cet effort de recherche s’est traduit par plusieurs publications dont [352] dans IEEE Journal on Selected Areas in Communications .

Évaluation de performances par simulation et mesures

Une activité importante porte sur les performances dans les réseaux optiques d’accès (du type PON) et métroaccès (des anneaux optiques). Nos études se focalisent notamment sur les architectures des noeuds optiques, les mécanismes d’accès multiples aux ressources partagées (dans PON et anneaux optiques) ainsi que la gestion de la qualité de service et des tampons. Plusieurs algorithmes dynamiques d’allocation de bande passante permettant d’améliorer les performances ont été proposés pour le réseau EPON. L’algorithme eDBA utilise le temps de calcul pour transmettre le trafic excédant, tandis que hcDBA suggère l’utilisation de la moitié du cycle de transmission s’il y a du trafic en excès dans les tampons [519, 617, 601]. Le problème de synchronisation dans l’interconnexion des anneaux slottés des réseaux métropolitains a également été étudié sous différents mécanismes de remplissage de paquets optiques [616]. Nous avons aussi modélisé un réseau métropolitain slotté par la chaîne de Markov discrète (EDTMC) afin d’analyser le délai d’attente et la distribution des paquets dans les tampons [488]. Ces travaux se sont déroulés dans le cadre du projet ANR ECOFRAME et du projet CARRIOCAS du pôle Systematic. Un algorithme d’agrégation de paquets IP a été proposé afin d’adapter le trafic à un réseau métropolitain optique [370, 656]. Ce mécanisme est conçu pour supporter directement le trafic IP dans les réseaux WDM tout en respectant les différents critères de qualité de service. Ce travail a été réalisé dans le cadre du projet 100 GRIA du pôle Systematic.

L’essor des réseaux sans fil et mobiles pose plusieurs défis scientifiques notamment au niveau de l’ingénierie du trafic et l’évaluation des performances de ces réseaux. L’équipe a été active dans ce domaine.

Un travail a été réalisé pour évaluer les performances des réseaux VANETs dans le cas des communications véhiculaires sans infrastructure. Une approche MAC d’allocation multicanal opportuniste dans un contexte sans infrastructure a été proposée [574]. Cette approche est conçue pour des applications de services de données (non urgentes), tout en assurant la transmission des messages de sécurité routière et des paquets de contrôle. Une technique visant à minimiser les collisions des émetteurs tout en évitant la contention de début d’intervalle, en particulier dans un contexte de densité élevée de véhicules a alors été développée [677]. Ce travail a été soutenu par une bourse EIFFEL.

L’une des thématiques de recherche de l’équipe porte sur la gestion de ressources dans les réseaux satellites. Un algorithme multiniveaux pour le transport de la voix sur IP dans ces réseaux a été proposé [505]. Cet algorithme fait intervenir la couche transport et la couche MAC. Son intégration dans l’architecture puis ses performances sont étudiées, et particulièrement son comportement en présence de trafic concurrent. Un algorithme multiniveaux a également été proposé pour l’affectation de la bande passante sur un lien par lequel transitent à la fois du trafic multimédia et du trafic de données [699]. Ces travaux ont été soutenus par un contrat bilatéral avec Astrium.

Les réseaux de capteurs ont également fait l’objet de plusieurs investigations. Un nouvel algorithme, l’algorithme "hybrid LQI", est proposé pour le routage dans un contexte de liens asymétriques [516, 472]. Ses performances sont testées sur une plate-forme réelle. On s’est aussi intéressé au comportement des algorithmes de formation de clusters. Une autre solution de mise en clusters a été proposée pour s’adapter aux performances limitées des nœuds et pour une étendue géographique raisonnable du réseau [615, 661]. Ses travaux ont été poursuivis et ont abouti à la proposition d’un algorithme de routage à répartition de charge avec des mécanismes de réduction des clusters singletons [389]. Ses travaux se sont déroulés dans la cadre du projet ANR CAPTEURS.