Architectures, Protocoles et Administration réseaux
Chap : Protocoles de routage par état de liaisons, OSPF
Rhouma Rhouma
https://sites.google.com/site/rhoouma
ESEN
Janvier 2015
1 / 87
Plan
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
2 / 87
Plan
Routage d’état de lisaison
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
3 / 87
Routage d’état de lisaison
Les protocoles de routage d’état des liaisons sont également
appelés protocoles SPF (Shortest Path First), car ils sont conçus
sur la base de l’algorithme SPF d’Edsger Dijkstra.
Les protocoles de routage d’état de liaisons IP sont présentés
dans la figure :
protocole OSPF (Open Shortest Path First) ;
protocole de routage IS-IS.
4 / 87
Routage d’état de lisaison
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.
chaque routeur exécute l’algorithme SPF et détermine le coût
depuis sa propre perspective.
5 / 87
Présentation de SPF : Arborescence
Routage d’état de lisaison
6 / 87
Processus de routage d’état de liaison
Plan
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
7 / 87
Processus de routage d’état de liaison
Processus de routage d’état de liaison
Chaque routeur prend connaissance de ses propres liaisons, de
ses propres réseaux directement connectés.
Chaque routeur est responsable de la détection de ses voisins sur
les réseaux connectés directement.
Chaque routeur crée un LSP (Link-State Packet) contenant l’état
de chaque liaison directement connectée.
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.
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
8 / 87
Processus de routage d’état de liaison
Etape1 : Etudes des réseaux connectés directement
soit la configuration suivante
9 / 87
Processus de routage d’état de liaison
R1
on s’interesse à l’étude de R1 :
10 / 87
Processus de routage d’état de liaison
11 / 87
Processus de routage d’état de liaison
Etape 2 : Découverte des voisins par l’envoie des
paquets Hello
12 / 87
Processus de routage d’état de liaison
Etape 3 : Creation de LSP
par ex : R1 crée son LSP pour l’envoyer à ses voisins
13 / 87
Processus de routage d’état de liaison
Etape 4 : diffusion des LSP
les LSP sont diffusés presque immédiatement après leur
réception, sans calcul intermédiaire. Contrairement aux
protocoles de routage à vecteur de distance, qui doivent d’abord
exécuter l’algorithme Bellman-Ford pour traiter les mises à jour de
routage avant de les envoyer aux autres routeurs, les protocoles
de routage d’état des liaisons calculent l’algorithme SPF après
que la diffusion soit complète. Résultat, les protocoles de routage
d’état des liaisons atteignent la convergence plus rapidement que
les protocoles de routage à vecteur de distance.
Un LSP doit être envoyé uniquement :
lors du démarrage initial du routeur ou du lancement du processus
de protocole de routage sur ce routeur ;
lorsque la topologie a été modifiée, notamment en cas d’activation
ou de désactivation d’une liaison ou d’établissement ou de rupture
d’une contiguïté entre voisins
14 / 87
Processus de routage d’état de liaison
15 / 87
Processus de routage d’état de liaison
Etape 4.5 : creation d’une base de données d’états de
liaison
16 / 87
Processus de routage d’état de liaison
Etape 5 : création de Arborescence SPF de R1
17 / 87
Publicité
Elaboration de l’arborescence SPF
Plan
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
18 / 87
Elaboration de l’arborescence SPF
19 / 87
Elaboration de l’arborescence SPF
20 / 87
Elaboration de l’arborescence SPF
21 / 87
Elaboration de l’arborescence SPF
22 / 87
Elaboration de l’arborescence SPF
23 / 87
Elaboration de l’arborescence SPF
SPF R1 final pour Les LAN
24 / 87
Elaboration de l’arborescence SPF
SPF R1 final pour les WAN
R1 détermine que le chemin le plus court vers chaque réseau distant :
le réseau 10.5.0.0/16 via R2 série 0/0/0, pour un coût de 22
le réseau 10.6.0.0/16 via R3 série 0/0/1 pour un coût de 7
le réseau 10.7.0.0/16 via R3 série 0/0/1 pour un coût de 15
le réseau 10.8.0.0/16 via R3 série 0/0/1 pour un coût de 17
le réseau 10.9.0.0/16 via R2 série 0/0/0 pour un coût de 30
le réseau 10.10.0.0/16 via R3 série 0/0/1 pour un coût de 25
le réseau 10.11.0.0/16 via R3 série 0/0/1 pour un coût de 27
25 / 87
Elaboration de l’arborescence SPF
Ajout des routes ds la table de routage
26 / 87
Elaboration de l’arborescence SPF
Avanatges des protocoles de routage à etat de liaison
Élaboration d’une carte topologique : chaque routeur crée sa
propre carte topologique du réseau pour déterminer le chemin le
plus court
l’innondation 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
une conception hiérarchique est utilisée lors de l’implémentation
de plusieurs zones.
27 / 87
Elaboration de l’arborescence SPF
notion de zones pour l’évolutivité
28 / 87
Plan
Le protocole de routage OSPF
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
29 / 87
Plan
Le protocole de routage OSPF
Format et fonctionnement
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
30 / 87
Format du message OSPF
Le protocole de routage OSPF
Format et fonctionnement
31 / 87
Types de paquet OSPF
Le protocole de routage OSPF
Format et fonctionnement
32 / 87
Hello
Le protocole de routage OSPF
Format et fonctionnement
33 / 87
intervalles hello et dead
Le protocole de routage OSPF
Format et fonctionnement
L’intervalle Dead est la période, exprimée en secondes, pendant
laquelle le routeur attendra de recevoir un paquet Hello avant de
déclarer le voisin « hors service ».
Dead = 4 * Hello = 40s
34 / 87
OSPF utilise Dijkastra
Le protocole de routage OSPF
Format et fonctionnement
35 / 87
Plan
Le protocole de routage OSPF
Configuration OSPF de base
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
Publicité
36 / 87
topologie utilisée
Le protocole de routage OSPF
Configuration OSPF de base
37 / 87
Conf de base des routeurs
Le protocole de routage OSPF
Configuration OSPF de base
38 / 87
Configuration OSPF
Le protocole de routage OSPF
Configuration OSPF de base
OSPF est activé à l’aide de la commande de configuration globale
router ospf process-id.
Le process-id (id de processus) est un nombre compris entre 1 et
65535 choisi par l’administrateur réseau.
Le process-id n’a qu’une signification locale, ce qui veut dire qu’il
n’a pas à correspondre à celui des autres routeurs OSPF pour
établir des contiguïtés avec des voisins.
39 / 87
la commande Network
Le protocole de routage OSPF
Configuration OSPF de base
Toute interface de routeur qui correspond à l’@ réseau dans la commande network est
activée pour envoyer et recevoir des paquets OSPF.
Ce réseau sera inclus dans les mises à jour de routage OSPF.
La commande network est utilisée dans le mode de configuration du routeur
Router(config-router)#network adresse réseau masque générique area area-id
le masque générique peut être configuré comme l’inverse d’un masque de sous-réseau.
Par exemple, l’interface FastEthernet 0/0 de R1 se trouve sur le réseau 172.16.1.16/28. Le
masque de sous-réseau pour l’interface est /28 ou 255.255.255.240. L’inversion du
masque de sous-réseau donne un masque générique.
area area-id fait référence à la zone OSPF. Une zone OSPF est un groupe de routeurs qui
partagent les informations d’état des liaisons. Tous les routeurs OSPF de la même zone
doivent avoir les mêmes informations dans leur base de données d’état des liaisons.
40 / 87
Plan
Le protocole de routage OSPF
ID du routeur
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
41 / 87
Détermination de l’ID
Le protocole de routage OSPF
ID du routeur
L’ID de routeur OSPF permet d’identifier de façon unique chaque routeur du domaine de routage
OSPF. Un ID de routeur est tout simplement une adresse IP. Les routeurs Cisco définissent leur
ID de routeur en utilisant trois critères, suivant la priorité suivante :
1 L’adresse IP configurée à l’aide de la commande router-id du protocole OSPF.
2 Si router-id n’est pas configuré, le routeur choisit l’adresse IP la plus élevée parmi ses
interfaces de bouclage IP.
3 Si aucune interface de bouclage n’est configurée, le routeur choisit l’adresse IP active la
plus élevée parmi ses interfaces physiques.
42 / 87
L’adresse IP active la plus élevée
Le protocole de routage OSPF
ID du routeur
R1 : 192.168.10.5, supérieur à 172.16.1.17 ou 192.168.10.1
R2 : 192.168.10.9, supérieur à 10.10.10.1 ou 192.168.10.2
R3 : 192.168.10.10, supérieur à 172.16.1.33 ou 192.168.10.6
43 / 87
Adresse de bouclage
Le protocole de routage OSPF
ID du routeur
Si la commande router-id OSPF n’est pas utilisée et que vous avez configuré des
interfaces de bouclage, OSPF choisit l’adresse IP d’interface de bouclage la plus élevée.
Une adresse de bouclage est une interface virtuelle et est automatiquement à l’état actif
lorsqu’elle est configurée.
Router(config)#interface loopback number
Router(config-if)#ip address ip-address masque de sous-réseau
44 / 87
Adresse de bouclage
Le protocole de routage OSPF
ID du routeur
45 / 87
Le protocole de routage OSPF
ID du routeur
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 - durée de temps pendant laquelle le routeur attendra un paquet Hello OSPF
du voisin avant de déclarer le voisin hors service. Cette valeur est réinitialisée lorsque
l’interface reçoit un paquet Hello.
Address - adresse IP de l’interface du voisin à laquelle ce routeur est directement
connecté.
Interface - interface sur laquelle ce routeur a établi une contiguïté avec son voisin.
46 / 87
Plan
Le protocole de routage OSPF
Autres Cammandes de verification OSPF
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
47 / 87
show ip protocols
Le protocole de routage OSPF
Autres Cammandes de verification OSPF
48 / 87
show ip ospf
Le protocole de routage OSPF
Autres Cammandes de verification OSPF
49 / 87
show ip ospf interface
Le protocole de routage OSPF
Autres Cammandes de verification OSPF
50 / 87
Plan
Le protocole de routage OSPF
Examen de la table de routage
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
Publicité
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
51 / 87
Le protocole de routage OSPF
Examen de la table de routage
52 / 87
Le protocole de routage OSPF
Examen de la table de routage
53 / 87
Le protocole de routage OSPF
Examen de la table de routage
54 / 87
Plan
Le protocole de routage OSPF
Mesure OSPF : Cout
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
55 / 87
Valeurs du cout OSPF Cisco
Le protocole de routage OSPF
Mesure OSPF : Cout
La mesure OSPF s’appelle le coût. RFC 2328 : "Un coût est associé au niveau de la sortie
de chaque interface de routeur. Ce coût est configurable par un administrateur système.
Plus le coût est faible, plus l’interface sera utilisée pour acheminer le trafic de données"
Pour calculer un coût, l’IOS cumule les bandes passantes des interfaces de sortie depuis
le routeur vers le réseau de destination
À chaque routeur, le coût d’une interface est déterminé par le calcul de 108 divisé par la
bande passante en bits/s. Le résultat est appelé bande passante de référence.
Par défaut, la bande passante est de 108, soit 100 Mbits/s. Résultat : des interfaces ayant
une bande passante de 100 Mbits/s et plus ont un même coût OSPF de 1.
La bande passante de référence peut être modifiée pour s’adapter aux réseaux ayant des
liaisons d’une rapidité supérieure à 100 000 000 bits/s (100 Mbits/s) à l’aide de la
commande OSPF auto-cost reference-bandwidth.
56 / 87
Le protocole de routage OSPF
Mesure OSPF : Cout
57 / 87
Modification du cout de la liaison
Le protocole de routage OSPF
Mesure OSPF : Cout
58 / 87
Modification du cout de la liaison autrement
Le protocole de routage OSPF
Mesure OSPF : Cout
59 / 87
Commandes equivalentes
Le protocole de routage OSPF
Mesure OSPF : Cout
60 / 87
Plan
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
61 / 87
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
62 / 87
Problème
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
Les LSA sur les réseaux à accès multiple peuvent présenter deux
difficultés pour OSPF :
La création de contiguïtés multiples, une pour chaque paire de
routeurs.
Une diffusion massive de LSA (Link-State Advertisements -
Annonces d’état des liaisons).
63 / 87
Solution : le routeur désigné (DR)
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
Dans les réseaux à accès multiple, OSPF sélectionne
Un routeur désigné (Designated Router - DR) comme point de
collecte et de distribution des LSA envoyées et reçues.
Un routeur désigné de secours (Backup Designated Router - BDR)
est également choisi en cas de défaillance du routeur désigné.
Tous les autres routeurs deviennent des DROthers (ce qui signifie
qu’ils ne sont ni DR, ni BDR).
au lieu de diffuser les LSA à l’ensemble des routeurs du réseau,
les DROthers envoient leurs LSA uniquement au DR et au BDR
en utilisant l’adresse multidiffusion de 224.0.0.6 (ALLDRouters -
tous les routeurs DR).
R1 envoie des LSA au DR. Le BDR est lui aussi à l’écoute. Le DR
est chargé de transmettre les LSA depuis R1 vers les autres
routeurs. Il utilise l’adresse multidiffusion 224.0.0.5
(AllSPFRouters - tous les routeurs OSPF). Au final, un seul
routeur assure la diffusion de l’ensemble des LSA dans le réseau
à accès multiple.
64 / 87
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
65 / 87
Processus de sélection DR/BDR
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
Les sélections de DR/BDR n’ont pas lieu dans les réseaux point à point. Donc, dans une
topologie standard à trois routeurs, R1, R2 et R3, il n’y a pas à choisir de DR ou de BDR, car les
liaisons existant entre ces routeurs ne sont pas des réseaux à accès multiple.
66 / 87
Processus de sélection DR/BDR
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
nous avons trois routeurs qui partagent un réseau à accès multiple Ethernet, 192.168.1.0/24.
Publicité
Chacun des routeurs est configuré avec une adresse IP sur l’interface Fast Ethernet et une
adresse de bouclage pour l’ID de routeur.
67 / 87
Processus de sélection DR/BDR
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
Comment le routeur désigné et le routeur désigné de secours
sont-ils sélectionnés ? On applique les critères suivants :
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.
Dans l’exemple suivant, la priorité d’interface OSPF par défaut est
1. Résultat : selon les critères de sélection énoncés plus haut,
c’est l’ID de routeur OSPF qui est utilisé pour sélectionner le DR
et le BDR. Comme vous le voyez, RouterC devient DR et RouterB,
qui a le second ID de routeur le plus élevé devient le BDR.
RouterA, n’étant sélectionné ni comme DR, ni comme BDR,
devient DROther.
68 / 87
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
69 / 87
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
70 / 87
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
71 / 87
Modifier la priorité
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
72 / 87
Forcer la selection de DR et BDR
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
73 / 87
Modification de la bande passante de reférence
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
100 Mbps représente la bande passante par défaut référencée lorsque la bande passante
réelle est convertie en mesure de coût.
L’utilisation d’une bande passante de référence de 100 000 000 a pour résultat que des
interfaces avec un débit de 100 Mbits/s et plus ont un coût OSPF de 1.
nous avons maintenant des débits de liaison bien supérieurs aux vitesses Fast Ethernet,
notamment le Gigabit Ethernet et 10GigE.
Pour obtenir des calculs de coûts plus précis, un ajustement des valeurs de bande
passante de référence peut s’avérer nécessaire
Notez que la valeur est exprimée en Mbits/s. Par conséquent, la valeur par défaut est
égale à 100. Pour passer à des vitesses en 10GigE, vous devez définir la bande passante
de référence sur 10 000.
74 / 87
Le protocole de routage OSPF
OSPF et les réseaux à accès multiples
75 / 87
Plan
Dijkastra
1 Routage d’état de lisaison
2 Processus de routage d’état de liaison
3 Elaboration de l’arborescence SPF
4
Le protocole de routage OSPF
Format et fonctionnement
Configuration OSPF de base
ID du routeur
Autres Cammandes de verification OSPF
Examen de la table de routage
Mesure OSPF : Cout
OSPF et les réseaux à accès multiples
5
Dijkastra
76 / 87
SPF
Dijkastra
les boucles dans RIP (basé sur Bellman-Ford) peuvent etre evités
SI tous les noueds (routeurs) connaissent instantnement la
topologie de leur réseau. OSPF sont basé sur Dijkastra.
dans un routage à été de lien, le noeud peut suivre tout incident
sur un état de lien
l’etat de lien veut dire sont cout. un cout = ∞ veut dire un lien
down
inonde le réseau par les états de lien
on utilise dijkastra pour calculer le lien du cout le plus faible
depuis un noeud pour construire par la suite la table de routage
les noeuds ont conniassance de la topologie du réseau parce que
chaque noeud diffuse :
tous les noeuds qu’il peut atteindre vers ses voisins
tous ses voisins vers tous les noeuds
si un plus court chemin de s −→ d passe par un noeud u, alors le
chemin s −→ u est le plus court chemin entre s et u.
77 / 87
Dijkastra
après k iterations, on peut connaître les plus courts chemins à k
noeuds
soit spf : une liste de noeuds dont les plus courts chemins sont
connus
initialement spf = {s}
un noeud est ajouté à spf chaque 1 itération
soit cost[v ] : cout d’un chemin depuis un noeud source s au
noeud v
initialement cost[v ] = c(s, v ) pour tous les noeuds adjacents à s
cost[v ] = ∞ pour les autres noeuds
mettre à jour continuellement cost[v ] à chaque fois q’un plus court
chemin est appris depuis notre voisinage
78 / 87
pseudocode
Dijkastra
79 / 87
Dijkastra
Exemple
la source s = b
80 / 87
Dijkastra
v = b
81 / 87
Dijkastra
v = a
82 / 87
Dijkastra
v = c
83 / 87
Dijkastra
v = d
84 / 87
Dijkastra
v = e
85 / 87
Dijkastra
v = f
par ex : spf b −→ f est : f ← e ← c ← a ← b
86 / 87
arbre final de point de vue b
Dijkastra
87 / 87