Archi RIP

Identification

Infoforall

18 - Routage dynamique RIP


Prérequis : l'activité sur les tables de routage et l'activité débranché précédente sur RIP

Evaluation ✎ : questions -

Documents de cours : open document ou pdf

1 - Les Systèmes Autonomes

Nous avons vu dans les activités précédentes la structure globale d'Internet.

Visualisation du transit
Internet simplifié (image réalisée avec Filius)

Les machines des clients individuels générent des paquets IP qui sont envoyés vers l'exterieur.Les clients individuels sont reliés par la boucle locale jusqu'à leur répartiteur (un local qui reçoit leurs communications des clients aux alentours).

A partir de là, leurs communications sont envoyées jusqu'à leur FAI : on atteint le premier vrai réseau.

La couche Réseau du premier routeur va alors être chargé de trouver vers où envoyer ce paquet IP. Comment ? En utilisant le protocole IP pour comparer son adresse réseau et l'adresse de destination du paquet. Ensuite, il part voir sa table de routage.

Vous avez vu qu'il existe différents opérateurs qui se partagent le trafic : les Fournisseurs d'Accès Internet (FAI) et d'autres opérateurs privés de réseaux traitant directement avec les FAI en leur permettant de faire passer les paquets IP par leurs réseaux.

Ces opérateurs possèdent leurs routeurs configurés et programmés par leurs personnels. Aucun n'a envie de voir des personnes extérieures interagir directement sur leurs machines ou connaître les détails de leurs infrastructures.

En réalité, le "nuage" Internet est composé d'un ensemble de réseaux contrôlés par des sociétés autonomes acceptant d'être reliés aux autres. Un Système Autonome est le nom donné à un ensemble de routeurs gérés par le même opérateur et sur lequel on fait tourner un algorithme de routage. Chaque SA peut utiliser et configurer son routage comme il veut.

Il y a donc deux types de protocole de routage :

  1. Les protocoles internes à l'intérieur d'un système autonome : les routeurs appartiennent à la même entité, on peut considérer qu'elles sont sures et on peut garantir qu'un unique protocole tourne sur toutes les machines.
  2. Les protocoles externes qui permettent de relier les systèmes autonomes entre eux. Cette fois, il peut y avoir des contraintes commerciales ou de sécurité visant à faire passer certains paquets par une route particulière.
Connexion entre Systèmes autonomes
Des protocoles pour le routage à l'intérieur des systèmes autonomes et d'autres protocoles pour le routage entre les systèmes autonomes

Nous allons voir cette année deux protocoles de routages internes : le protocole RIP et le protocole OSPF. Ces protocoles s'appliquent donc à l'intérieur d'un système autonome : tous les routeurs appartiennent bien à la même entité et peuvent donc facilement être configurés.

Les systèmes autonomes ont besoin d'un routage dynamique : ils sont composés de trop de routeurs pour qu'on puisse les configurer à la main :

  1. Les risques de mauvaises configurations avec des paquets faisant des aller-retours entre deux routeurs est trop grand si les règlages sont fait à la route avec un routage statique
  2. Une panne sur le réseau voudrait dire que les routes ne changent pas : les routeurs continueraient d'envoyer les paquets sur des routes défectueuses, le temps que quelqu'un écrive de nouvelles routes valides.

Bref, ce ne serait pas sérieux.

2 - Principe du routage RIP

Nous allons commencer aujourd'hui par le protocole RIP : Routing Information Protocol.

Du point de vue de ce protocole, la meilleure route à prendre est la route qui va demander le moins de sauts entre le routeur de départ et le routeur d'arrivée.

On dira que la métrique utilisée est le nombre de sauts jusqu'au réseau voulu.

Le principe général de RIP ?

  1. Toutes les 30 secondes, les routeurs transmettent leurs routes qu'il connait à leurs voisins directs (on parle de routeurs adjacents dans un graphe) : il envoie l'adrese du réseau IP et la métrique pour le joindre.
  2. Chaque routeur va alors augmenter la métrique de 1 sur ces informations pour prendre en compte le saut vers le routeur qui vient d'envoyer l'information
  3. Chaque routeur va alors choisir la route à garder dans sa propre table de routage en faisant la synthèse des tables reçues et en sélectionnant celles qui présentent le plus faible nombre de sauts.
  4. Si un routeur voisin n'a pas renvoyé de table de routage depuis trois minutes, on considère qu'il n'est plus joignable pour le moment : on lui attribue une métrique de 16. Nous verrons que cela correspond à une liaison non utilisable avec RIP.

3 - Initialisation

Lors de cette phase, le routeur va envoyer un message sur toutes ses cartes réseaux en précisant son adresse IP : les correspondants vont répondre s'ils appartiennent bien au même système RIP. Ils vont donner leurs propres noms et les routes (et les métriques associées) qu'ils connaissent.

Nous allons travailler en nous plaçant à la place d'un des routeurs, qu'on nommera le routeur A-100-1. On considère donc qu'il s'agit d'une machine appartenant au réseau A et au sous-réseau 100. Sur le sous-réseau, son identifiant machine est le 1.

On considère que son identifiant sur le réseau est juste 101 pour simplifier : pas de sous-réseau et autres subtilités. Le principe est de comprendre le principe du protocole permettant aux machines de coopérer.

On sait que cette machine possède 4 sorties extérieures, notée E/S1, E/S2, E/S3 et E/S4 : la dernière mène vers son réseau interne : le sous-réseau des machines A-100-X.

Le routeur A-100-1 initialement

Voici sa table de routage actuelle :

Le message est pour
IP Destinataire
Transmettre à la passerelle
(intermédiaire de communication)
Interface à utiliser
(carte réseau)
Métrique (nbr de sauts)
A100-1 Localhost Localhost 0
A100-X A100-1 E/S 4 0

01° Ce routeur reçoit les messages suivants sur ces interfaces :

Recu via l'interface E/S1 Message en provenance du routeur A-300-1 qui peut joindre :

  • A-300-X en 0 saut
  • A-100-X en 1 saut

Recu via l'interface E/S3 Message en provenance du routeur A-400-1 qui peut joindre :

  • A-400-X en 0 saut
  • A-500-X en 1 saut
  • A-100-X en 1 saut

Recu via l'interface E/S2 Message en provenance du routeur A-200-1 qui peut joindre :

  • A-200-X en 0 saut
  • A-700-X en 1 saut
  • A-100-X en 1 saut

Question : remplir la nouvelle table de routage du routeur A100-1 après réception et traitement de ces données.

Le message est pour
IP Destinataire
Transmettre à la passerelle
(intermédiaire de communication)
Interface à utiliser
(carte réseau)
Métrique (nbr de sauts)
A-100-1 Localhost Localhost 0
A-100 A-100-1 E/S 4 0
A-200 ... ... ...
... ... ... ...

...CORRECTION...

Il s'agit de prendre en compte les routes proposées en rajoutant 1 au nombre de sauts.

Le message est pour
IP Destinataire
Transmettre à la passerelle
(intermédiaire de communication)
Interface à utiliser
(carte réseau)
Métrique (nbr de sauts)
A-100-1 Localhost Localhost 0
A-100-X A-100-1 E/S 4 0
A-200 A-200-1 E/S2 1
A-300 A-300-1 E/S1 1
A400 A-400-1 E/S3 1
A500 A-400-1 E/S3 2
A700 A-200-1 E/S2 2

02° Quel message pourra envoyer le routeur aux routeurs adjacents dont il connait maintenant les adresses lorsqu'il devra leur envoyer les éléments de sa propre table ?

...CORRECTION...

Message en provenance du routeur A-100-1 qui peut joindre :

  • A-100-X en 0 saut
  • A-200-X en 1 saut
  • A-300-X en 1 saut
  • A-400-X en 1 saut
  • A-500-X en 2 sauts
  • A-700-X en 2 sauts

03° Nouveaux messages des routeurs adjacents :

Recu via l'interface E/S1 Message en provenance du routeur A-300-1 qui peut joindre :

  • A-300-X en 0 saut
  • A-500-X en 1 saut
  • A-600-X en 1 saut
  • A-100-X en 1 saut

Recu via l'interface E/S3 Message en provenance du routeur A-400-1 qui peut joindre :

  • A-400-X en 0 saut
  • A-500-X en 1 saut
  • A-100-X en 1 saut
  • A-300-X en 2 sauts

Recu via l'interface E/S2 Message en provenance du routeur A-200-1 qui peut joindre :

  • A-200-X en 0 saut
  • A-700-X en 1 saut
  • A-600-X en 2 sauts

Question : remplir la nouvelle table de routage du routeur A100-1 après réception et traitement de ces données.

Le message est pour
IP Destinataire
Transmettre à la passerelle
(intermédiaire de communication)
Interface à utiliser
(carte réseau)
Métrique (nbr de sauts)
A-100-1 Localhost Localhost 0
A-100 A-100-1 E/S 4 0
A-200 ... ... ...
... ... ... ...

...CORRECTION...

Le message est pour
IP Destinataire
Transmettre à la passerelle
(intermédiaire de communication)
Interface à utiliser
(carte réseau)
Métrique (nbr de sauts)
A-100-1 Localhost Localhost 0
A-100-X A-100-1 E/S 4 0
A-200 A-200-1 E/S2 1
A-300 A-300-1 E/S1 1
A400 A-400-1 E/S3 1
A500 A-400-1 E/S3 2
A600 A-300-1 E/S1 2
A700 A-200-1 E/S2 2

04° Combien de routes vont indiquer les 7 routeurs où bout d'un certain temps ?

...CORRECTION...

Chaque routeur va envoyer 7 routes au moins. Sans compter les routes statiques ou les routes vers les réseaux externes qu'on peut joindre depuis l'un des routeurs du système autonome.

05° Dans le pire des cas, combien faut-il d'échange pour que chaque routeur connaisse une route vers tous les autres ? Quel est ce pire des cas ?

...CORRECTION...

Visualisation du pire des cas : 7 routeurs en lignes
6 Sauts pour que les deux routes extrêmes connaissent une route vers l'autre

06° Combien de routes au bout d'un certain temps dans un système autonome de 200 routeurs si on applique juste ce principe basique de RIP ?

...CORRECTION...

Chacun des 200 routeurs va envoyer toutes les 30 secondes un message contenant sa métrique pour joindre les 200 routeurs. Et ils vont les envoyer à tous leurs routeurs adjacents.

4 - Métrique maximale

Métrique maximale

Pour limiter le nombre de routes inutiles et limiter la taille des messages RIP sur le réseau, on considère qu'une métrique de 16 correspond à une route impossible à atteindre.

Cette taille est un compromis entre le nombre de routes à envoyer aux autres routeurs toutes les 30s et la possibilité de joindre la destination.

Si un routeur apprend qu'un de ses voisins peut joindre un autre réseau en 15 sauts, il ne tiendra donc pas compte lui-même de cette route : en rajoutant 1, il faudra 16 sauts depuis ce routeur.

De la même façon, si un routeur normalement adjacent n'envoie plus de routes RIP depuis 30 minutes, le routeur le placera sur un nombre de sauts de 16, rendant le lien inexistant. De proche en proche, les autres routeurs apprendront donc également que cette route n'est plus disponible.

5 - Vision du réseau

RIP est donc un exemple d'algorithme répartie ou algorithme distribué : l'algorithme tourne sur plusieurs machines et on obtient au total un résultat exploitable.

Chaque routeur ne peut par contre que fournir la route la moins "longue" et à qui il doit fournir le paquet. Il ne sait absolument pas par où passera le paquet IP ensuite.

A l'aide de la table de routage, on ne peut imaginer que cela :

Visualisation du réseau avec les infos de la table
Le réseau connu par le routeur A-100-1

Conséquence ?

Avec cette version du routage dynamique, on ne contrôle pas le trajet : le routeur sait quelle est la passerelle suivante mais ne sait absolument pas quelle route prend REELLEMENT le paquet IP.

Pour des problèmes de sécurité, cela peut être génant.

07° Puisqu'on n'a pas de connaissance globale du système, quel problème va apparaitre si un paquet IP issu du routeur A-100 veut atteindre le réseau indiqué en haut à droite ?

Visualisation du réseau avec les infos de la table

Conclusion :

  • RIP est plutôt simple et solide
  • RIP utilise un algorithme totalement réparti : aucun routeur n'a un rôle plus particulier que les autres dans le processus
  • RIP ne permet pas de gérer des systèmes autonomes comportant des routeurs situés à plus de 15 sauts l'un de l'autre (sinon, le réseau serait encombré par les messages RIP et n'aurait plus le temps de gérer les vrais messages !)
  • RIP ne permet pas d'avoir une vision globale du réseau et de choisir certains chemins : on décide juste de la passerelle suivante à qui on transmet le paquet.
  • RIP met du temps à se mettre en place (connaissance de proche en proche) et encore plus à détecter les routeurs HS

6 - Algorithme de Bellman-Ford

Pour finir, nous verrons l'algorithme qui permet de trouver le plus court chemin à partir de l'ensemble des tables reçues. Vous avez fait le travail en cherchant la route nécessitant le plus petit nombre de sauts. Mais le routeur ne sait pas faire cela !

RIP utilise l'algorithme de Bellman-Ford qui permet de trouver sur un graphe le plus court chemin entre un sommet et les autres, même si certaines arêtes ont un poids négatif.

Nous verrons cet algorithme lors de l'étude des graphes (partie Données).

08° Faire le lien entre la variable graph et la figure représentant le réseau du système autonome.

Visualisation du réseau avec les infos de la table
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
from math import inf # nombre de noeuds dans le graphe n = 7+1 # graph contient les liens (sommet, sommet_adjacent, distance_entre_les_deux) graph = [ (0,0,0), # un faux sommet isolé pour commencer à 1... (1, 3, 1), (1, 4, 1), (3, 1, 1), (3, 5, 1), (3, 6,1), (4,1,1), (4,5,1), (5,4,1), (5,3,1), (2,1,1), (2,7,1), (7,2,1), (7,6,1), (6,3,1), (6,7,1) ] # nombre d'arêtes m = len(graph) def BellmanFord(src): # On initialise la distance du sommet source au sommet source à 0 et du sommet source aux autres sommets à l'infini dist = [float("inf") for i in range(n)] dist[src] = 0 # Relax all edges | V | - 1 times. A simple shortest path from src to any other vertex can have at-most |V| - 1 edges for i in range(n-1): # Update dist value and parent index of the adjacent vertices of the picked vertex. Consider only those vertices which are still in queue. for u, v, w in graph: if dist[u] != float("inf") and dist[u]+w < dist[v]: dist[v] = dist[u]+w # Etape 3 : on gère les arêtes de poids négatif et les cycles. cycle = 0 for u, v, w in graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print("Le graphe contient un cycle de poids négatif") cycle = 1 break if cycle == 0: print('Distance depuis le sommet origine',src) print("Sommet \t Distance depuis l'origine") for i in range(len(dist)): print(i,'\t',dist[i]) BellmanFord(1)

09° Lancer le programme qui suppose une connaissance totale du système autonome et vérifer la correspondante entre résultat et schéma.

10° Lancer le programme qui suppose une connaissance partielle du système autonome et vérifer la correspondante entre résultat et schéma : les données ci-dessous ne proviennent que de ce qu'envoie le routeur 1 et les 3 routeurs adjacents.

1 2 3 4 5 6 7 8 9 10
graph = [ (0,0,0), # un faux sommet isolé pour commencer à 1... (1, 2, 1), (1, 3, 1), (1,4,1), (2,1,1), (2,7,1), (2,4,2), (2,3,2), (2,6,2), (2,5,3), (3,1,1), (3, 6, 1), (3, 5, 1), (3,4,2), (3,7,2), (3,2,2), (4,1,1), (4,5,1), (4,3,2), (4,2,2), (4,7,3), (4,6,3), ]

11° Conclusion : RIP parvient-il à fonctionner simplement à partir des routes fournies par les voisins sans que le routeur ai besoin de connaître exactement la topologie du réseau ?

12° Créer une graphe linéaire de 7 routeurs dans le programme. Compter les arêtes. Visualiser le résultat.

13° Créer une graphe linéaire de 7 routeurs cyclique dans le programme. Compter les arêtes. Visualiser le résultat.

14° Créer une graphe linéaire de 7 routeurs formant un arbre dans le programme. Compter les arêtes. Visualiser le résultat.

7 - FAQ

Et pourquoi on dit Hop limit ?

Hop, c'est pour saut. Le Hop Limit correspond donc au nombre de sauts restants avant destruction. C'est pareil qu'un TTL.

Activité publiée le 26 10 2020
Dernière modification : 02 12 2020
Auteur : ows. h.