Chapitre 6

--------------------------------------------------------------------------------------------------------------------------

L’interconnexion niveau 3 : Les routeurs et le routage

Objectif: Comprendre les fonctions de base des appareils niveau 3.

Éléments de contenu:

La couche réseau
Les routeurs et le principe de routage
Les algorithmes et les protocoles de routage

I- La couche reseau et Les routeurs :

1/ Rappel :
Routeur : Un routeur est un équipement de couche 3 du modèle OSI qui permet de choisir la meilleure voie possible et de commuter des paquets de données entre deux réseaux différents. Les routeurs peuvent servir à segmenter un réseau local, ainsi qu'à créer de plus petits domaines de diffusion ou de collision. Cependant, l'utilisation la plus importante des routeurs est de servir d'équipement fédérateur pour les réseaux longues distances.
→ Principe : si les ponts connaissent l’adresse de tous les ordinateurs du réseau situé de chaque côté. Un routeur connaît non seulement l’adresse de tous les ordinateurs mais aussi des autres routeurs de façon à pouvoir choisir la meilleure route d’envoi d’un message. Les routeurs remplissent leurs fonctions en créant des tables de routage, qui sont habituellement tenues de manière dynamique par un protocole de routage, et en échangeant de l'information sur le réseau avec d'autres routeurs.

Mode	Datagramme	Circuit virtuel
Connexion	Pas de connexion préalable	Nécessite une connexion préalable
Routage	Chaque paquet a un routage indépendant	La route est établie à l’initialisation du circuit virtuel; chaque paquet suit cette route
Adressage	Chaque paquet contient l’adresse de la source et de la destination	Chaque paquet contient le numéro de circuit virtuel
Contrôle de congestion	Difficile et complexe	Facile lorsqu’il est possible d’allouer les ressources nécessaires (mémoires, bande passante, etc.) lors de l’établissement de circuit
Qualité de service	Ni contrôle d’erreurs, ni contrôle de flux (travail fait par l’utilisateur : couche transport) → alléger la tâche du réseau	garantie
Analogie	Le service postal	conversation téléphonique

2/ Réseau IP avec aiguilleur (Routeur):
·   Routeur (Router)?:
c’est un ordinateur ayant au moins 2 interfaces réseau et un logiciel d’aiguillage qui traverse les paquets selon sa table des routes. (travaille au niveau 3 du modèle OSI). Il peut être soit:
                   - un produit commercial (CISCO, Nortel, 3COM, …)
                   - un ordinateur avec UNIX ou NT avec le logiciel d’aiguillage
Utilités: - séparer 2 groupes d’ordinateurs ayant des vocations différentes
            - séparer un réseau contenant un nombre important d’ordinateurs
              - pour des raisons de sécurité

.

II- Routage des paquets :
But : acheminer un paquet vers sa destination finale en traversant un ensemble de réseaux.

1/ Principe de routage :
Lorsqu’un paquet doit être envoyé à une adresse IP donnée, l’ordinateur vérifie d’abord si l’adresse de destination est situé sur le même réseau local :

masque & @local = même partie réseau ?
·   Si l’adresse destination est sur le même réseau local → envoie du paquet directement à l’ordinateur destinataire. Sinon, l’ordinateur consulte sa table de routes pour identifier vers quel aiguilleur il enverra le paquet (généralement un seul).

·   Lorsqu’un ordinateur envoie un paquet sur Internet à un autre ordinateur (plusieurs aiguilleurs), le chemin du paquet n’est pas déterminé d’avance → chaque aiguilleur dans le parcours décide vers quel autre aiguilleur il envoie ce paquet.

2/ Redirection des routes:
Vu du PC:

Le routeur 192.168.2.1 sert le réseau 192.168.1.X

Le routeur 192.168.2.5 sert les autres réseaux

·     Si on configure notre PC en pointant le routeur 192.168.2.5 comme défaut et qu’on envoie un paquet à destination de 192.168.1.6, le routeur 192.168.2.5 ne sera pas en mesure d’acheminer les paquets vers le réseau 192.168.1.X
·     Dans ce cas, il renverra un message REDIRECT du protocole ICMP vers notre PC lui disant que pour le 192.168.1.X, le paquet doit être acheminé à l’autre routeur 192.168.2.1
·     Notre PC conservera cette information et enverra les prochains paquets au bon routeur
→ Chaque ordinateur se construit une table partielle des routes selon les informations renvoyées par les routeurs.

3/ Configuration simple d’un routeur CISCO :
Exemple d’un routeur avec 2 réseaux et Internet

Commande	Description
router rip	pour utiliser le protocole RIP
network 192.168.1.0	Annonce les routes connues sur le réseau 192.168.1.X
network 192.168.2.0	Annonce les routes connues sur le réseau 192.168.2.X
ip route 0.0.0.0 0.0.0.0 192.168.2.5	La route par défaut pour toutes les autres adresses inconnues se fait par le routeur 192.168.2.5

III- Les Algorithmes et les protocoles de routage :
But → Décider sur quelle ligne de sortie un paquet entrant doit être retransmis.

Comment ? : Généralement, les routeurs doivent collaborer pour trouver les meilleurs chemins.
Exemple : Toutes les routes optimales d’un nœud A vers les autres nœuds forment un arbre collecteur (construire l’arbre collecteur pour chaque nœud).

Classification :
- Statiques: Les routes sont pré-calculées et téléchargées dans les routeurs lors de l’initialisation du réseau.
- Dynamiques : Les routes changent selon les changements de la topologie du réseau (ajout et/ou élimination des liens et/ou des routeurs) et le trafic.
- Centralisés: Les routes sont calculées par un centre qui possède les informations nécessaires.
- Distribués: Collaboration entre les routeurs afin de déterminer les meilleures routes.

1- Le concept d’Autonomous System (AS) :

→ C’est un domaine de routage (réseaux+routeurs) sous la responsabilité d’une autorité unique (un réseau de société multinationale ou un fournisseur Internet). Il représente une architecture de routage indépendante des autres systèmes autonomes et identifié par un numéro unique (16 Bits) attribué par le NIC.
→ Un routeur dans un AS est dit «internal gateway», il implémente un protocole de routage appelé «Interior gateway Protocol»; Exemple de IGP’s: RIP, OSPF, IGRP.
→ Le protocole de routage entre «internal gateways» est appelé «Border Gateway Protocol», il sert à distribuer des informations de routage entre les providers.

2- Les algorithmes de routage statique :
è Le plus court chemin (Dijkstra) :
- Principe: À chaque étape: Choisir un nouveau nœud atteignable avec le coût minimal et ajouter l’arc, permettant de l’atteindre, à l’arbre.
→ Inondation (Flooding):
- Principe : Chaque paquet entrant est retransmis sur toutes les lignes de sortie, excepté sur la ligne d’arrivée. Les paquets dupliqués seront éliminés à l’arrivée.
- Avantages : → L’algorithme trouve toujours le meilleur chemin.
→ L’algorithme est robuste: la disparition de quelques nœuds intermédiaires est tolérée.
- Inconvénients : → Augmentation de la charge du réseau
→ Des paquets peuvent être dupliqués et circuler infiniment
Que faire pour les paquets dupliqués infiniment ? : Insérer un compteur dans chaque paquet (TTL) indiquant le nombre maximal de nœuds qu’il peut traverser. Ce compteur est décrémenté par chaque routeur traversé. Le paquet est éliminé lorsque le compteur devient nul.

3- Les algorithmes de routage dynamique :
→ Routage à vecteur de distance de Bellman-Ford : (Routage distribué)
- Principe : Chaque routeur connaît les distances qui le séparent de ses voisins. Toutes les T secondes, chaque routeur transmet à tous ses voisins son vecteur de routage, c'est-à-dire les routes qu’il connaît.
Une route est composée d’une adresse destination, d’une adresse de passerelle et d’une métrique indiquant le nombre de sauts nécessaires pour atteindre la destination. Une passerelle qui reçoit ces informations compare les routes reçues avec ses propres routes connues et met à jour sa propre table ou vecteur de routage: → si une route reçue comprend un plus court chemin,
→ si une route reçue est inconnue.

A, B et C : Routeurs
@₁ et @₂ : Adresses
0, 1, 2 … : Métriques
L : Local

- Exemple d’utilisation: les protocoles RIPv1 et IGRP.

→ Initialisation :
→ Premier échange :

→ Second échange :

- Amélioration apportée par RIP Version 2 :
→ Gestion de sous-réseaux et super-réseaux (CIDR et VLSM)
→ Utilisation de Multicast IP (l’adresse 224.0.0.9) au lieu de Broadcast IP.

M = F x

k1 et k2 sont des facteurs de pondération fixés par l’administrateur ou modifiés dynamiquement par la valeur du champ TOS.

- Différence entre RIP et IGRP : La différence la plus évidente se rapporte à la métrique. Si RIP compte seulement le nombre de sauts, IGRP annoncent jusqu’à cinq paramètres qui décrivent la métrique pour chaque route, calculée au moyen d’une formule mathématique :

   → La bande passante ou le débit « D »
   → Le délai « T »
   → La fiabilité « F »
   → La charge « C »
   → L’unité maximale de transmission.
- Inconvénients : → La taille des informations de routage est proportionnelle au nombre de routeurs du domaine,
→ Métrique difficilement utilisable : lenteur de convergence,
→ Bouclage, éventuellement à l’infini,
→ Pas de chemins multiples,
→ Coût des routes externes arbitraire.
→ Routage par information d’état de liens : l’algorithme Shortest Path First (SPF) :
- Principe : Périodiquement, chaque routeur fait les étapes suivantes:
→ Découvrir ses voisins: Envoyer un paquet spécial (HELLO) sur chaque ligne de sortie. Les routeurs qui recevront ce paquet doivent répondre en donnant leur nom, adresse réseau, etc.
→ Mesurer le temps d’acheminement vers ses voisins. Une solution consiste à envoyer un paquet spécial ECHO qui sera retourné par le nœud voisin. Comme temps d’acheminement, on prendra la moitié du temps aller retour du paquet ECHO.
→ Diffuser les informations collectées: Construire un paquet d’état de lien contenant les informations collectées (voisin, état up ou down, distance, etc.) et le diffuser à tous les nœuds du réseau en utilisant l’algorithme d’inondation.
→ Lorsque un message parvient à une passerelle, celle-ci met à jour la carte de liens et recalcule localement pour chaque lien modifié, la nouvelle route selon l’algorithme de Dijkstra qui détermine le plus court chemin pour toutes les destinations à partir d’une même source.
→ Les passerelles maintiennent une carte complète du réseau et calculent les meilleurs chemins localement en utilisant cette topologie.
- Exemple d’utilisation : les protocoles OSPF et integrated IS-IS.
- Avantages : → OSPF utilise la fonctionnalité “type de service” offerte par IP qui permet d’installer plusieurs routes pour une même destination, selon des critères différents (ex : délai court, débit important).
→ Si plusieurs routes vers une même destination sont de coûts équivalents, OSPF répartit la charge équitablement entre ces routes.
→ OSPF supporte l’adressage en sous-réseaux (subnets).
→ Découpe d’un système autonome en aréas.
→ Les liens extérieurs avec d’autres systèmes autonomes (via BGP par exemple) sont pris en compte.
→ Routage Hiérarchique :

- Problèmes des autres algorithmes de routage:
→ Augmentation de la charge de réseau (inondation)
→ Chaque routeur est obligé à connaître tous les autres
→ Table de routage assez volumineuse
→ Demande beaucoup d’espace et la recherche prend beaucoup de temps.
- Solution:
→ Découper le réseau en régions
→ Chaque routeur connaît les autres routeurs dans sa région (intra-routage)
→ Chaque routeur connaît les chemins vers les autres régions (inter-routage)
- Exemple d’utilisation : le protocole OSPF.
→ Routage Hybrides et l’algorithme DUAL (Diffusing Update Algorithm) :
- Principe : l’algorithme DUAL permet au routeur de calculer le meilleur chemin vers chaque sous-réseau et aussi de trouver des chemins alternatifs au cas où la route courante deviendrait inutilisable.
- Avantage : convergence rapide.
- Exemple d’utilisation : Le protocole EIGRP (Enhanced IGRP).

IV- Les Algorithmes de contrôle de congestion :

→ Problème : Quand le nombre de paquets qui circulent dans le réseau devient très grand (plus que sa capacité), les performances de ce dernier se dégradent.
→ Solutions :
- Préventives: Contrôler le nombre de paquets qui rentrent dans le réseau par unité de temps.
- Correctives: Envoyer des messages aux nœuds pour qu’ils diminuent leurs trafics.
Cas d’un Circuit virtuel : Avant d’établir un circuit, s’assurer qu’il n’y aura pas de congestion puis essayer de choisir des routes non congestionnées et refuser l’établissement de circuit, si cela n’est pas possible.

Bibliographie :
-      TCP/IP simplifié → MARC BLANCHET / Les éditions LOGIQUES
-      Réseaux et télécoms → Claude Servin / DUNOD
-      INTRO CCNA → Wendell Odom / CISCO SYSTEMS PRESS
-      TCP/IP – Le routage dynamique → Ph. Gautier et F. Playe / CentralWeb
-      La couche Réseau → IFT n° 14165 / Document Internet
-      Cours CCNA2 v3.1 : Théorie et pratique du routage