Thursday, October 25, 2012

Coded TCP va booster les performances de nos réseaux

Lu cela ce matin sur le blog de Korben : Coded TCP va booster les performances de nos réseaux.

Ledit Coded TCP est une évolution du protocole TCP dédiée aux réseaux à perte de paquets, genre Wifi, qui en envoyant les paquets différemment permet d'éviter les erreurs TCP et donc autorise des gains substantiels en débit pour des cas d'usage TCP (web et autres).
Les auteurs, des chercheurs du MIT et de Caltech, annoncent des tests où des débits effectifs de 1 Mbps sont passés à 16 Mbps grâce à Coded TCP.

Comment ça marche ?

Supposons que l'on veuille envoyer une série de n paquets TCP.

L'envoyeur choisit alors r séries de n coefficients (pour r combinaisons linéaires des contenus des n paquets du message entier), avec r >= n.
D'après l'étude statistique empirique des auteurs, un rapport r ~= 1,1 n est une valeur idéale.
L'envoyeur partage avec le destinataire les x n coefficients de ces combinaisons linéaires.

L'envoyeur envoie un par un les r paquets codés avec pour chacun comme contenu la combinaison linéaire correspondante des n paquets originaux.

Le destinataire déduit les n paquets originaux à partir des r paquets codés et de la table des coefficients.

Comme r >= n, on peut deviner les n paquets même s'il en manque. C'est un simple jeu d'équations linéaires à inconnues multiples. (Théoriquement, si les coefficients sont bien choisis, il peut même manquer r - n paquets.)

Remarque : Si on avait r = n, on obtiendrait un résultat équivalent à TCP, avec en plus des kilos de multiplications et d'additions.

Un des intérêts principaux est que l'on peut attendre d'avoir reçu (ou mal reçu) les r paquets avant de se rendre compte, la plupart du temps, que l'on a bien reçu tout le contenu des n paquets. Tandis qu'avec le protocole TCP original, dès qu'un paquet est manquant, le receveur se met en erreur jusqu'à ce que l'envoyeur le lui renvoie, dans l'ordre...

Supposons un fichier de 6ko envoyé par TCP. Il est coupé en quatre paquets 1 2 3 4 de 1,5ko chacun. Si le second paquet est perdu, le destinataire va se mettre en erreur, le temps que l'envoyeur reprenne là où ça s'était arrêté.
  • Côté envoyeur : 1 2 3 4 2 3 4.
  • Côté destinataire. OK1 Timeout2 KO2 KO2 KO2 OK2 OK3 OK4.
  • Le total est de 7 paquets lourds + 8 paquets légers de réponse. Le fichier est transmis en un temps 7 RTT + 1 timeout TCP. Ça, c'est TCP.
 La même chose avec Coded TCP en prenant n = 4 et r = 5 :
  • Côté envoyeur : 1 2 3 4 5.
  • Côté destinataire : OK1 [rien pour 2] OK3 OK4 OK5. Et on recalcule le 2 manquant à partir des quatre autres paquets.
  • Le total est de 5 paquets lourds + 5 paquets légers de réponse. Le fichier est transmis en un temps de 5 RTT + 0 timeout. Ça, c'est Coded TCP.
C'est un exemple volontairement simpliste (avec notamment l'hypothèse simplificatrice comme quoi 1 timeout TCP a une durée égale/voisine d'un RTT sur le réseau considéré) mais les résultats sont meilleurs encore si on choisit n et r supérieurs, comme ce serait le cas dans des situations quotidiennes d'usage d'un Wifi.

Le PDF complet des auteurs de Coded TCP est dispo, en anglais bien sûr.