1RWLRQVGH5RXWDJH,3
/HV3URWRFROHV
FRXUV#XUHFFQUVIU
? 1994: création Bernard Tuy
? Modifications
• 1995 Bernard Tuy
• 1997 Bernard Tuy
• 1998 Bernard Tuy
? Les protocoles de Routage IP
• Généralités
• RIP (2)
• IGRP
• OSPF
• EGP (2)
• BGP
• CIDR
? Evolutions
• IPv6 et les protocoles de routage
? Equipement de routage :
• équipement connecté à 2 réseauxau moins(ou 2 sous-réseaux)
• Un routeur ne connait que l’@IP du prochain routeur (next hop)
• remise directe (stations sur le même segment physique) :ARP
– ARP @IP_destination
• ou par l'intermédiaire d'un (plusieurs routeurs) :proxy ARP
– ARP @IP_NextHop
? La Table de routage
• chaque équipement de routage possède une table de routage
– unicast (et éventuellement multicast)
? Routage statique :
• route add | delete @IP_destination @IP_router metric
• route default @IP_destination metric • ip route @IP_destination netmask @IP_routeur
? Routage dynamique :
• échange périodique des tables de routage
• mise à jour automatique de la table de routage
? Pourquoi utiliser un protocole de routage ?
=> pallier les inconvénients du routage statique :
• boucles de routage, routages asymétriques
• "trous noirs", routages aberrants
? Routage au sein d’un Autonomous System (AS)
• Interior Protocol
=> RIP, OSPF, IGRP
? Routage entre deux AS
• Exterior Protocol => EGP, BGP
? Interior / Exterior
? Distance Vector / Link State
? Algorithm de Bellman-Ford :
• Chaque routeur diffuse à tous ses voisins :
– la liste des réseaux (destinations) qu'il sait atteindre,
– le nombre de sauts à effectuer
– l'@IP du routeur à utiliser,
• A réception de ces informations :
– chaque routeur met à jour sa table de routage
? Avantage :
• C’est simple !
• etinteropérable
? Inconvénients :
• Convergence peut être longue dans un réseau de grande dimension
– calcul des routes réparti entre tous les routeurs
• la notion de distance ne peut rendre compte de tout
• le volume des informations échangées est directement proportionnel aux nombres de réseaux
Chaque routeur :
? Surveille activement l'état de toutes ses liaisons
? diffuse cet état à tous les autres routeurs
? Construit à partir de ces informations unecarte topologiquecomplète du réseau
? Calcule lesroutes de plus court chemin
• Algorithme de Dijkstra
? Avantages :
• Chaque routeur calcule indépendamment la carte du réseau
• le volume des informations échangées ne dépend pas du nombre de réseaux
? Inconvénients :
• Le calcul peut être très complexe.
Distance Vector Interior Protocols
? Routing Information Protocol (RIP)
• cf le cours de la première partie
• RFC 1058
• a servi de base pour de nombreux autres protocoles – AppleTalk, Novel / IPX, Banyan Vines
• messages UDP sur le port 520
• broadcasts toutes les 30 secondes
? RIP v 2
• RFC 1387 et RFC 1388
• permet le routage des sous-réseaux(véhicule le netmask)
• identifie les routes externes utlisées par un EGP
• interopère "raisonnablement" avec RIP v 1
• diffusion multicast (224.0.0.9) plutôt que broadcast
• authentification
Distance Vector Interior Protocols (2)
? Interior Gateway Routing Protocol (IGRP)
• Propriétaire Cisco
• Broadcastsde mise à jour toutes les90 secondes
• mesures de protection contre les boucles de routage
• routage des sous-réseaux
• routage multi-chemins (secours + load balancing)
– la table de routage peut avoir plus d'un chemin pour atteindre unemême destination
– chaque chemin = @_prochain_routeur, N°_interface– avantages :
• secours automatique si un chemin devient indisponible
• partage du trafic entre les chemins de métriques voisines
• gestion des routes par défaut (candidates)
Distance Vector Interior Protocols (2)
? La métrique composite d'IGRP
• la métrique tient compte de :
– la bande passante (B)
– le délai de propagation (D)
– la charge de la liaison (C)
– et sa fiabilité (F)
=> B et D sont des caractéristiques statiques de la liaison => C et F sont des variables dynamiques calculées par le routeur.
? avantages :
• affiner le routage en fonction des besoins, des côuts des ressources , de la redondance
• en faisant varier les composantes de la métrique.
? Evolution :
• Extended IGRP(E-IGRP)
Link State Interior Protocols
? Open Shortest Path First (OSPF)
• RFC 1583
• Implante l’algorithme SPF de Dijkstra
• Le routage est hiérarchisé pour simplifier le calcul des routes :
– le Système Autonome (AS) est découpé en AREA
• uneAreaest un ensemble de réseaux contigüs
• chaque AREA se comporte comme un réseau indépendant
• elle ne connait que l'état des liaisons internes à l'AREA
• Deux niveaux de routage :
– intra Area
– inter Area
? On distingue 3 classes d’Aires :
• l’Aire backbone (Area 0)
– chemin obligatoire pour passer d'une aire à l'autre
• les Aires secondaires
– Tous les noeuds de routage ont une vue complète de la carte duréseau
– ils calculent localement la meilleure route entre une source etune destination.
• les Aires terminales (stub area)
– même comportement que les aires secondaires
– sauf : ne mémorisent pas les informations sur les routesexternes
– Toutes les routes externes sont récapitulées dans une route pardéfaut
? OSPF
• Calcule des coûtsen guise de métriques
• Sait router les sous-réseaux,
• par types de service,
• permet le load balancing
• Inclut un système d'authentification des messages échangés
• Envoie un LSA (Link state Announcement) – quand l'état d'une ligne change – ou toutes les 30 minutes.
Exterior Protocols
? Exterior Gateway Protocol (EGP)
• cf cours 1 ère partie
• échanges entre routeurs déclarés comme "pairs" (peers)
• situés sur un même réseau : réseau source
=> tout le trafic entre 2 AS passe par le même chemin physique
EGP ne doit pas donner d'information sur des réseaux situés en dehors de son AS
? Border Gateway Protocol (BGP)
• RFC 1105, BGP-1
• RFC 1163, BGP-2
• RFC 1267, BGP-3
Ni vraiment distance vector ni vraiment link state
• transmet le"chemin d’AS"entre la source et la destination
– détection simple et efficace des boucles
? Adapté à des topologie complexes (maillées)
• Echange des informations de routage par une connexion TCP (port 179)
• inclut un système d'authentification des messages échangés
• Peut aussi être utilisé comme protocole de routage interne (IBGP)
? Avantages :
– Convergence rapide
– Mises à jour incrémentales = gain de BW et de CPU
– Cohérence des métriques entre routages interne et externe
? BGG est LE protocole de routage externe moderne
• version 4 : RFC 1654 et RFC 1655
? Classless Inter Domain Routing(CIDR) pourquoi faire ?
? 2 problèmes à résoudre :
=> épuisement des adresses réseau de classe B (16.384)
(# 50% alloués dès 1992, l'épuisement était planifié pour 1994)
• pallié par allocation de réseaux de classe C
> 2 millions de réseaux de classe C
=> explosion de la taille des tables de routage
NSFnet, janvier 1993 : 9000 réseaux connectés janvier 1994 : 21400 et de la mémoire des routeurs
? Solutions à court terme :
• "découper" les réseaux de classe A
– en utilisant la technique des masques (subnet mask) .
– 1 réseau de classe A permet d'adresser > 16 millions de hosts
=> allocation de réseaux sans classe (classless)
• agréger les tables de routage :
=> allouer aux "utilisateurs" des réseaux de classe C contigus des réseaux contigus ont les mêmes bits de poids fort : ils ont même préfixe
=> grouper les préfixes par région, prestataires
=> router les préfixes des supernets (ou agrégats) une seule entrée par agrégat dans la table de routage suffit
• 193.127.32.0 <=> 193.127.32.0 255.255.255.0
<=> 193.127.32.0 / 24
• 193.127.33.0 <=> 193.127.33.0 255.255.255.0
<=> 193.127.33.0 / 24
• les 2 réseaux explicites 193.127.32.0 et 193.127.33.0sont agrégés en 193.127.32.0 255.255.254.0
• l’ agrégat est noté : 193.127.32.0 / 23 il désigne le couple préfixe / nb bits masque
dans la table de routage, il représente les 2 réseaux 193.127.32.0 et 193.127.33.0
• 32 => 0010 0000 netmask 254 => 1111 1110 (7 bits)
• 33 => 0010 0001 le dernier bit peut donc être 0 ou 1 => la suite de "1" du netmask doit être continue
ainsi 253 (1111 1101) et 250 (1111 1010) ne sont pas adéquats, mais 252 (1111 1100) et 248 (1111 1000) conviennent
? Correspondance Netmask /nombre de réseaux de l'agrégat:
• 255 => / 24 R = 1
• 254 => / 23 R = 2
• 252 => / 22 R = 4
• 248 => / 21 R = 8 • 240 => / 20 R = 16
•
R = (255 - netmask) + 1
• Implantation de CIDR :
Ce nouveau découpage -sans classe, classless- des réseaux et l'agrégation des tables de routage => une nouvelle version de Border Gateway Protocol
BGP-4 (RFC 1654 et RFC 1655)
? Quelques remarques en guise de conclusion :
• pour que l'agrégation des tables de routage soit "efficace"
=> il faut qu'elle soit utilisée par tous les prestataires de connectivité IP qui échangent des informations de routage entre eux.
• dès qu'un prestataire utilise l'option d'agrégation de BGP4
=> tous ceux qui échangent des informations de routage avec lui vont devoir faire de même
• et inversement
• l'agrégation sans "trou" versus l'agrégation de gros blocs
• Que se passe t-il quand un "utilisateur" change de prestataire de service (renumérotation ?)
• la technique d'agrégation des réseaux dans les tables de routage a permis de gagner une année, dans le processus d'inflation
? Solution à long terme :
IPv6 ou IP Next Generation
– permet un adressage hiérarchique sur 16 octets (128 bits)
=> une meilleure agrégation des tables de routage
– de nombreuses fonctionnalités seront ajoutées aux protocoles deroutage (sécurité, multicast )
• les protocoles en cours de développement / tests :
– RIPv6, (RIPng)
– OSPFv6
– BGP 4+ (ou BGP 5?)
