Télécharger le fichier original (Mémoire de fin d’études)
Routage adaptif
Le routage adaptif, contrairement au routage fixe, prend en compte l’évolution du réseau et s’adapte à celle-ci en utilisant une table de routage qui peut être rafraîchie périodiquement ou quand le besoin se fait sentir. C’est un type de routage qui essaie d’avoir une vue ponctuelle du réseau et vise une optimisation à court terme. Dans cette partie, nous ne considérons que le routage réparti : chaque routeur est impliqué dans l’application de l’algorithme de routage et calcule sa table de routage. Il y a ensuite échange d’informations entre routeurs. On s’appliquera alors à l’établissement d’un chemin le plus court. Plus court en terme de métrique. Cette métrique va beaucoup attirer notre attention car elle permet de mesurer en quelque sorte les disponibilités des constituants du réseau et de refléter ainsi l’état du réseau. Dans plusieurs protocoles de routage, on utilise une métrique composée pour mieux choisir la route qui peut être optimale selon plusieurs critères. Nous donnons maintenant un ensemble de critères pouvant être utilisés dans le calcul d’une métrique.
– Nombre de sauts : nombre de routeurs sur le chemin de la source à la destination.
– Bande passante : capacité d’une liaison.
– Charge : quantité d’activité au sein d’une composante réseau.
– Délai : temps nécessaire pour l’acheminent d’un paquet, de la source à la destination.
– Fiabilité : taux d’erreurs sur une liaison.
Cette liste n’est pas exhaustive mais elle donne une idée claire sur les critères de performance d’un réseau de transport de données. L’algorithme de routage génère donc une métrique basée sur ces critères. Le but de cette étude est de revoir les métriques dynamiques, c’est-à-dire celles qui changent au cours du temps et qui recèlent des aspects aléatoires. Les autres qu’on peut qualifier de statiques (nombre de sauts, bande passante) entraînent des comportements déterministes dans le routage. Les critères dynamiques, par exemple la charge ou le délai, vont justifier la nature stochastique des décisions de routage. Toutefois, on remarquera que le routage adaptatif se base beaucoup plus sur les changements de topologie (suppression ou ajout d’un nœud, modifications de la capacité d’une composante…) que sur l’état du trafic en tant que tel (charge, délai…). Nous allons voir les deux modes principaux de routage ; le routage à vecteur de distance et le routage à état de liens. Le but n’est pas de montrer comment fonctionnent ces protocoles, mais plutôt de voir comment intervient la métrique dans la détermination du plus court chemin.
Routage à vecteur de distance
Dans le routage à vecteur de distance, chaque routeur connaît les distances vers les autres routeurs adjacents et distribue ses meilleurs chemins à ces mêmes routeurs. Quand un routeur reçoit une information nouvelle, il met à jour sa table en modifiant son vecteur, si la route annoncée est meilleure, sinon il ignore cette information. Etudions maintenant la métrique d’un protocole de routage de type vecteur de distance. Nous nous intéressons pour cela au protocole propriétaire IGRP (Interior Gateway Routing Protocol) qui a une métrique composite constituée du délai, de la bande passante, de la MTU (Maximum Transmission Unit, qui n’est pas utilisée directement dans le calcul de la métrique), de la charge et de la fiabilité. Chaque caractéristique est pondérée d’un facteur. Ceci crée une vaste gamme pour le choix d’une route ; l’administrateur peut donc privilégier un critère par rapport à un autre en jouant avec les poids. Le délai et la charge vont le plus attirer notre attention, car ils constituent les critères qui peuvent changés au cours du temps. Cependant le protocole IGRP utilise un délai moyen fixe pour chaque technologie de transmission. Ce qui peut placer le délai dans la catégorie des critères statiques. Il faudrait plutôt, en fonction des caractéristiques réseaux, essayer d’avoir une valeur adaptée au contexte. La démarche suggérée consiste à calculer une approximation du délai de transfert sur chaque arc en se basant sur les résultats obtenus dans les files d’attente, puis à additionner les délais sur le chemin considéré. Aussi, faudrait-il avoir à notre disponibilité ces informations sur le trafic réseau ; la quantité moyenne (paramètre d’une loi aléatoire) de données présentes sur l’arc et la capacité de chaque arc pour calculer le délai moyen sur cet arc (annexe 1 : (4)). Le problème à notre niveau est de savoir si cette information sera disponible à temps et réellement utilisable dans le calcul de la métrique. Car si le temps nécessaire pour recevoir cette information est supérieur au temps pour connaître la route, cette information risque d’être obsolète.
L’idéal serait d’avoir un processus d’arrivée de Poisson sur chaque lien et des temps de service distribués exponentiellement pour les paquets. Ensuite mesurer les propriétés du réseau et transmettre ces données au routeurs pour la détermination d’une meilleure route. Le problème est encore l’envoi des tables de routage qui se fait toutes les 90 secondes, temps pendant lequel on peut observer pas mal de changements dans la topologie du réseau. La charge est également calculée au sein des nœuds et envoyée dans le calcul de la métrique. Par défaut, le protocole IGRP utilise la bande passante et le délai.
Routage à états de liens
Différent du routage à vecteur de distance, le routage à états de liens fonctionne de la manière suivante : les routeurs ont une vue globale de la topologie et établissent un arbre dont ils sont la racine. Il ne reste alors qu’à déterminer les plus courts chemins de la source (en l’occurrence lui-même) vers tous les autres nœuds. L’état des liens connus est ensuite envoyé à tous les routeurs. Comme nous l’avons tantôt dit les protocoles de routage adaptifs s’adaptent plus aux changements de topologie qu’aux variations de trafic. C’est le cas du protocole OSPF (Open Shortest Path First) qui, dans le calcul de sa métrique, utilise par défaut uniquement la bande passante. Il est évident que la prise en charge effective des aspects stochastique dans les problèmes de routage est un véritable problème. Les modèles que l’on a étudiés semblent être fiables mais les données intervenant dans ces calculs par contre ne sont pas toujours accessibles ou difficilement exploitables.
Autres procédés de routage
Dans cette partie, nous allons uniquement présenter d’autres techniques de routage qui ne sont pas tellement utilisées mais qui peuvent bien constituer des méthodes pouvant être couplées aux méthodes connues pour donner des procédés hybrides.
Le routage par inondation :
Le principe est très simple et consiste à émettre les paquets reçus sur toutes les autres voies de sortie. Cette méthode est garantie quant à l’arrivée des paquets à destination mais il est évident que la congestion du réseau sera vite au rendez vous !
Le routage aléatoire :
Même procédé que le routage par inondation mais les voies où il faut émettre sont choisies de manières aléatoires. On ne choisit donc pas toutes les voies de communication mais on en tire au hasard quelques unes.
Le routage « hot potato »
Le routeur cherche à débarrasser au plus vite du paquet reçu, par exemple en le plaçant à la fin de la file d’attente la plus courte. Cette méthode vise une optimisation locale et limite le temps que passe les paquets sur les routeurs. Toutefois, l’optimisation globale n’est pas assurée et un paquet peut être transmis indéfiniment (jusqu’à la limite du TTL) sur le réseau.
Nous voyons que ces techniques ont un point en commun ; elles ne nécessitent pas de tables de routage pour pouvoir émettre. Ce sont des routages locaux.
Table des matières
Présentation générale
1 Généralités sur les graphes
1.1 Graphe orienté, graphe non orienté
1.2 Chemins et circuits, chaînes et cycles
1.3 Connexité
1.4 Arbres et arborescences
1.5 Représentation en informatique des graphes
2 Plus court chemin
2.1 Formulation
2.2 Meilleurs chemins dans un graphe
2.2.1 Floyd-Wharshall (G <S, A, p> et p: A→R)
2.3 Meilleurs chemins issus d’un sommet s donné
2.3.1 Ford Bellman (G <S, A, p> et p: A→R)
2.3.2 Dijkstra (G <S, A, p> et p: A→R+)
2.3.3 Algorithme dans un graphe acyclique (G <S, A, p> et p: A→R)
2.4 Autre algorithme pour les meilleurs chemins dans un graphe
2.4.1 Johnson (G <S, A, p, p’> et p: A→R et p’: A→R+)
3 Flot maximal
3.1 Formulation
3.2 Obtention du flot optimal
3.2.1 Ford-Fulkerson
3.2.2 Amélioration avec Edmonds-Karp
3.2.3 Amélioration avec Dinic
3.2.4 Algorithme avec préflots
3.2.5 Algorithme d’élévation vers l’avant
3.2.6 Application au problème d’affectation
4 Flot maximal de coût minimal
4.1 Formulation
4.2 Obtention du flot maximal de coût minimal
4.2.1 Roy
4.2.2 Bennington
5 Transport à coût minimum
5.1 Formulation
5.2 Obtentions des solutions de base
5.2.1 Méthode du coin Nord-ouest
5.2.2 Méthode de la différence maximale (Vögel)
5.3 Algorithme du Stepping-Stone
6 Transport optimal (Problème de Monge)
6.1 Formulation
6.2 Discrétisation du problème
7 Problèmes de multiflots
7.1 Formulation
7.2 Dimensionnement
7.3 Routage.
8 Aspects stochastiques du routage
8.1 Introduction au routage
8.2 Routage fixe
8.3 Routage adaptatif
8.3.1 Routage à vecteur de distance
8.3.2 Routage à état de liens
8.4 Autres procédés de routage
Conclusion
Annexe 1 : Modèles aléatoires
I Rappels sur les lois de probabilité
I.1 Loi de Bernoulli
I.2 Loi Binomiale
I.3 Loi de Poisson
I.4 Loi Exponentielle
II Processus stochastiques
II.1 Chaînes de Markov à temps discret
II.1.1 Définitions
II.1.2 Chaînes de Markov homogènes
II.1.3 Vecteur stochastique
II.1.4 Comportement stable du système
II.2 Chaînes de Markov à temps continu
II.2.1 Définitions
II.2.2 Vecteur stochastique
II.2.3 Distribution stationnaire
II.3 Processus de Poisson
II.4 Processus de naissance et de mort
II.5 File d’attente M/M/1
II.5.1 File d’attente M/M/1 comme processus de naissance et de mort
II.5.2 Distribution stationnaire
II.5.3 Mesures de performance de la file M/M/1
Annexe 2 : Simulation graphique des préflots en Java
I Outils
II Implémentation
III Code
Bibliographie
