MASCOTTE no longer exists => visit the new project-team
Internship MASCOTTENouvelles Problématiques de routage dans les réseaux
by Julio Araujo
| | | | Advisor | Fré́dé́ric Giroire (CR2 CNRS) | | School | Universidade Federal do Ceará | | Degree | Master | | Period | 01/03/09-04/04/09 |
Dans les réseaux actuels la fonctionnalité de routage devient de plus en plus délicate à assurer. Divers
facteurs induisent cette difficulté : la taille, la dynamique, l’hétérogénéité. La problématique traditionnelle du
routage a été formalisée au cours des décennies 80-90 par la notion de tables de routage. Une table de routage
est une fonction associant à une en-tête de message un port/canal de sortie. Cette fonction est souvent stockée
de manière exhaustive sous forme de table, ce qui explique l’appellation utilisée. Le routage des messages
s’effectue alors en appliquant à chaque routeur la fonction de routage, ceci d´etermine un chemin que suit la
donnée. Dans ce cadre les chemins sont pré calculés (même lorsque les tables sont dynamiques). Par ailleurs
le flot de données et le flot de contrôle (déterminant la route à suivre) sont confondus. Or il est souhaitable
de modéliser des protocoles où le flot de contrôle (dont le but est de maintenir et de calculer les routes) et
le flot de données sont séparés. Il est aussi crucial de bien modéliser le fait que les routes soient calculées à
la demande. En effet si les réseaux actuels et à venir sont de très grande taille, la densité des routes utilisées
(i.e autrement dit la probabilité qu’un noeud communique avec un autre) tend vers zéro. Tout mécanisme
visant à maintenir l’ensemble des routes (comme un Dijkstra dynamique le ferait) est donc voué à l’échec. Le
calcul de route est donc un processus dynamique : la route utilisée peut et doit changer, en particulier elle
peut, partant d’une solution initiale médiocre, s’améliorer au fils du temps. Ceci peut avoir un impact très
important car si une communication courte (chargement d’une page web) nécessite la détermination rapide
d’une route médiocre, pour une communication longue et intense l’optimisation graduelle de la route utilisée
est souhaitable. Enfin le mécanisme de routage n’est plus réductible à une quantité de mémoire utilisée
dans les routeurs, c’est au contraire un protocole à part entière qui utilise les ressources du réseaux (bande
passante, mémoire, cpu). La définition d’un tel cadre formel est donc importante. Ce cadre devra permettre
d’étudier des caractéristiques des protocoles plus complexes que celles étudiées dans le cadre traditionnel
des tables de routage (principalement : la taille des tables, le stretch/l’élongation qui détermine la longueur
de la route par rapport au plus court chemin, la taille des en-têtes). Les critère de qualités principaux nous
semblent les suivants : – Latence : temps moyen nécessaire afin d’établir une première route, quantité de
ressources utilisées par le protocole de routage. – Élongation : longueur de la route par rapport au plus court
chemin. – Stationnarité : longueur de la route en phase stationnaire, quantité de ressources utilisées par le
processus de contrôle pour me maintient de route en phase stationnaire. Le premier but du stage est de
proposer un tel cadre en se basant sur les nombreux travaux existant. Ceci fait, la seconde partie du travail
consistera à utiliser ce formalisme afin d’étudier des protocoles existants et éventuellement d’en proposer
d’autres.
Les objectifs de ce stage : ´Etudier ces th´ematiques du routage dynamique dans les r´eseaux en se pla¸cant
dans le cas particulier de la grille 'a trous qui mod´elise certains r´eseaux sans-fil. Il faudra en particulier
trouver des algorithmes 'a faible latence, ´elongation et stationnarit´e.
List of interships | 
