Les protocoles de routage
Introduction
Un réseau informatique est composé d’un ensemble de routeurs interconnectés
par des liens multiples
Ces routeurs permettent de connecter des hôtes entre eux et d’acheminer leurs
paquets
La connaissance requise pour acheminer ces paquets est obtenue grâce à la
fonction de routage
Le rôle du routage consiste à trouver les bons chemins pour amener chaque
paquet à sa destination.
Il existe au sein d'un réseau plusieurs chemins possibles
La fonction de routage doit orienter le paquet vers le meilleur chemin. C-a-
d , le chemin qui mènera le paquet au plus près de sa destination et le plus vite
possible
Classement des fonctions de routage
On peut réaliser la fonction de routage en utilisant des techniques différentes
Ces techniques sont classées sous plusieurs critères :
Statique dynamique
Routage
Centralisé Distribué
Routage statique
• les administrateurs configurent manuellement les routeurs un à un au sein
du réseau
• Une route par défaut peut également être configurée de manière
statique.
• Si la structure d’inter-réseau change ou que de nouveaux réseaux deviennent
disponibles, l’administrateur doit prendre en charge les changements
manuellement
• Si une mise à jour n’est pas effectuée de manière opportune, les
informations de routage peuvent être incomplètes ou inexactes, entraînant
des retards, voire la perte éventuelle de paquets.
Routage dynamique
• La mise à jour de la table de routage par configuration statique manuelle n’est pas
toujours faisable
• Des protocoles de routage dynamiques sont utilisés pour configurer
automatiquement les routes
• Un protocole de routage est l’ensemble de règles permettant aux routeurs de partager
leurs informations de routage de manière dynamique
• Quand un routeur prend conscience de changements sur les réseaux connectés, ces
informations sont transmises aux autres routeurs
• Quand un routeur reçoit des informations sur des routes nouvelles ou modifiées, il met
à jour sa propre table de routage et transmet , à son tour, ces informations aux autres
routeurs
• L’échange d’informations de route ajoute une surcharge qui occupe une partie de la
bande passante du réseau.
Exemples de protocoles de routage dynamiques:
• RIP (Routing Information Protocol)
• EIGRP (Enhanced Interior Gateway Routing Protocol)
• OSPF (Open Shortest Path First)
•BGP (Border Gateway Protocol)
Classement des fonctions de routage
Routage centralisé
La procédure de routage est centralisée totalement au niveau d'un centre de contrôle.
Ce centre de contrôle doit avoir une vision complète du réseau, calculer les bons
chemins à chaque changement de la topologie et les envoyer aux routeurs.
Permet d’avoir un contrôle fin du routage
en cas de panne du centre de contrôle ou si celui-ci est isolé d'une partie du réseau, le
réseau peut être paralysé
Routage distribué
L’algorithme de routage est distribué sur les routeurs
Chaque routeur récupère des informations de ses voisins, fait ses propres calculs et
prends des décisions concernant sa table de routage
Certaines erreurs de routage peuvent survenir (incohérences, boucles, trou noirs, …etc)
Stratégies de routage
La stratégie de routage définit le meilleur moyen d’acheminer un paquet de la source à
la destination
Plusieurs stratégies existent et diffèrent en fonction de plusieurs paramètres (topologie
du réseau, moyens de connexion, mobilité des nœuds, …etc.)
La stratégie de routage influe sur les performances du protocole. Ces paramètres sont :
Le cout :
c’est le volume d’information supplémentaire induit par le protocole
La Qualité :
- nombre de sauts pour atteindre sa destination,
- rapidité de la traversée, …
La robustesse :
capacité du protocole à fonctionner en cas de pannes de quelques éléments
La réactivité :
capacité du protocole à réagir en cas de changement de la topologie
Quelques stratégies de routage (1)
Routage aléatoire
Le routeur choisit un chemin aléatoire et espère que
le paquet arrive à sa destination
Contrairement aux apparences, cette
stratégie peut donner de bons résultats
en cas d’une topologie fortement maillée
ou mobile
Surcout Qualité des routes robustesse Réactivité
pas de surcout Médiocres en général pas sensible aux Ne nécessite aucun
pannes temps de convergence
en cas de changement
de topologie
Quelques stratégies de routage (2)
Routage à inondation
A la réception d’un paquet, le routeur le
transmet à tous les routeurs auxquels il est
connecté, sauf à celui qui l’a envoyé
La stratégie offre la garantie pour le paquet
d’atteindre sa destination mais au cout d’une
grande surcharge du réseau
Adapté à certaines situations particulières
(forte mobilité des nœuds par exemple)
Surcout Qualité des routes robustesse Réactivité
Très élevé L’algorithme trouve Très robuste Ne nécessite aucun temps
toutes les routes (Bonne de convergence en cas de
est mauvaises) changement de topologie
Quelques stratégies de routage (3)
Routage pré calculé
Un centre de contrôle recueille toutes
les informations de la topologie du réseau
Il exécute ensuite un algorithme pour retrouver le
plus court chemin vers la destination
Tout le trafic est envoyé vers le centre de calcul
Le centre de calcul renvoie le paquet en incluant
la liste des routeurs que le paquet doit traverser
Surcout Qualité des routes robustesse Réactivité
Elevé Les routes passent Le centre de Correcte dans la
toutes par le centre contrôle est une mesure ou le centre
de calcul ressource critique de contrôle est
prévenu de tout
changement
Les stratégies dominantes
Actuellement deux stratégies de routage dominent et sont largement implémentées
sur la quasi totalité des routeurs
Ces deux stratégies se basent sur la communication entre les routeurs pour définir
les chemins optimaux
Ces deux stratégies sont :
Le routage à vecteur de distance
Le routage à état des liens
Routage à vecteur de distance
Les routeurs s’échangent régulièrement leurs informations concernant les routes
qu’ils connaissent ainsi que les couts des routes
En pratiques, les routeurs diffusent les routes se trouvant dans leurs tables de
routage aux voisins,
Quand un routeur reçoit une nouvelle route inconnue, il la rajoute dans sa table de
routage
Si un routeur reçoit une route qu’il connait déjà, celle-ci est prise en compte si elle
est meilleure que l’ancienne
Une fois sa table de routage mise à jour, le routeur la propage vers ses voisins
Au bout d’un certain temps (temps de convergence), tous les routeurs connaitront
les routes vers toutes les destinations
Surcout Qualité des routes robustesse Réactivité
Toute la table de Bonne qualité Peu sensible aux Peut être long si le
routage est pannes réseau est grand
transmise aux
voisins
immédiats
Routage à état des liens
Les routeurs ne s’échangent pas les routes mais leurs liens et leurs états (actif,
inactif, bande passante, …etc)
Au bout d’un certain temps, chaque routeur aura constitué une base de donnée
de la topologie complète du réseau
Chaque routeur doit calculer lui-même le chemin vers toutes les destinations du
réseau en utilisant ces données et insérer ces routes dans sa table de routage
Les algorithmes utilisés pour le calcul du plus court chemin sont assez complexes
et supposent que les routeurs soient dotés de capacités suffisantes
Surcout Qualité des routes robustesse Réactivité
Des informations Bonne qualité Peu sensible aux Pas très sensible au
sur l’état des pannes diamètre du réseau
liens à tous les
routeurs
synthèse
Protocole surcout Qualité routes Robustesse Réactivité
Statique
Aléatoire
Inondation
Pré-calculé
Vecteur de distance
Etat des liens
Performances Faibles Bonnes performances
Système autonome (AS)
Un système autonome est un groupement de réseaux informatiques appartenant á
une méme organisation
Généralement, seules les grandes organisations sont qualifiées de systèmes autonomes
Fournisseurs d’accès internet
Universités,
Grandes entreprises, …etc
A l’intérieur d’un système autonome, la stratégie de routage est sous la responsabilité
de l’organisation
Les protocoles de routage utilisés dans un système autonome sont dits IGP (Interior
Gateway Routing Protocols)
RIP : Routing Information Protocole : Protocole á vecteur de distance
OSPF : Open Shortest Path First : Protocole a état des lien
EIGRP : Enhanced Interior Gateway Routing Protocol : Protocole hybride
mélangeant les techniques de routage á état des liens et á vecteur de distance.
Protocole performant mais propriétaire á CISCO
Système autonome (AS)
OSPF
OSPF EIGRP
RIP
OSPF
OSPF
RIP
EIGRP
OSPF
RIP
AS (FAI par exemple)
Interconnexion des systèmes autonomes
Les systèmes autonomes sont interconnectés entre eux pour former le réseau internet
Ces systèmes autonomes qui sont formés généralement des fournisseurs d’accès
internet sont identifiés grâce á un numéro unique sur 32 bits,
Les interconnexions entre systèmes autonomes sont réalisés á travers des liaisons
pair a pair ou á travers des points d’échange après la négociation des offres de
service
Pour router des paquets entre les systèmes autonomes, on utilise une autre
catégorie de protocoles de routage dit externe ou EGP (Exterior Gateway
Protocol)
Ce type de protocole n’est pas activé sur tous les routeurs mais uniquement sur les
routeurs se trouvant aux bordures des réseaux de systèmes autonomes
En pratique, un seul protocole de routage externe est utilisé sur internet, ce
protocole est dit BGP (Border Gateway Protocole)
La stratégie de routage utilisée est la stratégie á vecteur de distance
Interconnexion de systèmes autonomes
BGP BGP
AS1 AS2
BGP
BGP
BGP
AS4
AS3
Interaction entre les protocols de routage
Plusieurs protocoles de routage peuvent s’exécuter en même temps sur un routeur
Chacun des protocoles trouve des routes en fonction de sa stratégie
Tous ces protocole interagissent avec la table de routage sur laquelle les route sont
installées
Les processus de transfert de paquets reposent sur cette table de routage pour
trouver la destination des paquets.
Des routes différentes peuvent être trouvées par les différents protocoles, le
routeurs installe uniquement les meilleurs routes dans la table de routage, les autres
routes sont enregistrée comme des routes de secours
Processus selection de routes
Le routeur sélectionne la route á mettre dans la table de routage selon trois critéres
La distance administrative
La métrique
La longueur du prefixe
Processus d’ajout de routes
1
192.168.24.0/24
EIGRP : 192.168.24.0/24 3 2
OSPF : 192,168,24,0/24 2
RIP : 192.168.24.0/24 1 3
Table de routage
……..
D 192.168.24.0/24 via 3
……..
Processus de selection de routes
1
EIGRP : 192.168.32.0/24 3 2
OSPF : 192.168.32.0/25 2
RIP : 192.168.32.0/27 1 3
Table de routage
……..
D 192.168.32.0/24 via 3
O 192.168.32.0/25 via 2
R 192.168.32.0/27 via 1
……..
Processus de decision de routage
Quand un paquet arrive á un routeur, ce dernier examine la table de routage pour
trouver la destination
La destination choisie est celle ayant le plus long préfixe correspomdant
1
2
192.168.32.1 ? Via 1
Table de routage
192.168.32.100 ?Via 2
……..
192.168.32.130 ?Via 3 D 192.168.32.0/24 via 3
O 192.168.32.0/25 via 2
R 192.168.32.0/27 via 1
……..
Résumé du processus de routage
