rdt2.

0 : canal avec erreurs binaires

• Hypothèse : canal introduit des erreurs binaires dans les paquets
• Comment se rétablir de ces erreurs ?
(a) Détection d’erreurs
• Somme de contrôle
(b) Accusé de réception
• ACK : acquittement - le destinataire informe l’expéditeur que le paquet a
été bien reçu
• NAK : acquittement négatif - le destinataire informe l’expéditeur que le
paquet comporte une erreur
• Boucle de retour
(c) Retransmission des paquets erronés
• À la réception d’un NAK

• Protocole “Send and wait”

• l’expéditeur émet un paquet ... puis se met en attente d’un ACK/NAK
66
 rdt2.0 : description
rdt_send(data)

snkpkt=make_pkt(data,checksum)
udt_send(snkpkt)
Destinataire
udt_rcv(rcvpkt) udt_rcv(rcvpkt)
&& isNAK(rcvpkt)
Attendre Attendre && corrupt(rcvpkt)
appel du ACK ou
dessus NAK udt_send(snkpkt)
udt_send(NAK)

udt_rcv(rcvpkt)
&& isACK(rcvpkt)
Attendre
appel du
dessous
Expéditeur

udt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
extract(rcvpkt,data)
rdt_rcv(data)
udt_send(ACK)
67
 rdt2.0 : fonctionnement sans erreur
rdt_send(data)

snkpkt=make_pkt(data,checksum)
udt_send(snkpkt)
Destinataire
udt_rcv(rcvpkt) udt_rcv(rcvpkt)
&& isNAK(rcvpkt)
Attendre Attendre && corrupt(rcvpkt)
appel du ACK ou
dessus NAK udt_send(snkpkt)
udt_send(NAK)

udt_rcv(rcvpkt)
&& isACK(rcvpkt)
Attendre
appel du
dessous
Expéditeur

udt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
extract(rcvpkt,data)
rdt_rcv(data)
udt_send(ACK)
68
 rdt2.0 : fonctionnement avec erreur
rdt_send(data)

snkpkt=make_pkt(data,checksum)
udt_send(snkpkt)
Destinataire
udt_rcv(rcvpkt) udt_rcv(rcvpkt)
&& isNAK(rcvpkt)
Attendre Attendre && corrupt(rcvpkt)
appel du ACK ou
dessus NAK udt_send(snkpkt)
udt_send(NAK)

udt_rcv(rcvpkt)
&& isACK(rcvpkt)
Attendre
appel du
dessous
Expéditeur

udt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
extract(rcvpkt,data)
rdt_rcv(data)
udt_send(ACK)
69
 rdt2.0 : quel est le problème ?
• Si un segment de données arrive erroné

• Mais que se passe-t-il si un ACK ou NAK arrive erroné ?

• L’expéditeur ne sait pas si son paquet est correctement arrivé au destinataire

• Solution : simplement retransmettre le dernier paquet envoyé ?

- Non, car comment le destinataire peut-il savoir si le message retransmis
est un duplicata ou une nouvelle donnée ?

- Note : une appli peut délivrer une succession de paquets identiques !

• Solutions possibles
- Avertir d’une répétition, puis retransmettre
• requiert de dé nir un nouveau type de paquet
- Ajouter un numéro de séquence dans le segment et retransmettre le
dernier paquet envoyé
• solution adoptée par TCP et rdt2.1
70
fi
 rdt2.1 : numéro de séquence (1)

• Ajouter un numéro de séquence dans le segment

- qui identi e chaque segment

- à la réception d’un ACK erroné, le segment est retransmis
- si un duplicata arrive au niveau du récepteur, le segment est
supprimé

• Pour un protocole “Send and wait”

- combien de bits sont nécessaires pour le numéro de séquence ?
- un bit suf t pour coder le numéro de séquence
- uniquement dans le paquet (pas dans les ACK/NAKs)

71
fi
fi
 rdt2.1 : numéro de séquence (2)
Expéditeur Destinataire Expéditeur Destinataire

send pkt0 pkt0 send pkt0 pkt0

rcv pkt0 rcv pkt0
ACK send ACK ACK send ACK
rcv ACK rcv ACK
send pkt1 pkt1 send pkt1 pkt1
Erreur de ???
ACK transmission NAK
???
resend pkt1 pkt1 resend pkt1 pkt1
rcv pkt1
(detect rcv pkt1
ACK duplicate) ACK send ACK
rcv ACK send ACK rcv ACK
send pkt0 pkt0 send pkt0 pkt0
rcv pkt0 rcv pkt0
ACK send ACK0 ACK send ACK

a) Erreur dans l’ACK b) Erreur dans le segment

72
 rdt2.1 : expéditeur gère les ACK/NAK erronés
• On double le nombre d’états des automates
- pour mémoriser si le numéro de séquence du paquet courant
vaut 0 ou 1

Expéditeur rdt_send(data)
snkpkt=make_pkt(0,data,checksum)
udt_send(snkpkt)
udt_rcv(rcv_pkt)
&& (corrupt(rcvpkt)
||isNAK(rcvpkt))
Attendre Attendre udt_send(snkpkt)
appel du ACK ou
dessus, 0 NAK, 0
udt_rcv(rcvpkt) udt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && notcorrupt(rcvpkt)
&& isACK(rcvpkt) && isACK(rcvpkt)
Attendre Attendre
ACK ou appel du
NAK, 1 dessus, 1

udt_rcv(rcv_pkt)
&& (corrupt(rcvpkt) rdt_send(data)
||isNAK(rcvpkt)) snkpkt=make_pkt(1,data,checksum)
udt_send(snkpkt) udt_send(snkpkt) 73
 rdt2.1 : destinataire gère les ACK/NAK erronés

udt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& has_seq0(rcvpkt)
udt_rcv(rcvpkt) udt_rcv(rcvpkt)
extract(rcvpkt,data) && corrupt(rcvpkt)
&& corrupt(rcvpkt)
rdt_rcv(data)
sndpkt=make_pkt(NAK,checksum) sndpkt=make_pkt(NAK,checksum)
sndpkt=makepkt(ACK,checksum)
udt_send(sndpkt) udt_send(sndpkt) udt_send(sndpkt)

Destinataire Attendre
appel du
Attendre
appel du
dessous, 0 dessous, 1

udt_rcv(rcvpkt)
udt_rcv(rcvpkt) && notcorrupt(rcvpkt) udt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && has_seq1(rcvpkt) && notcorrupt(rcvpkt)
u
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
&& has_seq0(rcvpkt)
sndpkt=make_pkt(ACK,checksum) rdt_rcv (data) sndpkt=make_pkt(ACK,checksum)
udt_send(sndpkt) sndpkt=makepkt(ACK,checksum) udt_send(sndpkt)
udt_send(sndpkt)

duplicata ! (l’acquittement du
paquet précédent a été erronné) 74
 rdt2.2 : un protocole sans NAK

• Faire comme rdt2.1 mais uniquement avec des ACKs ?

• Au lieu d’un NAK...

- ... le destinataire envoie un ACK associé au dernier segment

correctement reçu

• Les ACKs doivent être numérotés

- le destinataire doit explicitement inclure le #séquence du

paquet dont il accuse la bonne réception

• Recevoir 2 ACK identiques ⬄ recevoir 1 NAK

- et donc déclenche la retransmission du paquet courant

75
 rdt3.0 : canal avec erreurs et pertes
• Hypothèse : canal peut perdre des paquets (données et ACKs)
- somme de contrôle, #séquence, ACK, retransmission : pas suf sants !
• Que faut-il de plus ?
- Temporisateur (“timer” )
- L’expéditeur attend le retour de l’ACK
- Si le temporisateur expire avant (“timeout” ) il retransmet

- Si le paquet ou l’ACK arrive simplement trop tard ???

• paquets dupliqués mais #séquence pour y répondre
- Le destinataire doit spéci er le #séquence du paquet qu’il acquitte
- Si ACK arrive en erreur ou pas le bon ACK attendu
• pas de réaction, on laisse le timer gérer le problème
76
fi
fi
 rdt3.0 : canal avec erreurs et pertes

Expéditeur
rdt_send(data)
udt
rdt_rcv(rcvpkt) &&
sndpkt = make_pkt(0, data, checksum) ( corrupt(rcvpkt) ||
udt_send(sndpkt) isACK(rcvpkt,1) )
udt
rdt_rcv(rcvpkt) start_timer

Wait for Wait

for timeout
call 0from
ACK0 udt_send(sndpkt)
above
start_timer
udt
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) udt
rdt_rcv(rcvpkt)
&& isACK(rcvpkt,1) && notcorrupt(rcvpkt)
stop_timer && isACK(rcvpkt,0)
stop_timer
Wait Wait for
timeout for call 1 from
udt_send(sndpkt) ACK1 above
start_timer udt
rdt_rcv(rcvpkt)
rdt_send(data)
udt
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) || sndpkt = make_pkt(1, data, checksum)
isACK(rcvpkt,0) ) udt_send(sndpkt)
start_timer

77
 rdt3.0 en action (1)

Expéditeur Destinataire Expéditeur Destinataire

send pkt0 pkt0 send pkt0 pkt0
rcv pkt0
rcv pkt0
ACK0 send ACK0
ACK0 send ACK0
rcv ACK0
rcv ACK0
send pkt1 pkt1 send pkt1
pkt1
rcv pkt1 Perte
ACK1 send ACK1
Timeout
rcv ACK1
send pkt0 pkt0 resend pkt1 pkt1
rcv pkt0
ACK0 send ACK0
rcv pkt1
ACK1 send ACK1
rcv ACK1
send pkt0 pkt0
rcv pkt0
ACK0 send ACK0
temps temps

a) Sans perte b) Paquet perdu

78
 rdt3.0 en action (2)

Expéditeur Destinataire Expéditeur Destinataire

send pkt0 pkt0 send pkt0 pkt0
rcv pkt0
rcv pkt0
ACK0 send ACK0
ACK0 send ACK0
rcv ACK0
rcv ACK0
send pkt1 pkt1 send pkt1
rcv pkt1
pkt1
Timeout Perte ACK1 send ACK1
rcv pkt1
Timeout
1 send ACK1
resend pkt1
pkt1 rcv pkt1 pkt1 ACK
(detect resend pkt1
rcv pkt1
rcv ACK1 ACK1 duplicate) (detect
send ACK1
send pkt0 rcv ACK1 pkt0 ACK1 duplicate)
pkt0 send pkt0 send ACK1
rcv pkt0 rcv pkt0
ACK0 send ACK0 ACK0 send ACK0
temps temps

c) ACK perdu d) Expiration prématurée

79
 Pièces maîtresse d’un protocole de
transport de données able (“rdt”)
1. somme de contrôle
- détecter les erreurs
2. accusés de réception (ACK & NAK)
- boucle de contrôle
3. #séquence
- détecter duplicata et erreurs sur les ACKs
4. “timer” (temporisateur)
- pertes de paquets

80
fi
 Performances de rdt3.0
• rdt3.0 protocole fonctionnel mais performances ☹
- à cause de l’approche “send and wait”
• Exemple
- lien 1Gb/s→C, délai propagation 15ms, paquet 1Ko→L
- U : utilisation du lien (proportion de temps à émettre) → ef cacité
- Dutile : débit utile
- témission = 8L/C = 8μs
- U= témission / (témission + 2 x dpropag) = 2.7 10-4
- Dutile = U × C = 270 000 b/s = 270 kb/s
• A comparer avec les 1 Gbps !

• Fonctionnel mais pas performant

81
fi
 Protocoles à anticipation (1)
-.&,/.$,0)&"'('1'/%
• Pipeline
-.&,/.$.$23)%,$0,")#//'4%)56/(.&/,7)8.$9:/.2;(<7)+,(9('9
•=,9#1>$'4/,02,0)&>(%
Expéditeur peut transmettre plusieurs paquets à la suite sans
attendre des accusés de réception
"#$2,)':)%,?6,$1,)$65=,"%)56%()=,).$1",#%,0
• Ce nombre de paquets = fenêtre d’anticipation
=6::,".$2)#()%,$0,")#$0@'")",1,.A,"

a) “Send and wait” b) Pipeline

2'9B#1>9C7)
•!4')2,$,".1):'"5%)':)&.&,/.$,0)&"'('1'/%3)
Taille supposée de la fenêtre d’anticipation ?
%,/,1(.A,)",&,#(
1 34
!!"#$%&'"()*#+," !"#!
82
 Protocoles à anticipation (2)
Fenêtre W = 3
Fenêtre glissante (≠sautante)
m
es
sa
ge

1. message à envoyer
4
3
2
1

2. divisé en 4 segments

2 3. la fenêtre bloque le
4

3 1
4ème segment

3 4. les segments se
4

A1 A2
“transforment” en ACK

4 5. l’arrivée de ACK 1
déclenche le départ du
A2 A3 segment 4

6. le transfert prend n
A4 83
fi
 Protocoles à anticipation (3)

• Une meilleure utilisation des ressources réseaux

• Mais ...

- Déséquencement possible des segments

- Mémoire buffer chez l’expéditeur (et chez le destinataire ?)
- Augmenter la gamme des #séquence

• Buffer émission : nécessaire ?

- oui, pour sauvegarder les segments en cas de retransmission

• Buffer réception : nécessaire ?

- non mais peut sauvegarder les segments déséquencés

84
 Buffer de reséquencement
• Arrivées déséquencées des segments au niveau du récepteur : 1, 2, 4, 3, 8, 6,
5, 7

buffer buffer
pas de buffer
1 2 4 3 8 6 5 7 1 2 4 3 4 8 6 5 6 7 8

OU
App App

temps
Rejet sélectif Rejet simple temps

• Rejet Sélectif (“Selective Repeat” )

- La couche Transport maintient un buffer par connexion TCP
• les paquets peuvent entrer déséquencés
• et attendent jusqu’à être transmis dans l’ordre à la couche Application
• Rejet Simple (“Go-Back N” )
- La couche Transport ne maintient pas de buffer
• Seuls les paquets bien séquencés sont acceptés
85
 Plan

1. Services de la couche Transport

2. Multiplexage et démultiplexage
3. Transport sans connexion : UDP
4. Principes du transfert de données able
5. Contrôle de congestion TCP

86
fi
 Problématique

• Ressources du réseau sont limit es

- Capacit d’émission des liaisons
- Capacit de traitement des nœuds
- Capacit de stockage (buffers) des nœuds
• Lorsque le tra c soumis (charge) est trop important
- Contention sur les ressources
- Des les se forment dans les routeurs
- Retards et pertes de paquets ↗
- Ph nomène de congestion
• Contrôle de congestion en 3 étapes

87
é
fi
é
é
é
fi
é
 Étape 1 : détecter une congestion
• Comment détecter une congestion ?

- Sans assistance du réseau

- Uniquement à partir des terminaux
- Par la perte de paquets, détectée elle-même par ?
• “timeout”
• 3 ACKs identiques

• Hypothèse fondamentale

- Une congestion provoque des pertes de paquets

- L’inverse est-il vrai ?
• Non, les pertes ne sont pas toujours dues à une congestion

88
Étape 2 : comment réguler son débit ?

Réduction de
Détection Réduction
la taille de la
d’une du débit
fenêtre
congestion TCP
d’anticipation

89
 Étape 3 : à quel niveau réguler son
débit ?
• À combien réguler le débit d’une source TCP ?
• Exemple 1 : un lien dédié de capacité C

source TCP capacité C

- débit souhaitable pour la source ?

- proche de C
• Exemple 2 : un lien de capacité C partagé à plusieurs

source TCP
Tra c concurrent
- débit souhaitable pour la source ?
- capacité résiduelle (capacité disponible)
• Problème : quantité inconnue et dynamique. Comment la
découvrir ?
90
fi
 Hausse additive, baisse multiplicative
• Principe : détecter la capacité disponible sur le chemin
- augmenter progressivement le débit de TCP en agrandissant la taille
de sa fenêtre d’anticipation jusqu’à atteindre le débit max supporté
- comment savoir qu’on a atteint le max ? une perte se produit
• Hausse additive : augmenter la taille de la fenêtre d’anticipation d’1
segment après chaque RTT

• Baisse multiplicative : diviser la taille de la fenêtre d’anticipation par 2

➡ AIMD : “Additive Increase Multiplicative Decrease”
➡ “Congestion Avoidance”

Taille de la
fenêtre 16 ko Evolution en
d’anticipation dents de scie
8 ko

91 temps
 Synthèse : vue d’ensemble de TCP
[RFCs: 793, 1122, 1323, 2018, 2581]
• Orienté connexion
- échange d’information au début de la connexion (“handshaking” )
- expéditeur et destinataire xent les paramètres du transfert
• Mode duplex
- les données peuvent circuler dans les deux sens
• Point-à-point
- entre un expéditeur & un destinataire
• Livraison able et séquencée des données
- buffers d’émission et de réception
- taille des segments xée par
• MSS : “Maximum Segment Size” (hors en-tête)
• Pipeliné
- la fenêtre d’anticipation est dynamique
• Contrôle de ux
- le destinataire indique le nombre d’octets qu’il peut recevoir sans surcharger son
buffer
- En-tête : 20 octets
92
fi
fl
fi
fi
 Exemple 3
serveur DNS
serveur web Noeuds
UCBL Terminaux serveur
routeur
mobile
point d’accès commutateur
Internet
Alice

Alice

Résolution DNS : Requête DNS : segment UDP - Quelle adresse IP pour [Link]/watch?v=9Y29TXdrBM4 ?

Réponse DNS : segment UDP - [Link]

Requête / réponse http : Phase de négociation TCP

Requête HTTP : segment TCP - Envoie moi le contenu demandé
Acquittement TCP de la requête HTTP
Réponse HTTP : segment TCP - Voici le contenu demandé
Acquittement TCP de la réponse HTTP
93
Couche Réseau

94
 Plan

1. Introduction
2. IP : Internet Protocol
3. Tables d’acheminement
4. Algorithmes de routage
5. Le routage dans Internet

95
 La couche Réseau
Application
Transport
Réseaux Réseaux
Réseaux

• Liaison Liaison
Permet l’acheminement des segments Liaison
Physique Physique
de l’expéditeur jusqu’au destinataire Physique
Réseaux

•
Liaison
Expéditeur Physique

- encapsule les segments à émettre

…
Réseaux
dans des datagrammes Réseaux
Liaison
Liaison

• Récepteur Physique Physique

- transmet les segments reçus à la Réseaux

Application
Transport
couche Transport Réseaux Liaison Réseaux
Réseaux

•
Liaison Physique Liaison
Tous les terminaux et routeurs Physique
Liaison
Physique
Physique

- implémentent la couche Réseau

• Les routeurs examinent les en-têtes
des datagrammes

96
 Les services essentiels de
la couche Réseau
• Adressage
- Adresse = identi ant topologique d’un noeud
• Dépend de la position dans le réseau
• Utile pour router
• (En principe) unique
• Acheminement (Forwarding )
- Commuter un paquet d’une interface à une autre
- Interroger une table d’acheminement (table de routage)
• Routage
- Déterminer le chemin de bout-en-bout à suivre pour un
paquet depuis la source jusqu’à la destination
- Algorithme de routage
97
fi
 Plan

1. Introduction
2. IP : Internet Protocol
3. Tables d’acheminement
4. Algorithmes de routage
5. Le routage dans Internet

98
 Datagramme IPv4 (1)
• Format d’un datagramme

• En-tête de 20 octets
0 15 31
• TTL : “Time To Live”
Version HLen ToS Total length bits
- valeur initiale xée par l’émetteur
Identi cation Flags Frag. Offset
- puis décrémentée de 1 à chaque à saut (lien

En-tête
de communication) traversé dans le réseau TTL Protocol Checksum

- si TTL = 0, le paquet est supprimé Source IP address

- Utilité ? Destination IP address

• Permet d’éviter qu’un paquet tourne
Options
indé niment dans le réseau (par
exemple en présence d’une boucle de
routage)
Payload
• Protocol
- Identi er le protocole encapsulé dans IP
• 06 : TCP - 17 : UDP
99
fi
fi
fi
fi
 Datagramme IPv4 (2)

• Checksum : somme de contrôle

- détection des erreurs de transfert
- calculé sur l’en-tête IP seulement
- complément à 1 de la somme de l'entête
- en cas d’erreur, le paquet est supprimé

• Source IP Address & Destination IP Address

- codées sur 32 bits chacune
- Datagramme possède des infos pour être acheminé de sa
source à sa destination
- les datagrammes d’un ux sont « autonomes » les uns par
rapport aux autres

100
fl
 Adresses IPv4
• Adresse IP sur 32 bits
sous-réseau [Link]/24
- identi ant d’une interface réseau
• Interface réseau [Link]
- connexion entre un noeud et un lien [Link]
- un routeur a plusieurs interfaces [Link]
- un terminal a une ou plusieurs interfaces [Link] [Link]
- chaque interface a son adresse IP
• Adresse IP
[Link]
[Link]
- partie réseau : bits de poids fort [Link]
[Link] [Link]
- partie hôte : bits de poids faible
- masque : taille de la partie réseau
- a.b.c.d/x où
• x = masque de sous-réseau 10001100 01001101 00000001 00000000
• x indique le nombre de bits dans la Partie réseau Partie hôte
partie réseau 101
fi
 Sous-réseaux

• Sous-réseaux (“Subnets” )

- Ensemble des interfaces dont les adresses ont la même partie réseau
- Les interfaces d’un même sous-réseau peuvent communiquer directement
(sans l’intervention d’un routeur)

• Comment trouver pratiquement les sous-réseaux existants ?

- En désactivant les interfaces des routeurs

- Chaque nouveau réseau isolé est un sous-réseau
• Possibilité de

- découper un réseau en plusieurs sous-réseaux

- d’agréger des sous-réseaux
102
 Comment obtient-on son @IP ?
• Comment un terminal obtient-il son adresse IP ?

- “Codé en dur” par un admin système dans un chier

• Unix : /etc/[Link] g
• Windows : TCP/IP dans Panneau de Con gurations

- DHCP : Dynamic Host Con guration Protocol

• Obtient son adresse dynamiquement par un serveur
• “Plug and Play”

• Comment une organisation obtient-elle son pré xe ?

- Elle demande à son FAI de lui allouer une portion de son espace d’adresses
• Comment un FAI reçoit-il son bloc d’adresses ?
- ICANN : Internet Corporation for Assigned Names and Numbers
• alloue les adresses
• affecte les noms de domaines
• gère le DNS
• arbitre les con its
103
fl
fi
fi
fi
fi
fi
 IPv6
• Autre protocole IP pour faire face à la pénurie d’adresses IPv4

• Taille d’une adresse IPv6 = 128 bits

- 32 bits pour IPv4

• Autres champs

- Traf c class : pour faire de la différenciation de service

- Flow label : pour identi er les datagrammes appartenant à même ux pour un traitement plus « ef cace »
• Champ checksum disparaît

- on laisse d’autres couches s’en occuper pour plus d’ef cacité

• Migration IPv6

- a démarré en 2003

- toujours dans une phase de cohabitation entre IPv4 et IPv6

- mécanisme de tunneling : encapsulation des datagrammes IPv6 dans des datagrammes IPv4 sur les routeurs IPv4

104 Kurose et al.

fi
fi
fi
fl
fi
 Plan

1. Introduction
2. IP : Internet Protocol
3. Tables d’acheminement
4. Algorithmes de routage
5. Le routage dans Internet

105
 Table de d’acheminement (1)

• Tables de d’acheminement pour les datagrammes

- #Entrées = #@ IP ?
- Avec 4 milliards (232) d’@ IPv4, recherche serait trop longue
• Solution ?
- Une entrée ≠ une adresse IP
- Une entrée = un ensemble d’adresses IP = un sous-réseau
• Format : @ IP / masque
• [Link]/24 désigne les 256 (=28) adresses de
[Link] à [Link]
- Désigner toutes les adresses possibles ?
• [Link]/0 → route par défaut

106
 Table d’acheminement (2)
[Link]/25

m0 [Link]/25
R1
m1 m3
[Link]/22 [Link]/24
[Link]/22 [Link]/24
m2 [Link]/26

[Link]/26

Accessible
[Link]/26
sans routeur
Internet
Noté aussi
Table de routage de R1
[Link]
Adresse réseau Adresse du prochain Interface de
saut sortie
[Link]/26 ——— m2
[Link]/25 ——— m0
[Link]/24 ——— m3
[Link]/22 ——— m1
[Link]/0 [Link] m2 107
 Table d’acheminement (3)
• Que se passe-t-il si une adresse IP véri e plusieurs adresses de
sous-réseau ?

Adresse réseau Plage d’adresses Adresse du Interface de

prochain saut sortie
[Link]
[Link]/28 à ——— 0
[Link]
[Link]
[Link]/24 à ——— 1
[Link]
[Link]
[Link]/22 à ——— 2
[Link]
[Link]
[Link]/0 à [Link] 0
[Link]

• Exemple : [Link]
- on choisit la première qui apparaît dans la table de routage ?
- on tire au hasard ?
- on choisit l’entrée la plus récente
108
dans la table d’acheminement ?
fi
 Table d’acheminement (4)

• Si plusieurs choix dans la table sont possibles, on choisit la plus

spéci que

- Algorithme du Plus Long Pré xe Partagé

- Il suf t donc de parcourir les entrées de la table par les
pré xes les plus longs

109
fi
fi
fi
fi
 Table d’acheminement (5)
• Donc, seuls les pré xes suf sent dans les tables

Adresse réseau Pré xe des adresses réseaux Adresse du Interface de

prochain saut sortie

[Link]/28 11000000 10101000 00000000 00000000 ——— 0

[Link]/24 11000000 10101000 00000000 00000000 ——— 1

[Link]/22 11000000 10101000 00000000 00000000 ——— 2

[Link]/0 - [Link] 0

• Exemples, quelles interfaces de sortie pour ?

- Adresse destination : [Link]
11000000 10101000 00000000 00010001 → Interface : 1
- Adresse destination : [Link]
11000000 10101000 00000000 00000111 → Interface : 0
- Adresse destination : [Link]
11000000 10101000 00000100 00010001 → Interface : 0 110
fi
fi
fi
 Plan

1. Introduction
2. IP : Internet Protocol
3. Tables d’acheminement
4. Algorithmes de routage
5. Le routage dans Internet

111
 Pourquoi router ? (1)

Par mon interface de Par mon interface de

sortie je peux sortie je peux
communiquer avec B communiquer avec A

A B

1 câble
112
 Pourquoi router ? (2)
Interface 1 → B
Interface 2 → C
Interface 3 → D
Q R S etc.
P A
O
B
N
C
Ne passe pas à l’échelle :
M • # Interfaces D
• # Câbles
L E

K F
J
I 113
H G
 Pourquoi router ? (3)

D
B
Je sais
communiquer avec B et
C mais pas avec D !
C
A
Il faut trouver
un chemin !

114
 Problème de plus court chemin (1)
• Théorie des graphes • Coût d’un chemin
• Un graphe comprend - Composition des coûts des
liens qui le composent
- des noeuds
- des liens - Par ex.
• Coût (A→C→B→D→E) =
• Coûts des liens
c(A,C) + c(C,B) + c(B,D) +
- identiques c(D,E) = 6
• tous égaux à 1 • Comment trouver le chemin d'un
noeud à un autre de coût
- différents et constants minimal ?
• par ex. inversement
proportionnels à leur 1
capacité d’émission 3 B E
A
(exemple Cisco) 1 5 3
1
- différents et dynamiques 1
F
C
• par ex. liés à une mesure de
2 D
congestion
115
 Problème de plus court chemin (2)

• À la main
- Uniquement pour de petits graphes
- Sinon, grâce à un algorithme (automatisable)
• Deux grandes approches pour le routage dynamique
- Algorithmes par état de liens
• Chaque noeud a une connaissance complète du réseau
- Algorithmes à vecteur de distances
• Chaque noeud connait uniquement ses voisins et le coût
de ses liens

116
 Routage par état de liens

• Chaque noeud doit connaître la topologie complète du réseau

- Diffusion de l’état des liens

• Application de l’algorithme de Dijkstra (1959)

- exécuté pour chaque noeud du réseau

- retourne un arbre des plus courts chemins
- et donc, sa table d’acheminement
• Exercice en TD2

117
Routage par vecteur de distances (1)

• Notations
- dX(Y) : coût du plus court chemin de X vers Y
- Vx = {V1,V2,... ,VM} : l’ensemble des noeuds voisins de X
• Equation de Bellman-Ford
- dX(Y) = min (c(X,Vi)+dVi(Y))
Vx

- coût exact du plus court chemin de X vers Y

• On va manipuler DX(Y) = estimation courante de dX(Y)

• Recherche d’un point xe par itération

118
fi
Routage par vecteur de distances (2)
• Au niveau de chaque routeur

- Table d’acheminement
• Destination1 Coût Saut suivant
• Destination2 Coût Saut suivant …

- Vecteur de distances
• Destination1 Coût
• Destination 2 Coût …
• envoyé à ses voisins et reçu de ses voisins

• À la réception d’un vecteur de distances ou suite à un

changement sur un lien

- le noeud concerné applique l’équation de Bellman-Ford et

envoie son vecteur de distances à ses voisins
119
 Plan

1. Introduction
2. IP : Internet Protocol
3. Tables d’acheminement
4. Algorithmes de routage
5. Le routage dans Internet

120
 Routage hiérarchique (1)
• Pas possible d’appliquer un des algorithmes précédents directement
sur tous les routeurs de l’Internet

- Échelle gigantesque
• Internet est une fédération de réseaux autonomes interconnectés
- “Autonomous Systems ” - AS
- chaque administrateur d’un AS est maître de son réseau
-ensemble de routeurs- et de son routage
- ~120 000 AS en 2025
• Con dentialité
- topologie interne doit rester secrète
- ainsi que les accords négociés avec les autres AS
• Politiques et intérêts divergents
- pas de métriques standardisées pour le coût d’un lien
- contrôler d’où vient et où part le tra c
- décharger son réseau au détriment des autres
121
fi
fi
 Routage hiérarchique (2)
Autonomy: network of networks
routage inter-AS
détermine les chemins
entre les AS
DT
AS 2
AS 1

AS 3
LIP6
network

Internet = interconnection of Autonomous Systems (AS)

Distinct regions of administrative control routage intra-AS
Routeur passerelle : “Gateway router” détermine, entre autres,
interface avec les routeurs d’autres AS les routes vers les
Service provider, company, university, etc.
routeurs passerelles
4
122
 Routage intra-AS
• Routage entre les routeurs d’un même AS

- détermine le routage pour les destinations au sein de l’AS

• Tous les routeurs d’un même AS applique le même routage intra-
AS

• Des routeurs appartenant à des AS différents peuvent appliquer

des routages intra-AS différents

• Quelques protocoles de routage intra-AS

- RIP (Routing Information Protocol) : de type vecteur de

distances

- OSPF (Open Shortest Path First) : de type état de liens

- IGRP (Interior Gateway Routing Protocole) : de type vecteur
de distances ; propriétaire -CISCO-

123
 Missions du routage inter-AS
z
y
x

• Annoncer aux autres AS les sous- AS2 AS3

réseaux desservis par soi

• Apprendre les sous-réseaux accessibles w

depuis les AS voisins
AS1
- Puis en informer ses routeurs
v
internes

- Et propager l’information aux autres AS5 AS4

AS
u

t s
124
 Le protocole de routage inter-AS de
l’Internet z
y
x
• BGP : Border Gateway Protocol

- eBGP (external BGP) : permet AS2

d’obtenir les infos d’accessibilité AS3
des autres AS

- iBGP (internal BGP) : propage ces w

infos d’accessibilité aux routeurs
internes à l’AS
AS1
• Si AS4 annonce à AS5 le sous-réseau s v
(via eBGP)

- AS4 promet qu’il retransmettra les AS5 AS4

datagrammes au sous-réseau s
u

t s
125
 Couplage des routages inter- et intra- AS

Si X est
accessible
L’AS reçoit une depuis une seule
passerelle, Le routage
annonce pour inter-AS (iBGP)
un sous- Le routage intra-
informe les
réseau X hors AS calcule le plus
routeurs de l’AS
de son domaine court chemin vers
du chemin
Alors le routage cette passerelle
passerelle
inter-AS (eBGP)
Si X est choisie - X
décide de la
accessible passerelle à
depuis plusieurs utiliser selon les
passerelles, accords Chaque routeur
commerciaux et de l’AS ajoute dans
la règle de la sa table de routage
patate chaude (X,I) avec I
l’interface du
prochain saut vers
la passerelle
126 choisie
 Où fait-on du plus court chemin ?
• Qui choisit le prochain AS ? et donc la passerelle ?
- Le routage inter-AS
- Donc pas toujours le plus court chemin
• Qui choisit la route vers la passerelle ?
- Le routage intra-AS
- Donc selon le plus court chemin
AS27

x y

AS15
AS88 AS9

127