4. PAWS -- Protection contre le bouclage des numéros de séquence
4.1 Introduction
La section 4.2 décrit un mécanisme simple pour rejeter les anciens segments dupliqués qui pourraient corrompre une connexion TCP ouverte; nous appelons ce mécanisme PAWS (Protect Against Wrapped Sequence numbers, protection contre le bouclage des numéros de séquence). PAWS fonctionne au sein d'une seule connexion TCP, en utilisant un état qui est enregistré dans le bloc de contrôle de connexion. La section 4.3 et l'Annexe C discutent des implications du mécanisme PAWS pour éviter les anciens duplicata des incarnations précédentes de la même connexion.
4.2 Le mécanisme PAWS
PAWS utilise la même option TCP Timestamps que le mécanisme RTTM décrit précédemment, et suppose que chaque segment TCP reçu (y compris les segments de données et ACK) contient un horodatage SEG.TSval dont les valeurs sont monotones non décroissantes dans le temps. L'idée de base est qu'un segment peut être rejeté comme un ancien duplicata s'il est reçu avec un horodatage SEG.TSval inférieur à un certain horodatage récemment reçu sur cette connexion.
Dans les mécanismes PAWS et RTTM, les "horodatages (timestamps)" sont des entiers non signés de 32 bits dans un espace modulaire de 32 bits. Ainsi, "inférieur à (less than)" est défini de la même manière que pour les numéros de séquence TCP, et les mêmes techniques d'implémentation s'appliquent. Si s et t sont des valeurs d'horodatage, s < t si 0 < (t - s) < 2**31, calculé en arithmétique non signée de 32 bits.
Le choix des horodatages entrants à enregistrer pour cette comparaison doit garantir une valeur qui est monotone croissante. Par exemple, nous pourrions enregistrer l'horodatage du segment qui a avancé en dernier le bord gauche de la fenêtre de réception, c'est-à-dire le segment en séquence le plus récent. Au lieu de cela, nous choisissons la valeur TS.Recent introduite dans la Section 3.4 pour le mécanisme RTTM, car l'utilisation d'une valeur commune pour PAWS et RTTM simplifie l'implémentation des deux. Comme la Section 3.4 l'a expliqué, TS.Recent diffère de l'horodatage du dernier segment en séquence uniquement dans le cas des ACKs différés, et donc de moins d'une fenêtre. L'un ou l'autre choix protégera donc contre le bouclage des numéros de séquence.
RTTM a été spécifié de manière symétrique, de sorte que les horodatages TSval sont transportés dans les segments de données et ACK et sont reflétés dans les champs TSecr transportés dans les segments ACK ou de données de retour. PAWS soumet tous les segments entrants au même test, et protège donc contre les segments ACK dupliqués ainsi que les segments de données. (Un algorithme asymétrique alternatif protégerait contre les anciens ACKs dupliqués: l'émetteur de données rejetterait les segments ACK entrants dont les valeurs TSecr étaient inférieures au TSecr enregistré du dernier segment dont le champ ACK a avancé le bord gauche de la fenêtre d'envoi. Cet algorithme a été jugé manquer d'économie de mécanisme et de symétrie.)
Les horodatages TSval envoyés sur les segments {SYN} et {SYN,ACK} sont utilisés pour initialiser PAWS. PAWS protège contre les anciens segments non-SYN dupliqués, et les segments SYN dupliqués reçus alors qu'il existe une connexion synchronisée. Les segments {SYN} et {SYN,ACK} dupliqués reçus lorsqu'il n'y a pas de connexion seront rejetés par la poignée de main à 3 voies normale et les vérifications de numéro de séquence de TCP.
Il est recommandé que les segments RST ne transportent PAS d'horodatages, et que les segments RST soient acceptables quel que soit leur horodatage. Les anciens segments RST dupliqués devraient être extrêmement improbables, et leur fonction de nettoyage devrait avoir la priorité sur les horodatages.
4.2.1 Algorithme PAWS de base
L'algorithme PAWS nécessite que le traitement suivant soit effectué sur tous les segments entrants pour une connexion synchronisée:
S'il existe une option Timestamps dans le segment arrivant et SEG.TSval < TS.Recent et si TS.Recent est valide (voir la discussion ultérieure), alors traiter le segment arrivant comme non acceptable:
Envoyer un accusé de réception en réponse comme spécifié dans RFC-793 page 69 et rejeter le segment.
Note: il est nécessaire d'envoyer un segment ACK afin de conserver les mécanismes de TCP pour détecter et récupérer des connexions semi-ouvertes. Par exemple, voir la Figure 10 de RFC-793.
Si le segment est en dehors de la fenêtre, le rejeter (traitement TCP normal)
Si un segment arrivant satisfait: SEG.SEQ <= Last.ACK.sent (voir Section 3.4), alors enregistrer son horodatage dans TS.Recent.
Si un segment arrivant est en séquence (c'est-à-dire, au bord gauche de la fenêtre), alors l'accepter normalement.
Sinon, traiter le segment comme un segment TCP normal dans la fenêtre, hors séquence (par exemple, le mettre en file d'attente pour une livraison ultérieure à l'utilisateur).
Les étapes R2, R4 et R5 sont les étapes de traitement TCP normales spécifiées par RFC-793.
Il est important de noter que l'horodatage n'est vérifié que lorsqu'un segment arrive pour la première fois au récepteur, qu'il soit en séquence ou qu'il doive être mis en file d'attente pour une livraison ultérieure. Considérez l'exemple suivant.
Supposons que la séquence de segments: A.1, B.1, C.1, ..., Z.1 ait été envoyée, où la lettre indique le numéro de séquence et le chiffre représente l'horodatage. Supposons également que le segment B.1 ait été perdu. L'horodatage dans TS.TStamp est 1 (de A.1), donc C.1, ..., Z.1 sont considérés comme acceptables et sont mis en file d'attente. Lorsque B est retransmis en tant que segment B.2 (utilisant le dernier horodatage), il comble le trou et fait en sorte que tous les segments jusqu'à Z soient accusés de réception et transmis à l'utilisateur. Les horodatages des segments en file d'attente ne sont pas inspectés à nouveau à ce moment, car ils ont déjà été acceptés. Lorsque B.2 est accepté, TS.Stamp est défini sur 2.
Cette règle permet des performances raisonnables en cas de perte. Une fenêtre complète de données est en transit à tout moment, et après une perte, une fenêtre complète moins un paquet apparaîtra hors séquence pour être mise en file d'attente au récepteur (par exemple, jusqu'à ~2**30 octets de données); l'option d'horodatage ne doit pas entraîner le rejet de ces données.
Dans certaines circonstances improbables, l'algorithme des règles R1-R4 pourrait entraîner le rejet inutile de certains segments, comme le montre l'exemple suivant:
Supposons à nouveau que les segments: A.1, B.1, C.1, ..., Z.1 aient été envoyés en séquence et que le segment B.1 ait été perdu. De plus, supposons que la livraison de certains des C.1, ... Z.1 soit retardée jusqu'à APRÈS que la retransmission B.2 arrive au récepteur. Ces segments retardés seront rejetés inutilement lorsqu'ils arriveront, car leurs horodatages sont maintenant obsolètes.
Ce cas est très improbable. Si la retransmission a été déclenchée par un timeout, certains des segments C.1, ... Z.1 doivent avoir été retardés plus longtemps que le temps RTO. C'est probablement un événement improbable, sinon il y aurait de nombreux timeouts parasites et retransmissions. Si la retransmission de B a été déclenchée par l'algorithme de "retransmission rapide (fast retransmit)", c'est-à-dire par des ACKs dupliqués, alors les segments en file d'attente qui ont causé ces ACKs doivent avoir déjà été reçus.
Même si un segment était retardé au-delà du RTO, le mécanisme de retransmission rapide [Jacobson90c] provoquera la retransmission des paquets retardés en même temps que B.2, évitant un RTT supplémentaire et causant donc une très petite pénalité de performance.
Nous ne connaissons aucun cas avec une probabilité d'occurrence significative dans lequel les horodatages causeront une dégradation des performances en rejetant inutilement des segments.
4.2.2 Horloge d'horodatage
Il est important de comprendre que l'algorithme PAWS ne nécessite pas de synchronisation d'horloge entre l'émetteur et le récepteur. L'horloge d'horodatage de l'émetteur est utilisée pour horodater les segments, et l'émetteur utilise l'horodatage reflété pour mesurer les RTT. Cependant, le récepteur traite l'horodatage simplement comme un numéro de série monotone croissant, sans aucune connexion nécessaire à son horloge. Du point de vue du récepteur, l'horodatage agit comme une extension logique des bits de poids fort du numéro de séquence.
L'algorithme du récepteur impose certaines exigences sur la fréquence de l'horloge d'horodatage.
L'horloge d'horodatage ne doit pas être "trop lente".
Elle doit tic-taquer au moins une fois pour chaque 231 octets envoyés. En fait, pour être utile à l'émetteur pour le chronométrage aller-retour, l'horloge devrait tic-taquer au moins une fois par fenêtre de données, et même avec l'extension de fenêtre RFC-1072, 231 octets doivent être au moins deux fenêtres.
Pour rendre cela plus quantitatif, toute horloge plus rapide que 1 tic/sec rejettera les anciens segments dupliqués pour des vitesses de liaison de ~8 Gbps. Une horloge d'horodatage de 1ms fonctionnera à des vitesses de liaison allant jusqu'à 8 Tbps (8*10**12) bps!
L'horloge d'horodatage ne doit pas être "trop rapide".
Son temps de recyclage doit être supérieur à MSL secondes. Étant donné que l'horloge (horodatage) est de 32 bits et que le MSL dans le pire des cas est de 255 secondes, la fréquence d'horloge maximale acceptable est d'un tic toutes les 59 ns.
Cependant, il est souhaitable d'établir une période de recyclage beaucoup plus longue, afin de gérer les horodatages obsolètes sur les connexions inactives (voir Section 4.2.3), et de relâcher l'exigence MSL pour empêcher le bouclage des numéros de séquence. Avec une horloge d'horodatage de 1 ms, l'horodatage de 32 bits bouclera son bit de signe en 24,8 jours. Ainsi, il rejettera les anciens duplicata sur la même connexion si MSL est de 24,8 jours ou moins. Cela semble être un chiffre très sûr; un MSL de 24,8 jours ou plus peut probablement être supposé par le système de passerelle sans nécessiter une application précise du MSL par la valeur TTL dans la couche IP.
Sur la base de ces considérations, nous choisissons une fréquence d'horloge d'horodatage dans la plage de 1 ms à 1 sec par tic. Cette plage correspond également aux exigences du mécanisme RTTM, qui n'a pas besoin de beaucoup plus de résolution que la granularité du temporisateur de retransmission, par exemple, des dizaines ou des centaines de millisecondes.
Le mécanisme PAWS impose également une forte exigence de monotonicité sur l'horloge d'horodatage de l'émetteur. La méthode d'implémentation de l'horloge d'horodatage pour satisfaire cette exigence dépend du matériel et du logiciel du système.
-
Certains hôtes ont une horloge matérielle qui est garantie d'être monotone entre les réinitialisations matérielles.
-
Une interruption d'horloge peut être utilisée pour simplement incrémenter un entier binaire de 1 périodiquement.
-
L'horloge d'horodatage peut être dérivée d'une horloge système qui est susceptible d'être modifiée brusquement, en ajoutant une valeur de décalage variable. Ce décalage est initialisé à zéro. Lorsqu'une nouvelle valeur d'horloge d'horodatage est nécessaire, le décalage peut être ajusté si nécessaire pour rendre la nouvelle valeur égale ou supérieure à la valeur précédente (qui a été enregistrée à cette fin).
4.2.3 Horodatages périmés
Si une connexion reste inactive assez longtemps pour que l'horloge d'horodatage de l'autre TCP boucle son bit de signe, alors la valeur enregistrée dans TS.Recent deviendra trop ancienne; en conséquence, le mécanisme PAWS provoquera le rejet de tous les segments ultérieurs, gelant la connexion (jusqu'à ce que l'horloge d'horodatage boucle à nouveau son bit de signe).
Avec la plage choisie de fréquences d'horloge d'horodatage (1 sec à 1 ms), le temps pour boucler le bit de signe sera entre 24,8 jours et 24800 jours. Une connexion TCP qui est inactive pendant plus de 24 jours puis revient à la vie est extrêmement inhabituelle. Cependant, il est indésirable en principe de placer une quelconque limitation sur les durées de vie des connexions TCP.
Nous exigeons donc qu'une implémentation de PAWS inclue un mécanisme pour "invalider" la valeur TS.Recent lorsqu'une connexion est inactive pendant plus de 24 jours. (Une solution alternative au problème des horodatages obsolètes serait d'envoyer des segments de maintien en vie à un taux très faible, mais toujours plus souvent que le temps de bouclage pour les horodatages, par exemple, une fois par jour. Cela imposerait une surcharge négligeable. Cependant, la spécification TCP n'a jamais inclus les maintiens en vie, donc la solution basée sur l'invalidation a été choisie.)
Notez qu'un TCP ne connaît pas la fréquence, et donc, le temps de bouclage, de l'autre TCP, il doit donc supposer le pire. La validité de TS.Recent ne doit être vérifiée que si la vérification d'horodatage PAWS de base échoue, c'est-à-dire, seulement si SEG.TSval < TS.Recent. Si TS.Recent s'avère invalide, alors le segment est accepté, indépendamment de l'échec de la vérification d'horodatage, et la règle R3 met à jour TS.Recent avec le TSval du nouveau segment.
Pour détecter combien de temps la connexion a été inactive, le TCP peut mettre à jour une horloge ou une valeur d'horodatage associée à la connexion chaque fois que TS.Recent est mis à jour, par exemple. Les détails seront dépendants de l'implémentation.
4.2.4 Prédiction d'en-tête
La "prédiction d'en-tête (Header prediction)" [Jacobson90a] est une technique d'implémentation de protocole de transport à haute performance qui est la plus importante pour les liaisons à haute vitesse. Cette technique optimise le code pour le cas le plus courant, recevoir un segment correctement et dans l'ordre. En utilisant la prédiction d'en-tête, le récepteur pose la question, "Ce segment est-il le suivant dans la séquence?" Cette question peut être répondue en moins d'instructions machine que la question, "Ce segment est-il dans la fenêtre?"
L'ajout de la prédiction d'en-tête à notre procédure d'horodatage conduit à la séquence recommandée suivante pour le traitement d'un segment TCP arrivant:
Vérifier l'horodatage (même que l'étape R1 ci-dessus)
Faire la prédiction d'en-tête: si le segment est le suivant dans la séquence et s'il n'y a pas de conditions spéciales nécessitant un traitement supplémentaire, accepter le segment, enregistrer son horodatage, et sauter H3.
Traiter le segment normalement, comme spécifié dans RFC-793. Cela inclut le rejet des segments qui sont en dehors de la fenêtre et éventuellement l'envoi d'accusés de réception, et la mise en file d'attente des segments dans la fenêtre, hors séquence.
Une autre possibilité serait d'échanger les étapes H1 et H2, c'est-à-dire, d'effectuer l'étape de prédiction d'en-tête H2 EN PREMIER, et d'effectuer H1 et H3 uniquement lorsque la prédiction d'en-tête échoue. Cela pourrait être une amélioration des performances, car la vérification d'horodatage à l'étape H1 est très peu susceptible d'échouer, et elle nécessite une arithmétique d'intervalle sur un champ fini, une opération relativement coûteuse. Effectuer cette vérification sur chaque segment unique est contraire à la philosophie de la prédiction d'en-tête. Nous pensons que ce changement pourrait réduire le temps CPU pour le traitement du protocole TCP jusqu'à 5-10% sur les réseaux à haute vitesse.
Cependant, placer H2 en premier créerait un danger: un segment de 2**32 octets dans le passé pourrait arriver exactement au mauvais moment et être accepté par erreur par l'étape de prédiction d'en-tête. Le raisonnement suivant a été introduit [Jacobson90b] pour montrer que la probabilité de cet échec est négligeable.
Si tous les segments ont la même probabilité d'apparaître comme d'anciens duplicata, alors la probabilité qu'un ancien duplicata corresponde exactement au bord gauche de la fenêtre est la taille maximale du segment (MSS) divisée par la taille de l'espace de séquence. Ce ratio doit être inférieur à 2**-16, puisque MSS doit être < 216; par exemple, il sera (212)/(232) = 2-20 pour un lien FDDI. Cependant, plus un segment est ancien, moins il est susceptible d'être conservé dans l'Internet, et selon tout modèle raisonnable de durée de vie des segments, la probabilité d'un ancien duplicata exactement au bord gauche de la fenêtre doit être beaucoup plus petite que 2**-16.
La somme de contrôle TCP de 16 bits permet également une fiabilité de base d'une partie sur 2**16. Un mécanisme de protocole dont la fiabilité dépasse la fiabilité de la somme de contrôle TCP devrait être considéré comme "suffisamment bon", c'est-à-dire qu'il ne contribuera pas de manière significative au taux d'erreur global. Nous pensons donc que nous pouvons ignorer le problème d'un ancien duplicata accepté en faisant la prédiction d'en-tête avant de vérifier l'horodatage.
Cependant, cet argument probabiliste n'est pas universellement accepté, et le consensus actuel est que le gain de performance ne justifie pas le danger dans le cas général. Il est donc recommandé que H2 suive H1.
4.3 Doublons provenant d'incarnations antérieures de la connexion
Le mécanisme PAWS protège contre les erreurs dues au bouclage des numéros de séquence sur une connexion à haute vitesse. Les segments d'une incarnation antérieure de la même connexion sont également une cause potentielle d'erreurs de duplicata ancien. Dans les deux cas, les mécanismes TCP pour prévenir de telles erreurs dépendent de l'application d'une durée de vie maximale du segment (MSL) par la couche Internet (IP) (voir l'Annexe de RFC-1185 pour une discussion détaillée). Contrairement au cas du bouclage de l'espace de séquence, le MSL requis pour prévenir les erreurs de duplicata ancien des incarnations antérieures ne dépend pas du taux de transfert. Si la couche IP applique le MSL recommandé de 2 minutes de TCP, et si les règles TCP sont suivies, les connexions TCP seront protégées des incarnations antérieures, quelle que soit la vitesse du réseau. Ainsi, le mécanisme PAWS n'est pas requis pour ce cas.
Nous pouvons encore nous demander si le mécanisme PAWS peut fournir une sécurité supplémentaire contre les anciens duplicata des connexions antérieures, nous permettant de relâcher l'application du MSL par la couche IP. L'Annexe B explore cette question, montrant que des hypothèses et/ou des mécanismes supplémentaires sont nécessaires, au-delà de ceux de PAWS. Cela ne fait pas partie de l'extension actuelle.