Quelques compléments concernant le routage dynamique
Pour dessiner les graphes, je vous propose
le logiciel Grin (gratuit).
Calcul de produit de matrice en ligne :
Directement sur sa machine, on peut également utiliser :
http://michel.gosse.free.fr/documentation/decouverte/
http://michel.gosse.free.fr/documentation/fr/maxima.html
http://wikictm.ups-tlse.fr/mediawiki/index.php/Apprentissage_Maxima
Tout d’abord revenons sur le vocabulaire :
- Une matrices indiquant par un « zéro » ou un « un », la présence ou l’absence d’un arc entre deux de ses sommets, est appelée une matrice d’adjacence du graphe.
- Un chemin d’un graphe est une suite de p arcs telle que l’extrémité de chaque arc soit l’origine de l’arc suivant, sauf pour le dernier. P est la longueur du chemin.
- Un circuit est un chemin dont le premier et le dernier sommet sont confondus. Dans les réseaux pour éviter les circuits et les tempêtes de diffusion (broadcast) avec les commutateurs (switchs), on utilise le protocole Spannig Tree.
- Une boucle est un circuit de longueur 1.
- Un chemin hamiltonien est un chemin qui contient une fois et une seule chacun des sommets du graphe.
- La fermeture transitive d’un graphe G contient les arcs de G, plus les arcs (xi,xj), tels que, dans G, il existe au moins un chemin d’origine xi et d’extrémité xj.
- Niveau ou rang d’un sommet :
- Un sommet est de niveau zéro, ou de rang zéro, lorsqu’il n’a pas de prédécesseur.
- Un sommet est de niveau k (k élément de N*) lorsque k-1 est le maximum des niveaux de ses prédécesseurs.
- Ordonnancer un graphe : C’est classer ses sommets par niveaux. C’est aussi modifier sa représentation géométrique de façon que, de gauche à droite, les sommets soient de niveaux croissants ; les sommets de même niveau sont alors sur une verticale.
- Graphe valué : On appelle graphe à arcs valués, ou graphe valué, un graphe dans lequel un nombre entier est affecté à chaque arc. Ce nombre est la valeur de l’arc.
- La valeur d’un chemin est la somme des valeurs des arcs qui le constituent.
Liens :
Vous vous doutez que certaines des informations qui vous ont été fournies vont vous être très utiles pour traiter le problème.
Tout dépend de la méthode que vous allez utiliser pour effectuer le routage dynamique avec votre pool de routeurs.
Extraits :
Le routage dynamique permet permet de se mettre à jour de façon automatique. La définition d'un protocole de routage va permettre au routeur de se comprendre et d'échanger des informations de façon périodique ou événementielle afin que chaque routeur soit au courant des évolutions du réseau sans intervention manuelle de l'administrateur du réseau. Concrètement, le protocole de routage fixe la façon dont les routeurs vont communiquer mais également la façon dont ils vont calculer les meilleures routes à emprunter.
Dans un premier temps, on ajoute le réseau C au routeur 2 (on le connecte à l'interface du routeur 2). Une annonce va ensuite suivre pour que les autres routeurs sachent que le réseau C est joignable via le Routeur 2. Par la suite, les routeurs continueront à communiquer périodiquement pour voir si chacun des routeurs est toujours joignable. Si un routeur vient à tomber et qu'une autre route existe pour accéder à un réseau, les tables de routages des routeurs vont se modifier dynamiquement via des communications faites entres les routeurs et le calcul de la meilleur route possible à emprunter. Cela facilite la transmission des informations entre les routeurs et la mise à jour des topologies réseaux. On doit bien sûr pour cela définir la façon dont ils vont communiquer et calculer les routes (le protocole de routage qu'ils doivent utiliser). Ils pourront ensuite se comprendre par l'échange de messages de mise à jour, des messages « hello » (indiquant que l'hôte est toujours joignable), des requêtes et des réponses diverses et différentes selon le protocole de routage.
Il est important de savoir que certains protocoles de routage calculent les routes en fonction de la vitesse des liens les liants, d'autres en fonction du nombre de routeurs à passer avant d'atteindre notre destination (saut), etc.
Le routage dynamique présente les avantages suivants :
• Une maintenance réduite par l'automatisation des échanges et des décisions de routage
• Une modularité et une flexibilité accrue, il est plus facile de faire évoluer le réseau avec un réseau qui se met à jour automatiquement.
• Sa performance et sa mise en place ne dépendent pas de la taille du réseau
Mais aussi des désavantages :
• Il peut être plus compliqué à mettre en place lors de son initialisation
• Il consomme de la bande passante de par les messages que les routeurs s'envoient périodiquement sur le réseau
• La diffusion automatique de message sur le réseau peut constituer un problème de sécurité car un attaquant peut obtenir des informations sur la topologie du réseau simplement en écoutant et en lisant ces messages d'information du protocole de routage et même en créer afin de se faire passer pour un membre du réseau.
• Le traitement des messages réseau et le calcul des meilleures routes à emprunter représentent une consommation de CPU et de RAM supplémentaire qui peut encombrer certains éléments du réseau peu robuste.
Exemple de deux protocoles de routage :
- Protocole de routage à vecteur de distance RIP : Routing Information Protocol
- Protocole de routage à état de liens OSPF : Open shortest path first
Quelques conseils pour réaliser votre modélisation :
- Vous pouvez ne consulter que les réseaux proche d’un routeur donné (à votre charge de propager l’information).
- Chaque routeur peut obtenir une carte de l’ensemble des routeurs de votre pool.
- Le routage statique reste la base pour remplir les tables de routage.
- Il est possible d’optimiser le routage en termes de débit ou en terme de nombre de routeurs traversés.
- Le routage dynamique contrairement au routage statique nécessite des échanges entre les routeurs.
- Pensez éventuellement à une route par défaut.
- Pour simplifier on ne s’intéressera pas aux problèmes de sécurité.
- Votre raisonnement devra se faire à partir de plusieurs schémas (comportant plusieurs routeurs).
- Comment faire pour propager l'information, et donc pour l'acquérir ?
- Comment déterminer le chemin optimal (en fonction de votre critère) à partir du routeur i pour atteindre le routeur j.
- La représentation du modèle et des différents états que celui-ci peut prendre reste à déterminer.
- On ne demande pas de traiter tous les états de l'automate.
- Vous terminerez par la rédaction d'une
conclusion sur les problèmes que vous avez rencontrés, si vous avez des idées, faites des propositions.
- Vous devrez réaliser des choix parmi les options proposées,
ensuite vous pourrez construire un modèle pour réaliser votre modélisation