M1 Informatique
Réseaux
Cours 4 – Routage
Notes de Cours
E ROUTAGE RASSEMBLE LES TECHNIQUES ISSUES DE L’ ALGORITHMIQUE DISTRIBUÉE per-
L mettant de transférer les datagrammes de proche en proche, ainsi que de maintenir à
jour, en fonction de l’évolution réelle (et inévitable) de la topologie du réseau, les informa-
tions permettant de réaliser ce transfert de manière optimale.
1 Routage
1.a "Vous êtes Ici"
OSI TCP/IP
7 Application Application
6 Presentation Not present
in the model
5 Session
4 Transport Transport
3 Network Internet
2 Data link Host-to-network
1 Physical
1.b Définition du Routage
Définition : algorithme distribué ayant pour objectif d’acheminer des données depuis
une source jusqu’à une destination.
Difficultés :
E. Godard [Link] reseaux/
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
— le réseau évolue, son graphe est dynamique
— impossible de maintenir localement une connaissance complète et en temps réel de la
topologie globale.
=> deux problématiques
1. acheminement à l’aide d’une information locale, présente immédiatement sur le rou-
teur.
2. maintenance (en parallèle) de ces informations locales par échange global d’informa-
tions
1.c Questions Algorithmiques
Acheminement — acheminement de proche en proche
— prend en compte l’information sur la destination ou l’origine (paquets vs circuits)
— rapidité de l’algorithme de traitement => simplicité de la structure de données =>
tables de routage
nextHop[dest] vs nextHop(dest)
Maintenance — algorithmes distribués réagissant aux modifications topologiques
— la propagation des mises-à-jour se fait nécessairement avec du retard
— stabilité vs réactivité
1.d Commutation de Paquets
Packet Router Carrier's equipment
B D
4
H1 H2
1 Process P2
A E F
3 2
Process P1 LAN
C
A's table
initially later C's table E's table
A – A – A A A C
B B B B B A B D
C C C C C – C C
D B D B D D D D
E C E B E E E –
F C F B F E F F
Dest. Line
Ex : TCP/IP
2
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
1.e Commutation de Circuits
H3 Router Carrier's equipment
Process
P3
B D
H1 H2
1 Process P2
A E F
4
2
3
Process P1 LAN
C
A's table C's table E's table
H1 1 C 1 A 1 E 1 C 1 F 1
H3 1 C 2 A 2 E 2 C 2 F 2
In Out
Ex : ATM,MPLS
1.f Topologie et Routage IP
Leased lines Leased A European backbone
to Asia A U.S. backbone transatlantic
line
Regional
C IP router
network
National
network
SNA
network
Tunnel
D Host
B
A 1 2
IP Ethernet IP Ethernet
LAN IP token ring LAN LAN
Internet utilise la commutation de paquets. Les algorithmes de routage sont hiérarchiques.
3
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
2 Principes du Routage
2.a Graphes
Un graphe (symétrique) est constitué
— d’un ensemble de sommets V, Ex : V = { a, b, c, d}
— d’un ensemble d’arêtes E ⊂ P2 (V ), Ex : E = {{ a, b}, {b, c}, {c, d}, {d, a}, { a, c}}
a b
d c
2.b Graphes et Routage IP
— Le graphe de communication est le graphe complet : tout nœud peut émettre vers tout
autre nœud
— Le graphe du réseau physique n’est pas le graphe complet
— Le routage a pour rôle d’abstraire le réseau physique : architecture en couches !
2.c Tables et Routage
Une table locale Tx est définie par Tx : E −→ P (V ) (à chaque arc de sortie est associé
l’ensemble des destinations finales y qu’il permet de rejoindre) .
Pour qu’un ensemble de tables locale Tx définissent bien un schéma de routage, on doit
avoir
(relais) Il y a toujours une destination locale dans la table (sauf pour x).
pour tout sommet x ∈ V, (x,y)∈E Tx (y) ∪ { x } = V,
S
(routage) pour tout couple de sommets, il existe une route qui correspond aux tables lo-
cales.
Pour tout sommet x, y, avec x 6= y, il existe une suite de sommets u0 , . . . , ut telle que
— u0 = x et ut = y,
— pour tout 0 < i ≤ t, y ∈ Tui−1 (ui ).
Remarque : pas nécessairement via le chemin le plus court...
4
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
2.d Tables de Routage pour la Commutation de Paquets
Principe général : faire correspondre adresse et segment local
— interface physique ↔ segment local
Algorithme simplifié
— le destinataire appartient au même réseau physique
=> envoi direct (avec ARP)
— sinon transmettre le paquet à un hôte (dans le même réseau physique) plus proche de la
destination => “récursion”
Rappel : Comment déterminer si une adresse IP appartient au même réseau physique ?
=> masque de sous-réseau
2.e Optimalité du Routage
Rôles différents :
— routeur
— hôte
Compacité des tables =>
— adresses regroupées en sous-réseaux => plage d’adresses
— route par défaut.
— Indication de route efficace :
— plus court chemin
— limite la congestion
— Temps de stabilisation après changement topologie.
2.f Tables vs Plan d’adressage
Une table de routage est toujours (schématiquement)
Destination sortie
plage1 sortie1
plage2 sortie2
... ...
default passerelle par défaut
Une plage d’adresse est un intervalle d’adresses, organisé avec CIDR :
— préfixe /pp
— machine : sur 32 − pp bits
L’espace des adresses peut être vu comme étant décomposé de manière arborescente.
Le plan d’adressage doit viser à limiter la taille des tables.
5
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
2.g Exemples : Tables de Routage Réelles
ras> ip route status
Dest FF Len Device Gateway Metric stat Timer Use
[Link] 00 32 mpoa00 [Link] 1 03a9 0 0
[Link] 00 24 enet0 [Link] 1 041b 0
16279
default 00 0 mpoa00 ChangeMe 1 00ab 0
11209
$ /sbin/route
Table de routage IP du noyau
Destination Passerelle Genmask Indic Metric Ref Use Iface
[Link] * [Link] UH 0 0 0 ppp0
[Link] * [Link] U 0 0 0 lo
default [Link] [Link] UG 0 0 0 ppp0
$ netstat -nr
Table de routage IP du noyau
Destination Passerelle Genmask Indic MSS Fenêtre irtt Iface
[Link] [Link] [Link] U 0 0 0 eth0
[Link] [Link] [Link] UG 0 0 0 eth0
2.h Interprétation
Intervalle de destination routeur le plus proche
Adresse Masque Passerelle
IP locale 1 masque local 1 interface locale 1
IP locale 2 masque local 2 interface locale 2
... ... ...
IP 1 masque 1 IP voisin 1
IP 2 masque 2 IP voisin 2
... ... ...
toutes les autres adresses IP passerelle par défaut
2.i Commutations de Paquets : Algorithmes
Algorithmes de Routage :
— Acheminement d’un paquet
— Maintenance de la structure de données distribuée
Contraintes
— Décentralisation et expansion Internet : => algorithmes efficaces
— Multiples constructeurs : => standardisation et conseils d’implémentations (RFC)
6
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
— Deux techniques principales (basé sur le coût associé à un lien) : Vecteur de distance vs
Etat des liens
2.j Vecteurs de Distance
— Un nœud N connaît le coût pour joindre chacun de ses voisins
— Il transmet cette information à tous ses voisins
— Chaque voisin additionne cette information au coût pour joindre N et retient le total
minimum pour déterminer le meilleur intermédiaire pour chaque destination.
— On répète jusqu’à ce que les tables convergent (ie ne soient plus modifiées)
2.k État des Liens
Pour chaque interface
— adresse IP
— masque de sous-réseau
— type de réseaux auxquels celle-ci est connecté
— adresses des routeurs connectés
— débit
— ...
2.l Algorithme
Le but est de maintenir le plus court chemin pour chaque destination connue :
— A chaque changement, un routeur “publie” sa table d’état de tous ses liens
— La diffusion est faite par inondation
— A partir des données obtenues, l’arbre des plus “courts” chemins est calculé localement
par algorithme de Dijkstra (ou variante)
— La table de routage indique pour chaque adresse le routeur suivant (correspondant au
plus court chemin)
2.m Exercices sur les Algorithmes de Routage
B.1 Considérez le réseau ci-dessous. Donnez les vecteurs de distance de chacun des
nœuds.
7
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
Vecteurs de distance initiaux
A B C D
A 3 5 10
B 3 2 7
C 5 2 5
D 10 7 5
B.2 Le lien entre les nœuds B et C disparait. Donner la suite complète d’étapes par
lesquelles les tables se stabilisent vers leurs nouvelles valeurs.
— Etape 1
— B regarde l’annonce de A et ajoute le coût AB.
— C regarde les annonces de A et D, ajoute AC (resp. DC) et prend le minimum
(ex : AC=16 > CD+10).
A B C D
A 3 15 10
B 3 12 7
C 5 8 5
D 10 13 5
— Etape 2
A B C D
A 3 15 20
B 3 12 17
C 11 8 5
D 16 13 5
— Etape 3
A B C D
A 3 16 20
B 3 19 17
C 11 14 5
D 16 19 5
— Etape 4
A B C D
A 3 16 21
B 3 19 24
C 16 14 5
D 21 19 5
8
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
— Etape 5
A B C D
A 3 16 21
B 3 19 24
C 16 19 5
D 21 24 5
— Etape 6 => stabilisé !
B.3 En particulier déduisez en l’intérêt de l’information TTL (Time To Live) situé
dans les datagrammes IP.
Le TTL permet de limiter le temps d’errance d’un paquet en cas de reconfiguration
du réseau comme précédemment.
On reprend le réseau initial, et on considère une amélioration de la technique de vecteur
de distance par condition de faisabilité. Cette condition s’énonce de la manière suivante pour
un routeur R.
Si un voisin V annonce une route ρ avec une distance strictement inférieure à
celle depuis R, alors V est un successeur faisable.
L’amélioration consiste à conserver, pour chaque route,
— à choisir le "successeur primaire" parmi les successeurs faisables, et correspondant au plus
court chemin pour le vecteur de distance classique
— à conserver le second meilleur successeur faisable en tant que solution de secours. C’est
le "successeur secondaire".
B.4 On considère les routes vers D. Quel est le successeur secondaire , s’il existe,
depuis A ? depuis B ?
A est à distance 10 de D. Depuis A, B annonce 7 et C annonce 5. B est le successeur
primaire (route totale à 10). C est le successeur secondaire (5<10).
B est à distance 7 de D. A annonce 10 et C annonce 5. C est successeur priamire mais
il n’y a pas de successeur secondaire.
B.5 Quelle propriété importante possède un successeur faisable ?
Un successeur faisable n’utilise pas R pour son plus court chemin , puisque sa dis-
tance à la destination est inférieure à la distance depuis le nœud considéré. Donc utiliser
un tel succesuer ne peut créer de boucle.
9
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
Si le successeur primaire ne satisfait plus la condition de faisabilité et s’il n’y a pas d’autre
successeur faisable, la route associée devient A CTIVE. Le routeur contacte alors tous ses voi-
sins pour leur demander explicitement leur vecteur de distance. Une fois les réponses obte-
nues, la route est recalculée et elle redevient PASSIVE.
B.6 * Le lien entre les nœuds B et C disparait. Donner la suite complète d’étapes par
lesquelles les tables se stabilisent vers leurs nouvelles valeurs.
On recommence par les vecteurs de distance initiaux
A B C D
A 3 5 10
B 3 2 7
C 5 2 5
D 10 7 5
— Etape 1 : B n’a plus de successeur faisable donc il demande son vecteur à A. A
constate que sa route vers D passait par B, mais le lien est marqué A CTIVE donc ne
peut plus être utilisé.
— Etape 2 : A utilise C (successeur secondaire) pour router vers D. Donc sa distance
à D est 21. Pour C, et la route vers A, elle passait par B et A était successeur secon-
daire.
A B C D
A – 16 10
B 3 19 7
C 16 – 5
D 21 – 5
— Etape 3 : B utilise la réponse de A. D met à jour à partir du vecteur de distance de
C.
A B C D
A 3 16 21
B 3 19 24
C 16 19 5
D 21 24 5
— => les tables sont stabilisées.
B.7 * Le lien entre B et C réapparait avec un coût 10. Même question. Quelle est la
nouvelle table pour la route vers D depuis A ?
10
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
3 Exemples de Protocoles de Routage : IPv4
3.a Communication Hors-Bande : ICMP
Internet Control Message Protocol permet d’envoyer des informations “hors-bande” à l’ex-
péditeur d’un datagramme.
— Destination unreachable : problème de routage
— Time exceed : le TTL atteint 0
— Parameter problem : entête incorrect
— Redirect : rerouter => apprendre la géographie à un routeur
— Echo : demander à une machine si elle est en ligne => ping
— Echo reply : oui je suis en ligne
— Timestamp request : Echo avec horodatage
— Timestamp reply : Echo reply avec horodatage
=> Commandes ping,traceroute, ainsi que ping6 et traceroute6...
3.b Mise à Jour des Informations de Routage I
— Statiquement :
Gestion “manuelle” des routes, en salle TP (debian/ubuntu) :
— ip addr ifconfig
— ip route add, route add
— ip route : table de routage
— ip route add [Link]/28 via [Link] ajout de la route
vers la plage [Link]/28, la passerelle est [Link].
— ip route del [Link]/28 retrait de route
— pour activer le routage :
$ sysctl -w net.ipv4.ip_forward=1
pour que cela soit permanent, dans /etc/[Link], ajouter
net/ipv4/ip_forward=1
3.c Mise à Jour des Informations de Routage II
Leased lines Leased A European backbone
to Asia A U.S. backbone transatlantic
line
Regional
C IP router
network
National
network
SNA
network
Tunnel
D Host
B
A 1 2
IP Ethernet IP Ethernet
LAN IP token ring LAN LAN
— Dynamiquement :
— impossibilité d’échanger toutes les routes
11
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
— protocoles pour le routage hiérarchique
— parties de réseau organisées de manière autonome
— en intérieur : protocoles IGP Ex : RIP,OSPF,IGRP
— en extérieur : protocoles EGP Ex : EGP,BGP
3.d Architecture Globale
Les réseaux sont organisées en systèmes autonomes (AS) géré par une même institution.
La politique de routage est y cohérente.
AS boundary router Backbone
AS 1 AS 2
Backbone
router
Area
Internal router BGP protocol
connects the ASes
AS 3 AS 4 Area
border
router
Les routeurs d’un même système autonome partagent la même table BGP.
Les zones sont organisées en général avec
— un backbone : réseau central à haut débit
— des aires où l’on utilise un algorithme de routage interne
Une AS possède un ASN (sur 32 bits) délivré par un RIR (comme les adresses IP).
Une AS possède une politique de routage cohérente.
12
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
3.e Préfixe BGP : Le nombre de préfixes a augmenté
Un préfixe BGP désigne un ensemble d’adresses.
depuis les débuts d’Internet :
3.f Routes BGP
Une route BGP est une séquence de système autonome (désignés par leur ASN) permet-
tant de rejoindre un ensemble d’adresses donné.
Ceci permet de savoir quel est le routeur suivant mais également l’ensemble des réseaux
traversés pour parvenir à destination.
3.g BGP et Politiques de Routage
Le Border Gateway Protocol permet d’annoncer et de choisir des routes de manière sélective :
— sécurité (rappel : l’information TCP/IP circule en clair)
— géopolitique
— économique (facturation, échange de trafic)
3.h Organisation Tarifaires
Lorsque deux entités économiques s’échangent du trafic
13
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
— si facturation : transit
— si (presque) pas facturation : appairement (peering) ou échange de trafic
Tier 1 Peering uniquement
Tier 2 Mixte (transit et peering)
Tier 3 Transit (=> facturation) => votre FAI
3.i Le coeur d’Internet
Les AS dont les routeurs ont l’ensemble des routes d’Internet
(source [Link])
14
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
3.j OSPF vs RIP
— RIP (Routing Information Protocol)
— vecteur de distance
— diamètre limité (15)
— pas de routage sans classe
— diffusion régulière de toute la table de routage
— convergence en minutes
— métrique rudimentaire : nombre de hop
— réseaux non structurés
— RIP2
— améliorations
— toujours diamètre de 15 et lente convergence
3.k OSPF vs RIP
— OSPF ( Open Shortest Path First )
— état des liens
— diamètre non borné
— gestion fine des adresses
— propagation des modifications par diffusion IP
— meilleure convergence
— métrique permettant l’équilibrage de charge
— agrégation des réseaux en aires
— authentification des routeurs
— gestion des routes externes (injectées par BGP)
15
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
3.l Historique OSPF
— début des discussions : 1988
— début de la formalisation : 1991
— RFC 2328 : 1998
Synopsis :
— protocole non propriétaire pour remplacer RIP
— mais plus complexe à configurer/maintenir
3.m Plus Courts Chemins et Métrique OSPF
La métrique reflète le coût de traversée d’un lien, pour que le plus court chemin soit vrai-
ment le plus court :
108
δ(inter f ace) = debit bits/s
La métrique peut aussi être définie manuellement.
3.n Exemple
3.o Problème du Compte-à-l’infini
En utilisant uniquement les vecteurs de distance, il n’est pas possible de savoir exacte-
ment par où passe la route la plus courte. En particulier, il est impossible de savoir si elle
passe par le nœud même.
16
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
En supposant une distance de 1 par hop, on a que M3 annonce une distance de 2 pour M1.
Si M1 est hors ligne, alors M2 recevra toujours une annonce de M3 pour une distance de
2 pour M1. Par conséquent, M2 mettra son vecteur de distance (vis-à-vis de M1) à 3. Par
conséquent, M3 mettra son vecteur de distance à 4. Par conséquent, M2 mettra son vecteur
de distance à 5. Etc...
3.p Avancées Récentes
Des améliorations récentes de la technique de vecteur de distances permettent d’éviter le
problème du compte à l’infini.
— EIGRP ( Enhanced Interior Gateway Routing Protocol )
— protocole de routage développé par Cisco
— propriétaire
— basé sur les vecteurs de distance,
— condition d’évitement des boucles
— DSDV,AODV
— Babel
3.q Tolérances aux défaillances
Les algorithmes de routage sont très tolérants aux défaillances
Ces défaillances sont inévitables :
— matériel défectueux
— pelleteuses (suivre @alertepelleteuz)
— accidents et catatrophes diverses
3.r Auto-Stabilisation
Les algorithmes de routage ont la propriété suivante
3.r.1 Définition (Dijkstra 1974)
Un algorithme distribué est dit auto-stabilisant si il converge, lorsque les défaillances
cessent, vers un état final correct quelque soit la configuration de départ.
17
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
3.r.2
Cela signifie que les variables utilisées par l’algorithme ne sont pas nécessairement ini-
tialisées correctement...
— sur-approximation des incohérences induites par les changements dynamiques de to-
pologie et les défaillances temporaires
— pas de terminaison expicite
4 Routage en Commutation de Circuits
4.a Rappel du Principe
H3 Router Carrier's equipment
Process
P3
B D
H1 H2
1 Process P2
A E F
4
2
3
Process P1 LAN
C
A's table C's table E's table
H1 1 C 1 A 1 E 1 C 1 F 1
H3 1 C 2 A 2 E 2 C 2 F 2
In Out
Ex : ATM,MPLS
ATM= Asynchronous Transfer Mode
MPLS= Multi-Protocol Label Switching
4.b Le Protocole ATM
Historique :
— créé au CNET (Lannion, France) à partir de 1982
— adopté par l’ITU (International Telecommunication Union)
— répond initialement à des besoins spécifiques des opérateurs télécoms
— standards internationaux au sein de l’ATM Forum
— UNI, LANE
— MPOA
— utilisation
— IPoA IP over ATM : transport de paquet IP par un opérateur télécom au sein de
son réseau très haut débit
18
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
— offre triple play les différentes qualités de service nécessaires à une offre télévision
+ téléphone + internet peuvent être satisfaites en ATM
4.c Réseau de cellules
— découpage en cellules de taille fixe
— multiplexage temporel
— un circuit = un sous-intervalle dédié aux cellules du circuit
4.d Avantage des cellules
— la taille fixe simplifie la gestion du multiplexage
=> implémentation matérielle
— adapté aux réseaux homogènes (typiquement de télécoms)
4.e Cellule ATM
— cellule de petite taille
— compromis débit latence
19
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
4.f Entête
4.g Multiplexage
synchrone
asynchrone
Avantage : tous les sous-intervalles sont bien utilisés
20
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
4.h Principes d’ATM
— sur une connexion les cellules suivent toutes le même chemin
— la qualité de service peut être spécifique
— 2 couches principales (OSI 2-3)
— ATM
— AAL (ATM Adaptation Layer)
La couche AAL permet d’adpter le traffic à une qualité de service spécifique.
AAL1 voix
AAL2 audio-vidéo (débit variable)
AAL3/4 données en mode connecté
peu utilisé
AAL5 données en mode non-connecté
haut débit stupide informatique : utilisé pour IPoA
4.i En couches
4.j Structure du Réseau ATM
coeur du réseau (NNI) vs utilisateur (UNI)
21
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
NNI Network Node Interface
UNI User Network Interface
4.k Routage ATM
Les circuits sont structurés à 2 niveaux
Chemin virtuel (permanent) => VPI
Canal virtuel (à la demande) => VCI
22
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
4.l Commutateur ATM
4.m Utiliser ATM pour Internet
Le but de IP sur ATM est d’utiliser le réseau ATM de la même manière qu’IP peut être
déployé au dessus d’un LAN ethernet 802.3.
Limitation Le réseau ATM n’a pas de mécanisme de diffusion, on ne peut donc configurer
le réseau que statiquement.
4.n Le Protocole MPLS
On recherche le meilleur des deux mondes : MPLS
entête ATM entête MPLS entête IP reste de la trame...
=> couche 2,5 !
4.o Entête MPLS
Entête très simple
23
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
étiquette Exp S TTL
20 3 1 8
— L’étiquette (label) va en quelque sorte encoder un préfixe de l’adresse IP de destination,
mais en reprenant l’efficacité des circuits virtuels.
— Exp : expérimental
— S : bit d’empilement des étiquettes
— TTL : time to live
4.p Routage MPLS
Les éléments MPLS sont donc des routeurs à commutation d’étiquettes (LSR). Locale-
ment, un LSR choisit d’attribuer une étiquette (arbitraire) à certains préfixes (correspondant
par exemple à toutes les adresses qui doivent être transmises vers le même LSR voisin). Le
LSR informe ensuite tous ses voisins de l’étiquette que lui utilise pour ce préfixe, charge à
eux d’utiliser cette étiquette lorsqu’ils ont un paquet avec cette destination à lui transmettre.
5 Autres Protocoles de Routage
5.a Routage Probabiliste pour les Réseaux à Connexion Intermittentes
— concerne les réseaux très dynamiques où les modifications sont la règle et non l’ex-
ception
— communication entre satellites
— communication sur des réseaux de capteurs mobiles
— trajectoires périodiques (transports en commun)
— ou non
— Prophet : RFC 6693 (2012)
24
Réseaux : Cours 4 R ÉSEAUX M1 Informatique
Le principe de base de Prophet est d’utiliser l’histoire des rencontres entre deux ma-
chines.
5.b Une (R)Evolution à Venir ?
SDN (Software defined network) est une proposition d’ architecture en couches pour le rou-
tage :
plan données au niveau données il suffit de connaître les règles pour l’acheminement : garde
=> action
openflow est un standard proposé pour ce plan. Les critères pour la garde peuvent être
— type de protocole
— adresse de destination
— compteurs
— ...
— => règles très simple mais grande expressivité
plan contrôle celui est complètement déconnecté du plan données, il peut ne pas être exé-
cuté sur le routeur => serveurs puissants (et avec beaucoup de mémoire !) spécialisés
dans l’optimisation des routes sur l’ensemble du graphe.
6 Routage : Conclusion
Le routage c’est
— un algorithme distribué auto-stabilisant
— une structure de données distribuée
— organisation hiérarchique sur IP :
— en interne : algorithmes basés sur un calcul distribué des meilleures routes
— en externe : moins automatique, politiques de routage explicites car peu expres-
sibles en terme de métrique.
— voir aussi commutation de circuits
7 Crédits
— Figures A. Tanenbaum. Libre d’utilisation pour l’enseignement
— Cours ATM par Unité Réseaux CNRS (UREC, 1997)
— Wikimedia CC-BY-SA
25
