Proposition de stage de DEA
Titre: Routage à convergence par circuits couvrants
Contexte industriel:
Ce stage s'inscrit dans le cadre d'un projet industriel dont l'équipe
fait partie. Ce projet Réseau Optiue Multiservice (ROM) propose
l'étude d'un routeur haut débit. Elle envisage d'utiliser
en partie la technique de routage par eulériens pour obtenir certaines
garanties de performance. Les principaux partenaires sont Alcatel, France
Telecom R&D (CNET Lannion), l'Institit National des Telecommunications.
D'autre part, un groupe de chercheurs de la région parisienne travaille
dans le même domaine (PRISM à Versailles et LAMI à
Evry).
Contexte scientifique:
Quand on utilise un réseau haut débit, les mécanismes
de routage au niveau d'un noeud doivent être très simples.
C'est pourquoi le routage à déflexion a été
étudié. Ce routage consiste à ne pas stocker les message
passant par un noeud en attendant d'avoir la bonne sortie, mais à
les renvoyer dans une autre direction, laissant le soin aux autres noeuds
du réseau de router correctement le message. Des études
montrent que ce système est intéressant quand le réseau
n'est pas trop chargé, lorsque c'est le cas, ce routage peut ne
pas fonctionner: des messages peuvent attendre éternellement avant
d'arriver (live-lock). Afin d'améliorer ce point, le routage par
circuits eulériens garantit que tout message émis arrivera
dans un délai borné. Malheureusement, cette technique possède
une borne importante.
But:
Nous aimerions étudier l'apport du routage par circuit eulérien
dans le cas d'une décomposition du réseau considéré
en cycles couvrants (passant par tous les sommets). En effet la technique
utilisant un seul circuit eulérien montre que la contrainte majeure
est la distance entre deux occurrences du même noeud dans le circuit,
et cette valeur peut être très importante dans le cas de graphes
simples comme la grille. Elle peut même atteindre le nombre
d'arêtes du réseau.
Sujet:
Il s'agit dans un premier temps de faire le point sur les techniques de
routage par convergence. Puis à partir d'exemples de
réseaux simples expérimenter des méthodes on-line
ou off-line de décomposition du réseau en plusieurs circuits.
Il sera nécessaire d'évaluer (soit de manière théorique,
soit de manière expériementale) les systèmes obtenus
en terme de performance, et les comparer aux méthodes existantes.
Bibliographie:
[Barth1998] D. Barth "Une approche algorithmique du routage dans les
réseaux de télécommunication" Mémoire d'Habilitation. LRI 1998.