ISSATM
Contrôle de congestion dans
les réseaux
Nov 2020
Introduction
> Lorsque de très nombreux paquets sont présent dans le réseaux de
transmission (ou une partie du sous-réseau), ses performances se
dégradent.
C’est la situation de congestion
2
Principe
3
Facteurs causant la congestion
> La cause fondamentale de la congestion est que la demande
de trafic en entrée dépassent la capacité du réseau
> Pas assez de mémoire pour stocker les paquets qui arrivent
> Lenteur des processeurs des routeurs
> Trafic en rafales
> Dans les réseaux à commutation de paquets, cela peut se
produire assez facilement lorsque:
— Les liaisons de sortie sont plus lentes que les entrées
— Plusieurs sources de trafic en compétition pour une même liaison de
sortie en même temps
4
Facteurs causant la congestion (suite)
> Bande passante faible
— Problème physique (type de câble par exemple)
> Performance des processeurs
— Temps mis pour exécuter les tâches demandées (Mise en file
d’attente, MàJ tables de routage, retransmission,…)
> File d’attente des lignes d’entrée
— Taille finie implique perte de paquets possibles
— Augmenter la taille des mémoires tampon ?!!
5
Dans quelles couches ?
> Afin de contrôler la congestion d’un réseau, il s’agit de
réduire la charge imposer par la couche transport sur le
réseau de transmission.
> ce qui fait que les couches réseau et transport doivent
collaborer ensemble.
6
Effets d’un réseau en congestion
> La congestion est indésirable car elle peut causer:
— Une augmentation de retard, en raison des files d'attente dans
le réseau
— La perte de paquets, en raison d'un débordement de tampon
— Débit réduit, du fait de la perte de paquets et la retransmission
> La congestion peut se propager dans tout le réseau
> Analogie: "trafic routier pendant les heures de pointe"
7
Congestion sans contrôle
8
TCP congestion
Partie 1
Mécanismes de contrôle de congestion
9
Mécanismes de contrôle de congestion
> Les Réseaux devraient prévoir des mécanismes de contrôle de
congestion pour faire face à une telle situation
Le contrôle de congestion vise à maintenir le nombre de
paquets en dessous du niveau auquel les performances
diminuent considérablement
Deux types de solution : la prévention (ou anticipation) ou la
régulation (a posteriori).
10
Contrôle de flux vs. Contrôle de congestion
11
Politique de prévention de la congestion
12
Politique de prévention de la congestion
13
Stratégies préventives
14
Stratégies préventives
15
Stratégies préventives
16
Circuits virtuel
17
Circuits virtuels
18
19
20
21
Contrôle de l’écoulement
22
Contrôle de l’écoulement
23
Qualité de service : routage proportionnel
24
En résumé
> La préallocation des ressources
> Réservation des resources : l'espace de stockage,
portion de bande passante
— Utilisable uniquement dans le cadre d'une connexion.
> Efficace mais monopolisation inutile de ressources.
> Le contrôle de congestion isarythmique
> Conservation d'un nombre constant de paquets en
circulation dans le réseau : par utilisation de jetons.
— Mauvaise répartition des jetons en fonction de la charge.
25
En résumé (suite)
> Rétro-contrôle
Contrôle du débit des émetteurs
— chaque nœud surveille le taux d'utilisation de ses liaisons
– explicitement : envoi de paquet d'engorgement vers les nœuds
émetteurs de paquets devant être acheminés sur les liaisons
chargées.
– implicitement : l'absence d'acquittement témoigne de congestion
— délai de réaction
> Priorité/destruction des paquets
Sauf pré-réservation massive et donc inefficace, les
congestions sont inévitables
— nécessité de définir des critères pour choisir les paquets à
détruire ou à acheminer en priorité.
— inévitable mais en dernier ressort !
26
TCP congestion
Partie 2
Contrôle de la congestion par TCP
27
Rappel: Fonctions des protocoles de transport
> Protocoles de bout en bout (pas comme à la couche
réseau par exemple)
— Service connecté ou non
— fiabilité
— performance
> Transport d’un message d’un émetteur au récepteur
— Indépendamment des réseaux qui véhiculent l’information
– Pas de connaissance sur les réseaux traversés
> « Interface » entre les applications et le réseau
> S’appuie sur des protocoles (des couches basses)
pour l’acheminement des données.
> Deux protocoles principaux :
— TCP : fiabilité, contrôle d’erreur, de flux, d’ordre
— UDP : Vérification des erreurs
28
Rappel: Caractéristiques de TCP
> Fiabilité
— Numéro de séquence
— Détection des pertes :
– Aquittements positifs (ACK) du récepteur -> OK
– Pas d’ACK -> timeout (temporisation) -> retransmission
– ACK dupliqué
— Réordonnancement des paquets au récepteur
— Elimination des paquets dupliqués
— Checksum
— Retransmissions :
– Selective repeat
– Go back N
> Contrôle de flux par annonce de fenêtres
— Fenêtre modulée par le récepteur
— Inclus dans l’ACK
– Fenêtre qui indique le plus grand numéro de séquence pouvant être reçu
– Erreur = congestion
> Contrôle de congestion : adaptation à l’état d’occupation du réseau
— Sans signalisation réseau
> Orienté connexion
29
Rappel: Contrôle de flux TCP
Fenêtre annoncée
Transmis
Transmis et acquitté non acquitté
Non transmis Non transmissible
> Basé sur la fenêtre glissante
— Pointeur de début de fenêtre
— Pointeur indiquant la partie transmise et non acquittée
— Pointeur indiquant la fin de la fenêtre
— Envoi de données urgentes toujours possible
30
Rappel: Fenêtre glissante
> But : optimiser les ressources
— Contrôle de flux et contrôle de congestion
> L’émetteur peut envoyer n paquets dans une fenêtre de taille n sans
recevoir d’ACK.
> L’émetteur fait glisser la fenêtre sur réception d’un ACK.
> Fenêtre effective = Fenêtre annoncée - (octets transmis - octets non
acquittés)
> Arrêt de la transmission quand fenêtre effective=0
émetteur récepteur
DATA 1
DATA 2
DATA 3
DATA 4 1 2 3 4 5 6 7 8 9
DATA 5
ACK2
fenêtre
DATA 6 glissante
31
Rappel: Temporisateurs de TCP
> Temporisateur de retransmission
> Temporisateur de peristence
— Pour débloquer la situation après une fenêtre d’émission réduite
à zéro et une ouverture perdue
> Temporisateur d’inactivité
— Vérifie la présence de l’autre extrémité
> Temporisateur de déconnexion
— Deux fois la durée de vie des paquets
32
Concepts de contrôle de congestion par TCP (1)
> Concept primaire
— Il n'existe aucun moyen pour TCP afin de déterminer l'état du
réseau exactement.
— TCP considère toutes les pertes de paquets comme étant une
congestion.
> Contrôle de transmission avec des algorithmes simples.
— Si les paquets ne sont pas perdus ..
— TCP suppose le réseau non congestionné?
Augmente le taux de transfert.
— Si les paquets sont perdus ..
— TCP suppose le réseau congestionné ?
Diminue le taux de transfert.
TCP augmente le taux de transfert jusqu'à perte de paquets.
TCP tente d'estimer la limite du réseau en provoquant la perte de
paquets.
33
Concepts de contrôle de congestion par TCP (2)
> Comment contrôler le taux de transfert?
— Introduit une nouvelle variable appelé fenêtre de congestion
(cwnd) dans le mécanisme de fenêtre glissante.
— Ajuste la quantité de données injecté dans les réseaux
> Comment déterminer la taille de la fenêtre?
— La taille de la fenêtre = min (la fenêtre annoncée, la fenêtre de
congestion)
— La fenêtre annoncée est utilisé pour le contrôle de flux et
déterminé par le côté récepteur.
— La fenêtre de congestion est utilisé pour le contrôle de
congestion et déterminé par le côté source.
34
Concepts de contrôle de congestion par TCP (3)
> Horloge propre
— Utilise une arrivée d’ACK comme un déclencheur d'une
nouvelle transmission de paquets.
– L’intervalle d’arrivé des paquets va changer en fonction des
caractéristiques du réseau de transport.
> Ajuste le taux de transfert à la capacité du réseau
automatiquement.
— Pas besoin de mécanisme complexe pour contrôler le taux de
transfert! P b
Pr
Sender Receiver
As Ar
Ab
35
Terminologie
Avant de commencer, quelques éléments de terminologie:
— MSS (maximum segment size), la taille maximum d'un segment
(entête TCP + données);
— awnd (advertised window), fenêtre annoncée coté réception;
— cwnd (congestion window), fenêtre de congestion;
— swnd (sending window), fenêtre d'émission (= min (cwnd, awnd));
— RTO (retransmit timeout), temps de transmission maximal (souvent
2 fois le RTT);
— RTT (roundtrip time), durée d'envoi puis de réception
d'acquittement d'un paquet;
— ssthresh (slow start threshold), taille maximum d'une fenêtre
d'émission en slow start;
— LFN (long fat network), réseau avec une grande bande passante
mais aussi un long délai de réponse;
36
Les différentes phases basiques des
algorithmes d'évitement de congestion
> Le principe de base d'évitement de congestion est de réagir en
réduisant le débit de la connexion.
> Les protocoles mesurent l’importance du problème en observant
divers phénomènes comme :
— l’augmentation du temps de réponse
— la duplication de messages de type ACK signifiant une perte de paquet
par exemple.
> Si le protocole ne réagit pas aux congestions, le nombre de
retransmission peut continuer à augmenter et aggraver ainsi la
congestion.
> C’est la raison pour laquelle un algorithme de contrôle réduit le flux
en cas de congestion.
> Il n'y a pas de système central d'évitement de congestion, chaque
élément du réseau doit adapter son flux d'émission.
37
Algorithmes de contrôle de congestion et
gestion des fenêtres
> Slow start
> Congestion avoidance
> Fast retransmission
> Fast recovery
> cwnd++ (CA) ou /2 (si perte) => mécanisme AIMD
(Additive Increase, Multiplicative Decrease)
38
Slow Start
> But : retrouver rapidement la bande passante disponible
> cwnd = 1
> cwnd++ à chaque accusé reçu (cwnd *= 2 à chaque
RTT)
→ croissance exponentielle
> ssthresh = valeur arbitraire
> Si atteinte ssthresh :
— on entre en congestion avoidance
> Si perte :
— ssthresh = cwnd / 2
— cwnd = 1
— on relance le slow start
39
Slow Start
Paquets en transit lors du slow
start.
40
Congestion avoidance
> Utilisé quand cwnd >= ssthresh
— quand cwnd < ssthresh, c'est le slow start qui est utilisé
> But : augmenter le débit en testant gentillement la bande
passante disponible CWND
> cwnd++ à chaque RTT
— croissance linéaire
> Si perte :
— ssthresh = cwnd / 2
— cwnd = 1
— retour au mode slow start
41
Evolution du Cwnd dans la version tahoe du
TCP
42
Taille optimale de la fenêtre de transmission
43
Algorithme du Congestion Avoidance
Congestion avoidance
/* slowstart is over */
/* Congwin > threshold */
Until (loss event) {
every w segments ACKed:
Congwin++
}
threshold = Congwin/2
Congwin = 1
perform slowstart 1
1: TCP Reno skips slowstart (fast
recovery) after three duplicate ACKs
44
Fast retransmission
> But : détecter plus rapidement la perte d'un paquet (et le
retransmettre)
> Un paquet est considéré par l'émetteur comme perdu si :
— pas d'accusé au timeout (=> pertes successives), déjà traité
— ou bien récéption de N dupacks, N = 3 en gén. (=> perte isolée)
> Fast retransmission : si N dupacks, on n'attend plus le
timeout, mais :
— on retransmet le paquet
— on entre en slow start (Tahoe) ou fast recovery (Reno et
newReno)
45
Ack dupliqué
46
Ack dupliqué
Packets
1 2 3 4 5 6 7
Acknowledgements
1 2 3 3 3 3
47
48
Fast recovery
> Empêche le slow start après la congestion
> Slow start utilisé en cas de perte de paquets (expiration
du timer)
> ssthresh = cwnd / 2
> cwnd = ssthresh + 3 (“gonflement” de cwnd)
=> envoi éventuel de nouveaux paquets
3, car 3 paquets accusés
> 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
49
Fast Retransmission & Fast recovery
50
> Après 3 dupACKs
— Mettre ssthresh max(flightsize/2, 2)
— Retransmettre le paquet perdu
— Mettre cwnd ssthresh + ndup (window inflation)
— Attendre juqu’à W=min(awnd, cwnd) soit suffisament
large; Transmettre un nouveau packet(s)
— Lorsque non-dup ACK (1 RTT après), mettre cwnd
ssthresh (window deflation)
> Entrer en Congestion Avoidance CA
51
Exemple
S 1 2 3 4 5 6 7 8 1 9 10 11
time
Exit FR/FR
R 0 0 0 0 0 0 0 8 time
cwnd 8 7 9 11 4
ssthresh 4 4 4 4
52
Résumé du contrôle de congestion par TCP
(version Reno)
53
Résumé
> Il est important de comprendre que la stratégie de TCP est de contrôler la
congestion une fois qu‘elle se produit, plutôt que d'essayer d'éviter la
congestion en premier lieu.
> En fait, TCP augmente à plusieurs reprises la charge qu'il impose sur le
réseau dans un effort pour trouver le point où la congestion se produit, puis
il recule de ce point.
> Une alternative intéressante, mais qui n'a pas encore été largement
adoptée, est de prédire quand la congestion est sur le point d'arriver et puis
de réduire le taux auquel les hôtes envoient des données juste avant que
les paquets commencent à être jetés.
> Nous appelons une telle stratégie « évitement de la congestion », afin de
la distinguer du contrôle de la congestion.
54
Partie 3
Prévention des congestions dans
les réseaux
55
Algorithmes "de gestion de file d'attente" dans les
routeurs
> Il est devenu évident que les mécanismes TCP de contrôle de
congestion, bien que nécessaires et puissants, ne sont pas suffisants
pour fournir un bon service dans toutes les circonstances.
> Fondamentalement, il y a une limite à la quantité de contrôle qui peut
être accompli depuis les extrémités du réseau.
> Certains mécanismes doivent être ajoutés dans les routeurs pour
compléter les mécanismes d'évitement de congestion des points
d'extrémité.
> Les algorithmes de gestion de file d'attente gèrent la longueur des
files d'attente des paquets en abandonnant des paquets lorsque
nécessaire ou approprié, et utilisé principalement pour gérer
l'allocation de bande passante entre les flux.
56
Mécanismes Classiques de gestion des files
d'attente dans les routeurs
> Tail-drop
— Rejet des paquets qui se présentent quand le buer
est plein.
> Push Out
— Élimination de paquets moins importants déjà
présents pour faire de la place pour les paquets de
première classe. Tail-drop à l'intérieur de la classe la
plus haute.
57
Tail-drop
> La technique traditionnelle pour la gestion des longueurs de file
d'attente chez un routeur est
— d'établir une longueur maximum (en termes de paquets) pour chaque
file d'attente,
— d'accepter ces paquets pour la file d'attente jusque à ce que la
longueur maximum soit atteinte,
— puis de rejeter (abandonner) les paquets entrants suivants jusque à ce
que la file d'attente diminue à cause de la transmission d'un paquet de
la file d'attente.
> Cette technique est connue sous le nom de "abandon du bout de la
queue" (tail drop), car le paquet arrivé le plus récemment est
abandonné lorsque la file d'attente est pleine.
58
Drop-tail
Drop Tail
Drop Packets After
Actual
Queue Size Buffer Overflow
Early Random Drop
Drop Packets with
Fixed Drop Prob.
59
Inconvénients de tail-drop
> Cette méthode a bien servi l'Internet pendant des années, mais elle
présente des inconvénients importants.
— Verrouillage : dans certaines situations, l'exclusion du bout de la
queue permet à une seule connexion ou à quelques flux de
monopoliser l'espace de file d'attente, empêchant ainsi les autres
connexions d'obtenir de l'espace dans la file d'attente.
— Ce n'est pas du tout équitable et cela conduit à des retransmissions
de synchronisation.
— Quand une retransmission de synchronisation a lieu, la brusque
rafale de rejet d'un routeur qui a atteint sa limite entraînera une
rafale de retransmissions retardée qui inondera à nouveau le routeur
congestionné.
> Ces problèmes avec le "tail-drop" deviennent de plus en plus
préoccupants avec l'augmentation de l'utilisation d'applications hostiles
au réseau.
60
Gestion active de file d'attente dans les
routeurs (Active Queue Management)
> Dans l'Internet actuel, les paquets abandonnés servent de mécanisme
critique de notification d'encombrement aux nœuds d'extrémité.
> La solution au problème des files d'attente pleines est que les routeurs
abandonnent les paquets avant qu'une file d'attente ne soit pleine, de
façon à ce que les nœuds d'extrémité puissent répondre à
l'encombrement avant que les mémoire tampon ne débordent.
> On appelle une telle approche préventive "gestion active de file
d'attente".
> En abandonnant les paquets avant le débordement des mémoires
tampon, la gestion active de file d'attente permet aux routeurs de
contrôler le moment et la quantité de paquets à abandonner.
61
Avantages
Un mécanisme de gestion active de file d'attente peut fournir les
avantages suivants pour les flux de trafic :
>Réduire le nombre de paquets abandonnés dans les routeurs
— En maintenant petite la taille moyenne de file d'attente, la gestion
active de file d'attente donne une plus grande capacité d'absorption de
trafic sans abandonner de paquets.
>Fournir un service interactif à plus faible délai
— En conservant petite la taille moyenne de la file d'attente, la gestion de
file d'attente va réduire les délais subis par les flux.
>Éviter le comportement de verrouillage
— en s'assurant qu'il y aura presque toujours une mémoire tampon
disponible pour un paquet entrant.
62
Algorithme RED (Random Early Detection) de gestion
de file d'attente
> La détection précoce aléatoire (RED, Random Early Detection) est un
algorithme de gestion active de file d'attente pour les routeurs.
> À la différence des algorithmes traditionnels de gestion de file
d'attente, qui n'abandonnent les paquets que lorsque la mémoire
tampon est pleine, l'algorithme RED abandonne de façon probabiliste
les paquets arrivants.
> La probabilité d'abandon augmente avec la croissance de la taille
moyenne estimée de la file d'attente.
> RED répond à une longueur de file d'attente moyenne sur une période
de temps, et non à une taille instantanée. Et donc, si la file d'attente a
été presque vide dans le "passé récent", RED ne va pas tendre à
abandonner de paquets
> D'un autre côté, si la file d'attente a récemment été relativement pleine,
indiquant un encombrement persistant, les paquets nouveaux arrivants
auront plus de chances d'être abandonnés.
63
RED (Random Early Detection)
> RED élimine statistiquement des paquets du flux avant qu'il
n'atteigne sa limite "dure" (hard).
> Sur une dorsale congestionnée, cela entraîne un ralentissement en
douceur de la liaison et évite les retransmissions de
synchronisation.
> La technique RED aide aussi TCP à trouver une vitesse "équitable"
plus rapidement : en permettant d'éliminer des paquets plus tôt, il
conserve une file d'attente plus courte et des temps de latence
mieux contrôlés.
> La probabilité qu'un paquet soit éliminé d'une connexion particulière
est proportionnelle à la bande passante utilisée par cette connexion
plutôt qu'au nombre de paquets qu'elle envoie.
64
RED (Random Early Detection)
> L’idée est d’avertir les émetteurs que l’on approche d’une
congestion avant qu’elle n’arrive
> Une façon de ralentir le rythme des émetteurs est de supprimer de
façon aléatoire des paquets arrivant si le taux de remplissage a
atteint un seuil donné (les flots à débits plus important ont plus de
chance de perdre un paquet)
> La probabilité de suppression dépend du remplissage du tampon
65
RED (Random Early Detection)
1st Phase Calculate with Arrive
Calculate Avg. interval
Queue Size Max Calculate with Min
Queue Weight
Average Queue Size
2nd Phase Always Drop/Mark Always Serve
the Packet the Packet
Serve/Drop
the Packet Drop/Mark Packet
with flexible Prob.
66
Pourquoi RED ?
Inconvénients de RED :
> Rejeter des paquets avant que ce soit vraiment
nécessaire
— perte d'information et de débit
> Des paramètres fixes ne peuvent pas fonctionner dans
toutes les conditions de trafic.
— Mécanismes d'adaptation
Avantages :
> Doit permettre d'éviter les fermetures brutales des
sources et leur synchronisation
> Doit pénaliser également toutes les connexions TCP
67
L’algorithme
> L'algorithme RED lui-même comporte deux parties
principales :
— l'estimation de la taille moyenne de la file d'attente
— la décision d'abandonner ou non un paquet entrant.
68
Estimation de la taille moyenne de file d'attente
> RED estime la taille moyenne de la file d'attente soit dans le chemin
de transmission en utilisant une simple moyenne mobile à
pondération exponentielle (telle que celle présentée par Jacobson)
soit en arrière plan (c'est-à-dire, pas dans le chemin de
transmission) en utilisant un mécanisme similaire.
> La taille de la file d'attente peut se mesurer en paquets ou en
octets.
> Lorsque la taille moyenne de la file d'attente est calculée dans le
chemin de transmission, il y a le cas particulier de l'arrivée d'un
paquet alors que la file d'attente est vide. Dans ce cas, le calcul de
la taille moyenne de file d'attente doit prendre en compte le temps
passé depuis que la file d'attente est vide.
69
Décision d'abandon de paquet
> Dans la seconde portion de l'algorithme, RED décide de l'abandon
ou non d'un paquet entrant.
> Pour utiliser RED, on doit régler trois paramètres : Min, Max et
burst.
— Min est la taille minimum de la file d'attente en octets avant que les
rejets n'aient lieu,
— Max est le maximum "doux" (soft) en dessous duquel l'algorithme
s'efforcera de rester,
— burst est le nombre maximum de paquets envoyés "en rafale".
70
Décision d'abandon de paquet
> On doit configurer Min en calculant le plus grand temps de latence
acceptable pour la mise en file d'attente, multiplié par votre bande
passante.
> Par exemple, sur un lien ISDN à 64 Kbits/s, on veut avoir un temps de
latence de base de mise en file d'attente de 200 ms. on configure
donc Min à 1600 octets (= 0,2 x 64000 / 8).
— Imposer une valeur Min trop petite va dégrader le débit et une valeur Min trop
grande va dégrader le temps de latence. Sur une liaison lente, choisir un coefficient
Min petit ne peut pas remplacer une réduction du MTU pour améliorer les temps de
réponse.
> Vous devriez configurer Max à au moins deux fois Min pour éviter les
synchronisations.
— Sur des liens lents avec de petites valeurs de Min, il peut être prudent d'avoir Max
quatre fois plus grand que Min ou plus.
> Burst contrôle la réponse de l'algorithme RED aux rafales. Burst doit
être choisi plus grand que min/avpkt (paquet moyen).
Expérimentalement, on trouve que (min+min+max)/(3*avpkt) marche
bien. 71
> Deux seuils, tmin et tmax, soit taille le remplissage du buffer
— si 0 ≤ taille < tmin: le paquet passe
— si tmin ≤ taille < tmax: le paquet est rejeté avec une probabilité
dépendante de la taille de la file
— si tmax ≤ taille: le paquet est rejeté
72
73
74
1
Dropping/Marking
Probability
maxp
0
minth maxth Queue Size
Average Queue Length
75
Une fonction de rejet de RED
76
pb = maxp x (avg - minth)/(maxth - minth) [1]
where
pa = pb/ (1 - count x pb) [2]
Note: this calculation assumes queue size is measured in
packets. If queue is in bytes, we need to add [1.a]
between [1] and [2]
pb = pb x PacketSize/MaxPacketSize [1.a]
77
Résumé de l’algorithme RED
> Ainsi, la passerelle RED a deux algorithmes distincts:
> L'algorithme pour le calcul de la taille moyenne de file
d'attente déterminant le degré de rafale qui sera
permise dans la passerelle file d'attente.
> L'algorithme de calcul de la probabilité de marquage de
paquets déterminant la fréquence à laquelle la
passerelle marquera les paquets, étant donné le niveau
courant de la congestion.
> L'objectif pour la passerelle est de marquer les paquets
à intervalles assez espacés, afin d'éviter les préjugés et
d'éviter la synchronisation globale, et pour marquer les
paquets avec une fréquence suffisante pour contrôler la
taille moyenne de la file d'attente.
78
