Réseaux IP et Principes de l'Internet

Un réseau informatique est une interconnexion des différents éléments qui permettent la communication de l'information numérique.

Les principaux éléments sont les suivants :

Hôtes

des ordinateurs ou des périphériques connectés au réseau via des liens de communication. Les hôtes qui fournissent des services utiles à d'autres dispositifs sont appelés serveurs. On utilise aussi le terme nœud pour désigner tout appareil connecté au réseau.

Liens de communication

(ou liaisons) qui permettent la propagation de signaux qui encodent l'information numérique. Les liens peuvent utiliser différents types de supports de communication (médium de transmission) tels que des câbles en cuivre, fibres optiques, ondes radio.

Routeurs

ce sont des dispositifs de relayage de paquets entre des liens de communication.

L'interconnexion des routeurs et des liens de communication permet d'assurer la communication entre des hôtes et des serveurs.

Les réseaux offrent la possibilité de communiquer par la résolution de deux problèmes principaux :

1. Communication avec tout le monde — comment faire communiquer n'importe quelle paire d'hôtes ou de serveurs ?
2. Communication partout — comment obtenir la possibilité de communication sur de longues distances et partout dans le monde?

L'information numérique transmise sur le réseau de données est structurée en blocs appelés paquets. Un paquet contient un en-tête avec une certaine information de contrôle, par exemple les adresses source et destination, et une charge utile de données – les informations à transmettre.

Les routeurs relayent des paquets de données entre un hôte source et un hôte de destination en effectuant la commutation de paquets : un routeur reçoit un paquet sur un lien, recherche dans la table de routage une entrée correspondant à la destination pour trouver le lien sur lequel il transmet le paquet vers le routeur suivant sur le chemin vers la destination.

L'Internet est une interconnexion à grande échelle de routeurs et de liens de communication qui assurent une connectivité mondiale. Les routeurs fonctionnent selon le principe de commutation de paquets.

Les hôtes se connectent au premier routeur offrant la connectivité Internet à l'aide d'un réseau d'accès. Il existent différents types de réseaux d'accès : réseaux locaux comme Ethernet, lignes ADSL ou réseaux locaux sans fil tels que Wi-Fi (802.11).

Un système autonome (AS) est un ensemble de routeurs et des liens sous le contrôle d'un opérateur de réseau pour le compte d'une entité administrative unique avec une politique de routage unique. L'interconnexion des systèmes autonomes constitue l'Internet global.

Les systèmes autonomes échangent des paquets aux points d'échange Internet (Internet Exchange Points - IXP) – les réseaux locaux à haut débit reliant les routeurs de bordure des systèmes autonomes.

Le protocole d'Internet (Internet Protocol - IP) définit les principes de la communication sur l'Internet : le format des paquets et des adresses d'hôtes, et la commutation de paquets au niveau des routeurs.

La performance de protocoles concerne principalement le débit et le délai.

Une adresse IPv4 est un nombre de 32 bits représenté par la notation décimale pointée (dotted decimal), par exemple, 129.88.30.11. Chaque nombre décimal correspond à la valeur d'un octet.

Cette partie explique comment les routeurs relaient les paquets en fonction des adresses de destination.

Cette partie fournit les détails du protocole IPv4.

Un nœud apprend dynamiquement l'adresse MAC d'un routeur ou d'un nœud de destination à l'aide du protocole de résolution d'adresse (ARP) : il envoie une requête ARP dans un paquet en broadcast à tous les hôtes/routeurs connectés à un réseau local donné. Le paquet comprend l'adresse IP pour laquelle nous voulons connaître l'adresse MAC. Le nœud qui reconnaît son adresse IP répond avec un paquet unicast contenant son adresse MAC.

ARP maintient une table avec les correspondances entre des adresses IP et les adresses MAC. Une entrée ARP est supprimée de la table après un intervalle (généralement 20 minutes).

 1. ARP 10.0.1.254 ?               , E_10.0.1.1   à FF:FF:FF:FF:FF:FF
 2. ARP 10.0.1.254 est E_10.0.1.254, E_10.0.1.254 à E_10.0.1.1
 3. IP  10.0.1.1 à 10.0.2.1, E_10.0.1.1   à E_10.0.1.254, DNS sur UDP, www.imag.fr A?
 4. ARP 10.0.2.1?                  , E_10.0.2.254 à FF:FF:FF:FF:FF:FF
 5. ARP 10.0.2.1   est E_10.0.2.1  , E_10.0.2.1 à E_10.0.2.254
 6. IP  10.0.1.1 à 10.0.2.1, E_10.0.2.254 à E_10.0.2.1  , DNS sur UDP, www.imag.fr A?
 7. IP  10.0.2.1 à 10.0.1.1, E_10.0.2.1   à E_10.0.2.254, DNS sur UDP, www.imag.fr A 10.0.3.1
 8. IP  10.0.2.1 à 10.0.1.1, E_10.0.1.254 à E_10.0.1.1  , DNS sur UDP, www.imag.fr A 10.0.3.1
 9. IP  10.0.1.1 à 10.0.3.1, E_10.0.1.1   à E_10.0.1.254, ICMP Echo request
10. ARP 10.0.3.1?                  , E_10.0.3.1   à FF:FF:FF:FF:FF:FF
11. ARP 10.0.3.1   est E_10.0.3.1  , E_10.0.3.1   à E_10.0.3.254
12. IP  10.0.1.1 à 10.0.3.1, E_10.0.3.254 à E_10.0.3.1  , ICMP Echo request
13. IP  10.0.3.1 à 10.0.1.1, E_10.0.3.1   à E_10.0.3.254, ICMP Echo reply
14. IP  10.0.3.1 à 10.0.1.1, E_10.0.1.254 à E_10.0.1.1  , ICMP Echo reply

IP offre la possibilité d'envoyer un paquet en multicast : un paquet atteindra tous les hôtes inscrits à un groupe de multicast. Le multicast IP est utilisé pour la construction des tables de routage, dans le streaming, et pour d'autres types d'applications.

Les adresses de la Classe D (adresses de 224.0.0.0 à 239.255.255.255) permettent d'identifier des groupes multicast. Quelques adresses sont réservées :

224.0.0.1

tous les systèmes capables d'assurer le service multicast sur le sous-réseau,

224.0.0.2

tous les routeurs multicast sur le sous-réseau.

IP utilise le paradigme du groupe ouvert : n'importe quel hôte peut envoyer un paquet à un groupe – pas besoin d'une autorisation spéciale pour l'envoi d'un paquet à un groupe. Un hôte source peut envoyer un paquet à un groupe peu importe s'il appartient au groupe ou non. Un hôte peut appartenir à plusieurs groupes différents.

Pour recevoir un paquet multicast, un hôte doit souscrire à une adresse de groupe à l'aide d'un protocole spécifique : IGMP (Internet Group Management Protocole).

Les routeurs construisent un arbre de distribution de multicast à tous les membres d'un groupe en utilisant un protocole de routage multicast tel que PIM (Protocol-Independent Multicast). Si nécessaire, les routeurs répliquent un paquet pour la livraison à tous les membres d'un groupe.

Pour atteindre tous les hôtes d'un groupe donné sur un réseau local Ethernet, un routeur encapsule un paquet IP multicast dans une trame qui a l'adresse de destination de groupe. Cette adresse est dérivée de l'adresse IP de l'adresse de groupe.

Cette partie fournit les détails du protocole IPv6.

Remplace ICMP et ARP d'IPv4.

Principaux messages ICMPv6 :

- Destination unreachable (type 1)
- Packet too big (type 2)
- Time exceeded (type 3)
- Parameter problem (type 4)
- Echo request/reply (type 128 and 129)

Découverte de voisins (Neighbor Discovery) :

• Remplace ARP, ICMP (redirection, découverte de routeur)

Le protocole à Vecteur de Distances souffre du problème du comptage à l'infini : les routeurs échangent leurs vecteurs en augmentant la distance. Il existe deux façons de résoudre ce problème :

Horizon Partagé (Split Horizon)

un routeur ne peut pas annoncer sa route à un voisin, si le voisin est le next-hop pour une destination donnée. (La version Reverse Poisoning : un routeur annonce ces routes avec une distance infinie).

Distance Maximale

on fixe une limite à la distance et si le comptage à l'infini atteint cette limite, on arrête.

Des exemples de protocoles de routage : RIP, IGRP.

Pour trouver les meilleurs routes à toutes les destinations, un routeur exécute un algorithme d'optimisation de graphe tel que l'algorithme de Dijkstra pour trouver le chemin le plus court dans un graphe.

L'Internet est une interconnexion de systèmes autonomes (Autonomous Systems - AS) : un ensemble d'hôtes et de routeurs regroupés sous une seule autorité qui présente une politique de routage commune vis-à-vis des autres AS. Chaque AS gère un des protocoles de routage interne pour le transfert de paquets vers et à partir de ses sous-réseaux (RIP, OSPF, IGRP). Un AS annonce ses préfixes à d'autres ASs avec un protocole de routage externe tel que BGP (Border Gateway Protocol). Un AS apprend tous les autres préfixes en utilisant BGP.

Un routeur BGP d'un AS reçoit de l'information sur les préfixes et leurs attributs des autres AS et annonce les préfixes de ses sous-réseaux. Un attribut commun est AS_PATH : l'ensemble des AS à traverser pour atteindre une destination annoncée. Un routeur BGP prend des décisions de routage basées sur l'attribut AS_PATH, des politiques de routage ou des règles configurées par un administrateur réseau.

Chaque octet que ce soit Flag Sequence, Control Escape ou toute valeur d'octet de moins de 0x20 est remplacé par une séquence de deux octets constituée par l'octet Control Escape suivi par un octet résultat d'un "ou-exclusif" (exclusive-or) entre l'octet d'origine et la valeur hexadécimale 0x20 .

Exemples :

• 0x7e est codé 0x7d 0x5e (Flag Sequence),
• 0x7d est codé 0x7d 0x5d (Control Escape),
• 0x03 est codé 0x7d 0x23 (caractère ETX).

À la réception, chaque octet Control Escape est retiré et on fait un ou-exclusif (exclusive-or) entre l'octet suivant et la valeur hexadécimale 0x20, sauf si l'octet suivant est Flag Sequence (ce qui termine la réception de la trame).

La topologie est sous forme de segments de bus (câble coaxial) : un segment (épine dorsale) relie tous les autres segments. Le câble fournit le support de transmission commun avec un débit nominal de 10 Mb/s qui permet la transmission en broadcast (diffusion) : une trame envoyée par une station se propage sur le câble pour atteindre tous les autres appareils connectés, ce qui signifie que toutes les stations reçoivent toutes les trames transmises. Une trame envoyée à destination d'une seule station est reçue par toutes les stations et seule la station qui reconnait son adresse de destination, reçoit la trame.

Pour étendre la couverture spatiale du réseau, les répéteurs entre les segments amplifient le signal et retransmettent la trame envoyée sur un autre segment. Il y a des limites à la longueur du segment, le nombre de répéteurs, et la topologie du réseau qui impose une limite au temps d'aller-retour entre deux stations connecté au réseau à \(51,2 \mu s\) : la station qui envoie une trame est sûre qu'au bout de cet intervalle de temps, le début de sa trame a été reçu par toutes les stations dans le réseau.

n = 0
REPETER
	attendre que le canal soit libre
	attendre un temps intertrame (interframe gap)
	transmettre et détecter la collision
	SI (collision détectée) ALORS
	   arrêter la transmission
	   transmettre jam (32 bits)
	   n ++
	   SI (n == maxAttempts) ALORS
	       abandon
	   FIN_SI
	   k = min (n, 10)
	   r = random (2^k - 1)
	   attendre temps aléatoire (r × SLOTTIME)
	SINON
	   transmission réussie
	FIN_SI
JUSQU'A (transmission réussie ou abandon)

Une station qui veut transmettre, teste si le canal est déjà utilisé (carrier sense). Si le canal est libre, la station attend un intervalle appelé interframe gap (\(9,6\mu s\)) et transmet la trame. Lors de la transmission, elle vérifie si une collision se produit (en détectant une puissance accrue du signal sur le câble en raison d'un chevauchement de transmissions). En cas de collision (collision detected), la station cesse d'émettre la trame et transmet une séquence de bits aléatoires appelée jam (32 bits). Puis, elle incrémente \(n\), le compteur de collisions et choisit un intervalle de retransmission aléatoire :

$$T = r \times \mbox{SLOTTIME}$$

où

• \(r = \mbox{random}(2^k - 1)\),
• \(k = \min(n, 10)\),
• \(\mbox{SLOTTIME} = 51.2 \mu s\).

L'intervalle des valeurs de \(r\) pour les collisions successives est le suivant :

• Première collision, \(r \in [0, 1]\)
• Deuxième collision, \(r \in [0, 3]\)
• 10, \(r \in [0, 1023]\)
• …
• 14, \(r \in [0, 1023]\)
• 15, on arrete.

Une autre collision peut se produire si les deux stations choisissent la même valeur de \(r\) ce qui arrive avec une probabilité \(1/2\) pour la première collision, \(1/4\) pour la seconde, puis \(1/2^k\).

L'augmentation de l'intervalle pour choisir \(r\) de manière exponentielle est appelé exponential backoff.

La station retransmet la trame impliquée dans une collision après l'intervalle de retransmission (elle suit toujours la règle principale d'accès au canal : attendre que l'activité cesse sur le canal et attendre l'interframe gap).

La figure 10 illustre comment une collision est récupérée :

• à l'instant \(t = 0\), deux stations \(A\) et \(C\) ont des trames à envoyer, ils testent le canal et commencent à envoyer leurs trames, car le canal est libre à cet instant
• à l'instant \(t = T_p\), lorsque le signal de \(A\) arrive à \(C\) (et le signal de \(C\) à \(A\)), les deux stations détectent une collision, arrêtent leur transmissions et envoyent une séquence de bourrage
• après la séquence de bourrage, ils choisissent des intervalles de retransmission aléatoires :
  • \(A\) choisit un SLOTTIME, il reporte alors la tentative de transmission
  • \(C\) choisit 0, il peut alors procéder
• \(C\) teste le canal (il y a encore le signal correspondant à la séquence de bourrage de \(A\)), attend la fin du signal et envoie sa trame
• lorsque \(A\) teste le canal après un SLOTTIME, il y a encore la transmission de \(C\) en cours, il attend alors la fin de la trame
• \(A\) transmet après la fin de la trame de \(C\) (non représenté sur la figure).

Le SLOTTIME de \(51,2\mu s\) garantit qu'après le début d'une transmission, toutes les stations reçoivent le signal émis (canal occupé) ce qui fait que les stations ne vont pas initier une nouvelle transmission (les collisions ne peuvent pas se produire après cet intervalle). La valeur de \(51,2 \mu s\) vient de la limitation de la longueur d'un segment et du nombre maximal de répéteurs entre deux stations : tous les délais de propagation seront inférieurs à \(51,2 \mu s\), la valeur qui correspond à la transmission de 64 octets sur un débit nominal de 10 Mb/s. Cette limitation entraîne les propriétés suivantes :

• \(51,2 \mu s\) est l'unité de retransmission : si après une collision, une station tente de retransmettre après \(51,2 \mu s\), soit le canal est libre et la station essaie de transmettre, soit il y a une transmission en cours et la station va attendre sa fin (nous évitons d'autres collisions),
• Si une station a déjà envoyé 64 octets, le canal est acquis par la station - il n'y aura pas de collisions au cours de la transmission,
• Si il y a une collision, le reste de la transmission d'une trame (trame coupée) aura une taille \(< 64\) octets. Toute trame avec une taille $<64$octets est considérée comme invalide.

Encapsulation Ethernet 2 :

 0                   1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          DST_ADDR             |
|          (6 octets)           |
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          SRC_ADDR             |
|          (6 octets)           |
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    ETHER_TYPE  (2 octets)     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~                               ~
~           payload             ~
~       (46 - 1500 octets)      ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|      CHECKSUM (4 octets)      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Le champ DST_ADDR contient soit une adresse unicast ou une adresse de groupe (dans ce cas là, le premier bit de l'adresse = 1). Les données sur Ethernet sont transmises dans l'ordre suivant : le bit le moins significatif du premier octet en premier (un bug de processeurs Intel). La représentation canonique ainsi inverse l'ordre des bits dans un octet (le premier bit de l'adresse est le bit le moins significatif du premier octet).

Les adresses sont représentées selon notation hexadécimale suivante : 08:00:20:71:0d:d4. L'adresse de diffusion est ff:ff:ff:ff:ff:ff (broadcast).

Exemples :

• une adresse de groupe : 01:00:5e:02:a6:cf.
• une adresse multicast pour IPv4 : 01:00:5e:02:a6:cf.
• une adresse de multidiffusion pour IPv6 : 33:33:ff:02:a6:cf.

ETHER_TYPE détermine le protocole de la couche supérieure à laquelle la charge utile doit être remise: 0x0800 (IPv4), 0x86DD (IPv6), 0x0806 (ARP).

Fast Ethernet : 100 Mb/s sur 4 paires torsadées.

Gigabit Ethernet : 1 Gb/ s, 10 Gb/s, 40 Gb/s sur fibre.

Cas simple - faible charge, aucune activité sur le canal :

tester le canal
SI libre ALORS
   attendre intervalle DIFS (long),
   SI le canal libre ALORS
      transmettre la trame
      attendre intervalle SIFS (court)
      recevoir ACK
   FIN_SI
FIN_SI

Le cas plus complexe de la contention entre deux stations - il y a de l'activité sur le canal, stations appliquent l'évitement de collision : avant une transmission, elles choisissent un intervalle d'attente aléatoire :

Temps-résiduel = 0
n = 0

Début:
SI le canal est utilisé ALORS
   attendre que le canal devienne libre,
   attendre un intervalle DIFS (long)
   SI le canal libre ALORS
      SI Temps-résiduel  > 0
         attendre Temps-résiduel
	  SINON
         choisir temporisation r dans la fenetre de contention [0, Wmax]
         attendre r slots
         SI on reçoit un signal de transmission ALORS
            on arrête d'attendre, Temps-résiduel = slots restants, go to Début:
	     SINON
            transmettre la trame
            attendre intervalle SIFS (court)
            attendre ACK
            SI pas de ACK ALORS
               Wmax <- 2*Wmax; n++; go to Début:
	       FIN_SI
	 FIN_SI
      FIN_SI
   FIN_SI
FIN_SI

La méthode d'accès CSMA/CA et le surcoût de l'en-tête font que le débit utile est assez faible par rapport au débit nominal : il est égal à environ 60% de 11Mb/s pour 802.11b - 6.5Mb/s mesuré au niveau de la couche application.

Cette technique permet de définir un VLAN à partir des ports de raccordement sur le commutateur. Toutes les machines reliées à ce port appartiendront au VLAN affecté à ce port. L'administrateur du switch configure cette association port/VLAN via la table des VLAN.

La table des VLAN du switch présenté en figure 11 est la suivante :

+-+-+-+-+-+-+-+-+-+-+
|    TABLE VLAN     |
+-+-+-+-+-+-+-+-+-+-+
|   Port  |   VLAN  |
+-+-+-+-+-+-+-+-+-+-+
|   1     |   1     |
|   2     |   2     |
|   3     |   2     |
|   4     |   1     |
|   5     |   1     |
|   6     |   2     |
+-+-+-+-+-+-+-+-+-+-+

Ainsi, une trame envoyée en broadcast par la machine A derrière le port 1 sera reproduite par le switch sur tous les ports appartenant au même VLAN que le port 1 à l'exclusion du port de réception (port 4 et 5).

La principale limite de VLAN de niveau 1 est qu'un port ne peut appartenir à plusieurs VLAN. Ainsi la machine E doit avoir 2 interfaces connectées à 2 ports différents pour appartenir à 2 VLAN différents.

Afin de pallier cette limite et permettre à un port de relayer du trafic en provenance et à destination de différents VLAN, nous allons nous appuyer sur la norme 802.1Q qui permet de taguer les trames.

La figure suivante montre une trame Ethernet portant un tag 802.1Q.

 0                   1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          DST_ADDR             |
|          (6 octets)           |
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          SRC_ADDR             |
|          (6 octets)           |
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|ETHER_TYPE = 0x8100(<--802.1Q) | \
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  \
|      Priority  (3 bits)     	|   | --> 4 octets supplémentaires 
|       CFI (1 bit)             |  / 
|     VLAN ID (12 bits)         | /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    ETHER_TYPE  (2 octets)     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~                               ~
~           payload             ~
~       (46 - 1500 octets)      ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|      CHECKSUM (4 octets)      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Ce marquage peut se faire au niveau de l'interface des machines ou des ports des switches.

Coté switch, les ports doivent être configurés à travers la table des VLAN pour accepter/émettre du trafic tagué des VLAN autorisés sur ce port. Si du trafic non tagué arrive sur le port, il appartient au VLAN indiqué dans la table des VLAN.

La table des VLAN du switch présenté en figure 12 est la suivante :

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           TABLE VLAN            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Port  | (un)tagged  |  VLAN   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   1     | untagged    |  1      |
|   2     | untagged    |  2      |
|   2     | tagged      |  1      |
|   3     | untagged    |  2      |
|   4     | untagged    |  1      |
|   5     | tagged      |  2      |
|   5     | untagged    |  1      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

La table se lit de la manière suivante :

• le port 2 émet et accepte du trafic tagué du VLAN 1.
• le trafic non tagué entrant/sortant du port 2 appartient au VLAN 2

Ainsi une trame non taguée de broadcast émise par la machine D connectée derrière le port 4 sera reproduite sur les tous les ports appartenant au VLAN 1 avec un tag (VLAN 1) sur le port 2 et sans tag sur le port 1 et 5.

Coté machine, nous allons définir une nouvelle notion, celle d'interface virtuelle. À une même interface physique, on peut associer plusieurs interfaces virtuelles qui appartiendront à des VLANs différents.

Ces interfaces se configurent comme des interfaces Ethernet classiques. Ainsi tous les trames empruntant une interface virtuelle se verront automatiquement taguées du VLAN associé à cette interface.

Ansi au niveau de la machine E dispose de 2 interfaces : une interface physique em0 pour traiter les trames non taguées et une interface virtuelle em0.2 pour les trames taguées (VLAN 2).

Quand l'interface em0 reçoit une trame taguée, elle détermine le VLAN d'appartenance, retire le tag et aiguille la trame vers l'interface virtuelle liée à ce VLAN.

Envoyer et attendre (Send and Wait)

L'émetteur envoie un segment de données et attend un accusé de réception (ACK - Accusé de réception - la confirmation d'une bonne réception du segment) avant d'envoyer un nouveau segment de données. Nécessite tampon d'émission d'1 segment et tampon de réception d'1 segment. Faible performance pour un grand produit bande passante-délai.

Fenêtre glissante (Sliding Window)

Pour améliorer les performances, l'expéditeur a la possibilité d'envoyer plusieurs segments (une fenêtre) sans attendre les accusés de réception. Ainsi, l'émetteur peut constamment émettre, si la fenêtre est suffisamment grande.

Retransmission continue (Go-back-N)

Dans le cas d'un segment perdu, l'expéditeur retransmet tous les segments à partir du segment manquant. Nécessite un tampon d'émission de taille \(W\) (\(W\) - la taille de la fenêtre) et un tampon de réception d'1 segment. Peut entraîner un manque de performance en raison de segments retransmis inutilement.

Retransmission sélective (Selective Retransmit)

Dans le cas d'un segment perdu, l'expéditeur retransmet uniquement le segment manquant. Nécessite un tampon d'émission et de réception de taille \(W\). Obtient la meilleure performance, mais le protocole est plus complexe à implémenter.

 0                   1                   2                   3   
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          Source Port          |       Destination Port        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Sequence Number                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Acknowledgment Number                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Data |           |U|A|P|R|S|F|                               |
| Offset| Reserved  |R|C|S|S|Y|I|            Window             |
|       |           |G|K|H|T|N|N|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           Checksum            |         Urgent Pointer        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Options                    |    Padding    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             data                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

L'en-tête d'un segment TCP comporte les champs suivants :

Ports Source et Destination

Les nombres sur 16 bits pour identifier le processus source et le processus de destination.

Numéro de séquence

sur 32 bits, le numéro du premier octet de données dans le segment.

Numéro d'acquittement

sur 32 bits, si le drapeau ACK est positionné, le champ ACK indique le numéro de l'octet attendu dans le prochain segment. Ceci confirme la bonne réception de tous les octets avec les numéros ACK inférieurs.

Data offset

la taille de l'en-tête en mots de 32 bits. L'en-tête peut avoir des champs facultatifs, alors nous avons besoin de l'information sur sa taille.

Drapeaux (Flags)

URG

pointeur urgent valide

ACK

numéro d'acquittement valide

PSH

force TCP à faire partir les données mises en tampon d'émmission

RST

réinitialise la connexion en cas d'anomalies

SYN

initialise une connexion en synchronisant les numéros de séquence

FIN

fin d'envoi de données

Fenêtre Annoncée (Window)

le nombre d'octets que le récepteur peut accepter.

Checksum

le complément à 1 sur 16 bits de la somme de tous les mots de 16 bits du segment TCP avec le pseudo-en-tête ajouté au début. Ce pseudo-en-tête contient l'adresse IP source, l'adresse IP de destination, le protocole, et la longueur du segment TCP.

Pointeur Urgent (Urgent Pointer)

un offset à partir du numéro de séquence qui pointe vers le octet suivant les données urgentes.

Options

MSS (Maximum Segment Size)

la taille de segment proposé pour la connexion (uniquement dans le segment SYN). Le MSS choisi est le minimum des propositions de l'émetteur et de récepteur.

Pendant la phase d'etablissement de connexion, le client et le serveur négocient la taille de segment maximale (MSS) en octets en indiquant chacun leur proposition dans le champ Option (une valeur typique est 1460B ce qui correspond à la taille maximale de la trame Ethernet 1500B, en-têtes IP et TCP inclus).

Après l'établissement de connexion les deux ectrémités peuvent envoyer des segments de données.

Le client ou le serveur peuvent fermer la connexion en envoyant un segment en positionnant le flag FIN à 1. L'extrémité en face confirme la demande avec un ACK et ferme la connexion dans la direction opposée avec un segment FIN et ACK.

Exemple :

• 1er segment SEQ=100, LEN=10
• 2ème segment SEQ=110, LEN=20
• 3ème segment SEQ=130, LEN=10
• ACK pour le 1er segment: ACK=110
• ACK pour le 2e segment: ACK=130
• ACK pour le 3ème segment: ACK=140

Si les deux extrémités ont des données à envoyer dans des directions opposées, les ACK ne sont pas envoyés dans des segments distincts, mais directement dans les segments de données envoyés en retour (piggybacking). Chaque segment contient donc un numéro de séquence SEQ (pour l'envoi de données), ainsi qu'un numéro d'accusé de réception ACK (pour la direction inverse).

Exemple :

• Envoyer segment SEQ=100, ACK=1100, LEN=10
• Recevoir segment SEQ=1100, ACK=110, LEN=50
• Envoyer segment SEQ=110, ACK=1150, LEN=10
• Recevoir segment SEQ=1150, ACK=120, LEN=50

Exemple : lors de la réception d'un segment avec ACK = 1000, WND = 3000, l'expéditeur peut envoyer

• 1er segment SEQ=1000, LEN=1000
• 2ème segment SEQ=2000, LEN=1000
• 3ème segment SEQ=3000, LEN=1000

À la réception d'un segment avec WND=0, l'expéditeur ne peut plus envoyer de segments de données. Si l'expéditeur doit envoyer des données, il sonde le récepteur avec un segment contenant un octet de données après la fin de la fenêtre (après l'expiration de la temporisation Persist Timer).

Retransmission rapide (Fast Retransmit)

si 3 ACK dupliqués (la même valeur du champ ACK) sont reçus avant l'expiration de la temporisation RTO, l'expéditeur retransmet le premier segment non acquitté. La retransmission rapide accélère la récupération de pertes parce que le temps aller-retour necéssaire à la réception des ACK dupliqués est plus court que le RTO.

Lors d'une réception d'un segment de données, un récepteur TCP peut :

• Envoyer un accusé de réception immédiatement,
• Attendre qu'il y ait un segment de données à envoyer (le mécanisme de Delayed ACK), ou
• Attendre jusqu'à ce que les autres segments soient reçus, parce que les accusés de réception sont cumulatifs.

Le récepteur TCP doit immédiatement envoyer un ACK quand il reçoit un segment hors séquence (il y a un gap dans la suite des données reçues). Cet ACK sera un ACK dupliqué - il confirme les données précédemment reçues.

L'attente d'un segment de données à envoyer dans la direction opposée est limitée par la temporisation Delayed ACK (valeur typique de 200 ms) : si elle expire, un segment ACK sans données est envoyé.

Lorsque TCP envoie un segment, il démarre une temporisation. Si le délai expire avant la reception d'un ACK, il retransmet le segment non acquitté (timeout). Comme cette temporisation doit être plus longue que le temps d'aller-retour (RTT), TCP doit mesurer le RTT actuel.

Algorithme d'estimation du RTT.

RTT = 0, D = 3
RTO = RTT + 2 x D = 0 + 2 x 3 = 6 (for initial SYN)

RTT = RTT + g x (measured_RTT - RTT) (g = 1/8)
D = D + h x (|measured_RTT - RTT| - D) (h = 1/4)
RTO = RTT + 4 x D 

If (a segment has been retransmitted after a timeout)
    ; apply exponential backoff
    RTO = min(2 x RTO, 64 sec)
    RTT and D are not updated

Une source TCP doit adapter le débit d'envoi de données à la capacité disponible sur un goulot d'étranglement. Le goulot d'étranglement est le lien sur la route entre la source et la destination sur lequel la connexion TCP obtient la plus petite capacité en compétition par rapport aux autres connexions qui partagent le lien. Une source TCP essaie de se rapprocher de cette capacité disponible sans la dépasser.

TCP utilise l'algorithme AIMD (Additive Increase Multiplicative Decrease) pour le contrôle de congestion :

• Augmenter le débit de façon additive (on ajoute une valeur constante à la fenêtre actuelle), si il n'y a pas de congestion,
• Diminuer le débit de manière multiplicative (on multiplie la fenêtre actuelle par une fraction) en cas de congestion.

TCP interprète des pertes comme le signal d'une congestion (on dépasse la capacité disponible).

Dans les exemples de contrôle de congestion qui suivent, nous supposons que \(rwnd\) est suffisamment grand pour que seul \(cwnd\) limite la fenêtre \(W\).

Du point de vue du contrôle de congestion, TCP a évolué au fil du temps. Plusieurs variantes ont été définies : Tahoe, Reno, New Reno, Vegas (NewReno est la variante la plus utilisée). Les variantes plus récentes incluent : BIC, CUBIC, Compound, et beaucoup d'autres. Tahoe est le variante la plus simple à deux états : Slow Start et Congestion Avoidance. Reno ajoute Fast Recovery.

ssthresh = 64Ko
cwnd = 1 x MSS (valeur initiale dépend de la mise en œuvre et il peut aller
jusqu'à 3 MSS)
augmenter cwnd de 1 MSS pour chaque ACK reçu ce qui se traduit par une
augmentation exponentielle du nombre de segments : 1, 2, 4, 8 MSS etc.

si la perte de segment détectée sur temporisation, appliquer décroissance
   multiplicative : 
   ssthresh = cwnd/2 (mais pas moins de 2MSS)
 re-entrer en Slow Start

 si cwnd >= sshtresh, entrer en Congestion Avoidance

ssthresh correspond au seuil qu'une source TCP tente d'atteindre : TCP sonde le réseau pour obtenir la capacité disponible sur le goulot d'étranglement en augmentant progressivement la fenêtre de congestion jusqu'à :

• une perte, on retourne en Slow Start, ou
• cwnd \(>=\) sshtresh, on passe en Congestion Avoidance.