1. Le protocole de routage RIP

RIP est le protocole de routage intra-domaine IP le plus ancien. Son ancienneté et sa simplicité de mise en oeuvre en font encore aujourd’hui le protocole de routage IP le plus étudié pour illustrer les principes de routage automatique. RIP est un protocole de routage de type Distance-Vector (à vecteur de distance) des plus rudimentaires. En effet, sa métrique est pauvre et définie par le nombre de routeurs à traverser pour atteindre la destination. Le coût d’un arc est par conséquent fixé à 1. Ce coût ne peut pas dépasser la valeur 15, soit 15 arcs traversés pour éviter la formation de boucle de routage. La valeur 16 est synonyme d’infini. L’équilibrage de charge entre 2 chemins de même coût n’existe pas, RIP choisit arbitrairement un des 2 chemins.

Les routeurs construisent progressivement leur table de routage en s’échangeant de proche en proche les routes qu’ils connaissent. La convergence du réseau est donc lente.

Les échanges ont lieu toutes les 30 secondes et chaque routeur recalcul alors les distances aux réseaux qu’il connait et ajoute les nouvelles routes apprises à sa table de routage. Il a donc un vision locale du graphe que constitue le réseau et utilise un algorithme du plus court chemin pour choisir une route vers un réseau de destination.

RIP utilise pour ce calcul de distance l’algorithme de Bellman-Ford dans sa version distribuée.

rip
Figure 1. R1 et R2 s’échangent leur premier paquet RIPv2. Chacun ajoute une distance de +1 à la métrique du nouveau réseau qu’il annonce.

Source : https://cisco.goffinet.org/ccnp/rip/routage-dynamique-ripv2/

2. Objectif

Notre objectif est de produire une application python qui calcul le plus court chemin entre deux routeurs d’un réseau en s’appuyant sur le principe du routage RIP :

  • Utiliser un simuateur de réseau (Packet Tracer) pour configurer et observer le fonctionnement du routage RIP,

  • Modéliser un réseau et appliquer l’algorithme de Bellman-Ford distribué pour compléter les tables de routages de chaque routeurs,

  • Produire une application objet qui permet de définir des routeurs et leurs connexions, puis de compléter automatiquement leurs tables de routage.

simulation rip
Figure 2. Mise en situation avec Packet Tracer

3. Moyens

  • Packet Tracer version 7.3

  • Utilisez votre environement de développement préféré (idle, pycharm, spyder, …​ ) ou travaillez en ligne avec https://repli.it

  • Dépôt et versionning du code produit sur github

4. Prérequis

  • Adressage IP et principe général du routage

  • Listes et dictionnaires

  • Programmation objet

  • Algorithmes sur les graphes

5. Durée

  • 4 heures

6. Simulation d’un réseau

6.1. Compléter la configuration des routeurs

Ouvrez le fichier rip.pka

Assurez vous d’être en mode simulation.

Le réseau est partiellement configurer :

  • Toutes les adresses IP des interfaces des routeurs sont configurées.

  • Chaque PC obtient automatiquement une configuration TCP/IP grace au serveur DHCP qui a été configuré sur le routeur du LAN auquel il appartient.

Question :

Observez les tables de routage de chaque routeur. Quelles sont les réseaux que peut atteindre chaque routeur ?

Question :

A partir d’un des PC du réseau 192.168.1.0/24, testez la connectivité avec un PC du réseau 192.168.6.0/24.

Observez ce qui se passe et conclure sur les raisons de l’échec du test.

Question :

Sur chaque routeur, activez le routage RIP version 2 et annoncez les réseaux connus du routeur :

Sur Router1
Router1> enable
Router1# configure terminal
Router1(config)# router rip
Router1(config-router)#  version 2
Router1(config-router)# network 192.168.1.0
Router1(config-router)# network 10.1.2.0
Router1(config-router)# network 10.1.5.0

Question :

Sur chaque routeur desactivez le protocol RIP sur les interfaces connectés aux différents LAN pour éviter de diffuser les tables de routages vers les PC

Sur Router1
Router1(config-router)# passive-interface g0/0

6.2. Simulation

Question :

Utilisez l’outils d’inspection (loupe) pour inspecter la table de routage du routeur Router1. Lancez la simulation et observez les échanges de paquets RIP entre les routeur et l’évolution de la table de routage de Router1. Arrêtez la simulation lorsque le routeur a acquis toutes les routes nécessaires pour rejoindre tous les réseaux (convergence).

Question :

Complétez le tableau ci-dessous qui synthétise la table de routage du routeur Router1 :

Destination type Interface de sortie Distance

192.168.1.0

C

GigabitEthernet0/0

0

10.1.2.0

C

Serial0/1/0

0

10.1.5.0

C

Serial0/1/1

0

10.2.3.0

10.2.4.0

10.3.4.0

10.3.4.0

10.3.6.0

10.4.5.0

192.168.2.0

192.168.4.0

192.168.4.0

192.168.5.0

192.168.6.0

Question :

Observez les tables de routage de tous les routeurs et assurez vous qu’ils possèdent tous des routes à destination de tous les réseaux.

Question :

A partir d’un des PC du réseau 192.168.1.0/24, testez la connectivité avec un PC du réseau 192.168.6.0/24.

Observez ce qui se passe et conclure sur les raisons de la réussite du test.

7. Modélisation du réseau et du routage

7.1. Principe

Un réseau peut être modélisé par un graphe. En effet, un graphe est un ensemble constitué de noeuds et d’arcs reliant ces noeuds. Il suffit de considérer les routeurs comme des noeuds et les liaisons de données comme des arcs.

Cette modèlisation est particulièrement fructueuse car elle permet aux concepteurs de protocoles de routage de s’appuyer sur un ensemble théorique très riche.

Tout réseau peut être modèlisé comme un graphe connecté, orienté et pondéré.

En choisissant un routeur comme noeud racine, on peut alors calculer l’arbre recouvrant de poids minimal pour le réseau. On obtient ainsi l’ensemble des plus courts chemins reliant ce routeur à l’ensemble des destinations. C’est la démarche suivie par les protocoles de routage.

Les algorithmes de calcul de plus courts chemins les plus utilisés par les protocoles de routage sont ceux de BELLMAN-FORD et de DIJKSTRA.

  • Les protocoles de routage utilisant l’algorithme de BELLMAN-FORD sont dits de type Distance-Vector (à vecteur de distance). On ne tient compte ici que de la direction (interface de sortie) et de la distance.

  • Les protocoles de routage utilisant l’algorithme de DIJKSTRA sont dits de type Link-State (à état de liens). On tient compte ici également de l’état de la liaison, par exemple, le débit, l’emcombrement, …​.

7.2. Algorithme de Bellman Ford

L’algorithme de BELLMAN-FORD existe en 2 versions :

  • centralisée

  • distribuée

Seule la version distribuée appelée également algorithme de FORD-FULKERSON est utilisée par les protocoles de routage de type Distance-Vector.

Dans la version centralisée, chaque noeud connait la topologie du réseau et calcule l’arbre recouvrant de poids minimal dont il est la racine.

n et m étant respectivement le nombre de noeuds et le nombre d’arcs, on démontre que l’algorithme converge au plus en n 1 étapes et que sa fonction de complexité est : onxm

graph network
Modélisation du réseau par un graphe

Dans la version distribuée, les noeuds n’ont pas connaissance de la topologie du réseau.

Chaque noeud calcule ses distances minimales à l’ensemble des noeuds du réseau grâce aux messages que lui envoient ses noeuds voisins.

Ces messages sont appelés vecteurs de distance (routing vectors) et contiennent un ou plusieurs couples (noeud, distance). De fait, le noeud racine ne supporte pas l’intégralité du calcul puisque les noeuds voisins lui fournissent des résultats intermédiaires.

Le protocol RIP untilise une distance unitaire entre deux noeuds voisins et les liens sont bidirectionels donc, on a à faire à un graphe unitaire non orienté.

Comme pour la version centralisée, on démontre que la fonction de complexité est onxm. Cependant, l’algorithme converge parfois en plus de n 1 étapes. Cela peut se produire lors d’une modification de la topologie du réseau et le cas le plus grave peut théoriquement conduire à un comptage à l’infini.

7.3. Analyse

7.3.1. Initialisation

Question :

Au démarrage, chaque routeur ne connait que ses voisins immédiats qui sont situés à une distance de 1.

Complétez les tables de routages de tous les routeurs au démarrage :

Router1 Router2 Router3

Destination

Distance

Destination

Distance

Destination

Distance

Router1

0

Routeur2

0

Router3

0

Router2

1

Router5

1

 
Router4 Router5 Router6

Destination

Distance

Destination

Distance

Destination

Distance

Router4

0

Router5

0

Router6

0

 

 

 

7.3.2. Exploration 1

Question :

Etape 1 : Router1 reçoit les tables de routage de Router2 et Router5. Il met à jour sa table en ajoutant les nouvelles routes vers les destinations qu’il ne connaissait pas et compare les distances vers les destinations qu’il connaissait déjà pour choisir la plus petite.

Complétez la table de routage de Router1 lorqu’il reçoit les tables de Router2 et Router5

Router1 Router2 Router3

Destination

Distance

Destination

Distance

Destination

Distance

Router1

0

Routeur2

0

Router3

0

Router2

1

Router5

1

 

 

 
Router4 Router5 Router6

Destination

Distance

Destination

Distance

Destination

Distance

Router4

0

Router5

0

Router6

0

 

 

 

 

 

Question :

Etape 2 : Router2 reçoit les tables de routage de Router1, Router3 et Router4. Il met à jour sa table en ajoutant les nouvelles routes vers les destinations qu’ils ne connaissaient pas et compare les distances vers les destinations qu’il connaissait déjà pour choisir la plus petite.

Complétez la table de routage de Router2 lorqu’il reçoit les tables de Router1, Router3 et Router4

Router1 Router2 Router3

Destination

Distance

Destination

Distance

Destination

Distance

Router1

0

Routeur2

0

Router3

0

Router2

1

Router5

1

 

 

 
Router4 Router5 Router6

Destination

Distance

Destination

Distance

Destination

Distance

Router4

0

Router5

0

Router6

0

 

 

 

 

 

Question :

Etape 3 : Router3 reçoit les tables de routage de Router2, Router4 et Router6. Il met à jour sa table en ajoutant les nouvelles routes vers les destinations qu’il ne connaissait pas et compare les distances vers les destinations qu’il connaissait déjà pour choisir la plus petite.

Complétez la table de routage de Router2 lorqu’il reçoit les tables de Router2, Router4 et Router6

Router1 Router2 Router3

Destination

Distance

Destination

Distance

Destination

Distance

Router1

0

Routeur2

0

Router3

0

Router2

1

Router5

1

 

 

 
Router4 Router5 Router6

Destination

Distance

Destination

Distance

Destination

Distance

Router4

0

Router5

0

Router6

0

 

 

 

 

 

Question :

Etape 4 : Router4 reçoit les tables de routage de Router2, Router3 et Router5. Il met à jour sa table en ajoutant les nouvelles routes vers les destinations qu’il ne connaissait pas et compare les distances vers les destinations qu’il connaissait déjà pour choisir la plus petite.

Complétez la table de routage de Router4 lorqu’il reçoit les tables de Router2, Router3 et Router5

Router1 Router2 Router3

Destination

Distance

Destination

Distance

Destination

Distance

Router1

0

Routeur2

0

Router3

0

Router2

1

Router5

1

 

 

 
Router4 Router5 Router6

Destination

Distance

Destination

Distance

Destination

Distance

Router4

0

Router5

0

Router6

0

 

 

 

 

 

Question :

Etape 5 : Router5 reçoit les tables de routage de Router4, et Router1. Il met à jour sa table en ajoutant les nouvelles routes vers les destinations qu’il ne connaissait pas et compare les distances vers les destinations qu’il connaissait déjà pour choisir la plus petite.

Complétez la table de routage de Router5 lorqu’il reçoit les tables de Router4, et Router1

Router1 Router2 Router3

Destination

Distance

Destination

Distance

Destination

Distance

Router1

0

Routeur2

0

Router3

0

Router2

1

Router5

1

 

 

 
Router4 Router5 Router6

Destination

Distance

Destination

Distance

Destination

Distance

Router4

0

Router5

0

Router6

0

 

 

 

 

 

Question :

Etape 6 : Router6 reçoit la table de routage de Router3. Il met à jour sa table en ajoutant les nouvelles routes vers les destinations qu’il ne connaissait pas et compare les distances vers les destinations qu’il connaissait déjà pour choisir la plus petite.

Complétez la table de routage de Router6 lorqu’il reçoit la table de Router3

Router1 Router2 Router3

Destination

Distance

Destination

Distance

Destination

Distance

Router1

0

Routeur2

0

Router3

0

Router2

1

Router5

1

 

 

 
Router4 Router5 Router6

Destination

Distance

Destination

Distance

Destination

Distance

Router4

0

Router5

0

Router6

0

 

 

 

 

 

A ce stade de l’exploration du réseau, tous les routeurs ne se connaissent pas encore.

Il est donc nécessaire de renouveler l’exploration sur la base des nouvelles connaissances.

7.3.3. Exploration 2

Question :

Etape 7 : Complétez la table de routage de Router1 lorqu’il reçoit la table de Router5

Router1 Router2 Router3

Destination

Distance

Destination

Distance

Destination

Distance

Router1

0

Routeur2

0

Router3

0

Router2

1

Router5

1

 

 

 
Router4 Router5 Router6

Destination

Distance

Destination

Distance

Destination

Distance

Router4

0

Router5

0

Router6

0

 

 

 

 

 

Question :

Etape 8 : Complétez la table de routage de Router1 lorqu’il reçoit la table de Router2

Router1 Router2 Router3

Destination

Distance

Destination

Distance

Destination

Distance

Router1

0

Routeur2

0

Router3

0

Router2

1

Router5

1

 

 

 
Router4 Router5 Router6

Destination

Distance

Destination

Distance

Destination

Distance

Router4

0

Router5

0

Router6

0

 

 

 

 

 

Question :

Vérifiez que tous les routeurs ont acquis les routes les plus courtes vers tous les autres routeurs du réseau.

A ce stade de l’exploration du réseau, tous les routeurs ne se connaissent pas encore. On peut également remarqué que si l’on modifie l’ordre l’exploration, les tables de routage peuvevent être sensiblement différentes. Par exemple, actuellement, Router3 à découvert Router1 par l’intermédiaire de Router2 et le situe à 2 sauts. Si l’exploration avait été menée dans l’autre sens (Router1 → Router5 → Router4 → `Router3 → …​), Router3 aurait découvert Router1 par l’intermédiaire de Router4 et l’aurait situé à 3 sauts.

Il est donc nécessaire de renouveler l’exploration sur la base des nouvelles connaissances.

Dans cet exercice, nous avons procéder à l’étude d’un seul routeur à chaque étape. Dans la réalité, à chaque étape, tous les routeurs reçoivent la table de routage de leurs voisins. Le réseau converge donc plus rapidement.

Prenons deux noeuds les plus éloignés l’un de l’autre :

Etape 1 :

  • Router1 reçoit Router2 et Router5

  • Router2 reçoit Router1, Router4 et Router3

  • Router3 connait Router6 donc Router2 apprend l’existance de Router6 via Router3

Etape 2 :

  • Router1 reçoit Router2 et Router5 or Router2 connait Router6

Le réseau a convergé en 2 étapes

8. Programmation

Notebook routage automatique RIP

the_end.jpg