Introduction • Différentes politiques possibles: 1. Se débrouiller pour que ça n’arrive jamais (Autoroute sur-dimensionnée) 2. Prévenir l’embouteillage par un contrôle des accès 3. Attendre l’embouteillage et résoudre le problème une fois qu’il est là Méthode: • Surveiller le système • Envoyer des informations aux endroits où les décisions doivent être prise (péage des autoroutes) • Ajuster le comportement du système pour corriger le problème (agents aux carrefours, interdire certains accès) • Le contrôle peut être effectué à différents niveaux
Introduction • Le problème – But: Eviter que le réseau n’achemine plus correctement les paquets à cause d’un embouteillage – Dans le cas d’un embouteillage dans Internet, les routeurs détruisent les paquets qu’ils ne peuvent plus mémoriser – On peut retrouver les problèmes de congestion au niveau liaison de donnée. – La résolution des collisions d’Ethernet est un contrôle de congestion
Un exemple de solution par prévention • Les paquets d’engorgement: une solution pour prévenir la congestion quand elle n’est pas loin – Chaque nœud surveille le pourcentage d’utilisation de ses lignes de sorties qui sert à calculer une valeur à laquelle est associée un seuil – Dès que la valeur calculée est voisine du seuil le nœud envoie pour chaque paquet devant ressortir sur cette ligne un paquet d’engorgement à la source, en indiquant la destination du paquet – Un bit est positionné dans le paquet de donnée avant émission pour que les noeuds suivants ne génèrent plus de paquets d’engorgement – Quandla source reçoit un paquet signalant un engorgement, elle réduit le pourcentage d’émission à destination de cette adresse destination
Contrôle de congestion au niveau liaison de donnée Pas de noeud intermédiaire Peut être nécessaire seulement pour les réseaux à diffusion Algorithme de résolution des collisions d’Ethernet Contrôle de congestion après coup Ethernet envoie des que possible et s’arrête d’émettre au moment de la détection de la collision Peu efficace à forte charge (voir efficacité d’Ethernet) Dépend de la taille des paquets
Contrôle de congestion au niveau liaison de donnée Commutateurs Ethernet actuels: Plus de collisions (full-duplex) Le commutateur ne re-émet que vers la destination après mémorisation du paquet grâce à une table de commutation (obtenue grâce aux premiers paquets) Possibilités de saturation de la mémoire du commutateur Trames perdues -> reprise des pertes par la couche transport : l’efficacité s’effondre Paquets particulier dit de “PAUSE” vers la ou les machines source quand le commutateur arrive à saturation -> la carte arrête d’émettre pendant la durée donnée dans le paquet PAUSE Fait aujourd’hui partie de la norme Ethernet
• “Datagram”: Avantages: – Chaque paquet indépendant – Routes différentes possibles – Dynamique (exemple RIP), possibilité de métrique dynamique (charge des routeurs) pour le choix des routes Inconvénients: – Déséquencement – Calcul des routes et consultation de la table de routage pour chaque paquet donc charge CPU des routeurs importante – Pas de réservation possible dans les routeurs pour une communication – Contrôle de congestion délicat
Rappels sur le fonctionnement des routeurs d’Internet . Un routeur mémorise chaque paquet reçu, analyse son entête et décide de la route avant de le re-émettre . Besoin de mémoire, le temps de traversée d’un routeur dépend de sa charge (nombre de paquets rentrant, nombre de paquets sortant) . Possibilité de saturation du routeur : files d’attente pleines . Destruction des paquets si les files d’attente sont pleines Routeur
Amélioration de l’équité dans un routeur – Traitement d’attente équitable : FQ (Fair Queueing) – Une file d’attente supplémentaire par flux est mise en sortie – Un ordonnanceur prend de façon cyclique un paquet dans chacune de ces files – Le routeur partage de façon équitable les flux entrants (équité en nombre de paquet) – En cas de saturation les flux à gros débits auront plus de pertes Port1 Entrée Port Sorti Matrice de e commutati Port2 Entrée on
Amélioration de l’équité dans un routeur – Un flux à gros paquet est privilégié en terme de débit – Il existe aussi des ordonnanceurs pour partager la ligne de sortie en terme de nombre d’octets (plus équitable en terme de débit)
Port1 Entrée Matrice de Port Sortie commutati Port2 Entrée on
Traitement de la QoS dans un routeur – On peut décider d’autres critères pour la création des files d’attente sur un port de sortie: – Adresse IP source ou destination (Machine) – Port destination (Application) – Protocole de niveau supérieur – Marquage des paquets dans l’entête IP (voir plus loin “Diffserv”) – On peut donner des critères différents que “chacun son tour” (équité) à l’ordonnanceur pour privilégier certains flux: – Définition de flux pondérés: WFQ (Weighted Fair Queueing) – Intéressant pour privilégier par exemple une application “Temps réel”
Le WFQ (Weighted Fair Queueing) – Chaque file d’attente Fi se voit attribuer un poids Wi – On veut partager entre plusieurs flux d’entrée la bande passante de sortie (suivant les poids affectés aux flux) – L’ordonnanceur “donne”une partie de la bande passante de sortie à chaque file égale à Wi sur la somme des poids des files ayant des paquets en attente – Pour chaque file à traiter le nombre d’octet à émettre (avant de passer à la file suivante) est calculé en fonction de ces poids – Ainsi si à un moment donné un flux est seul à transiter, il peut utiliser 100 % de la bande passante
Solutions du contrôle de congestion dans Internet – Contrôle de congestion peu résolu dans les protocoles initiaux car non prévu au départ – Niveau Réseau: protocole IP: Mode Datagram – Techniquesmise en place après coup et utilisé dans des Intranets car difficile à mettre en oeuvre à grande échelle dans Internet • Groupes de travail de l ’IETF (Internet Engineering Task Force) • IntServ: intégration de service • DiffServ: différentiation de service
Réservation de ressources – IntServ (intégration de services) – Protocole RSVP ( Resource ReSerVation Protocol ) : – permet d’éviter la congestion et de garantir des QoS – Réservations de ressources (Mémoire) dans les routeurs par des messages particuliers de signalisation depuis la source – Modification de QoS à la demande du (ou des) récepteur; c’est lui qui connaît la QoS dont il a besoin – QoS possible: garantie de débit minimal, latence – Complexe et coûteux; Ne tient pas à grande échelle
Différentiation de services – Ne permet pas le contrôle de congestion mais permet de garantir des QoS à certains flux – Diffserv (différenciation de services): – Marquage dans l’entête IP – Au début – Champs Type de service (ToS): – Priorité sur 3 bits – 4 bits (délai, débit, fiabilité, coût) – AUJOURD’HUI: – Champs ToS remplacé par le champ DSCP (Differentiated Service Code Point) – 6 bits permettent de différentier les classes de service
Optimisation du travail des routeurs: Association connexion transport et route – Implémenté la plupart du temps aujourd’hui dans les routeurs et les machines hôtes: Association de la route à l ’identification de la connexion de niveau transport (UDP ou TCP) : @internet et Numéro port source , @internet et Numéro port destination. Fait pour le premier paquet, pour les suivants économie de la consultation de la table de routage(sauf modification dynamique de la table) Arrêt de l’association par timer d’inactivité
La fenêtre de congestion – Comment fixer la taille de la fenêtre de congestion ? – Découvrir la bande passante disponible le plus rapidement possible – L’idéeest de l’augmenter jusqu’à que l’on arrive à une perte qui signifie la congestion – L’émetteur va alors diminuer la taille de la fenêtre pour diminuer son flux d’émission – Comme on n’a aucune connaissance du réseau, l’idée est de démarrer d’une valeur très basse mais d’augmenter rapidement pour que l’efficacité reste bonne si le réseau est performant
La fenêtre de congestion • Soit MSS la taille maximum des segments envoyés sur le réseau • Algorithme dit du démarrage lent ( slow start ) • cwnd= MSS, • A la réception d’un acquittement faire – cwnd= cwnd + MSS • Si un temporisateur de re-émission expire (perte donc congestion) – cwnd= MSS – Lefait d’augmenter d’un MSS à chaque acquittement revient à doubler la taille de la fenêtre tous les RTT (Temps aller-retour) – Le slow start commence très bas mais augmente exponentiellement
Autres améliorations • D’autres versions du contrôle de congestion dans TCP existent – Vegas (1994) – New Reno 1999 (amélioration de Reno en cas de plusieurs pertes consécutives) • Une des plus novatrice, appelée Vegas consiste à ne plus attendre de perte pour ralentir son rythme d’émission – Pour cela elle se base sur l’évolution du RTT – Si le RTT augmente c’est que les files d’attentes dans les routeurs augmentent et que l’on s’approche de la congestion – On diminue alors la fenêtre jusqu’à que le RTT diminue • Acquittement sélectif (option TCP 1996) – TCP spécifie les plages de numéro de séquence reçus
Observation de flux TCP • Le contrôle de congestion de TCP Reno et Tahoe aboutissent à des phénomènes d’oscillation (augmentations fortes puis diminutions fortes des flux) • Dans le cas de plusieurs flux TCP, on observe des débits très variables suivant les flux • En effet en cas de saturation d’un routeur – De nombreux paquets peuvent être supprimés (congestion forte) – Une flux peut être pénalisé plus qu’un autre Flux 1 "prend le dessus" cwnd
• Au départ TCP spécifie si il gère ECN (bit avant le drapeau Urgent (ECE : ECN Echo) • Les routeurs peuvent marquer dans l’entête IP les deux bits inutilisés du champ Diffserv d’IP – 00: non ECN – 01 ou 10 : ECN possible, paquet non marqué – 11: ECN possible , CE (Congestion Experienced), paquet marqué