Protocole TCP/IP : Historique et Fonctionnement
Protocole TCP/IP : Historique et Fonctionnement
Protocole de transport
Jean-Patrick Gelas
Université de Lyon
Sources
●
« Réseaux locaux et Internet », 3rd édition, Laurent Toutain, Hermes.
●
“Analyse Structurée des réseaux, 2nd édition”, James Kurose, Keith Ross.
Pearson Education.
●
“Réseaux et Télécoms”, 2nd édition, Claude Servin. Dunod.
● Jacobson, Van (1995), "Congestion Avoidance and Control", ACM
SIGCOMM Computer Communication Review 25(1): 157 - 187
● Data Transport Research Group, GGF (Global Grid Forum), “A survey of
Transport Protocols other than Standard TCP”. Eric He, Pascale Primet,
Michael Welzl et al., May 10,2005.
● http://research.csc.ncsu.edu/netsrv/?q=content/bic-and-cubic
2
Historique
●
1970 : Première publication du « ARPANET Host-Host protocol » C.S. Carr, S.
Crocker, V.G. Cerf, "HOST-HOST Communication Protocol in the ARPA Network," in
AFIPS Proceedings of SJCC.
●
1974 : Vint Cerf et Bob Kahn publie un article qui spécifie en détail l'architecture
d'un programme de contrôle de transmission (TCP). « A protocol for Packet Network
Interconnection », IEEE Trans comm.
●
1975 : Satellite links cross two oceans (to Hawaii and UK) as the first TCP tests are
run over them by Stanford, BBN, and UCL
●
1978 (mars) : TCP se scinde en TCP et IP.
●
1981 (septembre) : RFC793 - Transmission Control Protocol
●
1982 : DCA and ARPA establish the Transmission Control Protocol (TCP) and Internet
Protocol (IP), as the protocol suite, commonly known as TCP/IP, for ARPANET.
– This leads to one of the first definitions of an "internet" as a connected set of
networks, specifically those using TCP/IP, and "Internet" as connected TCP/IP
internets.
– DoD declares TCP/IP suite to be standard for DoD
●
1989 (octobre) : RFC1122 - Requirements for Internet Hosts - Communication Layers
http://www.zakon.org/robert/internet/timeline/ 3
Les algorithmes TCP historique
●
1986 – Tahoe : Première implémentation. La plus simple et la moins efficace
(cwnd=1 MSS à chaque congestion, ssthreshold = cwndMax / 2)
●
1990 – Reno : Usage de Fast recovery. Cwnd=cwnd / 2. Débit offert un peu plus
stable.
●
1994 – Vegas : Prise en compte du temps de réponse du destinataire (RTT).
Modifications des trois algorithmes (slowstart, congestion avoidance et Fast
retransmit).
●
1999 – New Reno : Modification légère de Reno (reste en mode Fast recovery
tant qu'il n'a pas reçu les ACK de tous les paquets perdus).
http://www.zakon.org/robert/internet/timeline/ 4
Introduction
● Le protocole TCP standard (TCP Reno) est un protocole de transport
fiable qui fonctionne bien dans les réseaux traditionnels.
● Cependant, les expériences et l'analyse de ce protocole montre qu'il n'est
pas adapté à toutes les applications et à tous les environnements, par
exemples :
– les communications interactives ;
– le transfert haut débit de grosse quantité de données (bulk data
transfer) ;
– les réseaux dont le produit débit et temps d'aller/retour (throughput x
RTT (round-trip time)) sont grand.
– réseaux sans-fils.
5
La gestion de connexion TCP
Établissement de connexion en trois étapes
● La procédure d'établissement d'une connexion TCP constitue une partie non
négligeable du temps de réponse perçu par les utilisateurs.
● Etape 1 : segment SYN (bit SYN=1), le client choisi un numéro de séquence
initial (seq = client_isn).
● Etape 2 : segment SYNACK. Le récepteur alloue un tampon et des variables,
renvoie un datagramme avec SYN=1, seq = server_isn, ack = client_isn+1
● Etape 3 : Le client alloue un tampon des variables, et accuse réception de cette
autorisation de connection.
SYN=0, seq = cleint_isn+1, ack = server_isn+1
6
La gestion de connexion TCP
8
Deux composants
9
Le contrôle de flux de TCP
● Chaque pôle d'une connexion à un tampon de réception.
● L'application vient chercher ses données dans ce tampon de façon asynchrone.
● Sans service de contrôle de flux un émetteur pourrait rapidement saturer le tampon de
réception (RcvBuffer) dont la taille est fixe.
● L'expéditeur est informé de la taille variable de la fenêtre de réception (RcvWindow)
du destinataire.
● Le récepteur informe l'expéditeur de l'espace disponible en insérant la variable
RcvWindow dans la fenêtre de réception de tous les segments qu'il lui envoie.
● Lorsque RcvWindow=0 et que le récepteur n'a rien à envoyer, l'émetteur continue à
envoyer des segments de 1 octets qui généreront des acquittements porteur des
informations d'actualisation sur le tampon de réception.
10
Le contrôle de congestion de TCP
●
L'objectif principal du
contrôle de congestion est Throughput
d'éliminer la congestion.
capacity
●
Lorsque la demande totale
du trafic excède la capacité
(throughput) du lien, cette
demande doit être réduite. knee
●
Sinon, congestion collapse
potentiel... (événement load
couramment observé en
1986 avant l'ajout du contrôle
de congestion)
11
What’s Really Happening?
packet
knee cliff
loss
Throughput
●
Knee – point après lequel
– Le débit augmente doucement congestion
– Le délai augmente collapse
●
Cliff – point après lequel
– Le débit décroit rapidement
Load
(congestion collapse)
Delay
– Le délai tend vers l'infini
Load
12
Modèle de base du contrôle de congestion
Aggregate Bottleneck
traffic link demand
demand > capacity?
feedback
●
Quel est le type de feedback ?
●
Est-ce stable ?
13
Contrôleurs multiple
●
Dans le cas du contrôle de congestion de réseaux
(plusieurs connections partageant le même lien), il
y a plusieurs contrôleurs
Bottleneck
Σ link demand
…
> capacity?
feedback
●
Est-ce équitable ? (fairness)
14
Boucle de rétro-action binaire
●
Le cas le plus simple (binary feedback) :
– Le réseau est congestionné ou pas.
●
TCP utilise comme indication de congestion binaire
la destruction (ou non) de paquets.
●
Est-ce adéquat ?
15
Le contrôle de congestion de TCP
● Puisque IP ne fournit aucune information explicite aux terminaux, TCP a nécessairement recours
à une approche de bout-en-bout (plutôt qu'à un contrôle de congestion assisté par le réseau).
● La vitesse d'émission est régulée en fonction du niveau de congestion perçu.
● Régulation du taux d'envoi :
– La variable fenêtre de congestion (CongWin ou cwnd) impose une limite au rythme
auquel l'expéditeur est autorisé à charger des données sur le réseau.
– Le volume de donnée non-confirmées ne peut dépasser le minimum de CongWin et
RecvWin.
LastByteSent – LastByteAcked = min {CongWin, RecvWin}
● Le “phénomène de perte” est identifé/perçu soit par :
– l'expiration du temps imparti (timeout), soit par
– la réception d'ACK dupliqués de la part du destinataire,
et interprété comme un indice de congestion sur le parcours vers le destinataire.
16
Effets de bords des protocoles
à évitement de congestion
●
Wifi : Les protocoles à évitement de
congestion supposent toujours que les pertes
sont dues à une congestion. Sur un réseau
Wifi cela conduit à un débit faible.
●
Connexions courtes (short lived
connections) : Le protocole slow-start est
inadapté pour les connexions très courte. Il
est conseillé d'utiliser une même connexion
dans laquelle on effectuera plusieurs
transactions courtes.
Rappel sur le contrôle de congestion de TCP :
Départ lent (slow start)
● Au début d'une connexion, CongWin = 1 MSS, donc
un taux d'envoi ~= MSS/RTT (ex: 500 bytes / 200 ms = 20 kbit/s).
● Au début, l'émetteur à en fait recours à une accélération exponentielle. Pour chaque ACK
reçu cwnd = cwnd + 1.
18
Rappel sur le contrôle de congestion de TCP :
AIMD : Accroissement additif et décroissance
multiplicative
● L'idée de base est de faire en sorte que l'expéditeur réduise son taux d'envoi en
diminuant la taille (par 2) de sa fenêtre de congestion dés qu'un phénomène de
perte se déclare (ex: 20ko -> 10ko -> 5 ko ... -> 1 MSS (Maximum Segment
Size)) : cwnd = cwnd / 2
● Si le réseau ne présente pas de congestion, une “certaine” valeur de débit doit être disponible
pour la connection TCP.
● TCP procède a un agrandissement progressif de sa CongWin, “sondant” scrupuleusement toute
éventuelle fraction de débit disponible sur le chemin de bout-en-bout : Pour chaque
ACK reçu cwnd = cwnd + 1/cwnd.
● autrement dit, TCP ajoute environ 1 MSS à chaque temps de trajet aller/retour (RTT) tant
qu'aucun phénomène de perte ne se déclare.
segment 1
1
segment 2
2 2
A CK=
segment 3
=3
ACK
segment 4
4
segment 5
=3 5
ACK Reséquencement et
segment 6 délivrance
=3 6
ACK
Retransmission
sur temporisation s eg m
ACKen=t33
3
=7
ACK
segment 7 20
7
Le contrôle de congestion de TCP
La fenêtre glissante
21
Réaction au phénomène
d'expiration du temps imparti ou du triple ACK
● Le phénomène de congestion de TCP ne réagit pas de la même manière à un phénomène de perte
détecté par :
– l'expiration du temps imparti (timeout), ou
– l'arrivée de 3 ACK identiques
● Pour le cas Timeout : CongWin=1, agrandissement exponentielle jusqu'à une valeur seuil
(SSTreshold),puis agrandissement linéaire.
● Pour le cas Triple ACK : L'annulation de la phase de départ lent après un triple ACK est
appelé récuperation rapide (fast recovery).
● SSThreshold initial
par défaut = 64 ko, en cas
de perte
SSTreshold = CongWin / 2
22
Fast Retransmit
(Retransmission rapide)
23
Fast retransmit
(illustration)
●
Technique permettant d'éviter de réduire le débit d'une façon
trop brutale.
●
Sender enters “fast recover” phase
– Reduce ssthresh by half
– Temporarily reduce cwnd to (ssthresh + #dup_ack)
– Retransmit missing packet, assuming receiver caches out-of-
order packets
●
When receiver receives the retransmitted packet (filling the
gap) it acks all packets (incl. out-of-order ones).
●
Sender set cwnd to ssthresh and returns to congestion
avoidance phase.
●
See RFC2001
Comportement dynamique
car car
segment segment
TC P T CP
car car
ACK é ch é ch
o o
segme s eg . T
t TCP n CP + A
CK
écho écho
ACK
car
seg. TC
P + AC
K
car
28
Fairness in the real world!
● Les applications multimédia utilisent UDP car elles ne peuvent se permettre de voir leur débit bridé.
● Du point de vue de TCP les applications multimédia ne sont pas équitables car elles ne coopèrent
pas avec les autres connections et n'adapte jamais leur débit aux conditions du réseau.
● Il n'y a a priori pas moyen d'empêcher une application (TCP) d'utiliser plusieurs connexions en parallèle
(ex: navigateur web) → L'application bénéficie alors d'une plus grande proportion de la bande passante.
29
Taille de fenêtre et débit
●
De la taille de fenêtre de congestion dépend le
débit ! cwnd = 3
2
ACK
3
ACK
30
Fenêtre de congestion statique
Le temps de latence (latency) est le laps de temps séparant l'établissement de la connection TCP
par un client et la réception de l'objet dans son intégralité.
31
Fenêtre de congestion dynamique
32
TCP sur différents supports
● TCP utilisé universellement pour le transport fiable de
données sur Internet.
● Conçu à la fin des années 70 : époque où la topologie du
réseau et les caractéristiques des liens étaient différentes.
● TCP doit suivre les évolutions technologiques :
– Débits : de 9600 b/s (GSM) au Terabit/s (fibres optiques)
– Délais de propagation : de quelques microsecondes à une
seconde.
– Taux d'erreur : de quasi nul (fibre) à très élevé sur les
liaisons hertziennes (satellite)
33
Réseaux haut débit
TCP sur différents supports
34
Elephant networks
Long Fat Networks (LFN)
TCP sur différents supports
35
Utilisation inefficace du lien...
● Pour une connection TCP (standard) avec des paquets de 1500 octets et
un RTT (Round-Trip Time) de 100 ms sur un lien a 10 Gbps, il faudrait
une fenêtre de congestion moyenne de 83.333 paquets et un taux de
perte égal à au plus une congestion tous les 5 milliards de paquets (soit
toutes les 1h40).
● Cela est principalement du a l'algorithme d'évitement de congestion
(congestion avoidance) basé sur le principe “Additive Increase, Multiple
Decrease” (AIMD).
● Une connection TCP réduit sa bande passante par deux lors de la
détection d'une “congestion”, mais prend 1h40 pour utiliser à nouveau
toute la bande passante (si aucune perte n'est détectée pendant ce temps
la !).
37
Réseaux hertziens
TCP sur différents supports
38
Contexte
39
Propositions
ou
– utiliser des protocoles totalement nouveaux.
40
Les fonctions du service de transport
et les caractéristiques des protocoles
41
Caractéristiques des services de transport
44
Critères de comparaison et objectifs (2/2)
● Equité intra-protocole : Traite de l'équité parmi les connections utilisant
le même protocole.
● Déploiement : besoin de modifier ou reconstruire le noyau de l'OS, ou
juste ajouter une bibliothèque de niveau utilisateur qu'une application peut
appeler directement.
● Modèle analytique : (1) Si il existe il permet de comparer les résultats
expérimentaux aux prévisions. (2) Il permet aux développeurs d'identifier
systématiquement les facteurs qui influence les perf. global et prédire le
bénéfice d'une quelconque amélioration du protocole.
● Scénario d'usage : “One size fits all” c'est bien beau mais difficile à
concevoir.
45
État de l'art
(non exhaustif !)
● Variantes de TCP :
– HighSpeed TCP, Scalable TCP, Fast TCP, TCP Weswood+,
SACK TCP, BIC and CUBIC, Compound TCP.
● Protocoles basés sur UDP :
UDP Lite, Reliable Blast UDP, Tsunami, UDT,...
● Protocoles exigeant l'aide des routeurs :
XCP, CADPC/PTP,...
● Autres :
SCTP, DCCP,...
46
Variantes de TCP :
BIC and CUBIC
● Injong Ree, North Carolina Univ.
● Binary Search Increase --> target_win = (max_win – min_win ) / 2
● Additive Increase --> cwnd = cwnd + (target_win – cwnd) / cwnd
● Slow Start --> cwnd+1, cwnd+2, cwnd+4... cwnd+Smax
● En cas de pertes --> cwnd = cwnd * (1 - Beta)
54
Variantes de TCP :
Compound TCP (CTCP)
● Proposé par Microsoft (à partir de Windows Vista et WS 2008)
● Maintient deux fenêtres de congestion :
– Une première qui augmente de façon linéaire mais décroît en cas de
perte via un certain coefficient.
– La seconde est liée au temps de réponse du destinataire.
● C'est donc une combinaison de New Reno (perte de paquets) et Vegas
(adaptation préventive à la congestion).
● La taille de la fenêtre est la sommes des deux.
– Si le RTT est petit, la fenêtre basée sur le délai augmente rapidement.
– Si il y a perte de segments, la fenêtre basée sur la perte de paquet
diminuera rapidement.
● Les fenêtres se compensent et permettent de tendre de façon presque
constante vers une valeur de fenêtre effective proche de celle estimée.
● Bien adapté aux réseaux LFN.
55
Vocabulaire utilisé dans
les protocoles de contrôle de congestion
●
cwnd – congestion window
●
RTT – Round trip Time
●
RTO – Retransmission Timeout
●
MSS – Maximum Segment Size
●
DUPACK – ACK dupliqué
●
ssthresh – Slow Start Threshold
60
Conclusion
61