RTT Estimation at the CCID3 Receiver

This document describes the working principle of the RTT estimation algorithm and its limitations. The algorithm is based on ideas presented in (RFC 4342, 8.1) and uses a combination of timestamps and window counter CCVal comparisons to estimate the RTT.

1. Naming conventions

• dist(A, B) sequence number distance, dist(A, B) = (B + 2^48 - A) % 2^48

• nonloss packet with highest received sequence number so far
• nonloss.S sequence number of history entry nonloss
• nonloss.V CCVal of history entry nonloss

loss indication:

reception of a packet with a sequence number S and NDP count N such that D = dist(nonloss.S, S) > N + 1

pending loss:

holds if previously a loss indication occurred

loss event:

a pending loss event such that NDUPACK=3 packets were received with a sequence number higher than nonloss.S at the instant of the loss indication ((RFC 3448, 5.1), (RFC 4342, 6.1)).

2. Purpose of RTT estimation

3. RTT estimation in relation to loss detection

The receiver detects the first loss by receiving a packet with sequence number S and NDP count N such that dist(nonloss.S, S) > N + 1. This is called loss indication above. It is not the same as a loss event, since the missing packet(s) may still arrive due to e.g. re-ordering in the network.

However, as soon as there are holes in the sequence numbers, the receiver can no longer rely on their window counter values to estimate the RTT, since more than 1 RTT may have passed between sending the packets, or the CCVal counter may have wrapped around in the meantime. Therefore, the receiver does not sample RTT values once a loss indication occurred, i.e. while a loss event is pending. Should the sequence number hole later be filled by receiving the missing (reordered) packet(s), the receiver will resume sampling RTT values until the next loss indication occurs. If however a loss was detected, no further RTT sampling will be performed.

4. Implications for data history structures

With regard to data setup, this entails the following for the algorithm:

• clearing the RTT sampling data structure at the instant a loss indication occurs;
• re-enabling RTT sampling by appropriately initialising the same data structures; when a pending loss clears due to the arrival of until-then missing packets.

5. Limitations of the algorithm

If there were not sufficiently many RTT samples at the time of detecting the first loss event, the algorithm falls back on a static, predefined RTT value and complains with a warning that it has been unable to sample the RTT from packets received so far. There is nothing more that the algorithm can do in this case, since the absence of suitable RTT information is due to protocol design (RFC 3448/4342), but not implementation decisions.

Work is underway to develop an alternative which would allow the receiver to always track the RTT (and in particular until the first loss occurs); this will be communicated elsewhere.

6. Algorithm details

 (1) last = hist[0] is always used as the point of reference against which either
     the current packet or a previously suitable candidate packet (see below) is
     evaluated with regard to the difference of CCVal values;

 (2) hist[1] is used as dummy entry when the difference between current and last
     CCVal is 0, and when no previous candidate packet has been recorded;

 (3) prev = hist[2] is used to store a suitable candidate which is such that its CCVal
     difference D to the last = hist[0] packet is in the range 1..3 (and thus sub-optimal).

All three cases are controlled by a single variable, prev_sample, which is initialised to 0. The variable, an alias for loss_start, is also used in determining where the current packet's details are to be stored (for the purpose of tracking the highest received sequence number). The details of the current packet are always stored in the entry

    last_rcv  =  hist[(loss_start + loss_count) & NDUPACK]

which, since loss_count = 0 during RTT sampling and since prev_sample < 3, simplifies to

    last_rcv  =  hist[prev_sample]  =  hist[loss_start]

Hence setting prev_sample to a non-0 value avoids overwriting the last entry (hist[0]) with the details of the current packet. Furthermore, a prev_sample of 2 indicates that a previously suitable candidate entry has been recorded for possible later use.

The same trick is exploited when the loss record is initialised during loss detection:

  loss_start = 0 = prev_sample
  loss_count = 1
  loss_prev  = hist[loss_start]
  last_rcv   = hist[loss_count]

Here loss_prev records the highest received sequence number before the loss was detected, stored in hist[0]. The first packet after the hole is last_rcv = hist[1]. Since furthermore loss_count is now 1, RTT sampling is disabled (it is only based as long as loss_count is 0, cf. flowchart).

Finally there is one last subtlety: if the receiver first receives a packet with a CCVal difference to last = hist[0] of 0 and the next arriving packet has a CCVal difference to last of more than 4, the prev_sample flag needs to be cleared. Otherwise subsequent entries will refer to the outdated/stale last entry. In the flowchart this happens after receiving a packet with a CCVal distance > 4, where the prev_sample is reset to 0.

7. Illustration of how the RTT estimation works

Now assume that the next arriving packet has a CCVal difference to last = hist[0] of 2. Then prev_sample will be set to 2, and the details of that packet will be stored in hist[2]. Finally, if the next arriving packet exhibits a CCVal difference to last = hist[0] of 4, an optimal candidate for RTT sampling was found, and prev_sample is re-set to 0, after computing the sample.

Otherwise, if the next arriving packet has a CCVal difference to last of 0 or greater than 4, then the previous entry, prev = hist[prev_sample] = hist[2], is used for computing the RTT sample, after which in turn prev_sample is re-set to 0.