• Introduction
• Le Distance Vector
• Quelques problèmes
• Des solutions
• Le protocole RIP
• Conclusion

1. Introduction

– protocole de mise à jour des tables de routage
– L’acheminement (“datagram forwarding”),Le Routage est composée de 2 fonctions essentielles :
Acheminement:
– consultation de la table de routage qui indique le meilleur chemin
– La mise à jour des tables de routage
– réception d’un datagramme
– retransmission du datagramme
Mise à jour des table de routage
– base de données répartie des routes
– plusieurs classes de protocoles existent :
. Distance vector algorithm
. Link state algorithm
– domaines d’application de l’algorithme :
. domaine interne (“autonomous system”)
. domaine externe : interconnexion d’A.S.

2. L’algorithme “Distance Vector”

2.1. Présentation
Distance vectoralgorithm :
– algorithme simple,
– par diffusion d’un extrait des meilleurs chemins,
– (sous la forme d’un vecteur où chaque entrée contient une distance)
– entre voisins directs (de proche en proche)
– métrique simple :hop count.
Link statealgorithm (pour information) :
– 2 phases :
. diffusion à tous de la connaissance sur les liaisons locales
. calcul local par chacun des meilleurs chemins sur les informations ainsi rassemblées
– exemple : Short Path First
2.2. Historique
Algorithme (+ Protocole) :
– vecteur de distance (“distance vector algorithm”)
– algorithme de calcul du plus court chemin
. décrit par [Bellman – 1957]
. amélioré par [Bellman & Ford]
– algorithme réparti [Ford – Fulkerson 1962]
Implémentation :
– première apparition : RIP du réseau XNS de Xérox
– RIP-1 : RFC 1058 – juin 1988.
– RIP-2 : RFC 1388 – juin 1993.
2.3. Principes
Chaque routeur maintient localement une liste (BdD) des meilleures routes
-table de routage <@ de destination, distance, @ du prochain routeur>
Chaque routeur actif diffuse unextraitde sa table de routage (message de routage) :
– Périodiquement (30s)
– A tous leurs voisins immédiats
– Une liste de couple <@ de destination, distance>
Tous les routeurs mettent à jour leur tables de routage en conséquence. L’adresse
Etat des stations :
– Actif (les routeurs) diffusent leurs routes,
– Passif (les stations d’extrémité) écoutent.
du prochain routeur est implicitement celui de l’émetteur du message de routage.
2.4. Algorithme de mise à jour
Chaque couple de la liste est comparé aux entrées de la table de routage :
. [1] l’entrée n’existe pas dans la table et la métrique reçue n’est pas infinie :
– une nouvelle entrée est crée : prochain routeur = routeur d’où provient la liste; distance = distance reçue + 1.
. [2] l’entrée existe et sa métrique est supérieure à celle reçue :
– on met à jour l’entrée : prochain routeur = routeur d’où provient la liste;
. [3] l’entrée existe et son prochain routeur est celui d’où provient la liste :
. [4] sinon rien.
– distance = distance reçue + 1(augmentation ou diminution de la distance).
distance = distance reçue + 1.

Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Les principes de routage (206 KO) (Cours PDF)