3. RTTM -- Round-Trip Time Measurement (RTTM -- Mesure du temps aller-retour)
3. RTTM: Round-Trip Time Measurement (RTTM: Mesure du temps aller-retour)
3.1 Introduction
Accurate and current RTT estimates are necessary to adapt to changing traffic conditions and to avoid an instability known as "congestion collapse" [Nagle84] in a busy network. However, accurate measurement of RTT may be difficult both in theory and in implementation.
Des estimations précises et actuelles du RTT sont nécessaires pour s'adapter aux conditions de trafic changeantes et pour éviter une instabilité connue sous le nom d'"effondrement de congestion (congestion collapse)" [Nagle84] dans un réseau chargé. Cependant, la mesure précise du RTT peut être difficile tant en théorie qu'en implémentation.
Many TCP implementations base their RTT measurements upon a sample of only one packet per window. While this yields an adequate approximation to the RTT for small windows, it results in an unacceptably poor RTT estimate for an LFN. If we look at RTT estimation as a signal processing problem (which it is), a data signal at some frequency, the packet rate, is being sampled at a lower frequency, the window rate. This lower sampling frequency violates Nyquist's criteria and may therefore introduce "aliasing" artifacts into the estimated RTT [Hamming77].
De nombreuses implémentations TCP basent leurs mesures RTT sur un échantillon d'un seul paquet par fenêtre. Bien que cela produise une approximation adéquate du RTT pour les petites fenêtres, cela entraîne une estimation RTT inacceptablement mauvaise pour un LFN. Si nous considérons l'estimation du RTT comme un problème de traitement du signal (ce qu'elle est), un signal de données à une certaine fréquence, le taux de paquets, est échantillonné à une fréquence inférieure, le taux de fenêtre. Cette fréquence d'échantillonnage inférieure viole les critères de Nyquist et peut donc introduire des artefacts d'"aliasing (repliement de spectre)" dans le RTT estimé [Hamming77].
A good RTT estimator with a conservative retransmission timeout calculation can tolerate aliasing when the sampling frequency is "close" to the data frequency. For example, with a window of 8 packets, the sample rate is 1/8 the data frequency -- less than an order of magnitude different. However, when the window is tens or hundreds of packets, the RTT estimator may be seriously in error, resulting in spurious retransmissions.
Un bon estimateur RTT avec un calcul de timeout de retransmission conservateur peut tolérer l'aliasing lorsque la fréquence d'échantillonnage est "proche" de la fréquence des données. Par exemple, avec une fenêtre de 8 paquets, le taux d'échantillonnage est 1/8 de la fréquence des données -- moins d'un ordre de grandeur de différence. Cependant, lorsque la fenêtre compte des dizaines ou des centaines de paquets, l'estimateur RTT peut être gravement erroné, entraînant des retransmissions parasites.
If there are dropped packets, the problem becomes worse. Zhang [Zhang86], Jain [Jain86] and Karn [Karn87] have shown that it is not possible to accumulate reliable RTT estimates if retransmitted segments are included in the estimate. Since a full window of data will have been transmitted prior to a retransmission, all of the segments in that window will have to be ACKed before the next RTT sample can be taken. This means at least an additional window's worth of time between RTT measurements and, as the error rate approaches one per window of data (e.g., 10**-6 errors per bit for the Wideband satellite network), it becomes effectively impossible to obtain a valid RTT measurement.
Si des paquets sont perdus, le problème s'aggrave. Zhang [Zhang86], Jain [Jain86] et Karn [Karn87] ont montré qu'il n'est pas possible d'accumuler des estimations RTT fiables si les segments retransmis sont inclus dans l'estimation. Étant donné qu'une fenêtre complète de données aura été transmise avant une retransmission, tous les segments de cette fenêtre devront être acquittés avant que le prochain échantillon RTT puisse être pris. Cela signifie au moins un temps supplémentaire équivalent à une fenêtre entre les mesures RTT et, à mesure que le taux d'erreur approche un par fenêtre de données (par exemple, 10**-6 erreurs par bit pour le réseau satellite à large bande), il devient effectivement impossible d'obtenir une mesure RTT valide.
A solution to these problems, which actually simplifies the sender substantially, is as follows: using TCP options, the sender places a timestamp in each data segment, and the receiver reflects these timestamps back in ACK segments. Then a single subtract gives the sender an accurate RTT measurement for every ACK segment (which will correspond to every other data segment, with a sensible receiver). We call this the RTTM (Round-Trip Time Measurement) mechanism.
Une solution à ces problèmes, qui simplifie réellement considérablement l'émetteur, est la suivante: en utilisant les options TCP, l'émetteur place un horodatage dans chaque segment de données, et le récepteur reflète ces horodatages dans les segments ACK. Ensuite, une simple soustraction donne à l'émetteur une mesure RTT précise pour chaque segment ACK (qui correspondra à un segment de données sur deux, avec un récepteur raisonnable). Nous appelons cela le mécanisme RTTM (Round-Trip Time Measurement, mesure du temps aller-retour).
It is vitally important to use the RTTM mechanism with big windows; otherwise, the door is opened to some dangerous instabilities due to aliasing. Furthermore, the option is probably useful for all TCP's, since it simplifies the sender.
Il est extrêmement important d'utiliser le mécanisme RTTM avec de grandes fenêtres; sinon, la porte est ouverte à certaines instabilités dangereuses dues à l'aliasing. De plus, l'option est probablement utile pour tous les TCP, car elle simplifie l'émetteur.
3.2 TCP Timestamps Option (Option TCP Timestamps)
TCP is a symmetric protocol, allowing data to be sent at any time in either direction, and therefore timestamp echoing may occur in either direction. For simplicity and symmetry, we specify that timestamps always be sent and echoed in both directions. For efficiency, we combine the timestamp and timestamp reply fields into a single TCP Timestamps Option.
TCP est un protocole symétrique, permettant l'envoi de données à tout moment dans l'une ou l'autre direction, et par conséquent l'écho d'horodatage peut se produire dans l'une ou l'autre direction. Pour la simplicité et la symétrie, nous spécifions que les horodatages soient toujours envoyés et reflétés dans les deux directions. Pour l'efficacité, nous combinons les champs d'horodatage et de réponse d'horodatage en une seule option TCP Timestamps.
TCP Timestamps Option (TSopt):
Kind: 8
Length: 10 bytes
+-------+-------+---------------------+---------------------+
|Kind=8 | 10 | TS Value (TSval) |TS Echo Reply (TSecr)|
+-------+-------+---------------------+---------------------+
1 1 4 4
The Timestamps option carries two four-byte timestamp fields. The Timestamp Value field (TSval) contains the current value of the timestamp clock of the TCP sending the option.
L'option Timestamps contient deux champs d'horodatage de quatre octets. Le champ Timestamp Value (TSval) contient la valeur actuelle de l'horloge d'horodatage du TCP envoyant l'option.
The Timestamp Echo Reply field (TSecr) is only valid if the ACK bit is set in the TCP header; if it is valid, it echos a timestamp value that was sent by the remote TCP in the TSval field of a Timestamps option. When TSecr is not valid, its value must be zero. The TSecr value will generally be from the most recent Timestamp option that was received; however, there are exceptions that are explained below.
Le champ Timestamp Echo Reply (TSecr) n'est valide que si le bit ACK est défini dans l'en-tête TCP; s'il est valide, il reflète une valeur d'horodatage qui a été envoyée par le TCP distant dans le champ TSval d'une option Timestamps. Lorsque TSecr n'est pas valide, sa valeur doit être zéro. La valeur TSecr proviendra généralement de l'option Timestamp la plus récente qui a été reçue; cependant, il existe des exceptions qui sont expliquées ci-dessous.
A TCP may send the Timestamps option (TSopt) in an initial <SYN> segment (i.e., segment containing a SYN bit and no ACK bit), and may send a TSopt in other segments only if it received a TSopt in the initial <SYN> segment for the connection.
Un TCP peut envoyer l'option Timestamps (TSopt) dans un segment <SYN> initial (c'est-à-dire un segment contenant un bit SYN et aucun bit ACK), et ne peut envoyer une TSopt dans d'autres segments que s'il a reçu une TSopt dans le segment <SYN> initial de la connexion.
3.3 The RTTM Mechanism (Le mécanisme RTTM)
The timestamp value to be sent in TSval is to be obtained from a (virtual) clock that we call the "timestamp clock". Its values must be at least approximately proportional to real time, in order to measure actual RTT.
La valeur d'horodatage à envoyer dans TSval doit être obtenue à partir d'une horloge (virtuelle) que nous appelons "l'horloge d'horodatage (timestamp clock)". Ses valeurs doivent être au moins approximativement proportionnelles au temps réel, afin de mesurer le RTT réel.
The following example illustrates a one-way data flow with segments arriving in sequence without loss. Here A, B, C... represent data blocks occupying successive blocks of sequence numbers, and ACK(A),... represent the corresponding cumulative acknowledgments. The two timestamp fields of the Timestamps option are shown symbolically as <TSval= x,TSecr=y>. Each TSecr field contains the value most recently received in a TSval field.
L'exemple suivant illustre un flux de données unidirectionnel avec des segments arrivant en séquence sans perte. Ici A, B, C... représentent des blocs de données occupant des blocs successifs de numéros de séquence, et ACK(A),... représentent les accusés de réception cumulatifs correspondants. Les deux champs d'horodatage de l'option Timestamps sont représentés symboliquement par <TSval= x,TSecr=y>. Chaque champ TSecr contient la valeur la plus récemment reçue dans un champ TSval.
TCP A TCP B
<A,TSval=1,TSecr=120> ------>
<---- <ACK(A),TSval=127,TSecr=1>
<B,TSval=5,TSecr=127> ------>
<---- <ACK(B),TSval=131,TSecr=5>
. . . . . . . . . . . . . . . . . . . . . .
<C,TSval=65,TSecr=131> ------>
<---- <ACK(C),TSval=191,TSecr=65>
(etc)
The dotted line marks a pause (60 time units long) in which A had nothing to send. Note that this pause inflates the RTT which B could infer from receiving TSecr=131 in data segment C. Thus, in one-way data flows, RTTM in the reverse direction measures a value that is inflated by gaps in sending data. However, the following rule prevents a resulting inflation of the measured RTT:
La ligne pointillée marque une pause (de 60 unités de temps) pendant laquelle A n'avait rien à envoyer. Notez que cette pause gonfle le RTT que B pourrait déduire de la réception de TSecr=131 dans le segment de données C. Ainsi, dans les flux de données unidirectionnels, le RTTM dans la direction inverse mesure une valeur qui est gonflée par les lacunes dans l'envoi de données. Cependant, la règle suivante empêche un gonflement résultant du RTT mesuré:
A TSecr value received in a segment is used to update the averaged RTT measurement only if the segment acknowledges some new data, i.e., only if it advances the left edge of the send window.
Une valeur TSecr reçue dans un segment est utilisée pour mettre à jour la mesure RTT moyenne uniquement si le segment accuse réception de nouvelles données, c'est-à-dire uniquement s'il avance le bord gauche de la fenêtre d'envoi.
Since TCP B is not sending data, the data segment C does not acknowledge any new data when it arrives at B. Thus, the inflated RTTM measurement is not used to update B's RTTM measurement.
Étant donné que TCP B n'envoie pas de données, le segment de données C n'accuse réception d'aucune nouvelle donnée lorsqu'il arrive à B. Ainsi, la mesure RTTM gonflée n'est pas utilisée pour mettre à jour la mesure RTTM de B.
3.4 Which Timestamp to Echo (Quel horodatage refléter)
If more than one Timestamps option is received before a reply segment is sent, the TCP must choose only one of the TSvals to echo, ignoring the others. To minimize the state kept in the receiver (i.e., the number of unprocessed TSvals), the receiver should be required to retain at most one timestamp in the connection control block.
Si plusieurs options Timestamps sont reçues avant l'envoi d'un segment de réponse, le TCP ne doit choisir qu'une seule des TSvals à refléter, en ignorant les autres. Pour minimiser l'état conservé dans le récepteur (c'est-à-dire le nombre de TSvals non traitées), le récepteur devrait être tenu de conserver au plus un horodatage dans le bloc de contrôle de connexion.
There are three situations to consider:
Il y a trois situations à considérer:
(A) Delayed ACKs. (ACKs différés)
Many TCP's acknowledge only every Kth segment out of a group of segments arriving within a short time interval; this policy is known generally as "delayed ACKs". The data-sender TCP must measure the effective RTT, including the additional time due to delayed ACKs, or else it will retransmit unnecessarily. Thus, when delayed ACKs are in use, the receiver should reply with the TSval field from the earliest unacknowledged segment.
De nombreux TCP n'acquittent que chaque Kième segment d'un groupe de segments arrivant dans un court intervalle de temps; cette politique est généralement connue sous le nom d'"ACKs différés (delayed ACKs)". Le TCP émetteur de données doit mesurer le RTT effectif, y compris le temps supplémentaire dû aux ACKs différés, sinon il retransmettra inutilement. Ainsi, lorsque les ACKs différés sont utilisés, le récepteur devrait répondre avec le champ TSval du segment non acquitté le plus ancien.
(B) A hole in the sequence space (segment(s) have been lost). (Un trou dans l'espace de séquence (des segments ont été perdus))
The sender will continue sending until the window is filled, and the receiver may be generating ACKs as these out-of-order segments arrive (e.g., to aid "fast retransmit").
L'émetteur continuera à envoyer jusqu'à ce que la fenêtre soit remplie, et le récepteur peut générer des ACKs lorsque ces segments désordonnés arrivent (par exemple, pour aider la "retransmission rapide (fast retransmit)").
The lost segment is probably a sign of congestion, and in that situation the sender should be conservative about retransmission. Furthermore, it is better to overestimate than underestimate the RTT. An ACK for an out-of-order segment should therefore contain the timestamp from the most recent segment that advanced the window.
Le segment perdu est probablement un signe de congestion, et dans cette situation l'émetteur devrait être prudent concernant la retransmission. De plus, il vaut mieux surestimer que sous-estimer le RTT. Un ACK pour un segment désordonné devrait donc contenir l'horodatage du segment le plus récent qui a avancé la fenêtre.
The same situation occurs if segments are re-ordered by the network.
La même situation se produit si les segments sont réordonnés par le réseau.
(C) A filled hole in the sequence space. (Un trou rempli dans l'espace de séquence)
The segment that fills the hole represents the most recent measurement of the network characteristics. On the other hand, an RTT computed from an earlier segment would probably include the sender's retransmit time-out, badly biasing the sender's average RTT estimate. Thus, the timestamp from the latest segment (which filled the hole) must be echoed.
Le segment qui remplit le trou représente la mesure la plus récente des caractéristiques du réseau. D'autre part, un RTT calculé à partir d'un segment antérieur inclurait probablement le timeout de retransmission de l'émetteur, biaisant gravement l'estimation RTT moyenne de l'émetteur. Ainsi, l'horodatage du dernier segment (qui a rempli le trou) doit être reflété.
An algorithm that covers all three cases is described in the following rules for Timestamps option processing on a synchronized connection:
Un algorithme qui couvre les trois cas est décrit dans les règles suivantes pour le traitement de l'option Timestamps sur une connexion synchronisée:
(1) The connection state is augmented with two 32-bit slots: TS.Recent holds a timestamp to be echoed in TSecr whenever a segment is sent, and Last.ACK.sent holds the ACK field from the last segment sent. Last.ACK.sent will equal RCV.NXT except when ACKs have been delayed.
L'état de connexion est augmenté de deux emplacements de 32 bits: TS.Recent contient un horodatage à refléter dans TSecr chaque fois qu'un segment est envoyé, et Last.ACK.sent contient le champ ACK du dernier segment envoyé. Last.ACK.sent sera égal à RCV.NXT sauf lorsque les ACKs ont été différés.
(2) If Last.ACK.sent falls within the range of sequence numbers of an incoming segment:
Si Last.ACK.sent se situe dans la plage des numéros de séquence d'un segment entrant:
SEG.SEQ <= Last.ACK.sent < SEG.SEQ + SEG.LEN
then the TSval from the segment is copied to TS.Recent; otherwise, the TSval is ignored.
alors le TSval du segment est copié dans TS.Recent; sinon, le TSval est ignoré.
(3) When a TSopt is sent, its TSecr field is set to the current TS.Recent value.
Lorsqu'une TSopt est envoyée, son champ TSecr est défini sur la valeur TS.Recent actuelle.
The following examples illustrate these rules. Here A, B, C... represent data segments occupying successive blocks of sequence numbers, and ACK(A),... represent the corresponding acknowledgment segments. Note that ACK(A) has the same sequence number as B. We show only one direction of timestamp echoing, for clarity.
Les exemples suivants illustrent ces règles. Ici A, B, C... représentent des segments de données occupant des blocs successifs de numéros de séquence, et ACK(A),... représentent les segments d'acquittement correspondants. Notez que ACK(A) a le même numéro de séquence que B. Nous ne montrons qu'une direction de réflexion d'horodatage, pour plus de clarté.
o Packets arrive in sequence, and some of the ACKs are delayed.
Les paquets arrivent en séquence, et certains des ACKs sont différés.
By Case (A), the timestamp from the oldest unacknowledged segment is echoed.
Selon le cas (A), l'horodatage du segment non acquitté le plus ancien est reflété.
TS.Recent
<A, TSval=1> ------------------->
1
<B, TSval=2> ------------------->
1
<C, TSval=3> ------------------->
1
<---- <ACK(C), TSecr=1>
(etc)
o Packets arrive out of order, and every packet is acknowledged.
Les paquets arrivent dans le désordre, et chaque paquet est acquitté.
By Case (B), the timestamp from the last segment that advanced the left window edge is echoed, until the missing segment arrives; it is echoed according to Case (C). The same sequence would occur if segments B and D were lost and retransmitted.
Selon le cas (B), l'horodatage du dernier segment qui a avancé le bord gauche de la fenêtre est reflété, jusqu'à ce que le segment manquant arrive; il est reflété selon le cas (C). La même séquence se produirait si les segments B et D étaient perdus et retransmis.
TS.Recent
<A, TSval=1> ------------------->
1
<---- <ACK(A), TSecr=1>
1
<C, TSval=3> ------------------->
1
<---- <ACK(A), TSecr=1>
1
<B, TSval=2> ------------------->
2
<---- <ACK(C), TSecr=2>
2
<E, TSval=5> ------------------->
2
<---- <ACK(C), TSecr=2>
2
<D, TSval=4> ------------------->
4
<---- <ACK(E), TSecr=4>
(etc)