R

´eseau
x
Routag
Mr TALL
e
ESP/UCAD

2024-2025

Département des
Sciences
Informatiques

Mr TALL R´eseaux 1 / 88
Pla
n
1 Routage statique
Table de
routage
Routage par d
2
´efaut CIDR
Principes g´en´eraux du routage
3
dynamique
Protocoles deProtocoles de routage
routage interne (IGP) :
RIP
4 Protocoles de routage interne (IGP) :
OSPF Aire de routage
Messages
OSPF
Protocole
OSPF
Algorithme Département des
Sciences
Informatiques

Shortest Path
Mr TALL R´eseaux 2 / 88
 Routage statique

1 Routage statique
Table de
routage
Routage par d
´efaut CIDR
2 Principes g´en´eraux du routage
dynamique

3 Protocoles de routage interne (IGP) :

RIP

4
5 Protocoles de
Protocoles de routage
routage interne
externe (IGP)
(EGP): :
OSPF
BGP
6 R´ef´erences
bibliographiques Département des
Sciences
Informatiques

Mr TALL R´eseaux 3 / 88
 Routage statique

Adressage IP et
interface
Une adresse IP est associ´ee `a une interface.
Exemple : le routeur R a deux interfaces, il a donc deux
adresses : 193.51.25.254 et 193.51.24.3

193.51.24.1 193.51.24.5
Réseau 193.51.24.0/24

193.51.24.3
R

Département des
Sciences
Informatiques

Mr TALL R´eseaux 4 / 88
 Routage statique

Adressage IP et
interface
Une adresse IP est associ´ee `a une interface.
Exemple : le routeur R a deux interfaces, il a donc deux
adresses : 193.51.25.254 et 193.51.24.3

R
193.51.25.254

Réseau 193.51.25.0/24
193.51.25.192
Département des
Sciences
Informatiques

Mr TALL R´eseaux 4 / 88
 Routage statique

Adressage IP et
interface
Une adresse IP est associ´ee `a une interface.
Exemple : le routeur R a deux interfaces, il a donc deux
adresses : 193.51.25.254 et 193.51.24.3

193.51.24.1 193.51.24.5
Réseau 193.51.24.0/24

193.51.24.3
R
193.51.25.254

Réseau
193.51.25.0/24
193.51
.25.19
Département des
Sciences
Informatiques

Mr TALL R´eseaux
2 4 / 88
 Routage statique

Adresse IP et
interface

182.71.89.1
Primer
gy

193.51.25.2

193.51.25.1
212.10.24.19
10.2.101.3
43.22.19.76

193.51.24.3
172.22.8.19

212.10.24.1
172.22.8.254
172.22.8.18
93.51.20.187 212.10.24.18

93.51.20.1 172.22.8.198

Département des
Sciences
Informatiques

Mr TALL R´eseaux 5 / 88
 Routage statique

Adresse IP et
interface

182.71.89.1
Primer
gy

193.51.25.2

193.51.25.1
212.10.24.19
10.2.101.3
43.22.19.76

193.51.24.3
172.22.8.19

212.10.24.1
172.22.8.254
172.22.8.18
93.51.20.187 212.10.24.18

93.51.20.1 172.22.8.198

Département des
Sciences
Informatiques

Mr TALL R´eseaux 5 / 88
 Routage statique

Adresse IP et
interface

182.71.89.1
Primer
gy

193.51.25.2

193.51.25.1
212.10.24.19
10.2.101.3
43.22.19.76

193.51.24.3
172.22.8.19

212.10.24.1
172.22.8.254
172.22.8.18
93.51.20.187 212.10.24.18

93.51.20.1 172.22.8.198

Département des
Sciences
Informatiques

Mr TALL R´eseaux 5 / 88
 Routage statique

Adresse IP et
interface

182.71.89.1

193.51.25.2

193.51.25.1

193.51.24.3
10.2.101.3
43.22.19.76
212.10.24.19

212.10.24.1 172.22.8.19

212.10.24.18
93.51.20.187
172.22.8.18
172.22.8.254
93.51.20.1

172.22.8.198

Département des
Sciences
Informatiques

Mr TALL R´eseaux 5 / 88
 Routage statique Table de routage

Table de
routage

18.0.0.0/24

Pour Je 212.21.71.0/24

aller dois
sur le r passer par 194.21.36.0/24

´eseau 43.0.0.0/24

172.30.0.0/ 193.51.25.1
16 22
193.51.24.0/ 193.51.25.
195.56.16.0/24

24 3 193.51.24.0/24

18.0.0.0/24 193.51.25.2 193.51.25.254 193.51.25.3

54 193.51.25.0/24

212.21.71.0/ 193.51.25.2 193.51.25.192 193.51.25.122

24 54
43.0.0.0/24 193.51.25.2
172.30.0.0/16

54 Département des
Sciences
Informatiques

195.56.16.0/ 193.51.25.2
Mr TALL R´eseaux 6 / 88
 Routage statique Table de
routage
Simplification des tables de
routage

Si il faut r´epertorier tous les r´eseaux de l’Internet dans

chaque table de routage
⇒ Explosion des tables de routage

route par d´efaut

aggr´egation de r´eseaux : CIDR

Département des
Sciences
Informatiques

Mr TALL R´eseaux 7 / 88
 Routage statique Routage par d
´efaut
Route par d
´efaut

18.0.0.0/24

212.21.71.0/24

Pour Je
aller dois 194.21.36.0/24

sur le r passer par

´eseau 43.0.0.0/24

172.30.0.0/ 193.51.25.1
16 22 195.56.16.0/24

193.51.24.0/ 193.51.25. 193.51.24.0/24

24 3 193.51.25.254 193.51.25.3

18.0.0.0/24 193.51.25.2
54
193.51.25.0/24

193.51.25.192 193.51.25.122

212.21.71.0/ 193.51.25.2
24 54 172.30.0.0/16

43.0.0.0/24 193.51.25.2
54
Département des
Sciences
Informatiques

195.56.16.0/
Mr TALL 193.51.25.2 R´eseaux 8 / 88
 Routage statique Routage par d
´efaut
Route par d
´efaut

18.0.0.0/24

212.21.71.0/24

Pour Je 194.21.36.0/24

aller dois 43.0.0.0/24

sur le r passer par

´eseau 195.56.16.0/24

172.30.0.0/ 193.51.25.1 193.51.24.0/24

16 22
193.51.24.0/ 193.51.25.
193.51.25.254 193.51.25.3

24 3 193.51.25.0/24

default 193.51.25.2
193.51.25.192 193.51.25.122

54 172.30.0.0/16

Département des
Sciences
Informatiques

Mr TALL R´eseaux 8 / 88
 Routage statique Routage par d
´efaut
Route par d
´efaut

Internet
Pour Je
aller dois
sur le r passer par 193.51.24.0/24

´eseau 193.51.25.254 193.51.25.3

172.30.0.0/ 193.51.25.1 193.51.25.0/24

16 22 193.51.25.192 193.51.25.122

193.51.24.0/ 193.51.25.
24 3 172.30.0.0/16

default 193.51.25.2
54

Département des
Sciences
Informatiques

Mr TALL R´eseaux 8 / 88
 Routage statique CIDR

Aggr´egation de routes : CIDR (Classless Inter-

Domain Routing)

Pour agr´eger les tables de routage :

allouer aux ”utilisateurs” des r´eseaux de classe C contigus
des r´eseaux contigus ont les mˆemes bits de poids fort :
⇒ ils ont mˆeme pr´efi xe
grouper les pr´efixes par r´egion, prestataires ...
router les pr´efixes des supernets (ou agr´egats) une
seule entr´ee par agr´egat dans la table de routage
suffit
Exemple 1 :
Les deux r´eseaux :
193.51.32.0 de masque 255.255.255.0 (not´e 193.51.32.0 / 24)
193.51.33.0 de masque 255.255.255.0 (not´e 193.51.33.0 / 24)
sont agr´eg´es en 193.51.32.0 255.255.254.0 (193.51.32.0 / 23)
Département des
Sciences
Informatiques

Mr TALL R´eseaux 9 / 88
 Routage statique CIDR

Aggr´egation de routes : CIDR (Classless Inter-

Domain Routing)

Exemple 2 :

Les h u i t r´eseaux :
201.18.168.0/24
201.18.169.0/24
201.18.170.0/24
201.18.171.0/24
201.18.172.0/24
201.18.173.0/24
201.18.174.0/24
201.18.175.0/24
sont agr´eg´es en
201.18.168.0/21
Département des
Sciences
Informatiques

Mr TALL R´eseaux 10 / 88
 Routage statique CIDR

Agr´egation des tables de

routage
R´eseau destination Routeur
201.18.168.0/24 R1
201.18.169.0/24 R1
201.18.170.0/24 R1 193.51.32.0/24 193.51.33.0/24 193.51.34.0/24
201.18.171.0/24 R1
201.18.172.0/24 R1
201.18.173.0/24 R1 R2
201.18.174.0/24 R1
201.18.175.0/24 R1
201.18.168.0/24
18.0.0.0/16 R1 201.18.169.0/24 195.87.65.0/2
193.51.32.0/24 R2 201.18.170.0/24 195.56.16.0/2
201.18.171.0/24
193.51.33.0/24 R2 201.18.172.0/24
201.18.173.0/24
193.51.34.0/24 R2 201.18.174.0/24
195.87.65.0/24 R3 201.18.175.0/24 R1 R3
18.0.0.0/16
195.56.16.0/24 R3
Tous les r´eseaux de R4
l’Internet R4
1.0.0.0/8 R4
2.0.0.0/8 R4
... R4
128.0.0.0/16 R4
128.1.0.0/16 R4
Internet
... R4
223.255.254.0/24 R4
223.255.255.0/24 R4

Département des
Sciences
Informatiques

Mr TALL R´eseaux 11 / 88
 Routage statique CIDR

Agr´egation des tables de

routage

193.51.32.0/24 193.51.33.0/24 193.51.34.0/24

R´eseau Routeur
destination
201.18.168.0/24 R1 R2
201.18.169.0/24 R1
201.18.170.0/24 R1
201.18.171.0/24 R1 201.18.168.0/24
201.18.169.0/24 195.87.65.0/2
201.18.172.0/24 R1 201.18.170.0/24 195.56.16.0/2
201.18.171.0/24
201.18.173.0/24 R1 201.18.172.0/24
201.18.174.0/24 R1 201.18.173.0/24
201.18.174.0/24
201.18.175.0/24 R1 201.18.175.0/24 R1 R3
18.0.0.0/16
18.0.0.0/16 R1
193.51.32.0/24 R2
193.51.33.0/24 R2 R4
193.51.34.0/24 R2
195.87.65.0/24 R3
195.56.16.0/24 R3
default R4
Internet

Département des
Sciences
Informatiques

Mr TALL R´eseaux 11 / 88
 Routage statique CIDR

Agr´egation des tables de

routage

193.51.32.0/24 193.51.33.0/24 193.51.34.0/24

R2

R´eseau Routeur
destination 201.18.168.0/24
201.18.169.0/24 195.87.65.0/2
201.18.168.0/21 R1 201.18.170.0/24 195.56.16.0/2
201.18.171.0/24
18.0.0.0/16 R1 201.18.172.0/24
193.51.32.0/23 R2 201.18.173.0/24
201.18.174.0/24
193.51.34.0/24 R2 201.18.175.0/24 R1 R3
18.0.0.0/16
195.87.65.0/24 R3
195.56.16.0/24 R3
default R4 R4

Internet

Département des
Sciences
Informatiques

Mr TALL R´eseaux 11 / 88
 Routage statique CIDR

Exemple de r
´eseau

Internet

R1
10
194.168.235.0/27 dorsale

12
R3
194.167.235.32/27 45 14
1 réseau d’enseignement R4
R2 42 120
194.167.235.64/27 94 33 34 41 44
réseau de laboratoire G H I J L M
65 72 63 91 78 K administratif
réseau 98 99
83 194.167.235.96/27
A B C D E F 124 125
R5 R6
157 164
réseau comptabilité/gestion réseau service du personnel
194.167.235.128/27 194.167.235.160/27

130 136 140 142 150 161 165 170 171 182
N O P Q R S T U V W
Département des
Sciences
Informatiques

Mr TALL R´eseaux 12 / 88
 Routage statique CIDR

Tables de routage
(1/2)
R´eseau Destination Routeur Interface
default R FAI ext
194.168.235.0/27 (dorsale) lien local int
R 194.168.235.32/27 (enseignement) 194.168.235.1
2
int

1 194.168.235.64/27 (laboratoire)
194.168.235.64/27 (administratif)
194.168.235.1
194.168.235.1
int
int
4
194.168.235.128/27 194.168.235.1 int
(compta/gestion) 4
194.168.235.160/27 (personnel) 194.168.235.1 int
R´eseau Destination 4
Routeur Interface
default 194.168.235.1 ext
0
194.168.235.0/27 (dorsale) lien local ext
R 194.168.235.32/27 (enseignement) 194.168.235.1 ext
2
2 194.168.235.64/27 (laboratoire) lien local int
194.168.235.64/27 (administratif) 194.168.235.1 ext
4
194.168.235.128/27 194.168.235.1 ext
(compta/gestion) 4
194.168.235.160/27
R´eseau Destination (personnel) 194.168.235.1
Routeur ext
Interface
4
default 194.168.235.1 ext
0
194.168.235.0/27 (dorsale) lien local ext
R 194.168.235.32/27 (enseignement) lien local int
3 194.168.235.64/27 (laboratoire)
194.168.235.64/27 (administratif)
194.168.235.1
194.168.235.1
ext
ext
4
194.168.235.128/27 194.168.235.1 ext
Département des
Sciences
Informatiques

(compta/gestion) 4
194.168.235.160/27 (personnel) 194.168.235.1 ext
Mr TALL 4 R´eseaux 13 / 88
 Routage statique CIDR

Tables de routage
(2/2)
R´eseau Destination Routeur Interface
default 194.168.235.10 ext
194.168.235.0/27 (dorsale) lien local ext
R 194.168.235.32/27 (enseignement)
194.168.235.64/27 (laboratoire)
194.168.235.12
194.168.235.1
ext
ext
4 194.168.235.64/27 (administratif) lien local int
194.168.235.128/27 194.168.235.12 int
(compta/gestion) 4
194.168.235.160/27 (personnel) 194.168.235.12 int
5
R´eseau Destination Routeur Interface
default 194.168.235.12 ext
R 0
194.168.235.64/27 (administratif) lien local ext
5 194.168.235.128/27 lien local int
(compta/gestion)
194.168.235.160/27 (personnel) 194.168.235.12 ext
5
R´eseau Destination Routeur Interface
default 194.168.235.12 ext
R 0
194.168.235.64/27 (administratif) lien local ext
6 194.168.235.128/27 194.168.235.12 ext
(compta/gestion) 4
194.168.235.160/27 (personnel) lien local int

Département des
Sciences
Informatiques

Mr TALL R´eseaux 14 / 88
 Routage statique CIDR

Et si on rajoutait ou enlevait des

routeurs ?

Configurer les tables de routages des routeurs suppl

´ementaire Modifier les tables de routage de chacun des
routeurs d´ej`a pr´esents
... et surtout, ne pas se tromper ! ! !
⇒ Dans un environnement complexe, la mise en oeuvre
du routage statique est souvent difficile `a maintenir.

Département des
Sciences
Informatiques

Mr TALL R´eseaux 15 / 88
 Principes g´en´eraux du routage
dynamique

1 Routage
statique
2 Principes g´en´eraux du routage
dynamique Protocoles de routage

3 Protocoles de routage interne

(IGP) : RIP

4 Protocoles de routage interne

(IGP) : OSPF

5 Protocoles de routage externe

(EGP) : BGP

6 R´ef´erences bibliographiques Département des

Sciences
Informatiques

Mr TALL R´eseaux 16 / 88
 Principes g´en´eraux du routage
dynamique
Routage
dynamique

Dans un environnement complexe, la mise en œuvre

du routage statique est souvent difficile `a maintenir
La mise en place d’un m´ecanisme de routage
dynamique permet de faciliter les mises `a jour
Chaque routeur diffuse la liste des r´eseaux sur lesquels il
est connect´e
Chaque routeur met `a jour sa table de routage
`a partir des informations re¸cues depuis les
autres
D´emons de routage : routed, gated, ripd, ospfd

Département des
Sciences
Informatiques

Mr TALL R´eseaux 17 / 88
 Principes g´en´eraux du routage
dynamique
Routage
dynamique

Chemin de couˆt le moins

´elev´e Echange d’information
entre routeurs Algorithmes
`a vecteur de distance
(distance vector) : RIP
`a ´etat de liaison (link state) :
OSPF

Département des
Sciences
Informatiques

Mr TALL R´eseaux 18 / 88
 Principes g´en´eraux du routage dynamique Protocoles de
routage
Protocoles de
routage

Le protocole de routage consiste `a d´efinir comment sont

´echang´ees les informations de routage, et donc `a :
d´ecouvrir les autres routeurs du
r´eseau construire les tables de
routage maintenir les tables de
routage `a jour
Attention : protocole de routage /=
politique de routage (d´ecision)

Département des
Sciences
Informatiques

Mr TALL R´eseaux 19 / 88
 Principes g´en´eraux du routage Protocoles de routage
dynamique
Routage entre r
´eseaux

Interconnexion de r´eseaux de diff´erents op´erateurs ⇒

chaque op´erateur se d´ebrouille pour router ses propres
informations en interne.
protocole commun d’information de routage entre les r
´eseaux des diff´erents op´erateurs.

Département des
Sciences
Informatiques

Mr TALL R´eseaux 20 / 88
 Principes g´en´eraux du routage dynamique Protocoles de
routage
AS (Autonomous
System)
AS : ensemble de r´eseaux contrˆol´es par une
seule autorit´e.
AS AS AS

AS

AS

AS AS
Département des
Sciences
Informatiques

Mr TALL R´eseaux 21 / 88
 Principes g´en´eraux du routage dynamique Protocoles de
routage
AS (Autonomous
System)
AS : ensemble de r´eseaux contrˆol´es par une
seule autorit´e.
AS IGP AS AS
IG
P IGP

IGP
EGP AS
IGP
AS

IGP IGP
AS AS
Département des
Sciences
Informatiques

Mr TALL R´eseaux 21 / 88
 Principes g´en´eraux du routage dynamique Protocoles de
routage
AS (Autonomous
System)
Les ressources d’adressage et de routage de l’internet -constitu
´ees par les adresses IP et les num´eros AS- ont ´et´e r
´eparties par l’IANA aupr`es de RIR ((Regional Address
Registry). Les RIR r´epartissent ensuite ces ressources aupr`es
de Local Internet Registries (LIR = Registres Internet Locaux)
qui attribuent les adresses aux utilisateurs finaux.
ARIN pour les zones Am´erique
du Nord AfriNIC pour l’Afrique
APNIC pour les zones Asie-
Pacifique
LACNIC pour les zones Am´eriques du Sud -
Cara¨ıbes RIPE NCC pour la zone Europe
´etendue.
Département des
Sciences
Informatiques

Les num´eros d’AS sont des entiers stock´es sur 16 bits. ⇒ Il

Mr TALL R´eseaux 22 / 88
 Principes g´en´eraux du routage dynamique Protocoles de
routage
IGP (Interior Gateway
Protocol)

IGP : Protocole de routage utilis´e dans les r´eseaux sous

mˆeme entit´e administrative
qu’`a l’int´erieur d’une entit´e (entreprise,
association, etc)
d´ecisions (suppression/ajout d’une ligne) peuvent ˆetre
prises par un service unique
but : trouver la route la plus efficace, en faisant confiance
aux autres routeurs.
ex : RIP, OSPF

Département des
Sciences
Informatiques

Mr TALL R´eseaux 23 / 88
 Principes g´en´eraux du routage dynamique Protocoles de
routage
EGP (Exterior Gateway
Protocol)

EGP : Protocole de routage adapt´e `a la redistribution de pr

´efixes vers des r´eseaux ext´erieurs, ayant une entit´e
administrative diff´erente
s’utilise entre entit´es distinctes (souvent
concurrentes). Impossibilit´e de prendre une d
´ecision qui s’imposera `a tous. On n’est pas pr
´evenu de ce que vont faire les autres.
Id´ee de m´efiance : le but n’est pas de trouver la
meilleure route mais au contraire d’empˆecher les routeurs
de choisir une route dont on ne voudrait pas.
Pas d’information de routage mais
d’accessibilit´e ex : BGP
Département des
Sciences
Informatiques

Mr TALL R´eseaux 24 / 88
 Principes g´en´eraux du routage dynamique Protocoles de
routage
Protocoles de
routage
IGP
RIP (Routing Information Protocol) v1, v2 : protocole `a
vecteur de distance (Distance Vector)
OSPF (Open Shortest Path First) : protocole de routage
`a ´etat de lien (Link-state)
IGRP/EIGRP protocole propri´etaire CISCO
EGP
BGP (Border Gateway Protocol) : protocole `a vecteur
de chemin. C’est le protocole standard de l’Internet
pour les interconnexions entre op´erateurs.

BGP RIP
(port 179) (port 520)
ICMP (proto 1) TCP (proto 6) UDP (proto 17) OSPF (proto 89) IGMP (proto 2)

IP
Département des
Sciences
Informatiques

Mr TALL R´eseaux 25 / 88
 Protocoles de routage interne (IGP) : RIP

1 Routage statique

2 Principes g´en´eraux du routage

dynamique

3 Protocoles de routage interne (IGP) :

RIP

4
5 Protocoles de
Protocoles de routage
routage interne
externe (IGP)
(EGP): :
OSPF
BGP
6 R´ef´erences
bibliographiques

Département des
Sciences
Informatiques

Mr TALL R´eseaux 26 / 88
 Protocoles de routage interne (IGP) : RIP

RIP : Principe g´en

´eral

Principe :
Chaque routeur annonce p´eriodiquement (30s) tous ses r
´eseaux et le nombre de saut pour y aller
Chaque machine ´ecoute les annonces des passerelles et
actualise sa table de routage
Si au bout d’un certain temps (3mn=180s), un r´eseau
n’est plus annonc´e, il est supprim´e de la table de
routage.
Il n’y a pas d’accus´e de r´eception de message

Département des
Sciences
Informatiques

Mr TALL R´eseaux 27 / 88
 Protocoles de routage interne (IGP) : RIP

Principe g´en
´eral

réseau r1

réseau r2

C
D

réseau r3

Département des
Sciences
Informatiques

Mr TALL R´eseaux 28 / 88
 Protocoles de routage interne (IGP) : RIP

Principe g´en
´eral

Routeur Annonce Sur Machine Route

Temps
B r2 r1 A r2 via B
t1 r1 r2 C r1 via B
annonce r2 D r1 via B
réseau r1

annonce r1
réseau r2

C
D

réseau r3

Département des
Sciences
Informatiques

Mr TALL R´eseaux 28 / 88
 Protocoles de routage interne (IGP) : RIP

Principe g´en
´eral

Routeur Annonce Sur Machine Route

Temps
B r2 r1 A r2 via B
t1 r1 r2 C r1 via B
D r1 via B
réseau r1
D r1 et r2 r3 E r1 via D
A t2 r2 via D
B D r3 r2 B r3 via D
D C r3 via D
annonce r3
réseau r2

C
D

annonce r1 et r2
réseau r3

Département des
Sciences
Informatiques

Mr TALL R´eseaux 28 / 88
 Protocoles de routage interne (IGP) : RIP

Principe g´en
´eral

Routeur Annonce Sur Machine Route

Temps
B r2 r1 A r2 via B
t1 r1 r2 C r1 via B
annonce r2 et r3 D r1 via B
réseau r1
D r1 et r2 r3 E r1 via D
A t2 r2 via D
B D r3 r2 B r3 via D
D C r3 via D
annonce
r1 B r2 et r3 r1 A r3 via B
réseau r2 t3
B r1 r2
C D

réseau r3

Département des
Sciences
Informatiques

Mr TALL R´eseaux 28 / 88
 Protocoles de routage interne (IGP) : RIP

Principe g´en
´eral

Routeur Annonce Sur Machine Route

Temps
B r2 r1 A r2 via B
t1 r1 r2 C r1 via B
D r1 via B
réseau r1
D r1 et r2 r3 E r1 via D
A t2 r2 via D
B D r3 r2 B r3 via D
D C r3 via D
réseau r2 B r2 et r3 r1 A r3 via B
t3
B r1 r2
C
D

réseau r3
B tombe en
panne
E

Département des
Sciences
Informatiques

Mr TALL R´eseaux 28 / 88
 Protocoles de routage interne (IGP) : RIP

Principe g´en
´eral

Routeur Annonce Sur Machine Route

Temps
B r2 r1 A r2 via B
t1 r1 r2 C r1 via B
D r1 via B
réseau r1
D r1 et r2 r3 E r1 via D
A t2 r2 via D
B D r3 r2 B r3 via D
D C r3 via D
réseau r2 B r2 et r3 r1 A r3 via B
t3
B r1 r2
C
D

réseau r3
B tombe en
panne A r2 non rout´e
E
t3 + 180s r3 non rout´e
C r1 non rout´e
D r1 non rout´e

Département des
Sciences
Informatiques

Mr TALL R´eseaux 28 / 88
 Protocoles de routage interne (IGP) : RIP

Principe g´en
´eral

Routeur Annonce Sur Machine Route

Temps
B r2 r1 A r2 via B
t1 r1 r2 C r1 via B
D r1 via B
réseau r1
D r1 et r2 r3 E r1 via D
A t2 r2 via D
B D r3 r2 B r3 via D
D C r3 via D
réseau r2 B r2 et r3 r1 A r3 via B
t3
B r1 r2
C
D

réseau r3
B tombe en
panne A r2 non rout´e
E
t3 + 180s r3 non rout´e
C r1 non rout´e
D r1 non rout´e
E r1 non rout
t3 + 360s ´e

Département des
Sciences
Informatiques

Mr TALL R´eseaux 28 / 88
 Protocoles de routage interne (IGP) : RIP

Routage `a vecteur de distance

(Algorithme de Bellman-Ford)

P´eriodiquement un routeur envoie une copie de sa table

de routage `a tous les routeurs directement accessibles.
Lorsque que J transmet un rapport au routeur K, K
examine l’ensemble des destinations annonc´ees et leur
distance. K modifie son entr´ee vers une destination si :
J connait un plus court chemin
ou si J annonce une destination que K ne
poss`ede pas ou si une destination via J a
chang´e
l’entr´ee de la table de K mise `a jour signale
la distance n + 1 (avec n
la distance annonc´ee par J pour la
destination) Département des
Sciences
Informatiques

Mr TALL R´eseaux 29 / 88
 Protocoles de routage interne (IGP) : RIP

Routage `a vecteur de distance

(Bellman-Ford)
Table de routage
du routeur K
Destination Dist. Route
R´eseau 1 0 directe
R´eseau 2 0 directe r20 r22
r12
R´eseau 4 8 Routeur L r13
r38 r8 X X
R´eseau 17 5 Routeur M r7 X
r21 X r10 X r14 r4
r9 X
R´eseau 24 6 Routeur J X
X
r19 r24
R´eseau 30 2 Routeur Q r23
R´eseau 42 2 Routeur J L r2
X
r16 r18
r25 r15
Message de mise `a r1
J X
X X
r27
r11 r26
jour du routage issu r6 K r42
du routeur J r29
r32
r35
Destination Dist. Q M X r41
r5 r34 X
R´eseau 1 2 r37 X
r40
r3 X r36
R´eseau 4 3 X
r31
r33
R´eseau 17 6 r30 r39 r17
R´eseau 21 4
R´eseau 24 5
R´eseau 30 10
R´eseau 42 4

Département des
Sciences
Informatiques

Mr TALL R´eseaux 30 / 88
 Protocoles de routage interne (IGP) : RIP

Routage `a vecteur de distance

(Bellman-Ford)
Table de routage
du routeur K
Destination Dist. Route
R´eseau 1 0 directe
R´eseau 2 0 directe
R´eseau 4 4 Routeur J r20
r12 r22
r13
R´eseau 17 5 Routeur M r38 r8 X X
X r14
R´eseau 21 5 Routeur J r21 r10 r4
X r7 X
X X
r9
R´eseau 24 6 Routeur J r19 r24
X r23
R´eseau 30 2 Routeur Q L X
r2 r16 r18
R´eseau 42 3 Routeur J r25 r15
r1 X X

Message de mise `a J r11

X
r26
r27

jour du routage issu r6 K r42

du routeur J Q r29
M
r32
X r41 r35
Destination Dist. r5 r34 r40
X
R´eseau 1 2 r37 r3 X X
X r33 r36
R´eseau 4 3 r30
r31
r39 r17
R´eseau 17 6
R´eseau 21 4
R´eseau 24 5
R´eseau 30 10
R´eseau 42 4

Département des
Sciences
Informatiques

Mr TALL R´eseaux 30 / 88
 Protocoles de routage interne (IGP) : RIP

RIP (Routing Information

Protocol)
Principe :
Chaque routeur annonce (par diffusion) p´eriodiquement
(30s) tous ses r´eseaux et le nombre de saut pour y aller
Chaque machine ´ecoute les annonces des passerelles et
actualise sa table de routage
Si au bout d’un certain temps (3mn=180s), un r´eseau
n’est plus annonc´e, il est supprim´e de la table de
routage.
Il n’y a pas d’accus´e de r´eception de
message Protocole sur UDP, port 520
2 types de routeurs :
Routeur actif : diffuse ses informations de routage vers
les autres noeuds.
Routeur passif : ´ecoute ces informations et met `a jour
sa table de routage.
RIPv1 diffuse (broadcast) et RIPv2 multicast toute leur table
Département des
Sciences
Informatiques

deMrroutage
TALL toutes les 30 secondes.
R´eseaux 31 / 88
 Protocoles de routage interne (IGP) : RIP

RIP (Routing Information

Protocol)
Routage `a vecteur de distance.
chaque noeud n’a d’information que sur le prochain saut
(next hop) pas de d´ecisions globales
table de routage de B table de routage de C
rA : F (2) rA : B (3)
rD : C (2) rB : B (1)
rC : C (1) rD : D (1)
rE : C (2) rE : E (1)
rF : F (1) C rF : B (2)
1 1

B
table de routage de A D
rD : F (4) table de routage de D
rB : F (2) rA : C (4)
1
rC : F (3) rB : C (2)
1
rE : F (4) 1 rC : C (1)
A
rF : F (1) rE : E (1)
rF : E (4)
1

table de routage de E
F rA : F (4)
E rB : C (2)
3 rC : C (1)
rA : A (1) rD : D (1)
table de
rB : B (1) routage de rF : F (3)
rC : B (2) F
rE : E (3)
rD : B (3)
Département des
Sciences
Informatiques

Mr TALL R´eseaux 32 / 88
 Protocoles de routage interne (IGP) : RIP

Probl`emes de
RIP v1
limite de 16 sauts (16 : inaccessible) ⇒ ne peut pas aller
plus loin que 15 routeurs (hops)
converge lentement (si route changent souvent, peut
ne pas se stabiliser)
informations circulent
lentement trafic important
boucles possibles
ne se base que sur une seule m´etrique : le hop ⇒ peut
choisir des routes lentes.
pas de gestion de masque ⇒ pas de routage de
sous-r´eseaux pas d’authentification
25 entr´ees maximum dans la table de routage (car
taille du message
= 512 o)
Département des
Sciences
Informatiques

Mr TALL R´eseaux 33 / 88
 Protocoles de routage interne (IGP) : RIP

RIP
v2
2 algorithmes de plus :
split horizon : les donn´ees ne sont pas renvoy´ees vers le
noeud d’ou` on les a appris
hold down : Le routeur ignore les informations relatives `a un
r´eseau pendant une p´eriode fixe apr`es r´eception d’un
message qui en sp´ecifie l’innacessibilit´e.
poison reverse : si on d´etecte une route coup´ee et
qu’on re¸coit un message avec un couˆt tr`es sup
´erieur au couˆt initial, on ignore l’information (consid
´er´ee revenue par une boucle).
Plus les am´eliorations suivantes :
masque de sous-r´eseau : sous-r´eseaux possibles +
aggr´egation des routes
authentification (mot de passe en clair ou chiffr´e sur 16
octets) utilisation de domaines logiques (on ignore les Département des
Sciences
Informatiques

messages d’un autre domaine)

Mr TALL R´eseaux 34 / 88
 Protocoles de routage interne (IGP) : RIP

RIPv2 :
Format
commande :
1: demande
d’information
de routage
2: r´eponse 0 8 16 24 31

contenant les info Commande Version

Famille du réseau
0
Etiquette de route
de la table de

pour chaque réseau

Adresse IP du réseau

routage de l’exp Masque de sous−réseau

saut suivant
´editeur 9 : distance jusqu’au réseau

demande de mise
...
`a jour (avec
circuit de
commande)
10: r´eponse de
mise `a
jour (avec circuit
de commande) Département des
Sciences
Informatiques

11: accus´e de
Mr TALL R´eseaux 35 / 88
 Protocoles de routage interne (IGP) : RIP

RIPv2 : clivage d’horizon (split

horizon)

Contre le probl`eme de convergence lente :

Un routeur ne transmet pas les informations relatives `a une
route vers la mˆeme interface que celle qui l’a initialement
annonc´e.
⇒ Les bonnes nouvelles vont vite, les mauvaises
lentement. XXX

Département des
Sciences
Informatiques

Mr TALL R´eseaux 36 / 88
 Protocoles de routage interne (IGP) : RIP

RIPv2 : m´ecanisme de gel (hold

down)

Le routeur ignore les informations relatives `a un r´eseau

pendant une p´eriode fixe (60s) apr`es r´eception d’un
message qui en sp´ecifi e l’innacessibilit´e.
XXX

Département des
Sciences
Informatiques

Mr TALL R´eseaux 37 / 88
 Protocoles de routage interne (IGP) : RIP

RIPv2 : antidote (poison

reverse)

Apr`es la disparition d’une connexion, le routeur qui l’a

annonc´e conserve l’entr´ee pendant plusieurs cycles de mise
`a jour en incluant un couˆt infini dans ses messages de
diffusion.
XXX

Département des
Sciences
Informatiques

Mr TALL R´eseaux 38 / 88
 Protocoles de routage interne (IGP) : RIP

RIPv
2

RIP v2 corrige certains probl`emes de

RIP v1 Encore des probl`emes :
m´etrique : sauts
uniquement port´ee
maximum de 15 sauts
taille de la table de 25
entr´ees maximum.
⇒ RIPv2 ne peut
s’appliquer qu’aux petits
et moyens r´eseaux.

Département des
Sciences
Informatiques

Mr TALL R´eseaux 39 / 88
 Protocoles de routage interne (IGP) : OSPF

1 Routage statique

2 Principes g´en´eraux du routage

dynamique

3 Protocoles de routage interne

(IGP) : RIP
4 Protocoles de routage interne (IGP) :

OSPF Aire de routage

Messages OSPF
Protocole
OSPF
Algorithme
Shortest Path
5 Protocoles de routage externe (EGP) :
First (SPF)
BGP

6 R´ef´erences bibliographiques
Département des
Sciences
Informatiques

Mr TALL R´eseaux 40 / 88
 Protocoles de routage interne (IGP) : OSPF

Routage `a ´etat
de lien

Principe :
Envoyer `a tous les noeuds les informations au sujet
des voisins. Les noeuds ont une copie compl`ete de la
carte du r´eseau
Chaque noeud ex´ecute Dijkstra (plus court chemin
V := { s } ;
et pas de cycles).
1
C
for all v ∈ (V − V ) do
1
T
T

B procedureif DIJKSTRA
(s, v) exists setl [v
SP(V, E, ]w,
:= w
s) begin(s, v ) else set l[v ] := ∞ ;
D
while VT /= V do
Base generale du
1 reseau connue par begin
1
1 chaque routeur. find a vertex u such that
A A, F, 1 l[u] := min{l[v ]|v ∈ (V − VT ) } ;
F, B, A VT := VT ∪ u ;
1 B, C, 1
C, D, 1 for all v ∈ (V − VT )
C, E, 1 do l[v ] := min{l[v ], l[u] + w
D, E, 1 endwhil [u, v ]} ;
F 3 E F, E, 3
end e DIJKSTRA
SP

Département des
Sciences
Informatiques

Mr TALL R´eseaux 41 / 88
 Protocoles de routage interne (IGP) : OSPF

OSPF ( Open Shortest Path

First)
Routage `a ´etat de lien (Link-State) : permettre au routeur
d’avoir une vision globale du r´eseau et de sa topologie
une base de donn´ees sur chaque noeud repr´esentant
la topologie totale du r´eseau
d´etection de boucle
calcul de la route la plus courte par l’algorithme de
Dijkstra
configuration pour chaque interface
m´etrique par type de couˆt (longueur de la file
d’attente, d´ebit, distance en saut, etc)
ne diffuser que les modifications d´etect´ees dans
la topologie (accessibilit´e et couˆt)
routage par type de service (champ TOS du
datagramme) notion d’aire de routage Département des
Sciences
Informatiques

Mr TALL R´eseaux 42 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Aire de
routage

Un r´eseau OSPF est divis´e en plusieurs aires (Area) qui se

connectent `a une aire centrale de distribution appel´ee
dorsale (backbone).
Chaque aire est d´esign´ee par un identifiant de 32 bits mis
sous la forme
X.Y.Z.T. Cet identifiant ne correspond pas forc´ement `a
l’adresse r´eseau (mˆeme si par commodit´e, on le choisit
souvent ainsi).
Pas plus d’une cinquantaine de routeurs maximum
par aire. R´eduction du nombre de routeur par
zone de diffusion
⇒ trafic de gestion limit´e
⇒ ´echange entre routeurs plus nombreux Département des
Sciences
Informatiques

Mr TALL R´eseaux 43 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de routage

Aire dorsale (area

backbone)

L’aire dorsale :
a pour identifiant 0 . 0 . 0 . 0
obligatoirement sert pour
l’acheminement inter-aire
est obligatoire ⇒ si le r´eseau n’a pas ´et´e d´ecoup´e
en aire, il y en a qu’une seule et c’est la dorsale d’id
0.0.0.0.

Département des
Sciences
Informatiques

Mr TALL R´eseaux 44 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de routage

Routeur
s distingue 3 types de
On
routeurs dans OSPF :
routeur interne (Internal
Router
- IR) : qui annoncent les
routes internes `a leur aire
routeur de la dorsale
Aire 0.0.0.1

(Backbone Router - BR) : qui IR

annoncent les routes IR

ABR IR

internes `a la dorsale. (En

(BR) ASBR

IR
IR
fait ce sont des IR de l’aire
(BR)

”dorsale”) Aire 0.0.0.2 IR

ABR
routeur fronti`ere (Area IR

Boundary Router - ABR) : Aire 0.0.0.0

(dorsale)
qui assurent la connexion AS autre
`a la dorsale AS
Département des
Sciences
Informatiques

MT
rALL
routeur fronti`ereouter
System Boundary de R´eseaux 45 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Relation de voisinage et relation
d’adjacence
Deux routeurs sont voisins s’ils appartiennent `a une mˆeme
zone et sont reli´es par un mˆeme m´edia (lien de diffusion
(broadcast domain) ou `a chaque extr´emit´e d’un lien point-
`a-point).
Deux routeurs sont adjacents si ils sont voisins et synchronis
´es,
c’est-`a-dire s’ils ´echangent des informations sur la
topologie du r´eseau pour s’assurer du bon fonctionnement BDR

l’un de l’autre.
DR BDR

DR
BDR

DR

Département des
Sciences
Informatiques

Mr TALL R´eseaux 46 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Routeur D´esign´e (Designated
Router - DR)
Un seul routeur parmi les routeurs voisins est responsable.
le DR (et le BDR) assure la diffusion des messages vers
les routeurs de la zone
evite d’´etablir n2 relations entre routeurs voisins et de
dupliquer la mˆeme information
Le DR (designated router) sert de point central d’´echange.
Le BDR (backup designated router - DR de secours) surveille
le DR et prend sa place s’il ne r´epond plus.

BDR
DR BDR

DR
BDR

DR

Département des
Sciences
Informatiques

Mr TALL R´eseaux 47 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Election des
DR/BDR
D’abord ´election d’un BDR et puis, en l’absence d’un DR, le
BDR quitte son statut pour devenir DR.
Election `a deux tours :
1 1er tour : priorit´e la plus ´elev´ee sur les interfaces du r

´eseau partag´e (de 0 : disqualification automatique `a 255

: qualification automatique)
priorit´e d´efinie manuellement par interface ou par d
2 ´efaut (= 1) une interface d’un routeur d´ej`a DR est
in´eligible
2eme tour : cas de routeurs ex aequo. le routeur de plus
haut ID OSPF qui remporte l’´election.
ID OSPF
Le vainqueur de (32 bits) adresse
l’´election IP laBDR.
devient plus ´elev´ee parmi toutes
les interfaces du routeur.
Les routeurs placent leurs interfaces dans un ´etat en cons
´equence : DR, BDR ou DROTHER.
Si un DR n’existe plus ou pas du tout, le BDR devient DR et
une ´election a lieue pour d´esigner le nouveau BDR. Département des
Sciences
Informatiques

Mr TALL R´eseaux 48 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Roˆle du
DR
Le DR maintient la base topologique du r´eseau
Relation maitre-esclave entre le DR et les routeurs de la
zone.
Les routeurs de la zone ne sont adjacents qu’avec le DR
et le BDR. Par contre, ils ne sont pas adjacents entre eux
mais peuvent ˆetre voisins.
En cas de panne du DR, le routeur de secours (BDR)
maintiendra
´egalement la base de donn´ee et prendra le relais du DR
en devenant lui-mˆeme DR (et un autre BDR sera ´elu).

A` chaque fois qu’un routeur envoie une mise `a jour, il

l’envoie aux DR/BDR (via une adresse dite multicast) et
c’est le DR qui rediffuse cette information `a tous les
routeurs. Département des
Sciences
Informatiques

Les routeurs n’ont pas `a constamment se mettre `a jour

Mr TALL R´eseaux 49 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

DR BDR

Ri

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

DR BDR

LSU vers
224.0.0.6
Ri

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

DR BDR
LSU vers
224.0.0.5

Ri

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

DR BDR
LSAck
LSAck LSAck

LSAck LSAck LSAck

Ri

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)
Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)

Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Envoi par inondation
(flooding)

Envoi r´ecursif :
Le routeur envoit un LSU contenant l’info du nouvel etat
de lien au DR et BDR (224.0.0.6)
Le DR fait passer le LSU aux autres routeurs
(224.0.0.5) les autres routeurs acquittent avec
un LSAck
Si un routeur se trouve connect´e aussi `a un autre r
´eseau, il envoi le LSU au DR/BDR de cet autre r´eseau
(224.0.0.6) (innondation r´ecursive)
La coordination par les DR permettent d’´eviter de renvoyer
deux fois le mˆeme LSU et d’´eviter les boucles.
Département des
Sciences
Informatiques

Mr TALL R´eseaux 50 / 88
 Protocoles de routage interne (IGP) : OSPF Aire de
routage
Bases de donn´ees
OSPF
Trois bases de donn´ees sur chaque routeur :
Base de donn´ees d’adjacence - Adjacencies database :
Liste de tous les routeurs adjacents avec lesquels est
´etabli une communication bidirectionnelle.
⇒ Unique pour chaque routeur (Liste compos´ee d’un
DR et d’un BDR par interface).
Base de donn´ees topologique - Link-state database
(LSDB) : BD topologique contenant la liste des
informations sur tous les routeurs du r´eseau. Elle montre
la topologie du r´eseau (graphe).
⇒ Maintenue identique sur chaque routeur OSPF par
inondation p´eriodique des mises `a jours
⇒ Echang´e entre le DR et le BDR
Table de routage - Forwarding database : Liste des routes
g´en´er´ees par l’algorithme de djikstra sur la BD
topologique. ⇒ Unique pour chaque routeur Département des
Sciences
Informatiques

⇒ Calcul´e par chaque routeur

Mr TALL R´eseaux 51 / 88
 Protocoles de routage interne (IGP) : OSPF Messages OSPF

Types de
lien
Type de Description
lien
1 LSA Routeur (Router-LSA)
2 LSA R´eseau (Network-LSA)
3 LSA R´esum´e (BR) (Summary-
LSA)
4 LSA R´esum´e (ASBR)
(Summary-LSA)
0 8 16 24 31
5 LSA ASAge
externe
LSA (AS-external-
options LSA type LSA
En−tete
LSA) ID lien
routeur annonceur
LSA
numéro de séquence lien
somme de controle lien longueur LSA

corps suivant type de LSA Corps

LSA

Département des
Sciences
Informatiques

Mr TALL R´eseaux 52 / 88
 Protocoles de routage interne (IGP) : OSPF Messages OSPF

Types de
lien

1 - Router-LSA : chaque routeur d’une aire g´en`ere un

router-LSA d´ecrivant l’´etat et le couˆt de chacun de
ses liens (interfaces) vers l’aire.
2 - Network-LSA : chaque DR g´en`ere un Network-LSA
pour chaque r´eseau de l’aire supportant plus de 2
routeurs. Ce LSA d´ecrit tous les routeurs attach´es `a ce
r´eseau, y compris le DR.
3/4 - Summary-LSA : Chaque routeur fronti`ere (BR ou
ASBR) g´en`ere des Summary-LSA d´ecrivant les
destination inter-aires.
5 - AS-external-LSA : Chaque routeur fronti`ere de l’AS
(ASBR) g´en`ere un AS-external-LSA d´ecrivant les
destinations externes `a l’AS. Département des
Sciences
Informatiques

Mr TALL R´eseaux 53 / 88
 Protocoles de routage interne (IGP) : OSPF Messages OSPF

Message
OSPF

Types de
message
0 8 16 24 31
1 Hello (type 1) : ´etablit et maintien les Version Type Longueur du message
informations d’adjacence des
routeurs voisins Adresse IP du routeur source

2 DBD Database Description Packet (type Identifiant de l’aire

2) : description du Somme de controle Type d’authentification
contenu de la LSDB d’un routeur
Authentificatio
3 LSR - Link State Request (type 3) :
n (8
demande de certains ´etats de
liens `a la LSDB d’un voisin octets)

4 LSU - Link State Update (type 4) : mise `a jour

d’´etats de liens. Transporte les Message OSPF
annonce d’´etat de lien LSA (taille variable suivant le
(link-state advertisements) aux routeurs voisins type)
5 LSAck - Link-State acknowledgement (type 5) :
accus´e de r´eception des LSA

Département des
Sciences
Informatiques

Mr TALL R´eseaux 54 / 88
 Protocoles de routage interne (IGP) : OSPF Messages OSPF

Message OSPF HELLO

(type 1)
OSPF ´etablit et v´erifie l’accessibilit´e des routeurs
voisins en envoyant r´eguli`erement des messages HELLO
sur chaque lien.
31
0 Version Type = 1 Longueur du message
Adresse IP du routeur source
masque de sous-r´eseaux. 8 Identifiant de l’aire
p´eriode hello : nombre de secondes entre Somme de controle Type d’authentification
lesquels ce routeur envoit ses messages 16
Authentificatio
HELLO
n (8
Options support´ees par le 24
octets)
routeur Priorit´e du routeur Masque réseau
(pour l’election) période HELLO options prio routeur
temporisation de panne : nombre de secondes
temporisation de panne
avant qu’un routeur silencieux soit consid´er´e
comme Down. routeur désigné
Adresse du DR (0 si il n’y en a routeur désigné de secours
pas) adresse du BDR (0 si il ID routeur voisin 1
n’y en a pas) ID routeur voisin 2
ID routeurs voisins : adresses IP de chaque ...
router dont on a re¸cu r´ecemment les HELLO
messages. ID routeur voisin n Département des
Sciences
Informatiques

Mr TALL R´eseaux 55 / 88
 Protocoles de routage interne (IGP) : OSPF Messages OSPF

Message OSPF description de base de donn´ees

(type 2) DBD
Les routeurs s’´echangent des messages OSPF description
de base de donn´ees pour initialiser leur base de donn
´ees de topologie r´eseau. 31
Version Type = 2 Longueur du message
0
Adresse IP du routeur source
M T U int. : taille maximum des paquets IP que 8 Identifiant de l’aire
l’interface du routeur peut envoyer sans Somme de controle Type d’authentification
fragmentation. 16
Authentificatio
Options support´ees par le n (8
24
routeur 5 bits `a zero octets)
MTU interface options 00000 I M S
Bit I (Init bit) : I=1 si premier
packet de la sequence Numéro de séquence base de données

Bit M (More bit) : M=1 si d’autres paquets

En−tete LSA 1
doivent suivre
Bit MS (Master/slave bit) : MS=1 si le routeur
est le maitre durant le processus d’´echange En−tete LSA 2
de bases.
DD Sequence Number : s´equence utilis´ee
pour num´eroter les paquets pour pouvoir ...
les reconstituer dans l’ordre (incr
´ementation).
description des liens par des LSA (en-tˆete En−tete LSA n Département des
Sciences
Informatiques

seulement)
Mr TALL R´eseaux 56 / 88
 Protocoles de routage interne (IGP) : OSPF Messages OSPF

Message OSPF demande d’´etats de lien

(type 3) LSR
Demande aux voisins des informations de mise `a jour pour
les liens qui semblent obsol`etes. Dans cette demande sont
transmise les informations les plus r´ecentes qu’il poss`ede
`a propos de ces liens. 31
Version Type = 3 Longueur du message
0
Adresse IP du routeur source

8 Identifiant de l’aire
Somme de controle Type d’authentification
16 Authentificati
on (8
24 octets)

LS Type : type de LSA recherch´e demande de lien 1

Link State ID : L’identifiant du LSA
(generalement l’IP) demande de lien 2
L’ID du routeur (annonceur) qui a cr´ee les LSA ...
et dont l’update est recherch´ee.

demande de lien n

0 8 16 24 31
demand type LSA
e de ID lien
lien
Département
des Sciences
Informaqtiues

routeur annonceur

Mr TALL R´eseaux 57 / 88
 Protocoles de routage interne (IGP) : OSPF Messages OSPF

Message OSPF mise `a jour d’´etat de lien

(type 4) LSU
Les routeurs diffusent l’´etat des liens (LSA - link State
Advertisement) en transmettant des messages de mise `a jour
d’´etat de lien.
31
0 Version Type = 4 Longueur du message
Adresse IP du routeur source
8 Identifiant de l’aire
Somme de controle Type d’authentification
16
Authentificatio
n (8
24
octets)
description des liens par des LSA (en-tˆete et
corps)
LSA 1

LSA 2

...

LSA n
Département des
Sciences
Informatiques

Mr TALL R´eseaux 58 / 88
 Protocoles de routage interne (IGP) : OSPF Messages OSPF

Message OSPF accus´e de r´eception d’´etats

de liens (type 5) LSAck

0 8 16 24 31
Version Type = 5 Longueur du message
Adresse IP du routeur source
Identifiant de l’aire
Somme de controle Type d’authentification
Authentificatio
n (8
les en-tˆete LSA permettent d’accuser r octets)
´eception pour chaque LSA envoy´e.
En−tete LSA 1

En−tete LSA 2

...

En−tete LSA n

Département des
Sciences
Informatiques

Mr TALL R´eseaux 59 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Les 7 ´etats
OSPF
Down

Down Connectivit´e non assur´ee

Envoi de messages Hello annon¸cant son ID Init
Init A rec¸u son premier Hello (mais ne
contenant pas son ID)
Two−way
Two-way A re¸cu son premier Hello
contenant son ID ⇒ connectivit´e dans les
deux sens Exstart

Exstart
Exchange
Exchange Echanges de DBD coordonn
´ees par le DR.
Loading
Loading
Full ´etat terminal, routeurs en
compl`ete adjacence.
Département des
Sciences

Full
Informatiques

Mr TALL R´eseaux 60 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Les 7 ´etats
OSPF
Down

Down Connectivit´e non assur´ee

Init
Init A rec¸u son premier Hello (mais ne
contenant pas son ID)
Two-way A re¸cu son premier Hello Two−way
contenant son ID ⇒ connectivit´e dans les
deux sens
Exstart
Exstart
Exchange
Exchange Echanges de DBD coordonn
´ees par le DR.
Loading Loading

Full ´etat terminal, routeurs en

compl`ete adjacence. Département des
Sciences

Full
Informatiques

Mr TALL R´eseaux 60 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Les 7 ´etats
OSPF
Down

Down Connectivit´e non assur´ee

Init
Init A rec¸u son premier Hello (mais ne
contenant pas son ID)
Two-way A re¸cu son premier Hello Two−way
contenant son ID ⇒ connectivit´e dans les
deux sens
Exstart
Exstart
Exchange
Exchange Echanges de DBD coordonn
´ees par le DR.
Loading Loading

Full ´etat terminal, routeurs en

compl`ete adjacence. Département des
Sciences

Full
Informatiques

Mr TALL R´eseaux 60 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Les 7 ´etats
OSPF
Down

Down Connectivit´e non assur´ee

Init A rec¸u son premier Hello (mais ne Init
contenant pas son ID)
Two-way A re¸cu son premier Hello
contenant son ID ⇒ connectivit´e dans les Two−way
deux sens
Exstart Exstart
Si n´ecessaire, ´election du DR (et du BDR)
`a l’aide de paquets HELLO. Exchange

Exchange Echanges de DBD coordonn

´ees par le DR. Loading

Loading
Full ´etat terminal, routeurs en Département des
Sciences

Full
Informatiques

compl`ete adjacence.
Mr TALL R´eseaux 60 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Les 7 ´etats
OSPF
Down
Down Connectivit´e non assur´ee
Init A rec¸u son premier Hello (mais ne
contenant pas son ID) Init
Two-way A re¸cu son premier Hello
contenant son ID ⇒ connectivit´e dans les
deux sens Two−way

Exstart
Exchange Echanges de DBD coordonn Exstart
´ees par le DR.
Exchange
Les routeurs envoient des LSAck
Comparaison des DBD re¸cus avec
leur DBD locale, si nouvelle route, Loading
passage en ´et at ”Loading” en
envoyant un LSR.
Loading
Département des
Sciences

Full
Informatiques

Mr TALL R´eseaux 60 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Les 7 ´etats
OSPF
Down
Down Connectivit´e non assur´ee
Init A rec¸u son premier Hello (mais ne
contenant pas son ID) Init

Two-way A re¸cu son premier Hello

contenant son ID ⇒ connectivit´e dans les
Two−way
deux sens
Exstart
Exstart
Exchange Echanges de DBD coordonn
´ees par le DR. Exchange
Loading
le LSR a ´et´e envoy´e. Loading
Attente du LSU (contenant le
LSA). Acquittement avec un
LSAck Département des
Sciences

Full
Informatiques

Full ´etat terminal, routeurs

Mr TALL en
R´eseaux 60 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Les 7 ´etats
OSPF
Down
Down Connectivit´e non assur´ee
Init A rec¸u son premier Hello (mais ne
contenant pas son ID) Init
Two-way A re¸cu son premier Hello
contenant son ID ⇒ connectivit´e dans les
deux sens Two−way

Exstart
Exchange Echanges de DBD coordonn Exstart

´ees par le DR.

Exchange
Loading
Full ´etat terminal, routeurs en
Loading
compl`ete adjacence.
Les routeurs connaissent tous leurs
routeurs voisins et l’´etat de toutes les
liaisons du r´eseau. Cr´eation de la table Département des
Sciences

Full
Informatiques

de routage (algorithme SPF).

Mr TALL R´eseaux 60 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

E´tapes
OSPF
1 Etablir l’adjacence des routeurs (Hello) :
2 Election du DR et du BDR (si n´ecessaire) : champ de
priorit´e (0-255) dans paquet HELLO (et ID si ´egalit´e).
3 D´ecouvrir les routes : ´echange de DBD : Type
d’´etat de lien, les annonces d’adresses, le couˆt du
lien, un nombre de s´equence.
Comparaisons des DBD re¸cus avec leur propres DBD.
4 LSR+LSA dans LSU
5 Selectionner les bonnes routes :
Maintenir les informations de routage : Quand un
changement survient, les routeurs utilisent le processus
d’innondation (flooding) pour avertir leurs voisins sur le r
´eseau.
Si une ligne est down, le routeur envoie le nouvel ´etat au Département des
Sciences
Informatiques

DR ou BDR qui fera suivre aux autres routeurs

Mr TALL R´eseaux 61 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Adresses
multicast

224.0.0.1 tous les syst`emes du r´eseau local

224.0.0.2 tous les routeurs du r´eseau local
224.0.0.5 tous les routeurs OSPF
224.0.0.6 tous les routeurs OSPF d´esign´es (DR et BDR)
224.0.0.24 ´echange des descriptions de bases de donn´ees
compati-
bles TE durant la synchronisation des BD
(OSPFIGP-TE) - exp´erimental.

Département des
Sciences
Informatiques

Mr TALL R´eseaux 62 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Protocole d’inondation
(flooding)

A` chaque changement d’´etat d’un lien, le routeur qui en a

la charge
´emet un LSU (contenant le LSA) vers les DR/BDR
(224.0.0.6)
le DR attribue un num´ero de s´equence et ´emet le LSU
vers tous les routeurs (224.0.0.5).
Chaque routeur recevant le LSA cherche l’entr´ee du LSA
dans sa base par le num´ero de s´equence.
Si LSA non pr´esent ou si annonce plus r´ecente
met `a jour la base
retransmet le LSA sur toutes ses interfaces sauf celle par
laquelle il a re¸cu l’annonce
acquitte le message (OSPF type 5) Département des
Sciences
Informatiques

Mr TALL R´eseaux 63 / 88
 Protocoles de routage interne (IGP) : OSPF Protocole OSPF

Maintien des informations de

routage
D´etection d’un changement sur un lien :
disparition d’un lien : silence de la ligne. Toutes les 10
secondes par d´efaut, les routeurs envoient un HELLO. Si
silence pendant 40 secondes, la ligne est consid´er´ee
comme ”down”.
(r)´etablissement d’un lien : un HELLO est re¸cu par le
routeur sur ce lien.
Un routeur d´etecte un
changement : un LSU est
envoy´e par flooding
les routeurs recevant le LSU mettent `a jour leur base de
donn´ees d’etat de lien (LSDB)
les routeurs recalculent leur table de routage par
l’algorithme SPF.
Si aucun changement d’etat n’intervient dans le r
Mr TALL R´eseaux 64 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)

Calcul des plus courts chemin dans un graphe.

Algorithme de Dijkstra (plus court chemin et pas de
cycles) pour d´eterminer les routes les moins couteuse.
Chaque routeur se voit comme la racine d’un arbre
contenant les meilleures routes.

Département des
Sciences
Informatiques

Mr TALL R´eseaux 65 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro
A 1chaque ´etape
Identifier : les arˆetes
toutes
ai = (si 1, si 2) dans P × G
B C

tel que si 1 est dans P et 1

si 2 est dans G ; 10

A
10

1
2
Choisir l’arˆete aj = (sj1, sj2) 10
1

dans P × G qui donne la F D

48
10 G

distance minimum depuis r

1 10
E

`a sj2 en passant tous les

chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand P Département des
Sciences

devient un arbre couvrant de G

Informatiques

Mr TALL R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro
A 1chaque ´etape
Identifier : les arˆetes
toutes
ai = (si 1, si 2) dans P × G B 1 C

tel que si 1 est dans P et 10

10

si 2 est dans G ; 10

A
10

1
2
Choisir l’arˆete aj = (sj1, sj2) 10
0
1

dans P × G qui donne la F D

48
10 1 G
10
distance minimum depuis r
1 10
E
48
`a sj2 en passant tous les
chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand P Département des
Sciences

devient un arbre couvrant de G

Informatiques

R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro
A 1chaque ´etape
Identifier : les arˆetes
toutes
ai = (si 1, si 2) dans P × G B 1 C

tel que si 1 est dans P et 10

2

si 2 est dans G ; 10

A
10

1
2
Choisir l’arˆete aj = (sj1, sj2) 10
0
1

dans P × G qui donne la F D

48
10 1 G
10
distance minimum depuis r
1 10
E 11
11
`a sj2 en passant tous les
chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand P Département des
Sciences

devient un arbre couvrant de G

Informatiques

MT
rALL
R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro
A 1chaque ´etape
Identifier : les arˆetes
toutes
ai = (si 1, si 2) dans P × G B 1 C

tel que si 1 est dans P et 3

2

si 2 est dans G ; 10

A
10

1
2
Choisir l’arˆete aj = (sj1, sj2) 10
0
1

dans P × G qui donne la F D

48
10 1 G
10
distance minimum depuis r
1 10
E 11
11
`a sj2 en passant tous les
chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand P Département des
Sciences

devient un arbre couvrant de G

Informatiques

MT
rALL
R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro
A 1chaque ´etape
Identifier : les arˆetes
toutes
ai = (si 1, si 2) dans P × G B 1 C

tel que si 1 est dans P et 3

2

si 2 est dans G ; 10

A
10

1
2
Choisir l’arˆete aj = (sj1, sj2) 10
0
1

dans P × G qui donne la F D

48
10 1 G
10
distance minimum depuis r
1 10
E 11
11
`a sj2 en passant tous les
chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand P Département des
Sciences

devient un arbre couvrant de G

Informatiques

MT
rALL
R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro
A 1chaque ´etape
Identifier : les arˆetes
toutes
ai = (si 1, si 2) dans P × G B 1 C

tel que si 1 est dans P et 3

2

si 2 est dans G ; 10

A
10

1
2
Choisir l’arˆete aj = (sj1, sj2) 10
0
1

dans P × G qui donne la F D

48
10 1 G
10
distance minimum depuis r
1 10
E 11
11
`a sj2 en passant tous les
chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand P Département des
Sciences

devient un arbre couvrant de G

Informatiques

R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro
A 1chaque ´etape
Identifier : les arˆetes
toutes
ai = (si 1, si 2) dans P × G B 1 C

tel que si 1 est dans P et 3

2

si 2 est dans G ; 10

A
10

1
2
Choisir l’arˆete aj = (sj1, sj2) 10
0
1

dans P × G qui donne la F D

48
10 1 G
10
distance minimum depuis r
1 10
E 11
11
`a sj2 en passant tous les
chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand P Département des
Sciences

devient un arbre couvrant de G

Informatiques

R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro
A 1chaque ´etape
Identifier : les arˆetes
toutes
ai = (si 1, si 2) dans P × G B 1 C

tel que si 1 est dans P et 3

2

si 2 est dans G ; 10

A
10

1
2
Choisir l’arˆete aj = (sj1, sj2) 10
0
1

dans P × G qui donne la F D

48
10 1 G
10
distance minimum depuis r
1 10
E 11
11
`a sj2 en passant tous les
chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand P Département des
Sciences

devient un arbre couvrant de G

Informatiques

R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro
A 1chaque ´etape
Identifier : les arˆetes
toutes
ai = (si 1, si 2) dans P × G B 1 C

tel que si 1 est dans P et 3

2

si 2 est dans G ; 10

A
10

1
2
Choisir l’arˆete aj = (sj1, sj2) 10
0
1

dans P × G qui donne la F D

48
10 1 G
10
distance minimum depuis r
1 10
E 11
11
`a sj2 en passant tous les
chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand P Département des
Sciences

devient un arbre couvrant de G

Informatiques

R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´e ro Base de données topologique

A 1chaque ´etape
Identifier : les arˆetes
toutes 1
A

10

ai = (si 1, si 2) dans P × G D F

tel que si 1 est dans P et 1

10
10

si 2 est dans G ; C E G

2
Choisir l’arˆete aj = (sj1, sj2)
1

dans P × G qui donne la

B

distance minimum depuis r

`a sj2 en passant tous les
chemins cr´e´es menant
`a sj2. La placer dans P.
L’algorithme se termine soit
quand Pun arbre couvrant
devient
de G
Département des
Sciences
Informatiques

R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Algorithme Shortest Path First

(SPF)
Init : P = r , et la distance
de r `a lui-mˆeme vaut z
´echaque
A ro Base de données topologique
´etape :
1 Identifier toutes les arˆetes A

1 10

ai = (si 1, si 2) dans P × G D F

tel que si 1 est dans P et 1

10
10

si 2 est dans G ; C E G

2
Choisir l’arˆete aj = (sj1, sj2)
1

B
dans P × G qui donne la
distance minimum depuis r Table de routage
Pour aller vers le réseau Passer par le routeur

`a sj2 en passant tous les réseau(x)

réseau(x)
attaché(s) à D
attaché(s) à C
D
D
chemins cr´e´es menant
réseau(x) attaché(s) à E D
réseau(x) attaché(s) à G D
réseau(x) attaché(s) à B D
`a sj2. La placer dans P. réseau(x) attaché(s) à F F

L’algorithme se termine soit

quand Pun arbre couvrant
devient
de G
Département des
Sciences
Informatiques

R´eseaux 66 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Cou
ˆt
Par d´efaut, couˆts utilis´es en fonction de la bande
Type de du
passante r´eseau
lien : Couˆt par d
´efaut
FDDI, 1
FastEthernet
Ethernet 10 Mbps 10
E1 (2,048 Mbps) 48
T1 (1,544 Mbps) 65
64 Kbps 1562
56 Kbps 1758
Suivant la
19.2 Kbps 5208
formule :
bande passante de reference en
cout
bpsbande passante du lien en
=
bps de reference en bps =
(par d´efaut, bande passante
100Mbps) Département des
Sciences
Informatiques

R´eseaux 67 / 88
 Protocoles de routage interne (IGP) : OSPF Algorithme Shortest Path First (SPF)

Synth`ese
OSPF
Routage `a ´etat de lien (Link-State) : permettre au routeur
d’avoir une vision globale du r´eseau et de sa topologie
OSPF g`ere les limitations de RIP
s’applique sur de tr`es larges r´eseaux utilisant une
architecture hi´erarchique.
mises `a jour sont non p´eriodiques et d´eclench´ees sur
des changements de topologie, ce qui entraine un faible
temps de convergence des tables de routage.
Protocole `a ´etat de lien recommand´e pour
remplacer RIP plus fiable
hi´erarchis´e
authentificati
on Département des
Sciences
Informatiques

´equilibrage de
R´eseaux 68 / 88
 Protocoles de routage externe (EGP) : BGP

1 Routage statique

2 Principes g´en´eraux du routage

dynamique

3 Protocoles de routage interne (IGP) :

RIP

4
5 Protocoles de
Protocoles de routage
routage interne
externe (IGP)
(EGP): :
OSPF
BGP
6 R´ef´erences
bibliographiques

Département des
Sciences
Informatiques

R´eseaux 69 / 88
 Protocoles de routage externe (EGP) : BGP

EGP (External Gateway

Protocol)

AS AS AS

AS

AS

AS AS
Département des
Sciences
Informatiques

R´eseaux 70 / 88
 Protocoles de routage externe (EGP) : BGP

EGP (External Gateway

Protocol)

Routage inter-
domaine.
AS AS
OSPF RIP

EGP

Probl`emes techniques :
les m´etriques sont diff´erentes suivant les protocoles
internes aux AS.
Département des
Sciences
Informatiques

R´eseaux 71 / 88
 Protocoles de routage externe (EGP) : BGP

EGP (External Gateway

Protocol)
Probl`emes politiques :
s’utilise entre entit´es distinctes
(souvent concurrentes).
Impossibilit´e de prendre une d
´ecision qui s’imposera `a tous.
Internet
On n’est pas pr´evenu de ce que vont
faire les autres.
Id´ee de m´efiance : le but n’est pas de
Site A Site B
trouver la meilleure route mais au
contraire d’empˆecher les routeurs de
choisir une route dont on ne voudrait
pas.
Politique sur le trafic de transit
Département des
Sciences
Informatiques

R´eseaux 72 / 88
 Protocoles de routage externe (EGP) : BGP

EGP (External Gateway

Protocol)
Probl`emes politiques :
s’utilise entre entit´es distinctes
(souvent concurrentes).
Impossibilit´e de prendre une d
´ecision qui s’imposera `a tous.
Internet
On n’est pas pr´evenu de ce que vont
faire les autres.
Id´ee de m´efiance : le but n’est pas de
Site A Site B
trouver la meilleure route mais au
contraire d’empˆecher les routeurs de
choisir une route dont on ne voudrait
pas.
Politique sur le trafic de transit
Département des
Sciences
Informatiques

R´eseaux 72 / 88
 Protocoles de routage externe (EGP) : BGP

BGP (Border Gateway

Protocol)
protocole standard de l’Internet pour les
interconnexions entre op´erateurs.
on doit annoncer exactement le pr´efixe r´eseau que
l’on veut diffuser.
AS2
AS3

AS1

AS4

AS6 AS5

Département des
Sciences
Informatiques

R´eseaux 73 / 88
 Protocoles de routage externe (EGP) : BGP

BGP (Border Gateway

Protocol)
protocole standard de l’Internet pour les
interconnexions entre op´erateurs.
on doit annoncer exactement le pr´efixe r´eseau que
l’on veut diffuser.
AS2
AS3

AS1

193.51.24.0/24, AS Path (4, 3, 2,

1) AS4

AS6 AS5

Département des
Sciences
Informatiques

R´eseaux 73 / 88
 Protocoles de routage externe (EGP) : BGP

BGP (Border Gateway

Protocol)
protocole standard de l’Internet pour les
interconnexions entre op´erateurs.
on doit annoncer exactement le pr´efixe r´eseau que
l’on veut diffuser.
AS2
AS3

AS1

AS4
193.51.24.0/24, AS Path (6, 1)

AS6 AS5

Département des
Sciences
Informatiques

R´eseaux 73 / 88
 Protocoles de routage externe (EGP) : BGP

BGP (Border Gateway

Protocol)

protocole point `a point entre routeurs de bords de l’AS

´etablissement de session BGP (TCP port 179)
´echange de message BGP
un routeur peut participer `a plusieurs sessions BGP
routage par vecteur de chemin (et pas par vecteur de
distance, ni par
´etat de lien)
un noeud n’a pas `a accepter une route apprise par ses
voisins, il peut l’accepter ou la refuser.
un noeud BGP annonce une partie de sa table de routage
ce qui est partag´e et accept´e d´epend de la politique
de routage
Département des
Sciences
Informatiques

R´eseaux 74 / 88
 Protocoles de routage externe (EGP) : BGP

BGP (Border Gateway

Protocol)

Protocole `a vecteur de chemin

trouver des chemins sans cycle entre les AS
trouver un chemin optimal n’est pas un but en soi : ce
n’est ni un protocole par vecteur de distance ni par
´etat de lien.
Probl`emes :
pas de routage par d´efaut ! ! !
Environ 12.000 AS sur l’Internet, soit de tr`es grosses
tables dans les routeurs BGP
Besoin de flexibilit´e

Département des
Sciences
Informatiques

R´eseaux 75 / 88
 Protocoles de routage externe (EGP) : BGP

CIDR et longuest prefix

match
CIDR : utilisation de pr´efixes de longueur variable.
Pour l’instant les tables BGP de l’Internet comportent un
peu plus de
90.000 routes.
CIDR utilis´e pour r´eduire les tables de routage
(supernetting). Possibilit´e de recouvrement des pr
´efi xes
Il est choisi le pr´efixe de longueur maximale pour router.
Exemple : Un routeur entend :
R1 annonce
193.51.0.0/16 et R2
annonce 193.51.24.0/24
Pour router : Département des
Sciences
Informatiques

193.51.24.3 ⇒ R2 est R´eseaux 76 / 88

 Protocoles de routage externe (EGP) : BGP

BGP
4
BGP est utilis´e pour transporter des informations de routage
entre AS : num´ero d’AS
liste des r´eseaux de chaque AS
distance vers les sous-r´eseau
de l’AS
IP du routeur d’entr´ee vers les
sous-r´eseaux.
Protocole de transmission fiable (TCP sur port 179). Messages
´echang´es : Message d’ouverture (num´ero d’AS) entre
deux routeurs
Message de mise `a jour : signale chaque changement
d’´etat et les routes inaccessibles
Message de notification : motif de la fermeture Département des
Sciences
Informatiques

Message Hello keepalive : pourR´eseaux

signaler que le routeur est 77 / 88
 Protocoles de routage externe (EGP) : BGP

Domaine de transit et domaine

souche
Type de trafic
local source ou
destination au sein de
l’AS
transit trafic passant `a AS3

Typetravers
d’AS un AS. AS1
AS2
AS4

AS souche (stub AS) : AS7

AS5

connect´e AS6

`a un seul AS. Transporte

AS8

AS11

que du trafic local. AS9

AS multi-domicili´e : AS AS10
AS souche
(Stub−AS)

AS de transit

connect´e `a plus d’un (transit−AS)

AS multidomicilié
(multihomed−AS)

AS. Ne transporte pas

de trafic de transit.
AS transit : AS connect´e Département des
Sciences

`a plusded’un AS et
Informatiques

trafic
R´eseaux 78 / 88
 Protocoles de routage externe (EGP) : BGP

Domaine de transit et domaine

souche
Type de trafic
local source ou
destination au sein de
l’AS
transit trafic passant `a AS3

Typetravers
d’AS un AS. AS1
AS2
AS4

AS souche (stub AS) : AS7

AS5

connect´e AS6

`a un seul AS. Transporte

AS8

AS11

que du trafic local. AS9

AS multi-domicili´e : AS AS10
AS souche
(Stub−AS)

AS de transit

connect´e `a plus d’un (transit−AS)

AS multidomicilié
(multihomed−AS)

AS. Ne transporte pas

de trafic de transit.
AS transit : AS connect´e Département des
Sciences

`a plusded’un AS et
Informatiques

trafic
R´eseaux 78 / 88
 Protocoles de routage externe (EGP) : BGP

Domaine de transit et domaine

souche
Type de trafic
local source ou
destination au sein de
l’AS
transit trafic passant `a AS3

Typetravers
d’AS un AS. AS1
AS2
AS4

AS souche (stub AS) : AS7

AS5

connect´e AS6

`a un seul AS. Transporte

AS8

AS11

que du trafic local. AS9

AS multi-domicili´e : AS AS10
AS souche
(Stub−AS)

AS de transit

connect´e `a plus d’un (transit−AS)

AS multidomicilié
(multihomed−AS)

AS. Ne transporte pas

de trafic de transit.
AS transit : AS connect´e Département des
Sciences

`a plusded’un AS et
Informatiques

trafic
R´eseaux 78 / 88
 Protocoles de routage externe (EGP) : BGP

AS et
BGP

Chaque AS a
un ou plusieur border router g`erant le trafic inter
un BGP speaker (pour les AS participant au routage)
un speaker BGP ´etablit des sessions avec ses pairs et
annonce :
les r´eseaux locaux
les autres r´eseaux accessibles (pour les AS
de transit) donne des informations sur les
chemins (poids)
les routes supprim´ees

Département des
Sciences
Informatiques

R´eseaux 79 / 88
 Protocoles de routage externe (EGP) : BGP

Peering
2BGP
types de
peering client-
fournisseur
(customer-provider peering) :
laquelle un
Relation client (un
asym´etrique $
AS3

domaine de routage)
AS2

dans AS1 $ $
$
AS4

ach`ete une connectivit´e AS7

AS5

`a l’Internet aupr`es d’un AS6

$ $

fournisseur d’acc`es (un

AS8 $
AS11
$
autre domaine de AS9 $

routage). $

AS10
AS souche
(Stub−AS)

pair-`a-pair (shared-cost
AS de transit
(transit−AS)
AS multidomicilié
(multihomed−AS)

peering) : Relation sym $

shared cost
peering

´etrique ou` deux

client−customer
peering

domaines de routage
(souvent de mˆeme Département des
Sciences
Informatiques

importance) acceptent
d’interconnexi
R´eseaux 80 / 88
 Protocoles de routage externe (EGP) : BGP

Peering
BGP
client-fournisseur AS3

(customer-provider AS2
$

$ AS4
AS1 $
peering) : Relation asym AS7
$

´etrique dans laquelle un $ $

AS5

client (un domaine de

AS6
AS8 $

routage) ach`ete une

AS11
$

connectivit´e `a l’Internet
AS9 $
$

aupr`es d’un fournisseur

AS souche
(Stub−AS)
AS10
AS de transit
(transit−AS)

d’acc`es (un autre AS multidomicilié

(multihomed−AS)

domaine de routage). $
shared cost peering
client−customer
peering

Le client envoie ses routes internes et les routes

apprises de ses propres clients au fournisseur
⇒ Le fournisseur annoncera ces routes sur tout
l’Internet
Le fournisseur annonce `a son client toutes les routes Département des
Sciences
Informatiques

qu’il connaˆıt
R´eseaux 80 / 88
 Protocoles de routage externe (EGP) : BGP

Peering
BGP
AS3

$
AS2
AS4
AS1 $ $
$
pair-`a-pair (shared- AS7
AS5

cost
peering) : Relation sym AS6
$ $

´etrique ou` deux

AS8 $
AS11

domaines
(souvent de demˆeme
routage
$

AS9 $

importance) acceptent $

AS10
AS souche
(Stub−AS)

d’´echanger AS de transit
(transit−AS)
AS multidomicilié

gratuitement leurs
(multihomed−AS)

shared cost
peering

paquets `a travers un
$ client−customer
peering

point
Chaqued’interconnexion.
”peer” envoie `a l’autre ses propres routes et
celles de ses clients
Le point d’interconnexion sera utilis´e par l’un des pair
BGP pour atteindre les destinations de l’autre pair (ou
de ses clients) ⇒ Département des
Sciences

´echange de trafic local

Informatiques

R´eseaux 80 / 88
 Protocoles de routage externe (EGP) : BGP

Interconnexion
d’AS
Les routeurs des AS sont
connect´es :
AS4

par liaison point-`a-point

⇒ Seul mat´eriel AS1 AS5
commun : la liaison.
⇒ Cher si beaucoup
d’AS voisins g
´eographiquement AS2
par point d’´echange GIX
(Global Internet eXchange)
AS3
´egalement appel´e IXP
(Internet Exchange Point)

Département des
Sciences
Informatiques

R´eseaux 81 / 88
 Protocoles de routage externe (EGP) : BGP

Interconnexion
d’AS
Les routeurs des AS sont
connect´es :
AS4

par liaison point-`a-point

⇒ Seul mat´eriel AS1 AS5
commun : la liaison.
⇒ Cher si beaucoup Switch
d’AS voisins g
´eographiquement AS2 GIX
par point d’´echange GIX
(Global Internet eXchange)
AS3
´egalement appel´e IXP
(Internet Exchange Point)

Département des
Sciences
Informatiques

R´eseaux 81 / 88
 Protocoles de routage externe (EGP) : BGP

Messages et d´eroulement du
protocole BGP

1 open (1) : Chaque routeur BGP ´echange avec ses voisins

des messages pour ouvrir et n´egocier les param`etres la
session BGP. Initialement les routeurs BGP ´echangent la
2 totalit´e des information de routage.
update (2) : seules les modifications sont transmises. Un
num´ero est associ´e `a chaque version des informations
collect´ees par un routeur. Tous les voisins BGP doivent
3 avoir le mˆeme num´ero. Ce num´ero est modifi´e `a
chaque mise `a jour.
4 Keepalive (4) : transmis p´eriodiquement pour v
´erifier le bon fonctionnement de la session BGP.
Notification” (3) : messages sp´eciaux utilis´es pour
informer les voisins BGP des erreurs et des cas sp´eciaux.
Département des
Sciences
Informatiques

R´eseaux 82 / 88
 Protocoles de routage externe (EGP) : BGP

Informations ´echang´ees par les

routeurs BGP
Tableau d’accessibilit´e de pr´efixes IP (destinations). Pour
chacun des pr´efixes :
AS path : chemin d’AS sans boucle suivi pour atteindre la
destination. Next hop : Le prochain saut pour atteindre le r
´eseau
Poids (Weight) :
Pr´ef´erences locales : pour influencer le processus de
s´election du meilleur chemin. Interpretation locale `a
l’AS.
Multi-exit discriminator : pour informer une pr´ef´erence
relatives entre diff´erents points d’entr´ees.
Communaut´e (Community) : regroupement de
destination identifi´ee par un num´ero.
Origine :
... :
Ces informations permettent de construire un graphe form´e
Département des
Sciences
Informatiques

d’AS (sans boucle) sur lequel une

R´eseauxpolitique de routage peut 83 / 88
 Protocoles de routage externe (EGP) : BGP

Dorsales
paires

AS AS AS

Dorsal
e
routeur
AS AS core

POP1

AS AS
POP2

routeur
core

AS AS
AS
Département des
Sciences
Informatiques

R´eseaux 84 / 88
 Protocoles de routage externe (EGP) : BGP

En
pratique

chaque grand FAI est un AS

entre 2 AS, accord d’´echange de trafic entre 2 FAI :
entre GIX (Internet Exchange Point) ou ligne priv´ee
lou´ee
communication avec ses pairs par BGP
validation des annonces : Serveurs de routes IRR (Internet
Routing Registry) infos relatives aux blocs d´etenus par
chaque FAI
BGP est le coeur de l’Internet
probl`eme de validation des donn´ees des
serveurs de routes. probl`eme de routage
temporaire, trous noirs de l’Internet beaucoup de
mise `a jour BGP chaque jour !
Département des
Sciences
Informatiques

trop trop trop grosses table de routage `a

R´eseaux 85 / 88
 R´ef´erences
bibliographiques

1 Routage statique

2 Principes g´en´eraux du routage

dynamique

3 Protocoles de routage interne (IGP) :

RIP

4
5 Protocoles de
Protocoles de routage
routage interne
externe (IGP)
(EGP): :
OSPF
BGP
6 R´ef´erences
bibliographiques

Département des
Sciences
Informatiques

R´eseaux 86 / 88
 R´ef´erences
bibliographiques

TCP/IP : Architectures, protocoles et applications par

Douglas Comer aux ´editions Pearson education , 5`eme
´edition.
http ://www-lsr.imag.fr/users/Martin.Heusse/
le support de cours de Bernard Cousin sur BGP : le
routage inter-domaine
le support de cours de Jean-Jacques Pansiot sur le
routage inter-domaine et BGP
R´eseaux et t´el´ecoms - cours avec 129 exercices
corrig´es par Claude Servin aux ´editions Dunod ;
2`eme ´edition

Département des
Sciences
Informatiques

R´eseaux 87 / 88
 R´ef´erences
bibliographiques

RFC 2453 : RIPv2

RFC 2080 : RIPng
RFC 2328 :
OSPFv2 RFC
3630 : OSPF-TE
RFC 1584 : Multicast
OSPF5340
RFC RFC :4203
OSPF: OSPF
for IPV6
pour MPLSRFC 4271 : BGP4
(OSPFv3)

Département des
Sciences
Informatiques

R´eseaux 88 / 88