Gestion de congestion

RESEAUX HAUT DEBIT

Master Réseaux et Systèmes

PARTIE 1

Master Réseaux et Systèmes

A.Boulouz

Département de mathématiques et informatiqueFaculté des sciences d’Agadir

103/01/2011

INTRODUCTION

203/01/2011

303/01/2011

Une des finalités de la gestion du haut débit est deproposer un service de transport de données numériques

Pourquoi donc le haut débit ?

proposer un service de transport de données numériquesentre deux utilisateurs finaux distants mettant en œuvredes paramètres de qualité de service adaptés aux besoinset aux disponibilités du fournisseur.

403/01/2011

Ces nouvelles exigences concernent :

•la fourniture d’une bande passante importante, à un instant donné,adapté à la nature sporadiques des flux ;•disposer d’une garantie du délai d’acheminement des PDU ;•un contrôle sur le taux d’erreur.Tous ces besoins entrent dans le cadre de la définition de paramètresdite qualité de service QoS.

Ces derniers concernent trois domaines :

•Les contraintes temporelles existantes entre la source et la destination.Cette contrainte concerne, par exemple, les applications téléphoniques où le temps réel exige un transport de données isochrone.•Les contraintes de débit demandées et offertes : dans quelles conditions contractuelles, quelle plage horaire et dans quelles conditions les PDU vont être transportés ?•Les contraintes d’acheminement d’un PDU entre l’émetteur et le destinataire qui vont préciser la façon dont le service de « bout en bout » sera fourni par l’opérateur.

503/01/2011

Différence entre applications( informatiques et télécoms)

603/01/2011

Les besoins en bande passante, nécessaire aux échangesd’informations (par définition variables), génèrent des flux dits« sporadiques » qui sont de nature à être structurants pourl’opérateur. La mise en place d’application de type JAVA quiconsiste à charger, sur un poste-client à code exécutable, latransmission de données multimédias – est de nature à modifierces flux.

703/01/2011

La fourniture d’une bande passante n’est pas de nature suffisante pour

répondre aux besoins de la transmission des clients. Leurs exigences sont

autres :

�Une bande passante variable adaptés, à un moment donné aux besoins.

�Une garantie de temps de réponse.

�Un support d’applications temps réels. �Un support d’applications temps réels.

Toutes ces contraintes supposent que les opérateurs ( ISP ) soient en mesure

de fournir un service adapté à des typologies de trafic. C’est ce que l’on

appelle la gestion de la qualité de service ou QoS

� La messagerie n’a pas de contrainte de temps.� Le trafic transactionnel suppose une garantie de temps de réponse minimum.� Le transfert de la voix suppose une garantie du temps d’acheminement.

803/01/2011

Un protocole atteint ses limites en débit quand le temps de

traitement dans les nœuds devient prépondérant sur le lien

1er approche : Simplifier

2eme approche : un 2eme approche : un autre protocole qui

prenne en compte les un Protocole déjà existant

prenne en compte les spécifications d’un trafic

multiservices

Frame Relay Simplification de X25

ATMAsynchronous Transfer

Mode

903/01/2011

� Frame Relay ( suite X25) préfigure déjà un certain nombre de choix

L'interconnexion de réseaux locauxdistants doit pouvoir offrir aux usagersde la bande passante « à la demande »

technologique à mettre dans les réseaux haut débit comme le report d'un maximum de fonctionnalités du réseau vers les équipementsusagers (voir partie 2)

� DQDB est une tentative pour offrir une interconnexion flexible multi-service.( voir partie2)� ATM reprend un certain nombre de concept comme la petite taille despaquets ( voir partie 2)

1003/01/2011

• Asynchronous Transfer Mode. TTA en français (technologietemporelle asynchrone). Technologie de réseau à haut débit(centaines de Mbit/s, jusqu'à 2.5 Gbit/s) très sérieusementnormalisée et présentée comme une solution d'avenir. Lesdonnées sont transmises sous forme de paquets de taille fixe(53 octets de long), appelés cellule.

• Originellement conçu pour la voix et les WANs, l'ATM est entrain de passer aux LANs. Cette technologie semble prendre

ATM

train de passer aux LANs. Cette technologie semble prendrel'ascendant en ce moment sur ses concurrentes. Le principalproblème étant la rapidité de commutation, qui doit êtreélevée vue la taille des cellules.

• Distributed Queue Dual Bus DQDB. Standard de réseau surfibre optique, compatible avec ATM, fonctionnant avec unbus double et permettant des débits allant jusqu'à 140 Mbps.

1103/01/2011

Tout ces paramètres conduisent à définir des

classes de services qui répondront aux besoins

suivants :

Bande passante Qualité de service

Transmission de la voix 64 Kb/s par canal Flux isochrones

Transaction Faible Intégrité des données

Visio conférence Minimum 384 K Flux isochrones

Transfert de fichiers Variable Intégrité des données

Certains flux – comme la transmission de données – exigent une bande passante

importante mais variable. D’autres – comme les flux multimédias – sont plus tolérants

sur l’intégrité des données mais exigent une transmission isochrone. C’est la

complémentarité de ces exigences qui permet d’envisager un partage des supports.

1203/01/2011

La mise en place d’un service de communication, quel que soitl’environnement, s’inscrit dans le cadre d’un processus logique précisqui, à plusieurs échelons, met en lumière les concepts d’architecture.On définira une architecture comme l’art d’organiser des services.

Une architecture se présente sous la forme d’un plan quireprésente la façon dont les services sont fournis, la façon dont

DÉFINITION D’UNE ARCHITECTURE

représente la façon dont les services sont fournis, la façon dontles données s’échangent. Il existe plusieurs visions d’une mêmeorganisation du système d’information, examinés de plusieurspoints de vue différents.

Il est cependant d’usage de mettre en lumière trois composantsde base qui sont :

Le modèle, les services et les protocoles

1303/01/2011

Un modèle décrit la façon dont sont organisées les différentesfonctions de l’architecture, ainsi que la manière dont lescomposants des fonctions communiquent entre-eux.

Sur le plan matériel, les composants du modèle sont articulés dansdes équipements que l’on désignera, dans le cadre de leur

DÉFINITION DU MODÈLE

des équipements que l’on désignera, dans le cadre de leurimplémentation, sous la forme d’une structure nodale.

En matière de communication, les modèles se présentent encouches fonctionnelles adjacentes, et chaque couche dispose d’unmoyen pour identifier l’émetteur ou le récepteur

1403/01/2011

TYPOLOGIES DU MODÈLE

Sur le plan théorique il existe deux familles de modèles qui ne sontpas exclusives l’une de l’autre :

�Les modèles dits « hiérarchisés », qui consistent à concentrer lesfonctions dans des nœuds dépendants les uns des autres.Ainsi, pour accéder à un nœud, il n’existe qu’une route possible pouraller d’un nœud à l’autre.

Ces modèles sont applicables à l’organisation de l’entreprise, les systèmes d’information et composants techniques.

�Les modèles dits « distribués » qui communiquent entre eux selonune structure maillée.

1503/01/2011

MODÈLE EN COUCHE

Ce modèle consiste à structurer les services en couchesfonctionnelles. Les éléments de services qui les composent sontregroupés en fonction des domaines relatifs au déroulement desprocessus de communication, lesquels constituent une hiérarchie deservices.

La communication d’une couche à l’autre s’effectue par desLa communication d’une couche à l’autre s’effectue par desinterfaces qui décrivent les opérations nécessaires à la transmissiondes PDU (voir cours SMI5-FSA), d’une couche n vers une couche n+

ou -1.

C’est l’organisation de ces couches qui constitue le fondement del’architecture.

Voir aussi le TD 2

1603/01/2011

Les interfaces qui décrivent la façon dont les PDU vont échanger lesdonnées sont de deux natures :

a) Des interfaces logiques qui sont décrits – par exemple – par des API(Application Program Interface). Celles-ci se composent de primitives quise présentent comme des fonctions associées à des paramètres,générant une opération élémentaire (exemple : programmation del’envoi ou de la réception d’un message)

b) Des interfaces physiques qui décrivent la façon dont des équipementsvont être raccordés entre eux (exemple : modem, PC réseau Ethernet)

Exemple : modèle en couche OSI de ISO ( voir cours de Licence SMI5)

1703/01/2011

Chapitre 1 : TCP/IP

PARTIE 1

Chapitre 1 : TCP/IP

1803/01/2011

Pour IP, voir le polycopie de cours SMI5

Réseau TCP/IP

1903/01/2011

Application Ouvrir :ww.dest.fr

Ecrire(f,message)

IPww.dest.fr = 111.111.111.111

adresse locale = 111.111.111.222

ROUTAGE

Choix destinataire --> dest

SocketN° port=20

Envoyer : messageà ww.dest.frN°port= 21

Envoyer

'20,21,message'a ww.dest.fr

DNS

Adresse IP deww.dest.fr ?

L’adresse est :111.111.111.111

Réseau TCP/IP

TCP|20|21|message

|

Choix destinataire --> dest

|Adr1|adr2|...|20,21,message|

HDLCMise en forme trame

|F|dest|controle|adr1,adr2,...,20,21,message|bce|F||erreurs|F|

Messagepour ww.dest.frn° port =21

Envoyer à dest'Adr1,adr2,...,20,21,message'

Réseau

ARP

Adresse mac de111.111.111.111?

Adresse = dest

20

Pour ARP, @IP, @MAC

Voir SMI5

03/01/2011

Service en mode connecté ==> garantie de non perte de messages ainsi que de l'ordonnancement

Transport fiable de la technologie TCP/IP :

LE MODÈLE TCP

•Adresse les processus (N° Port)

•Fiabilise IP (Connexion et acquittements)

•Optimise les ressources (Fenêtres variables)

2103/01/2011

No port Mot-clé Description

20 FTP-DATA File Transfer [Default Data]

21 FTP File Transfer [Control]

23 TELNET Telnet

25 SMTP Simple Mail Transfer

42 NAMESERVER Host Name Server

LE MODÈLE TCP/IP

Exemples d’application

42 NAMESERVER Host Name Server

53 DNS Domain Name Server

80 HTTP WWW

110 POP3 Post Office Protocol - Version 3

TCP doit assurer un transport fiable des datagrammes IP :

1. service en mode connecté

2. garantie de non perte de messages ainsi que de l'ordonnancement

2203/01/2011

On suppose que l'émetteur du premier paquet avec le bit SYN aconnaissance du couple (adresse IP du récepteur, numéro de port duservice souhaité).

L'émetteur du premier paquet est à l'origine de l'établissement du circuitvirtuel, c'est une attitude généralement qualifiée de `` cliente ''. On dit aussique le client effectue une `` ouverture active '' (active open).

Le récepteur du premier paquet accepte l'établissement de la connexion, ce

LE MODÈLE TCP

Le récepteur du premier paquet accepte l'établissement de la connexion, cequi suppose qu'il était prêt à le faire avant que la partie cliente en prennel'initiative. C'est une attitude de `` serveur ''. On dit aussi que le serveureffectue une `` ouverture passive '' (passive open).

23

Contrairement aux réseaux orientés connexion, comme X25 ou ATM, laconnexion TCP est différente de la notion de circuit virtuel : les routeursintermédiaires ne maintiennent aucun contexte pour la connexion TCP quiest transparente pour eux. La connexion TCP ne fait invoquer que les deuxnœuds terminaux

03/01/2011

A noter que, la caractérisation de la qualité du service dansl'Internet est généralement exprimée par les critères suivants:

• Délai: temps écoulé entre l'envoi d'un paquet par un émetteur et saréception par le destinataire. Le délai tient compte du délai depropagation le long du chemin et du délai de transmission induitpar la mise en file d'attente des paquets dans les systèmesintermédiaires.

LE MODÈLE TCP/IP

• Gigue : variation du délai de bout en bout

• Bande passante ou débit maximum: taux de transfert maximumpouvant être maintenu entre deux points terminaux

• Disponibilité : taux moyen d'erreurs d'une liaison

2403/01/2011

L'établissement d'une connexion TCP s'effectue en trois temps

TCP

2503/01/2011

TCP : L'établissement d'une connexion TCP

L'établissement d'une connexion TCP s'effectue en trois temps.

- Au début SYN =ISN (Numéro de séquence initial, c’est un compteur sur 32 bit,

incrémenté tout les 4µs)

-SYN de serveur contient un acquittement égal à ISN du client + 1. Le SYN = ISN de

serveur

- Le client acquitte et informant le serveur de l’ouverture de la connexion

2603/01/2011

Comme une connexion TCP est une connexion bidirectionnelle, le processus client et serveur doivent demander la fermeture de la connexion de façon individuelle.

• Quand un des deux processus, client ou serveur, demande la fermeture dela connexion, le processus homologue n’ayant pas encore demandé lafermeture de la connexion, peut continuer à envoyer des données.

• Au niveau de la couche TCP, suite à une demande de fermeture deconnexion, TCP envoie un segment de type FIN et une confirmation dedéconnexion est transmise au processus ayant demandé la fermeture de laconnexion.

TCP : Déconnexion TCP (en quatre phases)

déconnexion est transmise au processus ayant demandé la fermeture de laconnexion.

• Le segment FIN est acquitté par l’entité TCP homologue. Cette dernièrerentre dans un état dit semi-fermé (“half-close”) et peut continuer àenvoyer normalement des données.

• Après avoir fini cette procédure d’envoi, un segment FIN est envoyé. Laconnexion est fermée à la réception de l’acquittement du deuxièmesegment FIN. Une indication de déconnexion est alors transmise au secondprocessus.

2703/01/2011

TCP : Déconnexion TCP

28

Elle se fait en quatre phases

03/01/2011

TCP : Déconnexion TCP

2903/01/2011

L’une des particularités du protocole TCP est l’utilisation desnuméros d’octets et non pas des numéros de paquets pour gérer lesacquittements et les retransmissions.

Le champ séquence indique la position du premier octet du paquetdans le flux de données alors que le champ acquittement indique leprochain numéro de l’octet attendu par le récepteur. TCP effectue letransfert d’un flux continu de données dans les deux directions enregroupant à chaque fois un certain nombre d’octets pour former

TCP : Echange des données

regroupant à chaque fois un certain nombre d’octets pour formerdes segments. En général, TCP décide quand il doit bloquer etenvoyer des données en utilisant un contrôle de flux connu sousl’appellation fenêtre glissante

Ce contrôle de flux permet d’envoyer plusieurs paquets avant de sebloquer en attente d’acquittements (“Stop and Wait”). Ceci permetd’améliorer le débit puisque l’émetteur n’est pas obligé d’attendre

la réception d’acquittement après chaque envoi de paquet dedonnées

3003/01/2011

Note : le protocole TCP utilise la notion de “Piggy Backing” pour acquitter des données.

Le “Piggy Backing” permet d’optimiser l’utilisation de la bandepassante lorsque l’émetteur et le récepteur ont des données àémettre et consiste à ne pas envoyer un acquittementsystématiquement après la réception d’un paquet de données.

TCP : Echange des données

systématiquement après la réception d’un paquet de données.

En recevant des données, TCP vérifie s’il a des données à envoyer.Si c’est le cas, TCP envoie un segment de données tout enmettant à jour le champ acquittement de sorte à acquitter ledernier segment reçu.

3103/01/2011

TCP : Exemple d’échange

Sur le diagramme nous avons présenté les champs :

séquence, acquittement, fenêtre, drapeaux, taille du

segment et options TCP. Les segments

•1, 2, 3 correspondent à l’établissement de la

connexion TCP en 3 phases. La connexion est établie

à l’initiative de la machine A qui annonce, dans le

champ options, un MSS de 1460 et une fenêtre de

4096 octets (segment 1).

• La machine B accepte la connexion en envoyant le

32

• La machine B accepte la connexion en envoyant le

segment 2 qui annonce un MSS de 1024 octets et

une fenêtre de 6144. L’échange de données se fait

en utilisant des segments de taille maximale égale à

1024 octets.

* Ensuite la machine A envoie 6 segments de taille

1024 octets (segment 4, 5, 6, 7, 8, 9) avant de se

bloquer en attente d’un acquittement

Ns= ISN + Nb Octets transmis + 1

Le N° du 1er octet transmis est ISN + 1

03/01/2011

TCP : Retransmission de paquet perdu

Après l’établissement de la connexion1, la

machine A envoie les segments 1, 2 et 3 et

arme un temporisateur. Le paquet 1 est perdu

dans le réseau. A la réception de chacun des

paquets 2 et 3, la machine B envoie un

acquittement avec un numéro d’acquittement

égal au numéro de séquence du segment 1.

L’utilité de ces acquittements est, d’une part,

d’informer l’émetteur (machine A) que le

segment 1 (séquence 501) n’est toujours pas

reçu, et d’autre part d’annoncer la nouvelle

taille de fenêtre. A l’expiration du

33

taille de fenêtre. A l’expiration du

temporisateur, la machine A retransmet le

segment ayant le numéro de séquence 501. La

machine B délivre les 3 segments de données

et acquitte simultanément les 3 paquets de

données par le segment 7.

Notons que la fenêtre annoncée dans le

segment 7 est de 6144.

L’établissement de la connexion n’est pas

représenté pour simplifier la compréhension

03/01/2011

TCP : Retransmission de paquet perdu

34

Retransmission de paquet perdu avec duplication des ACK(voir 50)

03/01/2011

TCP : Fenêtres glissantes

• Au départ du Paquet i une horloge sedéclenche. Si cette horloge dépasseune valeur limite avant réception del'ACK le Paquet i est retransmis.

• Le temps qui s'écoule entre l'émissiond'un paquet et la réception de sonacquittement est le RTT. Il estcourant sur l'Internet actuel d'avoirun RTT de l'ordre de la seconde. Il

35

un RTT de l'ordre de la seconde. Ilfaut noter que le RTT est la sommedes temps de transit entre chaquerouteur et du temps passé dans lesdiverses files d'attente sur lesrouteurs.

• L'émetteur conserve la trace duPaquet i pour éventuellement lerenvoyer.

03/01/2011

• Avec ce principe, la bande passante du réseau est beaucoup mieuxemployée.

• Si l'un des paquets doit être réémis, la couche TCP du destinataireaura toute l'information pour le replacer dans le bon ordre.

• À chaque paquet est associée une horloge comme sur la figure diapo37.

• Le nombre de paquets à envoyer avant d'attendre le premieracquittement est fonction de deux paramètres :

– La largeur de la fenêtre, précisée dans le champ WINDOW de l'en-tête, change


– La largeur de la fenêtre, précisée dans le champ WINDOW de l'en-tête, changedynamiquement pour deux raisons :

• L'application change la taille du `` buffer de la socket qui correspond à la taille decette fenêtre.

• Chaque acquittement ACK envoyé est assorti d'une nouvelle valeur de taille de lafenêtre, permettant ainsi à l'émetteur d'ajuster à tout instant le nombre de segmentqu'il peut envoyer simultanément. Celle valeur peut être nulle, comme par exemplelorsque l'application cesse de lire les données reçues. C'est ce mécanisme qui assurele contrôle de flux de TCP.

3603/01/2011


3703/01/2011


3803/01/2011

• Le débit obtenu dépend de la taille de la fenêtre et bien sûr dela bande passante disponible. On conçoit aisément qu'entrela situation de la figure (diapo 33) et celle de la figure (diapo34) l'usage de la bande passante s'améliore. Par contrel'agrandissement de la taille de la fenêtre ne se conçoit quejusqu'à une limite optimale au delà de laquelle des paquetssont perdus parce que envoyés trop rapidement pour êtrereçus par le destinataire. Or, pour fonctionner de manièreoptimale, TCP se doit de limiter au maximum la perte de


optimale, TCP se doit de limiter au maximum la perte depaquets et donc leur réémission.

• Cette taille limite optimale de la largeur de la fenêtre est,comme on peut le deviner, fonction de la bande passantethéorique du réseau et surtout de son taux d'occupationinstantané. Cette dernière donnée est fluctuante, aussi TCPdoit-il asservir continument les tailles de fenêtre pour entenir compte.

3903/01/2011

● Lien (bande passante, latence)

● Ex. : taux de transfert idéals entre différents ordinateurs

● CC = adaptation à la bande passante disponible à chaque instant

TCP: Introduction à la congestion

4003/01/2011

● Congestion = routeur avec file d'attente pleine

● Si routeur avec file d'attente (quasi) pleine :

– rejet/perte de paquet (car débordement mémoire routeur)

– délais importants de transfert (car attente dans les files des routeurs)


● Causes de la perte d'un paquet :

– problème matériel

– problème d'environnement (souvent dans les réseaux sans fil)

– mais surtout congestion d'un routeur

● En filaire, perte d'un paquet ~= congestion d'un routeur

4103/01/2011

Exemple de problème réseau :


● En regardant, une application UDP est très utilisé● UDP ne s'adapte pas à la bande passante disponible● TCP s'adapte => TCP est défavorisé

42

Un utilisateur se plaint d'un débit faible ?

03/01/2011

● Une machine réseau « hôte » est impliquée dans 1 transfert, un routeur dans beaucoup de transferts

● Les deux hôtes d'extrémité sont responsables du débit de transfert des données :

TCP: comment faire pour minimiser la congestion

Principe “end to end”

– à quelle vitesse transmettre ?– quand transmettre ?– quand accélérer et décélérer le débit ?

● Le réseau ne leur fournit pas des informations explicites

4303/01/2011

● Contrôle de flux : par rapport au récepteur

– l'émetteur adapte le nombre de paquets envoyés à la taille du buffer de

réception

TCP: comment faire pour minimiser la congestion?

● Contrôle de congestion : par rapport au réseau

– l'émetteur adapte le débit des données envoyées à la bande passante

instantanée du réseau

Ce n'est pas la taille des paquets, mais leur débit d'envoi qui change

4403/01/2011

● Buffer de réception : espace de stockage des données (reçues ou non)

● Fenêtre de réceptionnombre max de paquets que le récepteur est capable de recevoir à un certain moment (l'espace libre au récepteur)

● Fenêtre d’émission : les données de l'application

TCP: Quelques définitions liées à la congestion

● Fenêtre d’émission : les données de l'application

● Fenêtre de congestion (cwnd)– sous fenêtre mobile de la fenêtre d'émission– nombre max de paquets que l'émetteur peut envoyer avant de recevoir un accusé lui permettant de poursuivre la transmission

● Seuil de démarrage lent (ssthresh)– estimation de la bande passante disponible

4503/01/2011

● Accusé de réception– récepteur >émetteur

– numéro du 1er octet attendu par le récepteur

● TCP classique : les accusés sont cumulatifs


● DupACK : un accusé identique au précédent

– si paquet N arrive au récepteur avant N - 1, son accusé est

identique à l'accusé de N - 2

● Delayed ACK : retarder les accusés

4603/01/2011

● RTT (Round Trip Time)– temps entre l’envoi d’un paquet et la réception de son

accusé

● RTO (Retransmission Timeout)– à chaque envoi d'un paquet, une horloge propre est lancée


– si l'horloge expire, le paquet est retransmis

● le RTO est affecté dynamiquement, en fonction du RTT [RFC 2988]

● exemple : RTO = 2*RTT

4703/01/2011

● En général, la perte d'un paquet est la seule information sur l'état du réseau

● Le CC est géré exclusivement par l'émetteur

– le récepteur ne fait que renvoyer des accusés de réception

● Les mécanismes basiques de CC supportés par TCP sont [RFC 2581] :

– slow start ( départ lent )

– congestion avoidance ( évitement de congestion)

– fast retransmission ( retransmission rapide )

TCP : Mécanismes de CC

– fast retransmission ( retransmission rapide )

– fast recovery ( recouvrement rapide)

� algorithmes AIMD (Additive Increase, Multiplicative Decrease

48

Principe de base: TCP augmente progressivement (au rythme des RTT) la valeurde cette fenêtre jusqu’à la détection d’une perte. A ce point, la source réduit lataille de la fenêtre de congestion et recommence l’augmentationprogressivement.Cet aspect dynamique de la fenêtre est connu dans la littérature par le terme :AIMD (“Additive Increase/Multiplicative Decrease”).

03/01/2011

But : retrouver rapidement la bande passante disponible● cwnd = 1

● cwnd++ à chaque accusé reçu (cwnd *= 2 à chaque RTT)– (croissance exponentielle)

● ssthresh = valeur arbitraire

● Si perte :– ssthresh = cwnd / 2

TCP : Slow start

– ssthresh = cwnd / 2– cwnd = 1– on relance le slow start

● Si atteinte ssthresh :– on entre en congestion avoidance

49

L'émetteur commence par transmettre un segment. Quand l'accusé de réception estreçu, cwnd est incrémenté de 1 à 2, et 2 segments peuvent être envoyés. Lorsque unACK arrive pour chacun de ces segments, cwnd est incrémentée de 2 à 4 et ainsi desuite...jusqu'à la fin du transfert ou jusqu'à ce que le buffer de l'émetteur soit plein.La croissance de cwnd est exponentielle ou presque, le destinataire pouvant retarderles accusés de réception et envoyer un accusé pour deux segments reçus.

03/01/2011 50

Evolution de la fenêtre de congestionpendant la phase slow-start

03/01/2011

• Après l’établissement de la connexion ou après l’expirationd’un temporisateur de retransmission, l’émetteur1 fixe lataille de la fenêtre de congestion à 1 segment (MSS). A chaqueréception d’acquittement, il augmente la taille de la fenêtre decongestion par 1 MSS Figure diapo 53).

TCP : Slow start

Principe de base :

• Cet algorithme continue jusqu’à ce que la fenêtre decongestion atteigne un seuil (SS-threshold). Ceci résulte enun accroissement exponentiel de la fenêtre de congestion : sichaque paquet est acquitté, la fenêtre de congestion doublede taille après chaque RTT

5103/01/2011

● Utilisé quand cwnd >= ssthresh

● cwnd++ à chaque RTT– (croissance linéaire)

But : augmenter le débit en testant la bande passante disponible

TCP : Congestion avoidance

52

● Si perte :– ssthresh = cwnd / 2– cwnd = 1– retour au mode slow start

03/01/2011

Contrôle de la congestion TCP Tahoe

TCP : Slow start

53

cette Figure montre l’évolution de la fenêtre de congestion TCP enfonction du temps d’aller retour : RTT (“Round Trip Time”)1. La croissancede la fenêtre de congestion se fait en deux phases : Slow-start etcongestion avoidance

03/01/2011

L'idée de l'algorithme est qu'une indication de pertes de paquetssignale une situation de congestion. Une perte de paquets peutêtre signalée soit par un timeout, soit par la réception de ACKsdupliqués.

Quand la congestion est signalée, TCP doit ralentir son débitd'émission des paquets et demander à l'algorithme slow-start dereprendre la situation en main. Bien que les deux algorithmes sontindépendants (congestion avoidance et slow-start), ils sont

TCP : Congestion avoidance

indépendants (congestion avoidance et slow-start), ils sontgénéralement implémentés ensemble. Ils nécessitent, outre lafenêtre de congestion définie précédemment (cwnd), un seuil associéau slow-start appelé ssthresh.

Lorsqu'une situation de pertes de paquets est signalée, la fenêtre decongestion est décrémentée de moitié : cette taille est conservéecomme seuil pour l'algorithme slow-start (ssthresh).De plus, si laperte de paquets est signalée par un timeout, cwnd est ramenée à savaleur initiale et TCP se remet en mode slow-start.

5403/01/2011

� But : détecter plus rapidement la perte d'un paquet

� Un paquet est considéré par l'émetteur comme perdu si :

– pas d'accusé au timeout (=> pertes successives), déjà traité

TCP : Fast Retransmission

traité– ou bien réception de N dupacks, N = 3 en gén. (=> perte)

� Fast retransmission : si N dupacks, on n'attend plus letimeout, mais :

– on retransmet le paquet– on entre en slow start (Tahoe) ou fast recovery (les autres)

5503/01/2011

� ssthresh = cwnd / 2

� cwnd = ssthresh + 3 (“gonflement” de cwnd)– envoi éventuel de nouveaux

Paquets

TCP : fast recovery

� Pour chaque dupack, cwnd++– envoi éventuel d'un nouveau paquet

� Réception d'un non dupack(“dégonflement” de cwnd) :

– cwnd = ssthresh– retour au congestion avoidance

5603/01/2011

TCP: Contrôle de la congestion TCP Reno

57

Voir TD3

03/01/2011

� Tahoe : slow start + congestion avoidance + fast retrans

� Reno : Tahoe + fast recovery

� Newreno : Reno + adaptation aux pertes successives

TCP : algorithmes de CC

� Vegas : basé sur l'historique du RTT (état des routeurs)

� SACK, DSACK : spécifie exactement les paquets reçus� Westwood+ : basé sur l'historique du RTT, meilleureutilisation si pertes aléatoires� Beaucoup d'autres...

5803/01/2011

Perte <=> timeout ou 3 dupacks

Utilise :– slow start– congestion avoidance– fast retransmit

TCP : Tahoe

– fast retransmit

Initialisation :

cwnd 1(MSS);ssthresh Init_Ssthresh; State SlowStart;

59

Voir TD3

03/01/2011

Documents

Gestion de congestion