Protocole IP

Présentation des
principaux mécanismes
« avancés » de routage
Mamadou NDIAYE

Ecole Supérieure Polytechnique

Département Génie Electrique
Cours réseaux IP avancé
version 1.0

IP « avancé » M. NDIAYE 1
 Plan du cours
✔ Quelques rappels
q Allocation des adresses via DHCP
q Système de translation NAT / PAT
q Fonctionnement du routage : notions générales
q Les algorithmes de routage intra-domaine (IGP)
q Les algorithmes de routage inter-domaine (EGP)

IP « avancé » M. NDIAYE 2
 Quelques rappels …
Principales caractéristiques du protocole IP
q Réseau IP
– Interconnexion de réseaux « physiques », via des routeurs
q Adressage IP
– Adresses distribuées par plages, suivant trois classes : A, B et C
– Une classe d’@ peut être sous-adressée = ensemble de sous-classes
– Chaque classe ou sous-classe est associée à un masque d’adresse
– Une classe ou une sous-classe est installée sur un réseau physique
– Plusieurs classes/sous-classes peuvent être installées sur un réseau physique donné
q Une @IP est codée sur 32 bits
– Sur un réseau IP, chaque équipement relié à un réseau physique possède une @IP
unique sur ce réseau physique
q La couche IP s’appuie sur une famille de protocoles
– ICMP : gestion des erreurs et administration
– ARP, RARP : gestion de la résolution des adresses

IP « avancé » M. NDIAYE 3
 Quelques rappels …
Principales caractéristiques du protocole IP
q Les datagrammes sont routés indépendamment les uns des autres
– IP est un protocole en mode non connecté
– Chaque datagramme contient les informations nécessaires à son
acheminement (@émetteur, @destinataire)
– Equivalent d’un service postal
q IP est un protocole non fiable
– Les datagrammes peuvent être perdus
• Erreurs sur les réseaux physiques traversés
• Destruction par un routeur, suite à une congestion
– Les datagrammes peuvent être déséquencés ( = ne pas arriver dans l’ordre
d’émission)
q Toutes les normes du « monde IP » s’appellent des RFC (Request For
Comments)
– Par ex. : ICMP, RFC 792, 09/1981

IP « avancé » M. NDIAYE 4
 Quelques rappels …
Un exemple simple
Configuration IP de la station
•@IP : [Link]
•Masque : [Link]
•Routeur par défaut : [Link]
• @IP du serveur DNS : [Link] Serveur DNS d’@ [Link]
•Domaine par défaut : [Link] C
[Link],
[Link]

A
« reste du réseau IP »
Envoi de datagrammes IP
vers « [Link] »
B
Machine de nom « [Link] » ,
[Link],[Link] et d’@ IP [Link]
[Link]

IP « avancé » M. NDIAYE 5
 Quelques rappels
Récupération de l’@ IP de « [Link] »
Configuration IP de la station

802.3 vers @ϕ C | IP de [Link] à [Link] | UDP | Req. DNS « [Link] » ?

802.3 vers @ϕ B | IP de [Link] à [Link] | UDP | Rép. DNS [Link]

•@IP : [Link] Serveur DNS d’@
•Masque : [Link] [Link]
•Routeur par défaut : [Link] 4
• @IP du serveur DNS : [Link] On suppose ici que C
•Domaine par défaut : [Link] C connaît @ϕ B,
et que B connaît @ϕ C
[Link],
[Link]

B 5
[Link],[Link]

1 Broadcast 802.3 | Req ARP [Link] ?

2 802.3 vers @ϕ A | Rép ARP @ϕ B

802.3 vers @ϕ B | IP de [Link] à [Link] | UDP | Req. DNS « [Link] » ?

802.3 vers @ϕ A | IP de [Link] à [Link] | UDP | Rép. DNS [Link] 3

IP « avancé » M. NDIAYE 6
 Quelques rappels …
Envoi des datagrammes IP vers [Link]
Configuration IP de la station
•@IP : [Link]
•Masque : [Link]
•Routeur par défaut : [Link]
• @IP du serveur DNS : [Link]
•Domaine par défaut : [Link]

Relai de IP de [Link] à [Link] | TCP | Req. http

par le routeur, vers le « reste du réseau IP »
A 2
« reste du réseau IP »

B
Machine de nom « [Link] » ,
[Link],[Link] et d’@ IP [Link]

1
802.3 vers @ϕ B | IP de [Link] à [Link] | TCP | Req. http

IP « avancé » M. NDIAYE 7
 q Quelques rappels
✔ Allocation des adresses via DHCP
q Système de translation NAT / PAT
q Fonctionnement du routage : notions générales
q Les algorithmes de routage intra-domaine (IGP)
q Les algorithmes de routage inter-domaine (EGP)

IP « avancé » M. NDIAYE 8
 DHCP
Dynamic Host Configuration Protocol

q Protocole permettant l’allocation dynamique de

configuration IP : @IP, masque, routeur par
défaut, @IP du DNS, nom de domaine par défaut
– Offre plus de paramètres que le protocole BOOTP
– Compatible avec BOOTP (même format de messages,
même ports utilisés)
q S’appuie sur un modèle client / multi-serveurs
q Offre deux modes d’allocation
– Dynamique : distribution par pool (plage) d’adresses,
limitée dans le temps
– Statique : association @MAC,@IP fixée par
l’administrateur
IP « avancé » M. NDIAYE 9
 DHCP
Modèle client / serveur

q Les messages DHCP sont encapsulés dans UDP

– Port client : 67, port serveur : 68
q Le client recherche le ou les serveurs DHCP
disponibles en diffusant un broadcast IP :
[Link]
– Par défaut, ce message ne peut pas franchir un routeur
– Sans configuration spécifique du routeur par défaut (en
agent relais DHCP), client et serveur DHCP doivent se
trouver sur le même réseau physique, et dans la même
classe (ou sous-classe) d’@ IP
q Le serveur DHCP répond également via un
broadcast IP (le client ne connaît pas encore son
@ IP)
IP « avancé » M. NDIAYE 10
 DHCP
Notion de « bail »

q Utilisée pour l’allocation dynamique

q Bail = durée d’attribution d’une @ IP
q Le serveur DHCP affecte à une station une @
pendant une durée limitée (lease-time)
q Le client avant l’expiration doit demander à
renouveler ce bail, ou cesser d’utiliser cette @
– Le bail peut être résilié explicitement par le client
(message DHCPrelease)

IP « avancé » M. NDIAYE 11
 Exemple de configuration
Extrait du fichier de configuration [Link]
d’un serveur dhcpd sous Unix
# allocation dynamique d’une plage d’@ IP
# indique sur quel subnet fonctionne le serveur DHCP
subnet [Link] netmask [Link] {
range [Link] [Link]; # pool d’@ IP à distribuer
option domain-name-servers [Link]; # @ IP du dns
option domain-name « [Link] »; # nom de domaine par défaut
option routers [Link]; # @ IP routeur par défaut
option subnet-mask [Link]; # masque
default-lease-time 6000;
# durée du bail attribué par le serveur au client, si le client
n’en propose pas une lui même
max-lease-time 72000;
# durée du bail max. attribué par le serveur;
}

# allocation statique d’une @ IP

host pegasus {
hardware ethernet 00:50:04:5B:29:32;
fixed-address [Link];
}
IP « avancé » M. NDIAYE 12
 DHCP
Principaux messages DHCP

Nom du message Description

DHCPdiscover Utiliser par le client pour localiser les serveurs DHCP
disponibles
DHCPoffer Réponse du serveur à un message DHCPdiscover

DHCPrequest Envoyé par le client à un serveur pour accepter le serveur, le

refuser, ou bien encore renouveler le bail de son adresse
DHCPack Message du serveur contenant les paramètres de la
configuration IP du client
DHCPnack Message du serveur pour signaler au client que son bail d’@
a expiré, ou bien pour signaler au client qu’il demande une
mauvaise configuration réseau
DHCPrelease Permet au client d’informer le serveur qu’il libère son @ IP

IP « avancé » M. NDIAYE 13
 Initialisation
DHCP
Scénario d’échange de messages
serveur serveur
(sélectionné) client (non sélectionné)

Renouvellement d’une @
puis libération
serveur
client
Détermine Détermine
la configuration la configuration

Retrouve la
Sélection de configuration
la configuration

…….
Accord sur
la configuration

Configuration
effectuée

IP « avancé » M. NDIAYE 14
 q Quelques rappels
q Allocation des adresses via DHCP
✔ Système de translation NAT / PAT
q Fonctionnement du routage : notions générales
q Les algorithmes de routage intra-domaine (IGP)
q Les algorithmes de routage inter-domaine (EGP)

IP « avancé » M. NDIAYE 15
 NAT
Network Address Translation

q Motivations
– Nombre d’@ IPv4 insuffisantes pour couvrir la
totalité des besoins
q Solutions
– Utilisation plus « rationnelle » des classes d’@
IPv4
• Redistribution des classes existantes, sous-adressage
– Technique de translation d’adresses ou NAT
– Déploiement IPv6 (adressage sur 128 bits)
IP « avancé » M. NDIAYE 16
 NAT
Principe généraux
q Classes privées
– A : [Link] à [Link]
– B : [Link] à [Link]
– C : [Link] à [Link]
q Problématique : comment passer de manière
« transparente » d’une @ privée à une adresse public, et
inversement ?
Routeur réalisant
q Différentes formes de NAT un système de translation
d’adresses
– Statique
Réseaux « privés »
– Dynamique Utilisation de classes Réseau public
IP privées,
– Overloading non utilisée sur
= Internet

Internet

IP « avancé » M. NDIAYE 17
 NAT statique
q Configuration d’une table fixe de translation par
l’administrateur
– @IP privée <-> @IP public
q Utile quand une station du réseau privée doit être
accessible depuis Internet
Table statique :
[Link]<->[Link] Réseau public
Réseaux « privés » [Link]<->[Link]
[Link]<->[Link]

Source :
Source :
[Link]
[Link]

IP « avancé » M. NDIAYE 18
 NAT dynamique
q Translate une @IP privée en une @IP public « libre »,
choisie dans une plage d’@ configurée dans le routeur
– Les translations actives @IP privée <-> @IP public sont
conservées par le routeur dans une table
– Une @ public sort de la table et redevient libre, si aucun trafic
relatif à cette adresse n’est détecté par le routeur au bout d’un
certain temps Plage NAT dynamique
[Link] à [Link]
Table des @ allouées :
[Link]<->[Link]
Nouvelle entrée dans
Réseau public
Réseaux « privés » [Link]<->[Link] la table de translations
[Link]<->[Link]
[Link]<->[Link]

Source :
Source :
[Link]
[Link]

IP « avancé » M. NDIAYE 19
 Overloading ou PAT
Port Address Translation
q Le routeur dispose d’une seule @IP public (ex. un routeur ADSL), chaque
adresse privée est translatée vers cette adresse unique
q Pour distinguer les différents flots de trafic, on translate cette fois-ci les ports
source au niveau TCP et UDP, ou le champ « identifiant » d’un message
ICMP
– Les translations actives sont conservées par le routeur dans une table
– Une entrée de la table est purgée, si aucun trafic relatif à cette entrée n’est détecté
par le routeur au bout d’un certain temps
– Le routeur traite directement les éventuels conflits de ports
– Un serveur du réseau privé peut être rendu accessible via un mécanisme de port
forwarding (par ex. tout paquet destiné au port 23 d’une station du réseau privé est
translaté vers la même @ IP)
Table de translations actives
Réseaux « privés » [Link]:1332<->[Link]:1332 Réseau public
[Link]:1447<->[Link]:1447
Paquet TCP
@IP source : [Link] Paquet TCP
@IP source : [Link]
Port TCP source : 1332
Port TCP source : 1332
Paquet TCP
@IP source : [Link] Paquet TCP
@IP source : [Link]
Port TCP source : 1447
Port TCP source : 1447

@IP unique : [Link]

IP « avancé » M. NDIAYE 20
 q Quelques rappels
q Allocation des adresses via DHCP
q Système de translation NAT / PAT
✔ Fonctionnement du routage : notions générales
✔ Routage dynamique vs. routage statique
✔ La notion de Système Autonome (AS)
✔ Routage intra-domaine et inter-domaine
✔ Mécanismes CIDR, classless vs. classfull
q Les algorithmes de routage intra-domaine (IGP)
q Les algorithmes de routage inter-domaine (EGP)

IP « avancé » M. NDIAYE 21
 Notions générales
Routage statique / dynamique

q Routage statique
– Les entrées de routage sont configurées manuellement
par l’administrateur
– Convient bien à des « petites » configurations
– Difficile à faire évoluer
– Pas de prises en compte des pannes
q Routage dynamique
– Les routeurs s’échangent des messages pour
« apprendre » les routes
– Prise en compte automatique des nouvelles routes, en
cas d’extension du réseau, ou de pannes
– Les routes sont caractérisées par une métrique

IP « avancé » M. NDIAYE 22
 Notions générales
Routage dynamique : un peu de vocabulaire

q Protocole de routage (1)

– Fournit les mécanismes permettant au (2)

routeur de construire ses tables de routage

en partageant des informations de routage
avec les autres routeurs
– Ex. : RIP, OSPF (1)

q Algorithme de routage (2)

– Processus mathématique utilisé par le
routeur pour calculer ses tables de routage,
en fonction des informations récupérées à
l’aide du protocole de routage
– Ex. : vecteur distance (RIP), plus court
chemin d’abord (OSPF)
IP « avancé » M. NDIAYE 23
 Notions générales
Définition d’un Système Autonome

q Système autonome ou AS (Autonomous System)

– Ensemble de routeurs fonctionnant sous une seule
administration technique (mise en œuvre, configuration
et administration, surveillance …)
– Entreprise, campus, cœur d’un réseau national, un
ISP …
• Ex. : RENATER
– Un AS est désigné par un numéro codé sur 16 bits
• Actuellement, environ 11000 AS publics visibles
• AS officiels (publics et visibles) : 1 - 64511
• AS privés (non annoncés par les opérateurs) : 64512 - 65535
• Ex. : RENATER = AS 1717
q Internet = un ensemble d’AS interconnectés
IP « avancé » M. NDIAYE 24
 Notions générales
Interconnexion d’AS

ASx ASy

Routage intra-domaine = routage

à l’intérieur d’un AS

Routeur interne
Routeur « de bord »
ou routeur frontière Routage inter-domaine = routage
ASz entre AS

IP « avancé » M. NDIAYE 25
 Notions générales
Routage intra-domaine et inter-domaine

q Mise en œuvre des mécanismes de routage intra-domaine,

par l’administration technique de l’AS
– Mettre en œuvre un routage efficace qui reflète l’état du réseau à
l’intérieur d’un AS, selon des critères purement techniques = le plus
souvent, calculer le plus court chemin en fonction du débit, de la fiabilité,
du nombre de routeurs à traverser …
– Le routage intra-domaine peut s’appuyer sur le routage statique, et des
protocoles de routage « intérieur » ou intra-domaine = IGP (Interior
Gateway Protocol)
q L’administration technique de l’AS fait en sorte « d’annoncer » des
informations corrects de routage (= reflétant les @ accessibles au sein
de l’AS) au niveau des routeurs de frontière
– Permet la mise en œuvre du routage entre AS = routage inter-domaine
– Le routage inter-domaine s’appuie sur des protocoles de routage
« extérieur » ou inter-domaine = EGP (Exterior Gateway Protocol)
q Protocoles IGP ≠ Protocoles EGP
IP « avancé » M. NDIAYE 26
 Notions générales
IGP vs. EGP : des objectifs distincts

q Protocoles IGP
– Optimiser, trouver le meilleur
chemin « physique » à ASx ASy
l’intérieur de l’AS
– RIP, RIPv2, IGRP, EIGRP,
OSPF, IS-IS
q Protocole EGP
– Maintenir la connectivité entre
AS
– Sécuriser, appliquer une
politique de routage, on parle de
routage « politique » ≠ meilleur ASz
chemin physique
– Mécanisme d’annonces de Ex de routage « politique » : ASy peut refuser
routes = ASx déclare à ASy le trafic venant directement de ASx, et qui n’a
« les routes qu’il veut rendre pas transité par ASz (bien qu’un chemin
accessibles » pour ASy « plus direct » existe)
– EGP, BGPv4, MP-BGP
IP « avancé » M. NDIAYE 27
 Notions générales
Partage des adresses IP sur cinq niveaux
1. IANA (Internet Assigned Number Authority)
• Entité au niveau mondial qui a la plus haute autorité pour le
partage des @ IP
• Distribue des groupes d’@ IP à quatre organismes régionaux
2. APNIC (Asie et Pacifique), ARIN (Amérique du Nord et
Afrique du Nord), LACNIC (Amérique du sud) et RIPE
(Europe, Moyen Orient, Asie Centrale)
3. Les AS reçoivent les @ IP de leur base régionale
• Il n’est généralement pas nécessaire pour une entreprise de
monter un AS pour fournir des services Internet, à moins d’avoir
à gérer un trafic très dense !
• Coûts élevés de mise en œuvre et de gestion du réseau
4. « Fournisseurs Internet », au sens large (ISP) !
5. Puis l’utilisateur final, qui reçoit son ou ses @ IP du
fournisseur
IP « avancé » M. NDIAYE 28
 Notions générales
Ex. d’interrogation de la base du RIPE
[bidule:~] fweis% whois -h [Link] [Link] route: [Link]/16
% This is the RIPE Whois server. descr: RENATER
% The objects are in RPSL format. descr: Universite Pierre et Marie Curie
% descr: 4 place Jussieu 75252 PARIS CEDEX 05
% Rights restricted by copyright. descr: FRANCE
% See [Link] origin: AS2200
mnt-by: RENATER-MNT
inetnum: [Link] - [Link] changed: RenSVP@[Link] 19991008
remarks: source: RIPE
remarks: This inetnum has been transfered as part of the ERX.
remarks: It was present in both the ARIN and RIPE databases, so person: Roger Negaret
remarks: the information from both databases has been merged. address: Universite de Rennes 1, CRI
remarks: If you are the mntner of this object, please update it address: Campus de Beaulieu, Avenue du General Leclerc
remarks: to reflect the correct information. address: 35042 Rennes Cedex, France
remarks: phone: +33 2 23 23 71 49
remarks: Please see the information for this process: e-mail: [Link]@[Link]
remarks: [Link] nic-hdl: RN252-RIPE
remarks: mnt-by: RENATER-MNT
remarks: **** INFORMATION FROM ARIN OBJECT **** changed: rensvp@[Link] 19970416
remarks: netname: VERDUR-E changed: rensvp@[Link] 20030103
descr: Centre Interuniversitaire de Calcul de Bretagne (CICB) source: RIPE
descr: Campus de Beaulieu
descr: 35042 Rennes Cedex person: Odile Germes
remarks: country: FR address: Universite de Rennes 1
admin-c: OG238-RIPE address: CRI - Campus de Beaulieu,
tech-c: OG238-RIPE address: 35042 RENNES-cedex,
remarks: changed: hostmaster@[Link] 19910409 address: FR
remarks: changed: hostmaster@[Link] 19980410 phone: +33 2 99 84 71 31
remarks: **** INFORMATION FROM RIPE OBJECT **** e-mail: hostmaster@[Link]
netname: VERDUR-E nic-hdl: OG238-RIPE
descr: Centre Interuniversitaire de Calcul de Bretagne mnt-by: RIPE-ERX-MNT
descr: Universite de Rennes I changed: hostmaster@[Link] 19980410
descr: Campus de Beaulieu, Avenue du General Leclerc, 35042 Rennes CEDEX, France changed: hostmaster@[Link] 19980410
country: FR changed: er-transfer@[Link] 20031003
admin-c: RN252-RIPE source: RIPE
tech-c: RN252-RIPE
status: ASSIGNED PA
mnt-by: RENATER-MNT
changed: ripe-dbm@[Link] 19990706
changed: ripe-dbm@[Link] 20000225
changed: rensvp@[Link] 20020328
changed: er-transfer@[Link] 20031030
changed: ripe-dbm@[Link] 20040430
source: RIPE

IP « avancé » M. NDIAYE 29
 Notions générales
CIDR : Classless Inter-domain Routing (1)
q Différents problèmes
– Pratiquement plus de classes B disponibles
– Espace d’adressage IPv4 en cours d’épuisement
– Croissance très rapide de la taille des tables de routage
• Problème crucial en routage inter-domaine : de plus en plus de routes à
annoncer entre les AS
q CIDR
– Supprime l’usage des classes A, B, C : on parle de classless
– Toutes les adresses réseaux sont annoncées avec un masque qui peut être
de taille arbitraire, par ex. /9 indique que les 9 premiers bits de l’@
désigne le numéro de réseau
– Les routeurs ne se basent plus sur les trois premiers bits de chaque @ pour
déterminer la classe du réseau (=classfull), seul le préfixe fait loi
q Avant CIDR
– 256 classes C consécutives = 256 routes annoncées !
q Avec CIDR
– [Link]/15 offre un nombre d’@ équivalent à 512 classes C (217 @)

IP « avancé » M. NDIAYE 30
 Notions générales
CIDR : Classless Inter-domain Routing (2)

q Exemple : un ISP doit fournir 900 @ à un

client
– Une classe B
– Une partie de classe B sous adressé
– Quatre classes C Annonce
– Le bloc [Link]/22 (soit 1024 @ [Link]/22
disponibles)
F Système plus « souple » que le
sous-adressage
q Concerne avant tout le routage
inter-domaine, et les « gros » ISP
– Nécessite que les routeurs supportent
l’environnement classless et puisse
interpréter les « préfixes » CIDR dans les
annonces de routes
– Les agrégations CIDR sont supportées par
l’algorithme de routage inter-domaine
BGPv4
IP « avancé » M. NDIAYE 31
 q Quelques rappels
q Allocation des adresses via DHCP
q Système de translation NAT / PAT
q Fonctionnement du routage : notions générales
✔ Les algorithmes de routage intra-domaine (IGP)
✔ Les algorithmes « vecteur distance » (distant vector)
✔ RIP, RIPv2, IGRP, EIGPR
✔ Les algorithmes « état de lien » (link state)
✔ OSPF
q Les algorithmes de routage inter-domaine (EGP)

IP « avancé » M. NDIAYE 32
 RIP : algorithme + protocole
« vecteur distance »
q S’appuie sur l’échange d’information entre routeurs adjacents = deux
routeurs connectés via une liaison directe = voisins directs, sans
routeur intermédiaire
– Très simple à mettre en œuvre sur un réseau local (par ex. Ethernet)
q Chaque routeur connaît initialement le coût de ses propres liaisons
– Métrique simple : coût = 1 ou one hop
– Métrique d’une route = nombre de routeurs à traverser pour atteindre la
destination
q Chaque routeur diffuse vers les routeurs adjacents la liste des routes
qu’il connaît (=protocole)
q Puis chaque routeur calcule localement les meilleurs routes, sur la base
des informations récoltées (=algorithme)
☞ Apprentissage progressif de toutes les routes

IP « avancé » M. NDIAYE 33
 Algorithme « vecteur distance »
Envoi d’une route
q Format d’une route reçue
@réseau destination + masque + métrique Route envoyée par @routeur,
(@ routeur adjacent + interface de sortie sont implicitement connues par le routeur qui reçoit la route) Reçue sur interface ifx

q Chaque route reçue est comparée aux entrées de la table

de routage (en rajoutant +1 à la métrique reçue)
1. Si la destination reçue n’existe pas, et que la métrique n’est pas
infinie, la route est ajoutée dans la table du routeur
2. Si la destination reçue existe, et que la métrique obtenue est
meilleure, alors on met à jour la table du routeur
3. Si la destination reçue existe, et que le routeur qui a envoyé la
table est le routeur adjacent déjà connu, et que la métrique
obtenue est différente, alors on met à jour la table du routeur
• Permet d’augmenter éventuellement la métrique (reconfiguration,
modification de la topologie du réseau)
4. Sinon, aucun changement
IP « avancé » M. NDIAYE 34
 Exemple (1)
IF1 : [Link] IF2 : [Link] IF1 : [Link] IF2 : [Link] IF1 : [Link] IF2 : [Link]
[Link] [Link] [Link] [Link]

Destination RA. Int. Métr. Destination RA. Int. Métr. Destination RA. Int. Métr.
[Link] - IF1 0 [Link] - IF1 0 [Link] - IF1 0
[Link] - IF2 0 [Link] - IF2 0 [Link] - IF2 0

[Link],0 [Link],0 [Link],0 [Link],0 [Link],0 [Link],0

[Link],0 [Link],0 [Link],0 [Link],0 [Link],0 [Link],0

Destination RA. Int. Métr. Destination RA. Int.Métr. Destination RA. Int. Métr.
[Link] - IF1 0 [Link] - IF1 0 [Link] - IF1 0
[Link] - IF2 0 [Link] - IF2 0 [Link] - IF2 0
[Link] [Link] IF2 1 [Link] [Link] IF1 1 [Link] [Link] IF1 1
[Link] [Link] IF2 1

IP « avancé » M. NDIAYE 35
 Exemple (2)
[Link],0 [Link],0
[Link],0 [Link],0 [Link],0 [Link],0 [Link],0 [Link],0
[Link],0 [Link],0 [Link],1 [Link],1 [Link],0 [Link],0
[Link],1 [Link],1 [Link],1 [Link],1 [Link],1 [Link],1

Destination RA. Int. Métr. Destination RA. Int.Métr. Destination RA. Int. Métr.
[Link] - IF1 0 [Link] - IF1 0 [Link] - IF1 0
[Link] - IF2 0 [Link] - IF2 0 [Link] - IF2 0
[Link] [Link] IF2 1 [Link] [Link] IF1 1 [Link] [Link] IF1 1
[Link] [Link] IF2 2 [Link] [Link] IF2 1 [Link] [Link] IF1 2

[Link],0 [Link],0 [Link],0 [Link],0 [Link],0 [Link],0

[Link],0 [Link],0 [Link],0 [Link],0 [Link],0 [Link],0
[Link],1 [Link],1 [Link],1 [Link],1 [Link],1 [Link],1
[Link],2 [Link],2 [Link],1 [Link],1 [Link],2 [Link],2

Destination RA. Int. Métr. Destination RA. Int.Métr. Destination RA. Int. Métr.
[Link] - IF1 0 [Link] - IF1 0 [Link] - IF1 0
[Link] - IF2 0 [Link] - IF2 0 [Link] - IF2 0
[Link] [Link] IF2 1 [Link] [Link] IF1 1 [Link] [Link] IF1 1
[Link] [Link] IF2 2 [Link] [Link] IF2 1 [Link] [Link] IF1 2
Régime stable

IP « avancé » M. NDIAYE 36
 RIP
Périodicité des échanges

q En régime stable (pas de changement dans les

tables)
– Messages RIP échangés toutes les 30s ± 0 à 5s
q Principe du triggered update ou flash update
– Un message RIP est diffusé à ± 0 à 5s dès que la table
de routage locale est modifiée
– Permet une prise en compte rapide des modifications
q Principe du route time-out
– Un routeur dont on ne reçoit plus de messages RIP
depuis 180 s devient inaccessible (métrique = ∞)
– Les entrées de la table de routage apprises via RIP sont
donc valables 3 minutes
IP « avancé » M. NDIAYE 37
 RIP : problème de convergence (1)
Le routeur ne reçoit plus de message RIP
[Link],1 [Link],1 [Link],1 depuis 3 min. La route est déclarée inaccessible,
[Link],1 [Link],1 [Link],1 et n’est plus diffusée
[Link],2 [Link],2 [Link],2
[Link],3 [Link],3

Destination RA. Int. Métr. Destination RA. Int.Métr.

[Link] - IF1 1 [Link] - IF1 1
[Link] - IF2 1 [Link] - IF2 1
[Link] [Link] IF2 2 [Link] [Link] IF1 2 Routeur en panne
[Link] [Link] IF2 3 [Link] [Link] IF2 ∞ Accès à [Link] impossible

[Link],1 [Link],1 [Link],1

[Link],1 [Link],1 [Link],1
[Link],2 [Link],2 [Link],2
[Link],3 [Link],3

Destination RA. Int. Métr. Destination RA. Int.Métr.

[Link] - IF1 1 [Link] - IF1 1
[Link] - IF2 1 [Link] - IF2 1
[Link] [Link] IF2 2 [Link] [Link] IF1 2
[Link] [Link] IF2 3 [Link] [Link] IF1 4

IP « avancé » M. NDIAYE 38
 RIP : problème de convergence (2)
[Link],1 [Link],1 [Link],1
[Link],1 [Link],1 [Link],1
[Link],2 [Link],2 [Link],2
[Link],5 [Link],5 [Link],4

Destination RA. Int. Métr. Destination RA. Int.Métr.

[Link] - IF1 1 [Link] - IF1 1
[Link] - IF2 1 [Link] - IF2 1
[Link] [Link] IF2 2 [Link] [Link] IF1 2
[Link] [Link] IF2 5 [Link] [Link] IF1 4

q La convergence prend un temps infini !

q Afin de réduire le temps de convergence, on « limite » la
valeur de l’infini
– Dans RIP, ∞ = 16
– Un « domaine » de routage RIP n’excède pas 15 sauts de routage,
ce qui limite l’usage de RIP à des petites configurations

IP « avancé » M. NDIAYE 39
 Technique de « l’horizon
coupé » (1)
Split horizon
q Utilisé pour accélérer le problème de
convergence présenté précédemment
– On interdit à un routeur d’envoyer une route à
un routeur adjacent quand cette route passe par
ce routeur adjacent
Le routeur ne reçoit plus de message RIP
[Link],1 [Link],1 [Link],1 depuis 3 min. La route est déclarée inaccessible,
[Link],1 [Link],1 [Link],1 et n’est plus diffusée
[Link],2 [Link],2 [Link],2
[Link],3 [Link],3

Destination RA. Int. Métr. Destination RA. Int.Métr.

[Link] - IF1 1 [Link] - IF1 1
[Link] - IF2 1 [Link] - IF2 1
[Link] [Link] IF2 2 [Link] [Link] IF1 2 Routeur en panne
[Link] [Link] IF2 3 [Link] [Link] IF2 ∞ Accès à [Link] impossible

IP « avancé » M. NDIAYE 40
 Technique de « l’horizon
coupé » (2)
Split horizon

q Mais cette technique ne résout pas tous les

problèmes de convergence !
– Dans RIP, on s’appuie sur une connaissance de l’état
du réseau qui ne dépasse pas le lien vers le routeur
adjacent
– Une route peut passer par un lien coupé, et la
« mauvaise nouvelle » mettra du temps à se propager
vers l’ensemble des routeurs
q Solution : s’appuyer sur un protocole à état de
lien, par ex. OSPF (cf. suite du chapitre)
IP « avancé » M. NDIAYE 41
 Technique du « poison reverse »
q Un routeur diffuse les destinations qui deviennent
inaccessibles (route time out = 180 s, métrique = ∞)
– Les messages RIP informent des mauvaises routes, en
plus des meilleures routes
q Le routeur qui reçoit une route marquée inaccessible
(métrique = ∞) l’intègre en tant que telle dans sa
table
– Si au bout d’une durée route flush = 120 s, aucune
nouvelle entrée n’est venue modifier la métrique, et donc
que cette route est toujours marquée inaccessible, elle est
effacée de la table
IP « avancé » M. NDIAYE 42
 Les deux versions de RIP
Principales caractéristiques

q Encapsulation : IP | UDP (port 520) | RIPv1 ou RIPv2

q RIPv1
– Pas de support du sous-adressage
– Diffusion des messages RIP en broadcast IP ([Link])
– Pas d’authentification des routeurs
q RIPv2
– Support du sous-adressage
– Diffusion multicast ([Link])
– Permet l’authentification des routeurs
q RIPv1 et RIPv2 a priori compatible
– Mais leur cohabitation au sein d’un même réseau est souvent
délicate
IP « avancé » M. NDIAYE 43
 Format d’un message RIPv1
0 7-8 15-16 31 bits
Commande Version = 1 à0
q Commande
– 1 : requête, utilisée
par un routeur pour Identificateur de la famille d’@ = à0
réclamer une table, 2
sans attendre sa @ de destination
diffusion normale

Répété jusqu’à 25 fois

(par ex., utilisé au
démarrage du à0
routeur)
– 2 : réponse, utilisée à0
par un routeur pour
envoyer ses tables
Métrique

IP « avancé » M. NDIAYE 44
q
Format d’un message RIPv2
Domaine de routage
– Numéro de plan de routage
permettant de créer une 0 7-8 15-16 31 bits
partition au sein des Commande Version = 2 Domaine de routage
routeurs ; un routeur ne
prend en considération que
les messages RIP venant de Identificateur de la famille d’@ = Route tag
son domaine de routage
2 ou 0xFFFF
q Route tag
– Utilisé pour distinguer les @ de destination

Répété jusqu’à 25 fois

routes apprises via d’autres
protocoles de routage
inter-domaine Masque
q Routeur adjacent
– Peut prendre Routeur adjacent
éventuellement une autre
valeur que l’@ du routeur
émetteur du message RIP Métrique
q Un message RIPv2
authentifié contient 0xFFFF
dans le champ
« identificateur », le champ
route tag contient le type
d’authentification + 16
octets suivants pour la clef
d’authentification
IP « avancé » M. NDIAYE 45
 IGRP
Interior Gateway Routing Protocol

q Protocole propriétaire CISCO

q Utilise les informations envoyées par les voisins directement
connectés (comme RIP)
q Implémente les mécanismes de poison reverse et split horizon
q Permet de lever certaines limitations de RIP
– Pas de limite à 15 routeurs
– Capable de faire de l’équilibrage de charge entre plusieurs routes
équivalentes (jusqu’à 4 routes équivalentes pour une même destination)
– Charge moins le réseau que RIP : messages IGRP envoyés toutes
les 90 s
q Métrique associée au coût d’un lien plus « fine » que dans RIP,
combinant plusieurs paramètres
q Protocole remplacé par EIGRP

IP « avancé » M. NDIAYE 46
 EIGRP
Enhanced Interior Gateway Routing Protocol

q Tout comme IGRP, utilise une métrique hybride

q Plus performant que IGRP
– Convergence plus rapide
– Pas d'échange périodique des tables de routage, mais
mise à jour partielle
☞Moins de bande passante consommée
q Différence principale entre IGRP et EIGRP :
DUAL
– Diffusing Update ALgorithm : algorithme recherchant
une convergence plus rapide des informations
q Mais reste propriétaire, et complexe à mettre en
oeuvre
IP « avancé » M. NDIAYE 47
 EIGRP et IGRP
Calcul des métriques

q Métrique hybride, combinaison de plusieurs données

q Données statiques
– Bande passante de la liaison (1200b/s a 10Gb/s)
– MTU de la liaison (Maximum Tranfer Unit)
q Délai
– 100 : Ethernet 100, FDDI ou ATM 155 Mb/s
– 1000 : Ethernet 10
– 20000 : Interface série ou RNIS.
– 100000 : Interface asynchrone
q Données calculées
– Charge liaison (rapport sur 255) (Load)
– Fiabilité de la liaison (rapport sur 255) (Rely)

IP « avancé » M. NDIAYE 48
 q Quelques rappels
q Allocation des adresses via DHCP
q Système de translation NAT / PAT
q Fonctionnement du routage : notions générales
✔ Les algorithmes de routage intra-domaine (IGP)
✔ Les algorithmes « vecteur distance » (distant vector)
✔ RIP, RIPv2, IGRP, EIGPR
✔ Les algorithmes « état de lien » (link state)
✔ OSPF
q Les algorithmes de routage inter-domaine (EGP)

IP « avancé » M. NDIAYE 49
 Etat de lien vs. vecteur distance (1)
q Dans les protocoles à vecteur distance, le calcul
des routes s’appuie sur une vision « locale » du
réseau (= état du lien connecté au routeur)
– Convergence lente
– Existence de boucles de routage en cas de
reconfiguration
– Peu adapté à de grandes configuration réseau
[Link] [Link] [Link]
…….

?
Destination RA. Int. Métr.
[Link] - IF1 1
[Link] - IF2 1 État des liens traversés inconnu
[Link] [Link] IF2 9

IP « avancé » M. NDIAYE 50
 Etat de lien vs. vecteur distance (2)
q Solution : protocole à état de lien
– Chaque routeur possède une base de données qui
rassemble l’état de tous les liens du réseau
– Grâce à cette connaissance fine de l’état de tous les
liens, chaque routeur peut calculer rapidement sa table
de routage, s’adapter à des reconfigurations réseaux
(pannes, redémarrage, extension du réseau …)
État de tous
les liens du réseau

Calcul des routes

lien

IP « avancé » M. NDIAYE 51
 OSPF
Open Shortest Path First
q Un protocole (Hello, échange, inondation) + un algorithme (SPF)
q Chaque routeur possède une base de données résumant l’état des liens
du réseau
– = Link state routing
q Chaque routeur exécute l’algorithme SPF (Dijkstra) pour calculer les
tables de routage, en utilisant les données de sa base
– Permet de déterminer localement le plus court chemin vers chaque
destination du réseau
q Convergence plus rapide que RIP
q Adapté à des configurations de taille importante
– S’appuie sur une vision hiérarchique et évolutive des réseaux
– Un ensemble de zones (area) interconnectés à une zone backbone
q Peut fonctionner sur des réseaux à diffusion (par ex. Ethernet), et sur
des réseaux sans diffusion (par ex. Frame Relay)

IP « avancé » M. NDIAYE 52
 Protocole OSPF
Repose sur trois « sous-protocoles »
1. Hello
– Identification des voisins immédiats (= routeurs
connectés via un lien physique), et évaluation de l’état
des liens du routeur
3. Echange
– Echange de l’état des liens, afin d’initialiser au
niveau de chaque routeur sa base d’état de liens
5. Inondation
– Utilisé quand l’état d’un lien du réseau a changé ou
périodiquement, permet une mise à jour rapide des
bases de données sur l’ensemble des routeurs
IP « avancé » M. NDIAYE 53
 Protocole Hello
q Message court envoyé périodiquement par un routeur sur
toutes ces interfaces, afin de vérifier l’état de ces liens
q Principaux paramètres d’un message Hello
– Router ID : plus grande @IP de l’interface qui envoie le message
– Hello interval : période des envois de messages Hello (10 s)
– Dead interval : temps au bout duquel le routeur considère un
voisin comme mort, s’il n’a pas reçu de message Hello (40 s)
– Neighbor : liste des @IP des routeurs voisins que le routeur a
reconnu via des échanges de messages Hello
– Area : numéro de la zone à laquelle appartient le routeur (cf. suite)
– Router priority : priorité du routeur (cf. suite), utilisé pour
l’élection du DR et du BDR
– DR et BDR : @IP du routeur élu et du routeur de secours (cf.
suite), s’ils existent

IP « avancé » M. NDIAYE 54
 Notion de routeurs « adjacents »
q Des routeurs sont dits adjacents s’ils ont
les mêmes valeurs ( = la même vision de
l’état du réseau) dans leur base d’état de
lien
– Les bases sont « synchronisées »
q Les routeurs voisins s’envoient chacun
des messages Hello, pour s’assurer de
Message Hello
leur présence « mutuelle », et de l’état
du lien les reliant
q Les routeurs peuvent ensuite construire
une relation d’adjacence, en diffusant
l’état de leurs liens, via le protocole
d’échange Echange des états
de lien

IP « avancé » M. NDIAYE 55
 Protocole d’échange
q Ce protocole est utilisé pour l’initialisation des bases, après une exécution
« mutuellement » réussi du protocole Hello
q Le routeur place l’état de tous ces liens dans des messages LSAs (Link State
Advertisement)
q Une entrée LSA contient principalement
– @ IP du routeur
– Le coût de la liaison avec un voisin immédiat
– Un numéro de séquence (qui permet de dater l’information d’état du lien)
q Le protocole d’échange permet à l’ensemble des routeurs de s’échanger des
messages LSAs, afin de synchroniser leur base, et de posséder une vue
d’ensemble du réseau
– Des routeurs possédant des bases synchronisées sont dits « adjacents »
– A la fin du processus d’échange, tous les routeurs doivent avoir la même base
d’état de lien
– Ils passent alors au statut FULL
– Un routeur qui n’a échangé aucune information avec aucun autre routeur a le statut
DOWN
q Une fois la base synchronisée, le routeur exécute l’algorithme SPF pour
calculer ses tables de routage
q Par la suite, c’est le protocole d’inondation qui est utilisé
IP « avancé » M. NDIAYE 56
 Protocole d’inondation
flooding

q Protocole utilisé lorsqu’un lien a changé d’état dans le réseau

– Panne du lien, apparition du lien, modification de la métrique …
q … ou pour des échanges périodiques (toutes les 30 minutes)
q Un routeur qui a détecté le changement envoie des paquets
LSUs (link state update) à tous les routeurs
– Contient les entrées LSAs mises à jour
q A la réception des paquets LSUs, un routeur
– Met à jour sa base d’état de lien
– Exécute l’algorithme SPF pour recalculer ses tables
q Permet une mise à jour rapide des tables de routage

IP « avancé » M. NDIAYE 57
 Utilisation d’un routeur élu (1)
DR : Designated Router
q La diffusion des messages LSAs via les protocoles
d’échange et d’inondation, génère beaucoup de
charge sur le réseau
q Objectif : réduire le trafic des mises à jour des
informations de routage
– N routeurs -> N*(N-1) / 2 relations d’adjacences !
q Solution : utiliser un « routeur élu » (DR), et un
« routeur élu de secours » (BDR : Backup DR)
– Sur chaque réseau physique (ex. Ethernet, Frame
Relay), on désigne un DR et un BDR
– Pour effectuer cette élection, les routeurs comparent
leur priorité respective durant l’échange des messages
Hello
IP « avancé » M. NDIAYE 58
 Utilisation d’un routeur élu (2)
Contenu d’un message Hello

q Principaux paramètres d’un message Hello

– Router ID : plus grande @IP de l’interface qui envoie le message
– Hello interval : période des envois de messages Hello (10 s)
– Dead interval : temps au bout duquel le routeur considère un
voisin comme mort, s’il n’a pas reçu de message Hello (40 s)
– Neighbor : liste des @IP des routeurs voisins que le routeur a
reconnu via des échanges de messages Hello
– Area : numéro de la zone à laquelle appartient le routeur (cf. suite)
– Router priority : priorité du routeur, utilisé pour l’élection du
DR et du BDR
– DR et BDR : @IP du routeur élu et du routeur de secours, s’ils
existent

IP « avancé » M. NDIAYE 59
 Fonctionnement (1)
q Le routeur élu agit comme un « point central » de contact pour l’envoi
des messages LSAs
– Les routeurs envoie leur information d’état de lien au DR
– Le DR diffuse ces informations à l’ensemble des routeurs
q Avantages
– Moins de messages échangés lors de l’exécution du protocole d’échange
et d’inondation
– Les bases sont synchronisées beaucoup plus facilement : un routeur est
adjacent du seul DR
DR

Sans routeur élu

Avec routeur élu
N*(N-1)/2 adjacences
N-1 adjacences

IP « avancé » M. NDIAYE 60
 Fonctionnement (2)
q Sur une ligne « point-à-point » connectant deux routeurs,
une telle élection ne sert à rien
– Pas de DR et de BDR
q Le BDR remplit les tâches du DR, si ce dernier tombe en
panne
– BDR = routeur ayant la seconde priorité, après le DR
– Si le DR ne répond pas assez rapidement aux messages du BDR, le
BDR le remplace, et un nouveau BDR est élu
q La priorité associée à chaque routeur peut être modifiée
par l’administrateur
– Possibilité de forcer l’élection, afin de désigner un routeur plus
puissant, à même de supporter la charge induite par la fonction de
DR
– Sur un routeur Cisco : ip ospf priority number
IP « avancé » M. NDIAYE 61
 Résumé
1. Au démarrage, identification de ces voisins, et élection éventuelle
d’un DR et BDR sur chaque réseau (protocole Hello)
2. Formation d'une adjacence (les routeurs échangent leur LSAs avec
le DR) entre chaque routeur et le DR (protocole d’échange)
ü Le DR transmet alors une base synchronisée à chaque routeur
ü Chaque routeur à l’état FULL
3. Exécution de l’algorithme SPF au niveau de chaque routeur ayant
l’état FULL : calcul des tables de routage
PUIS (en parallèle)
4a. Echange périodique de messages Hello, pour vérifier l’état des
liens, et modifier si besoin le DR et le BDR
4b. Echange périodique de LSA, ou mise à jour suite à un changement
d’état (protocole de flooding)

IP « avancé » M. NDIAYE 62
 Découpage en zones (1)
q Problème
– Les protocoles utilisés par OSPF génèrent
beaucoup de charge sur le réseau
– L’algorithme SPF utilisé pour le calcul des
routes est gourmand en ressource processeur
☞Le réseau géré via OSPF ne peut pas
dépasser une certaine taille (50 routeurs)
q On découpe le réseau en zones (area)

IP « avancé » M. NDIAYE 63
 Découpage en zones (2) Base d’état de lien pour la zone x

Base d’état de lien pour la zone y

q Chaque zone est identifiée par un numéro
ZONE x
q Dans chaque zone, on exécute les trois protocoles
d’OSPF
q Chaque routeur maintient une base d’état des
liens relative à la zone auquel il appartient
q Un routeur de bordure de zone (ABR : Area
Border Router) possèdent des interfaces attachées Échanges des
à plusieurs zones, et assure ainsi le passage des informations de
routage
ABR

informations de routage entre zones

q Un ABR possède une base d’état de lien pour
chacune des zones à laquelle il est connecté
q Une zone peut avoir un ou plusieurs ABRs

ZONE y

IP « avancé » M. NDIAYE 64
 Découpage en zones (3)
Prise en compte de l’intra-area et inter-area dans la base de données

q On distingue deux types de routage

1. Intra-area
2. Inter-area
☞ Assurer une vue globale du routage entre les
différentes zones
q La base de données d’un routeur contient en fait
1. L’état des liens de la zone
2. Les enregistrements récapitulatifs envoyés par le ou
les ABR de la zone
☞ Sur cette base, l’algorithme SPF calcule une table de
routage globale pour toutes les zones
IP « avancé » M. NDIAYE 65
 Zones principales et secondaires (1)
Structure hiérarchique d’un réseau OSPF

q Zone backbone, de numéro 0, obligatoire

q Les autres zones, dites secondaires
– Numérotées de 1 à 4294996795
– Connectées obligatoirement à la zone backbone
q C’est la zone backbone qui assure le passage des
tables de routage entre les zones secondaires
– Elle doit donc offrir une bonne connectivité
– Minimiser les risques de partition du réseau, en cas de
panne

IP « avancé » M. NDIAYE 66
 Zones principales et secondaires (2)
Structure hiérarchique d’un réseau OSPF

Area 0 (backbone)

ABR ABR

Zone secondaire
Tous les nœuds ont une vue
complète du réseau (routage
intra-area et inter-area) et
calculent toutes les routes pour
Routeur interne
l’ensemble du réseau

Area 1 Area 2
Aide secondaire

IP « avancé » M. NDIAYE 67
 Zones principales et secondaires (3)
Rôle d’un ASBR

ASBR
Area 0 (backbone)

ABR ABR

Présence éventuelle d’un

AS Border Router (ASBR),
au niveau de
la zone backbone :
Routeur frontière de l'AS
Routeur interne qui exporte via OSPF
les routes extérieures
à l'AS (apprises via un protocole
Inter-domaine, comme BGP par ex.)
Area 1 Area 2
Aide secondaire

IP « avancé » M. NDIAYE 68
 Zones principales et secondaires (4)
Structure hiérarchique d’un réseau OSPF

Area 0 (backbone)

ABR ABR ABR

Zone terminale (stub area)

•Même comportement que les
zones secondaires
•Ne mémorisent pas les
informations sur les routes
externes, envoyées par des
routeurs utilisant d’autres
algorithmes de routage
Area 1 Area 2 Area 3 •Toutes les routes externes sont
récapitulées dans une route par
défaut

IP « avancé » M. NDIAYE 69
 OSPF en résumé
q Routage intra-domaine, par état de lien (link state)
q Messages OSPF encapsulés directement dans IP (protocole numéro 89)
q Utilisation d’@ multicast
– [Link] pour le DR et le BDR
– [Link] pour les autres routeurs
q Pas de limitation du nombre de routeurs
q Support théorique de métriques multiples, fonction de paramètres
multiples
– Débit, délai, coût, fiabilité
– Capable d’utiliser les critères du champ TOS d’un datagramme IP
– Permet de gérer plusieurs routes pour une même destination
q Valeur de la métrique par défaut
– 108 / débit max. en b/s
• Lien Ethernet, coût = 10
• Ligne série à 56kb/s, coût = 1785
q Authentification possible des routeurs
– Mot de passe en clair
– Mot de passe crypté

IP « avancé » M. NDIAYE 70
 q Quelques rappels
q Allocation des adresses via DHCP
q Système de translation NAT / PAT
q Fonctionnement du routage : notions générales
q Les algorithmes de routage intra-domaine (IGP)
✔ Les algorithmes de routage inter-domaine
(EGP)
✔ Protocole EGP
✔ Protocole BGP

IP « avancé » M. NDIAYE 71
 Routage inter-domaine
q Routage inter-domaine ou EGP
– Routage entre AS, maintien de la connectivité entre AS
– Mise en œuvre d’un routage « politique » via un mécanisme
d’annonce de routes
– En annonçant une route à un AS, on la rend accessible à cet
AS
q Deux protocoles de type EGP
– EGP : Exterior Gateway Protocol
• Simple, obsolète, de moins en moins utilisé
• Repose sur une architecture fortement hiérarchisée d’un réseau IP
– BGP : Border Gateway Protocol
• Version 4 la plus récente, supporte notamment l'agrégation CIDR et
des architectures d’interconnexion d’AS complexes

IP « avancé » M. NDIAYE 72
 EGP (1)
Caractéristiques
q EGP (RFC 904)
– Un des premiers protocoles de
routage inter-domaine entre le cœur
ARPANET, et les réseaux connectés Réseau fédérateur
« périphériques » connectés à ce cœur As w
q Ne peut être utilisé qu’avec une
topologie fortement
« hiérarchisée »
– Un réseau fédérateur, interconnectant
des AS périphériques via un routeur
unique AS x AS y AS z
– Topologie en étoile
☞ Repose sur une vision ancienne et
maintenant obsolète de ce qu’est
un réseau IP
IP « avancé » M. NDIAYE 73
 EGP (2)
Caractéristiques

q EGP repose sur le concept de voisinage

– Echange de messages EGP entre deux routeurs, sans diffusion
q Deux types de voisinage possibles
– Voisin EGP intérieur : routeur situé dans un même AS
– Voisin EGP extérieur : routeur situé dans un autre AS
q Les deux routeurs voisins échangent à intervalle régulier des messages
du type
– "Es-tu là ?" (Hello) <====> "oui, je suis là !" (I hear you)
– "Envoie moi ta liste de réseaux accessibles " <====> "voici ma liste"
q EGP est davantage un protocole d’accessibilité qu'un protocole de
routage
– Dans un même AS, sur une liaison point à point, on peut tout à fait utiliser
EGP pour tester l’accessibilité d’un routeur !
• Par ex., à l’IUT, EGP était utilisé au début pour valider la connexion avec le
routeur RENATER situé à Rennes

IP « avancé » M. NDIAYE 74
 EGP (3)
Caractéristiques

q Les messages EGP sont encapsulés directement dans des

datagrammes IP
– Numéro de protocole 8
q Pas de réelles métriques dans EGP
– Utilisation d’un champ « distance » dans les paquets EGP, propre à
l’AS qui fait l’annonce de routes
– Dépend de la valeur que lui accorde l’administrateur de l’AS
– Ce champ n’est ni interprété, ni modifié par EGP
q Ne gère pas les problèmes de boucles
q Ne prend pas en charge le classless CIDR
q Implémenté par de nombreux constructeurs
q En fin de vie, remplacé maintenant par BGP v4

IP « avancé » M. NDIAYE 75
 Fonctions principales d’EGP
q Acquisition d’un routeur voisin
– Envoi d’une demande d’acquisition
– En retour, acceptation ou refus
– Permet de négocier la périodicité des messages Hello,
et le routeur (actif) qui enverra ces mêmes messages
(vers le routeur passif)
q Test périodique sur l’accessibilité d’un voisin
– Requête Hello
– En retour, I-H-U (I hear you)
q Accessibilité des routes
– Un routeur demande périodiquement à son voisin de lui
communiquer la liste des routes qu’il connaît
IP « avancé » M. NDIAYE 76
 Exemple de configuration
Commandes IOS Cisco

autonomous-system 1447 AS local

router egp 1512 AS distant
network [Link]
network [Link] Routes annoncées
network [Link]
...
neighbor [Link] @IP du routeur voisin EGP

IP « avancé » M. NDIAYE 77
 q Quelques rappels
q Allocation des adresses via DHCP
q Système de translation NAT / PAT
q Fonctionnement du routage : notions générales
q Les algorithmes de routage intra-domaine (IGP)
✔ Les algorithmes de routage inter-domaine
(EGP)
✔ Protocole EGP
✔ Protocole BGP

IP « avancé » M. NDIAYE 78
 BGP : principes (1)
q Routeur participant à des échanges BGP inter-domaine = AS
Border Router ou ASBR
q Etablissement d’une session BGP entre deux routeurs
voisins
– Association des ASBR en point à point
– Utilisation du protocole de transport fiable TCP (port 179)
– Encapsulation : IP | TCP | BGP
– Les messages BGP s’échangent entre routeurs voisins au dessus
d’une connexion TCP
ASBR
(AS Border
Router) Session BGP

AS 1023 Connexion TCP

AS 744

IP « avancé » M. NDIAYE 79
 BGP : principes (2)
q Un ASBR peut établir des
sessions BGP avec plusieurs AS 1023 AS 744
ASBR
q Il se peut qu’un AS ne soit
qu’un lieu de passage (AS « de
transit ») d’un AS vers un autre AS 1400
– Les routes annoncées
consistent donc en une liste de
paires n°réseau / n°AS AS 1023 AS 744
– Le chemin vers l’AS contient
la liste des AS à traverser et les
numéros de réseau à utiliser
– La métrique de BGP permet à
l’administrateur de donner un
degré de préférence pour un
chemin donné AS 1400

IP « avancé » M. NDIAYE 80
 Annonce des routes
Support du CIDR

[Link]
[Link]

[Link] AS 744 [Link]

Annonce BGP limitée à
[Link]/16
…….

[Link]

IP « avancé » M. NDIAYE 81
 Messages BGP
Sur chaque session BGP (entre deux
routeurs), quatre types différents de
messages BGP sont échangés

1. Ouverture (open message)

2. Mise à jour (update message)
3. Notification (notification message)
4. Sonde (keepalive message)
IP « avancé » M. NDIAYE 82
 Sonde
q Message court émis périodiquement pour informer
du bon état de la liaison et du routeur voisin
q Dépend de deux paramètres
– Hold-timer = 180 s
– Keepalive = 60 s
q Keepalive = période d’envoi des messages de
sonde
q Hold-timer = temps maximum qui doit s’écouler
après réception d’un message de sonde, avant de
considérer que le routeur voisin est inaccessible
IP « avancé » M. NDIAYE 83
 Ouverture
q Message émis à l’initialisation de la session BGP
en direction de l’autre routeur
q Contient différents paramètres
– Numéro d’AS de l’émetteur
– Paramètres Hold-timer, keepalive
– Le numéro de version de BGP utilisé
– Le type d’authentification (champ optionnel)
q En retour, un message de sonde est envoyé si la
session est acceptée par l’autre routeur
IP « avancé » M. NDIAYE 84
 Mise à jour (1)
q Permet au routeur d’envoyer ses informations de
routage
– Seules les modifications sont transmises
☞ Messages de longueur variable
q Message divisé en deux parties
1. Description des routes à retirer
2. Description des informations que le routeur voisin doit
prendre en considération (en plus des routes à retirer)
• Annonce des routes
• Chaque route est associée à des attributs, qui permettent au
routeur de prendre une décision concernant cette route

IP « avancé » M. NDIAYE 85
 Mise à jour (2)
Principaux attributs utilisés dans la deuxième partie du message
q ORIGIN : IGP, EGP, incomplète
– IGP : la route annoncée provient du même AS que le routeur annonceur
– EGP : la route annoncée a été apprise via un autre protocole inter-domaine
– Incomplète : la route annoncée a été apprise d’une autre manière (via une
configuration statique par exemple)
– Pour la sélection des routes : IGP < EGP < incomplète
q AS_PATH : liste des AS déjà traversés
q NEXT_HOP : @IP du routeur adjacent qui permet d’atteindre le réseau
annoncé (il s’agit généralement du routeur qui fait l’annonce)
q Les autres attributs sont optionnels, par ex. MULTI_EXT_DISC (MED) :
permet d’indiquer une préférence pour une route, dans le cas où il existe
plusieurs routes (= plusieurs routeurs) vers un AS donné
– Plus la valeur est petite, plus la route est préférée
– Attribut non transitif = non propagé vers les autres routeurs
IP « avancé » M. NDIAYE 86
 Mise à jour (3)
q Partant des routes et des attributs associés, le
routeur construit trois tables ou RIB (Routing
Informations Base)
– Adj-RIB In : informations reçues, ne nécessitant pas de
calcul
– Adj-RIB Out : informations à propager via BGP,
classées par routeur destination
– Loc-RIB : sélection des routes par le routeur (calcul de
routes, en utilisant l’attribut MED par exemple)

IP « avancé » M. NDIAYE 87
 Détection des boucles
Utilisation de l’attribut AS_PATH

1. Le routeur A envoie un message

BGP de mise à jour, avec
B [Link]/16 et
AS_PATH : 1400
AS 744
A
AS 1400
[Link]/16
2. Le routeur B envoie un message
BGP de mise à jour, avec
[Link]/16 et
AS_PATH : 744 1400 3. Le routeur C envoie un message
BGP de mise à jour, avec 4. Le routeur A détecte son
[Link]/16 et numéro d’AS, et ignore
AS_PATH : 1023 744 1400 le message de mise
C à jour

AS 1023

IP « avancé » M. NDIAYE 88
 Notification
q Message émis quand une erreur est détectée
– La session BGP entre les deux routeurs est
immédiatement fermée
q Exemples de cause de notification
– Collision de connexion, les deux routeurs voisins
essaient d’ouvrir une session BGP en même temps
– Version du protocole BGP non supportée
– Echec de la procédure d’authentification
– Boucle dans le chemin d’AS
– …

IP « avancé » M. NDIAYE 89
 Exemple de quelques commandes
IOS Cisco

router bgp n° AS local

network numéro de réseau / préfixe
neighbor @IP remote-as n° AS distant
neighbor @IP version n° version BGP
neighbor @IP password xxxxxxxxx
Si le routeur a plusieurs voisins avec des annonces de routes
équivalentes, on crée des peer group
– Pour simplifier la configuration du routeur
– Mise à jour plus efficace
neighbor nom du peer group peer-group
neighbor @IP peer-group nom du peer group
...

IP « avancé » M. NDIAYE 90
 Rôle de iBGP (1)
internal BGP
q Dans un AS, on a souvent plusieurs ASBR qui ont une
session BGP avec d’autres AS
– Par exemple dans le cas d’un AS géographiquement étendu
q Ces routeurs BGP doivent être synchronisés entre-eux
– On établit des sessions BGP entre ces routeurs = iBGP
– Par opposition, session BGP entre deux routeurs voisins
appartenant à des AS différents = eBGP (external BGP)
– Dans une configuration de routeur, dès que n° AS local = n° AS
distant, le routeur sait qu’il ouvre une session iBGP
router bgp 103 iBGP
neighbor [Link] remote-as 103
neighbor [Link] remote-as 109 eBGP

q iBGP et eBGP se comportent différemment

– iBGP ne rajoute pas d’information à l’attribut AS_PATH
IP « avancé » M. NDIAYE 91
 Rôle de iBGP (2)
AS 744

AS 1400

AS 1409
AS 1023

eBGP

iBGP

IP « avancé » M. NDIAYE 92