Routage & Commutation 2

Séance N°4
Miloud LAHMAIM

ENSA de Marrakech

1
 Protocole d’état de lien

368
 Introduction
 Les protocoles de routage à vecteur de distance revenaient à
utiliser des panneaux de signalisation routière pour nous guider
vers la destination
– Les voyageurs font confiance aux panneaux de signalisation pour leur
indiquer la distance exacte jusqu‟à la ville suivante
– Un routeur fait confiance à un autre routeur pour lui indiquer la
distance réelle jusqu‟au réseau de destination.
– Un routeur détermine son chemin préféré en fonction de cette distance
 Les protocoles de routage d’état des liaisons reviennent à
utiliser une carte routière
– Les voyageurs utilisent une carte pour trouver la route vers une autre
ville
– Les routeurs créent une carte topologique du réseau
– Les routeurs utilisent cette carte pour déterminer le chemin le plus
court vers une autre destination.

369
 Introduction
 Protocoles de routage à état de liens
– connu comme les algorithmes de plus court
chemin en premier
– également appelés protocoles SPF (Shortest
Path First),
– Ces protocoles sont construits sur la base de
l'algorithme SPF d‟Edsger Dijkstra.

370
 Algorithme SPF
 L’algorithme de Dijkstra est en général désigné sous le nom
d’algorithme SPF (shortest path first - chemin le plus court
d’abord).
 Cet algorithme cumule les coûts de chaque chemin, depuis leur
source jusqu’à leur destination.
 Le coût du plus court chemin pour que R2 envoie un paquet au
réseau local rattaché à R3 est de 27.

371
 Protocole d’état de lien
 Les routeurs qui exécutent un protocole de routage d’état
des liaisons envoient des informations sur l’état de leurs
liaisons vers d’autres routeurs du domaine de routage.
 L’état de ces liaisons concerne les réseaux qui lui sont
directement connectés et contiennent des informations sur
le type de réseau et tous les routeurs de voisinage, d’où le
nom protocole de routage d’état des liaisons.
 L’objectif ultime est que chaque routeur reçoive les
informations sur l’état des liaisons de tous les autres
routeurs de la zone de routage. Avec ces informations,
chaque routeur peut créer sa propre carte topologique du
réseau et calculer de façon indépendante le chemin vers
chacun des réseaux.
 Il est basé sur la technique Shortest Path First (SPF)
372
 Processus de routage
1. Chaque routeur prend connaissance de ses propres réseaux
directement connectés.
2. Chaque routeur est responsable de la détection de ses voisins sur les
réseaux connectés directement en échangeant des paquets Hello
avec d’autres routeurs d’état de liaisons situés sur des réseaux
directement connectés.
3. Chaque routeur crée un LSP (Link-State Packet) contenant l’état de
chaque liaison directement connectée.
4. Chaque routeur diffuse son LSP à l’ensemble de ses voisins, qui
stockent tous les LSP qu’ils reçoivent dans une base de données.
Les voisins diffusent ensuite le LSP à leurs voisins, jusqu’à ce que
tous les routeurs de la zone aient reçu le LSP.
5. Chaque routeur utilise la base de données pour élaborer une carte
complète de la topologie et calcule le meilleur chemin vers chaque
réseau de destination. L’algorithme SPF sert à construire la carte de
la topologie et à déterminer le meilleur chemin vers chaque réseau.
373
 1. Réseaux directement connectés
 Lien ou liaison désigne une interface de routeur.
 Les état des liaisons incluent :
– adresse IP et masque de sous-réseau de l‟interface ;
– type de réseau, par exemple Ethernet (diffusion) ou liaison série point-à-point ;
– coût de la liaison ;
– éventuels routeurs voisins sur cette liaison.

374
 2. Détection des voisins
 Les routeurs qui utilisent le même protocole de routage à état de
liens échangeront des paquets hello pour détecter les voisins
– Un voisin est un routeur qui prend en charge le même protocole d‟état
des liaisons.
 Une fois que les routeurs ont découvert leurs voisins, ils forment
une adjacence
– Deux voisins adjacents échangeront des paquets hello
– Ces paquets serviront à surveiller l‟état du voisin.

375
 3. Création des LSPs
 chaque routeur crée un paquet d’état des liaisons (LSP)
contenant l’état de chacune des liaisons directement
connectées.
 Une fois qu’un routeur a détecté les voisins, il est en mesure de
créer des paquets d’état des liaisons (LSP) relatifs à ses
propres liaisons.

376
 4. Diffusion des LSPs
 Une fois que les LSP sont créés, ils sont transmis
aux voisins en utilisant des LSA (Link State
Advertisement)
 Après Les voisins le retransmet aux autres
(inondation)
 Les LSP n’ont pas besoin d’être envoyés de
façon périodique. Un LSP doit être envoyé
uniquement :
– Au démarrage du routeur ou du processus de
routage
– Lorsque il y a un changement topologique,
377
 5. Création d’une base de données d’état des liaisons

 Chaque routeur mémorise ces enregistrements dans une

base de données dites `Link State DataBase` (LSDB).
 La LSDB est construite sur la base des LSPs reçues

378
 6. Elaboration d’une carte de la topologie et calcule le meilleur
chemin

 Lorsque la base de données d’état des liaisons

est complète, chaque routeur de la zone de
routage peut maintenant :
– mettre à jour la carte de liens
– Puis, il recalcule localement pour chaque lien modifié, le
meilleur chemin vers toute destination
– Le calcul est basé sur l‟algorithme SPF

379
 Arborescence SPF
 Le processus débute en examinant l'information
LSP de R2
– R1 ignore le premier paquet LSP
 Raison: R1 connaît déjà son lien directement connecté à R2
– R1 utilise le second paquet LSP
 Raison: R1 peut créer un lien de R2 vers R5.
 Cette information est ajoutée à l'arbre SPF de R1
– R1 utilise le troisième paquet LSP
 Raison: R1 apprend que R2 est connecté au réseau
10.5.0.0/16.
 Ce lien est ajouté à l'arbre SPF de R1.

380
 Arborescence SPF
 Traitement de LSP de R3:
– R1 ignore le premier paquet LSP
 Raison: R1 connaît déjà son lien directement connecté à R3
– R1 peut utiliser le deuxième LSP
 Raison: créer une liaison de R2 vers R4,
 Cette information est ajoutée à l‟arborescence SPF.
– R1 utilise la troisième LSP,
 Raison: R1 a appris que R3 possède un réseau 10.6.0.0/16,
avec un coût de 2, sans voisin.
 Ce lien est ajouté à l‟arbre SPF de R1.

381
 Arborescence SPF
 Traitement de LSP de R4:
– R1 ignore le premier paquet LSP
 Raison: R1 connaît déjà son lien directement connecté à R4
– R1 ignore le deuxième paquet LSP
 Raison: R1 connaît déjà le réseau 10.6.0.0.0/16 par R3.
– R1 peut utiliser le troisième LSP
 Raison: créer une liaison de R2 vers R5 en passant par R4
 Cette information est ajoutée à l‟arborescence SPF.
– R1 utilise la quatrième LSP,
 Raison: R1 a appris que R4 possède un réseau 10.8.0.0/16, avec
un coût de 2, sans voisin.
 Ce lien est ajouté à l‟arbre SPF de R1.

382
 Arborescence SPF
 Traitement de LSP de R5:
– R1 ignore le premier paquet LSP
 Raison: R1 connaît déjà son lien directement connecté à R2
– R1 ignore le deuxième paquet LSP
 Raison: R1 connaît déjà son lien directement connecté à R4
– R1 utilise la troisième LSP,
 Raison: R1 a appris que R5 possède un réseau 10.11.0.0/16,
avec un coût de 2, sans voisin.
 Ce lien est ajouté à l‟arbre SPF de R1.

383
 Arborescence SPF
 Le chemin le plus court
– Le chemin le plus court vers une destination est
déterminé en ajoutant les coûts & en trouvant le coût le
plus bas

384
 Table de routage
 Une fois que l'algorithme SPF a déterminé les routes
de plus court chemin, ces routes sont placées dans la
table de routage.

385
 Protocole à état de liens
 Éléments requis pour un protocole de routage à
état de liens
– Mémoire
 Les protocoles de routage à état de liens utilisent plus de
mémoire pour sauvegarder la base de données
– Processus
 Plus de processus CPU est exigé pour l‟exécution de
l‟algorithme SPF
– Bande passante
 Au démarrage initial des protocoles de routage à état de liens,
plus de bande passante est consommée pour l‟inondation des
paquets LSP

386
 Avantages du protocole à état de liens

 Avantages du protocole de routage à état de liens:

– Chaque routeur crée sa propre carte topologique du
réseau pour déterminer le chemin le plus court
– L‟inondation immédiate de paquets LSP permet une
convergence plus rapide
– Les paquets LSP ne sont envoyés qu‟en cas de
modification de la topologie et contiennent uniquement
les informations concernant cette modification
– les paquets LSP ne concernent que les liens directs
entre routeurs et ne sont donc pas proportionnels au
nombre de réseaux dans le domaine (vs V-D).
– Une conception hiérarchique est utilisée lors de
l‟implémentation de plusieurs zones.
387
 Protocole à état de liens
 L’utilisation et la configuration de plusieurs zones
permet de réduire la capacité des éléments requis
pour le protocole d routage à état de liens

388
 Protocole à état de liens
 Deux protocoles de routage d’état des liaisons
sont utilisés pour le routage du trafic IP :
– le protocole OSPF (Open Shortest Path First )
 conçu par le groupe de travail OSPF de l‟IETF. il en existe
aujourd‟hui deux versions :
 OSPFv2 : OSPF pour les réseaux IPv4 (RFC 1247 et RFC
2328)
 OSPFv3 : OSPF pour les réseaux IPv6 (RFC 2740)
– le protocole de routage IS-IS (Intermediate System-
Intermediate System ).
 à l‟origine conçu par ISO (ISO 10589) pour l‟ensemble de
protocoles OSI et non pour TCP/IP.
 Par la suite Integrated IS-IS ou Dual IS-IS prend en charge les
réseaux IP.
389  Principalement utilisé par les FAI et les opérateurs télécom
OSPF
Open
S hortest
P ath
F irst
 Introduction
 Le développement du OSPF a débuté en 1987
 1989 OSPFv1 sortie dans la RFC 1131
– Version expérimentale & jamais déployée
 1991 OSPFv2 sortie dans la RFC 1247
 1998 OSPFv2 mis à jour dans la RFC 2328
 1999 OSPFv3 publiée dans la RFC 2740

391
 OSPF
Encapsulation du message OSPF:
 Type de paquets OSPF: 5 types
 Entête du paquet OSPF: Contient ID de routeur, ID de la zone et
“Type code” pour le type du paquet OSPF
 Entête du paquet IP : contient adresse IP source et destination
et champ protocole à 89

392
 OSPF
Types de paquets OSPF:
 Il y a cinq différents types de LSP OSPF.

393
 Protocole Hello
 Intérêt de paquet Hello OSPF :
– Découvrir les voisins OSPF & établir des adjacences
– Annoncer des paramètres sur lesquels les routeurs doivent être d'accord pour devenir voisins
– Utilisés par les réseaux multi-accès pour élire un designated router et un backup designated
router
 Les champs importants de paquet Hello:
– Type : Hello (1), DD (2), LS Request (3), LS Update (4), LS ACK (5)
– ID du routeur : ID du routeur d‟origine
– ID de la zone : zone d‟origine du paquet
– Masque de réseau : masque de sous-réseau
– Intervalle Hello : nombre de secondes qui s‟écoulent entre deux envois de paquets Hello
– Priorité du routeur : utilisé dans la sélection du routeur désigné ou du routeur désigné de
secours
– Routeur désigné (DR) : ID du
routeur désigné, le cas échéant
– Routeur désigné de secours
(BDR) : ID du routeur désigné de
secours, le cas échéant
– Liste des voisins : indique l’ID
de routeur OSPF du ou des
routeurs voisins

394
 Algorithme OSPF
 Les routeurs OSPF construisent et maintiennent une base
de données à état de liens contenant les LSA reçues
d'autres routeurs
 L'information trouvée dans la base de données est utilisée
pour l'exécution de l'algorithme SPF de Dijkstra
 L'algorithme SPF est utilisé pour créer l'arbre SPF
 L'arbre SPF est utilisé pour fournir à la table de routage IP
les meilleurs chemins vers chaque réseau.

398
 Distance administrative
 La distance administrative pour OSPF est 110
 Le protocole OSPF est préféré aux protocoles IS-
IS et RIP.

399
 Authentification OSPF
 Permet de chiffrer et authentifier leurs informations de
routage.
 Les routeurs accepteront seulement l'information de
routage d'autres routeurs qui ont été configurés avec le
même mot de passe ou information d'authentification

400
 Mesure OSPF
 La mesure de l’OSPF est le coût
 Plus le coût est faible, plus la route est meilleure
 Le coût est basé sur la bande passante d'une interface
– Coût = 10^8/bandwidth
– Le résultat est appelé bande passante de référence.
 Elle peut être modifiée en utilisant la commande
auto-cost reference-bandwidth

401
 Mesure OSPF
 Le coût d’une route OSPF est la valeur cumulée
depuis un routeur jusqu’au réseau de destination.

402
 Mesure OSPF
Modification du coût du lien
 Commandes utilisés pour modifier le coût du lien:
– bandwidth bandwidth-kbps permet de modifier la
bande passante
– ip ospf cost permet de spécifier directement le coût
associé à l'interface

404
 OSPF et les réseaux multi accès
 Un réseau à accès multiple est un réseau comportant
plus de deux périphériques sur le même support partagé.
 Sur les réseaux point à point, en revanche, le réseau ne
comporte que deux périphériques, un à chaque extrémité.

405
 OSPF et les réseaux multi accès
 Deux difficultés présentés par les réseaux multi
accès pour OSPF
– La création de contiguïtés multiples, une pour chaque
paire de routeurs.
– Une diffusion massive de LSA

406
 OSPF et les réseaux multi accès
Diffusion des LSA
 Les routeurs OSPF diffusent les LSA lorsque OSPF est
initialisé ou qu’une modification de topologie intervient.
 Pour tous les LSA envoyées, il doit y avoir un acquittement
renvoyé au routeur qui a émis la mise à jour.
 conséquence: beaucoup de bandwidth utilisée sur le
réseau

407
 OSPF et les réseaux multi accès
 Solution à l'inondation LSA est l'utilisation du Designated router
(DR) et Backup designated router (BDR)
 Tous les autres routeurs deviennent des DROthers
 Les routeurs DR & BDR sont des points de collecte et de
distribution des LSA envoyées et reçues
 Envoi & Réception des LSA
– DRothers envoient leurs LSAs via une adresse multicast 224.0.0.6 au
DR & BDR
– DR transmet les LSA via une adresse multicast 224.0.0.5 aux autres
routeurs

408
 OSPF et les réseaux multi accès
Processus de sélection du DR/BDR
 La sélection du DR/BDR a lieu seulement sur les
réseaux multi accès
 Critères pour sélectionner un DR/BDR
– DR : est le routeur avec la priorité d‟interface OSPF la
plus élevée.
– BDR : Il s‟agit du routeur dont la priorité d‟interface
OSPF est la seconde valeur la plus élevée.
– Si les priorités d‟interface OSPF sont égales, c‟est le
routeur dont l‟ID est le plus élevé qui est choisi.

409
 OSPF et les réseaux multi accès
Processus de sélection du DR/BDR
 ROthers ne constitue des contiguïtés FULL qu’avec le DR et le BDR
 tous les routeurs DROther du réseau à accès multiple continueront de
recevoir des paquets Hello de tous les autres routeurs DROther.

410
 OSPF et les réseaux multi accès
Synchronisation de la sélection du DR/BDR
 Le processus de sélection du DR et du BDR a lieu aussitôt que
le premier routeur ayant une interface configurée OSPF est
activé sur un réseau à accès multiple
 il se peut qu’un routeur dont l’ID n’est pas le plus élevé
devienne le DR. Cela peut signifier que son amorçage a pris
moins de temps.
 Si un nouveau routeur entre dans le réseau une fois que le DR
et le BDR ont été sélectionnés, il ne devient pas DR ou BDR,
même si sa priorité d’interface OSPF ou son ID de routeur est
plus élevé que ceux du DR ou du BDR courants.
 Quand un DR est sélectionné , il reste DR jusqu'à ce que
– le DR tombe en panne ;
– le processus OSPF sur le DR échoue ;
– l‟interface à accès multiple du DR ne fonctionne plus.
411
 OSPF et les réseaux multi accès
Manipulation du processus de sélection du DR/BDR
 Si on veut influencer la sélection du DR & BDR
sans procéder à une nouvelle configuration, alors
on peut faire les choses suivantes :
– Démarrer le DR en premier, suivi du BDR et booter tous
les autres routeurs ensuite; ou
– Désactiver l'interface sur tous les routeurs, suivi d'un no
shutdown sur le DR, puis sur le BDR, et enfin tous les
autres routeurs

412
 OSPF et les réseaux multi accès
Priorité d’interface OSPF
 Au lieu d’utiliser uniquement l’ID du routeur pour décider quels
routeurs deviendront DR et BDR, il est préférable de contrôler le choix
de ces routeurs à l’aide de la commande d’interface ip ospf priority
– Router(config-if)# ip ospf priority {0 - 255}
– 0 indique que le routeur ne veut pas participer au processus d'élection du
DR et BDR
– 1 est la valeur par défaut de la priorité définie sur les interfaces des
routeurs

Désactiver puis activer les interfaces OSPF des routeurs

413
 Router ID
 C'est une adresse IP utilisée pour identifier un
routeur.
 3 critères pour déterminer le router ID
– Utiliser l'adresse IP configurée avec la commande
OSPF router-id
 A priorité sur les adresses IP des interfaces loopback et
physiques
– Si la commande router-id n'est pas utilisée alors le
routeur choisit l'adresse IP la plus haute sur les
interfaces loopback
– Si aucune interface loopback est configurée, alors le
routeur choisit l'adresse IP la plus haute configurée sur
n'importe quelle interface utilisée.

414
 Interface de bouclage
 Une interface de bouclage (Lo) est une interface
purement logicielle utilisée pour émuler une interface
physique.
 Elle peut se voir attribuer une adresse IP.
 Elle peut recevoir une requête ping et le sous-réseau,
être annoncé dans les mises à jour de routage.
 Les interfaces de bouclage sont utiles à la création de
réseaux supplémentaires sans avoir à ajouter
d’autres interfaces physiques au routeur.
 Elles sont parfaites pour simuler plusieurs réseaux
reliés au même routeur.

415
Interface de bouclage

 interface loopback {n°}

 Configuration d’une interface logique
 Mode de configuration globale

Router(config)# interface loopback 1

Router(config-if)# ip address 10.0.0.1 255.0.0.0
 Router ID
 Commandes utilisées pour vérifier le router ID
– Show ip protocols
– Show ip ospf
– Show ip ospf interface
 Comme nous n’avons pas configuré d’ID de routeur ou
d’interface de bouclage, alors l’ID de chacun des routeurs
est déterminé par le critère numéro 3 de la liste

417
 Configuration de base
 La commande OSPF router-id Introduit dans la
version IOS 12.0(T). La commande est
– Router(config)#router ospf process-id
– Router(config-router)#router-id ip-address
 Si vous avez modifié l’ID de routeur alors recharger le
routeur ou utiliser la commande suivante :
– Router# clear ip ospf process
 Router ID & Adresses loopback
– L'adresse la plus haute de l'interface loopback sera utilisée
comme router ID si la commande router-id n'est pas utilisée.
– Avantage de l'interface loopback
 l'interface loopback est toujours active (up)  stabilité d'OSPF

418
Configuration de base

 router ospf {id}

 Activation d’OSPF sur le routeur
 Mode de configuration globale
 id : n° de processus (1<=id<=65535)
Configuration de base
 network adresse_réseau masque_générique area area-id
 Indique les réseaux directement connectés au routeur
 Ces réseaux (ou sous-réseaux) seront inclus dans les
mises à jour de routage OSPF.
 Les interfaces de routeur qui correspond aux adresses de
ces rééseaux sont activées pour envoyer et recevoir des
paquets OSPF.
 Configuration de base
Vérification d'OSPF
 La commande show ip ospf neighbor peut être utilisée pour vérifier
et réparer les relations de voisinage OSPF. La commande affichera :
– Neighbor ID - ID du routeur voisin.
– Pri - priorité OSPF de l‟interface.
– State - état OSPF de l‟interface. L‟état FULL signifie que le routeur et son
voisin ont des bases de données d‟état des liaisons OSPF identiques.
– Dead Time - Address - Interface
 Pas relations de voisinage OSPF lorsque :
– Le routeur ID d'un routeur voisin n'est pas affiché
– Un état full n'est pas affiché
 Conséquence de la non adjacence:
– Pas d'information à état de lien échangé
– Arbre SPF & tables de routages non cohérentes

421
 Configuration de base
Vérification d'OSPF
 Les autres commandes de dépannage OSPF:
– show ip protocols: affiche l‟ID de routeur, l‟ID de processus OSPF,
les réseaux d‟annonce du routeur, et la distance administrative par
défaut,
– show ip ospf: affiche l‟ID de routeur, l‟ID de processus OSPF, SPF
schedule delay (délai d‟attente programmé de SPF). les informations
de zone OSPF, dernière fois où l‟algorithme SPF a été calculé.
– show ip ospf interface affiche les intervalles Hello et Dead

422
 Configuration de base
 Examen de la table de routage
– Utiliser la commande show ip route
 Un “O” au début d'une route indique que la source de la route
est OSPF
– Noter qu'OSPF ne résume pas automatiquement les
routes.

423
 OSPF: Configuration supplémentaire
Redistribution d'une route par défaut
 Le routeur connecté à Internet (FAI) est nommé un routeur
frontière d'un système autonome (Autonomous System
Boundary Router ASBR)
 Ce routeur sert à diffuser une route par défaut aux autres
routeurs du domaine de routage OSPF.
 La commande utilisé pour
– configurer la route par défaut est ip route 0.0.0.0 0.0.0.0 interface-
sortie
 R1(config)#ip route 0.0.0.0 0.0.0.0 loopback 1
– Diffuser la route statique est default-information originate
 Exemple: R1(config-router)#default-information originate

424
 OSPF: Configuration supplémentaire

425
 OSPF: Configuration supplémentaire
 Modification de la bande passante de référence
– Cout = 10^8/bande passante
– 10^8 = 100 000 000 représente la bande passante de référence
– Puisque les vitesses des liens deviennent plus rapides (Gigabit Ethernet), il peut
être nécessaire de changer la valeur de la bande passante de référence
– la commande utilisée est auto- cost reference-bandwidth

Table de routage de
R1 avant et après les
modifications
426
 OSPF: Configuration supplémentaire
Modification des intervalles OSPF
– Conséquence : Détection plus rapide des défaillances
– Les intervalles Dead et Hello OSPF peuvent être
modifiés manuellement à l‟aide des commandes:
 Router(config-if)# ip ospf hello-interval seconds
 Router(config-if)# ip ospf dead-interval seconds
– Attention: Les intervalles Hello & Dead doivent être
identiques entre les voisins

427
 OSPF: Résumé
 Protocole de routage intérieur (IGP)
 Protocole à état de lien
 Protocole de routage classless
 Utilisation d’aires (area) au sein d’un même système
autonome (AS)
 Supporte le VLSM
 Métrique  coût
 Distance administrative  110
 Chaque noeud connaît l’existence de ses voisins
adjacents
 Construction de l’arbre SPF (Shortest Path First tree)
 Utilisation de l’algorithme Dijkstra
428