Quic Timestamps For Measuring One-Way Delays

1.1. Terms and Definitions

The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

2.1. Negotiation

The use of the time_stamp frame extension is negotiated using a transport parameter:¶

• enable_time_stamp (TBD)¶

The enable time stamp transport parameter is included if the endpoint wants to receive or accepts to send time_stamp frames for this connection. This parameter is encoded as a variable integer as specified in section 16 of [I-D.ietf-quic-transport]. It can take one of the following three values:¶

1. I would like to receive TIME_STAMP frames¶
2. I am able to generate TIME_STAMP frames¶
3. I am able to generate TIME_STAMP frames and I would like to receive them¶

Peers receiving another value SHOULD terminate the connection with a TRANSPORT PARAMETER error.¶

A peer that advertises its capability of sending TIME_STAMP frames using option values 2 or 3 MUST NOT send these frames if the other peer does not announce advertise its desire to receive them by sending the enable_time_stamp TP with option 1 or 3. This condition is described as "successful sending negotiation" in Section 2.2.¶

Peers that receive TIME_STAMP frames when they have not advertised their desire to receive them MAY terminate the connection with a PROTOCOL VIOLATION error.¶

As specified in Section 2.2, TIME_STAMP frames MUST NOT be sent in 0-RTT packets. Clients that use 0-RTT MUST NOT reuse a value of the server's enable_time_stamp parameter that they remember from the resumed session.¶

2.2. Sending TIME_STAMP frames

Following successful sending negotiation, a peer SHOULD add a time_stamp frame to 1RTT packets carrying an ACK frame. This specification does not impose a placement of TIME_STAMP frames in the packet. They MAY be sent either before or after the ACK frame.¶

Implementations SHOULD NOT send more than one TIME_STAMP frame per packet, but they MAY send more than one in rare circumstances. When multiple TIME_STAMP frames are present in a packet, the receiver retains the frame indicating the largest timestamp.¶

Implementations MUST NOT send the TIME_STAMP frame in Initial, 0-RTT or Handshake packets, because there is a risk that the peer will receive such packets before the negotiation completes. This restriction may appear excessive because some Handshake packets are typically sent after the negotiation completes, but restricting TIME_STAMP frames to 1RTT packets is simpler and less error prone than allowing the TIME_STAMP frame in just a fraction of Handshake packets.¶

2.3. TIME_STAMP frame format

TIME_STAMP frames are identified by the frame type:¶

• TIME_STAMP (TBD)¶

TIME_STAMP frames carry a single parameter, the time stamp, encoded as a variable length interger. They are formatted as shown in Figure 1, which uses the notational conventions specified in Section 1.3 of [I-D.ietf-quic-transport].¶

   TIME_STAMP Frame {
     Type (i) = TBD,
     Time Stamp (i)
   }

The time stamp encodes the number of microseconds since the beginning of the connection, as measured by the peer at the time at which the packet is sent. It is encoded using the exponent selected by the peer in the ack_delay_exponent. The exponent reduced time stamp is encoded as a variable length integer.¶

The beginning of the connection is defined as follow:¶

• for the client, the time when the first Initial packet is sent;¶
• for the server, the time when the first Initial packet is received.¶

TIME_STAMP frames are not ack-eliciting. Their loss does not require retransmission.¶

2.4. RTT Measurements

RTT measurements are performed as specified in Section 4 of [I-D.ietf-quic-recovery], without reference to the Timestamp parameter of the Timestamped ACK frames.¶

2.5. One-Way Delay Measurements

An endpoint generates a One Way Delay Sample on receiving a packet containing both a TIME_STAMP frame and an ACK frame that meets the following two conditions:¶

• the largest acknowledged packet number is newly acknowledged, and¶
• at least one of the newly acknowledged packets was ack-eliciting.¶

The One Way Delay sample, latest_1wd, is generated as the time elapsed since the largest acknowledged packet was sent, corrected for the 'phase_shift' difference between connection time at the sending peer and connection time at the receiving peer.¶

latest_1wd = time_stamp - send_time_of_largest_acked - phase_shift¶

By convention, the phase_shift is estimated upon reception of the first RTT sample, noted as first_rtt. It is set to:¶

phase_shift = time_stamp - send_time_of_largest_acked - first_rtt. /2¶

In that formula, we assume that the connection times are measured in microseconds since the beginning of the connection.¶

We understand that clocks may drift over time, and that simply estimating a phase shift at the beginning of a connection may be too simplistic for long duration connections. Implementations MAY adopt different strategies to reestimate the phase shift at appropriate intervals. Specifying these strategies is beyond the scope of this document.¶

3.1. Management of Time

There are two known issues with deducing one way delays from RTT measurements: clock drift and undefined phase difference.¶

The phase difference problem is easy to understand. We start from a list of measurements associating the send time of packet number x (s[x]), the receive time of the acknowledgement of packet (a[x]), and the time stamp indicating when packet x was received by the peer (p[x]). The peer's time stamp are expressed in the peer's clock.¶

Suppose that we model the peer's clock as local time plus phase difference f, and that we model the rtt as the sum of two one way delays, up (u[x]) and down (d[x]). We get:¶

    u[x] = p[x] + f - s[x]

    d[x] = a[x] - p[x] - f

Just looking at the equation shows that the value of f cannot be determined from the a series of measurement (s[x], a[x], p[x]). You can just add constraints that all u[x] and d[x] are positive numbers, which gives a range of plausible values for f: max(s[x] - p[x]) < f < min(a[x]-p[x]). In case you wonder, you get similar formulations in a multipath scenario. The plausible range may narrow to the min rtt of the shortest path, but no further.¶

The phase difference uncertainty is not a big issue in practice, because control algorithms are much more interested in the variations of the delays than by their absolute values. Suppose we want to compare one way delays at measurement (x) and (y). We get:¶

    u[x] = p[x] + f - s[x]

    u[y] = p[y] + f - s[y]

    u[x] - u[y] = p[x] - p[y] - s[x] + s[y]

The phase difference does not affect the measurement of variations in the one way delay.¶

The clock drift is another matter. All the equations above assume that the local clock and the remote clock have the same frequency. This is an approximation. Clocks drift over time. Instead of just considering a stable phase difference, one should consider the sum of a phase difference and a time-varying drift component. Estimating drift is a complex problem. This was studied in detail in the development of the Network Time Protocol (NTP) [RFC5905]. In theory, implementations of Quic could copy the algorithms of NTP to build a model of the clocks used by the local node and the peer. That would be very complex.¶

Fortunately, implementations of Quic no not need to implement something as complex as NTP. Most time based algorithms are only interested in variations of delays over a short horizon. Clock drift happens at a slow pace, maybe 1 millisecond per minute. Time base congestion control algorithms already have to cope with the potential drift of the minimum RTT due to changing network conditions. They do that by periodically restarting themeasurement of the minimum RTT after some delay, typically less than a minute. A simple implementation of one way delay measurements could follow the same approach, for example resetting the phase difference every 30 seconds or so.¶