Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 5348

TCP Friendly Rate Control (TFRC): Protocol Specification

Pages: 58
Proposed Standard
Errata
Obsoletes:  3448
Updates:  4342
Part 2 of 3 – Pages 19 to 39
First   Prev   Next

Top   ToC   RFC5348 - Page 19   prevText

5. Calculation of the Loss Event Rate (p)

Obtaining an accurate and stable measurement of the loss event rate is of primary importance for TFRC. Loss rate measurement is performed at the receiver, based on the detection of lost or marked packets from the sequence numbers of arriving packets. We describe this process before describing the rest of the receiver protocol. If the receiver has not yet detected a lost or marked packet, then the receiver does not calculate the loss event rate, but reports a loss event rate of zero.

5.1. Detection of Lost or Marked Packets

TFRC assumes that all packets contain a sequence number that is incremented by one for each packet that is sent. For the purposes of this specification, it is REQUIRED that if a lost packet is retransmitted, the retransmission is given a new sequence number that is the latest in the transmission sequence, and not the same sequence number as the packet that was lost. If a transport protocol has the requirement that it must retransmit with the original sequence number, then the transport protocol designer must figure out how to distinguish delayed from retransmitted packets and how to detect lost retransmissions.
Top   ToC   RFC5348 - Page 20
   The receiver maintains a data structure that keeps track of which
   packets have arrived and which are missing.  For the purposes of this
   specification, we assume that the data structure consists of a list
   of packets that have arrived along with the receiver timestamp when
   each packet was received.  In practice, this data structure will
   normally be stored in a more compact representation, but this is
   implementation-specific.

   The loss of a packet is detected by the arrival of at least NDUPACK
   packets with a higher sequence number than the lost packet, for
   NDUPACK set to 3.  The requirement for NDUPACK subsequent packets is
   the same as with TCP, and is to make TFRC more robust in the presence
   of reordering.  In contrast to TCP, if a packet arrives late (after
   NDUPACK subsequent packets arrived) in TFRC, the late packet can fill
   the hole in TFRC's reception record, and the receiver can recalculate
   the loss event rate.  Future versions of TFRC might make the
   requirement for NDUPACK subsequent packets adaptive based on
   experienced packet reordering, but such a mechanism is not part of
   the current specification.

   For an ECN-capable connection, a marked packet is detected as a
   congestion event as soon as it arrives, without having to wait for
   the arrival of subsequent packets.

   If an ECN-marked packet is preceded by a possibly-lost packet, then
   the first detected congestion event begins with the lost packet.  For
   example, if the receiver receives a data packet with sequence number
   n-1, followed by an unmarked data packet with sequence number n+1,
   and a marked data packet with sequence number n+2, then the receiver
   detects a congestion event when it receives the marked packet n+2.
   The first congestion event detected begins with the lost packet n.
   The guidelines in Section 5.2 below are used to determine whether the
   lost and marked packets belong to the same loss event or to separate
   loss events.

5.2. Translation from Loss History to Loss Events

TFRC requires that the loss fraction be robust to several consecutive packets lost or marked in the same loss event. This is similar to TCP, which (typically) only performs one halving of the congestion window during any single RTT. Thus, the receiver needs to map the packet loss history into a loss event record, where a loss event is one or more packets lost or marked in an RTT. To perform this mapping, the receiver needs to know the RTT to use, and this is supplied periodically by the sender, typically as control information
Top   ToC   RFC5348 - Page 21
   piggy-backed onto a data packet.  TFRC is not sensitive to how the
   RTT measurement sent to the receiver is made, but it is RECOMMENDED
   to use the sender's calculated RTT, R, (see Section 4.3) for this
   purpose.

   To determine whether a lost or marked packet should start a new loss
   event or be counted as part of an existing loss event, we need to
   compare the sequence numbers and timestamps of the packets that
   arrived at the receiver.  For a marked packet, S_new, its reception
   time, T_new, can be noted directly.  For a lost packet, we can
   interpolate to infer the nominal "arrival time".  Assume:

      S_loss is the sequence number of a lost packet.

      S_before is the sequence number of the last packet to arrive,
      before any packet arrivals with a sequence number above S_loss,
      with a sequence number below S_loss.

      S_after is the sequence number of the first packet to arrive after
      S_before with a sequence number above S_loss.

      S_max is the largest sequence number.

   Therefore, S_before < S_loss < S_after <= S_max.

      T_loss is the nominal estimated arrival time for the lost packet.

      T_before is the reception time of S_before.

      T_after is the reception time of S_after.

   Note that T_before < T_after.

   For a lost packet, S_loss, we can interpolate its nominal "arrival
   time" at the receiver from the arrival times of S_before and S_after.
   Thus:

      T_loss = T_before + ( (T_after - T_before)
                  * (S_loss - S_before)/(S_after - S_before) );

   To address sequence number wrapping, let S_MAX = 2^b, where b is the
   bit-length of sequence numbers in a given implementation.  In this
   case, we can interpolate the arrival time T_loss as follows:
Top   ToC   RFC5348 - Page 22
      T_loss = T_before +  (T_after - T_before)
                  * Dist(S_loss, S_before)/Dist(S_after, S_before)

   where

      Dist(S_A, S_B) = (S_A + S_MAX - S_B) % S_MAX

   If the lost packet S_old was determined to have started the previous
   loss event, and we have just determined that S_new has been lost,
   then we interpolate the nominal arrival times of S_old and S_new,
   called T_old and T_new, respectively.

   If T_old + R >= T_new, then S_new is part of the existing loss event.
   Otherwise, S_new is the first packet in a new loss event.

5.3. The Size of a Loss Interval

After the detection of the first loss event, the receiver divides the sequence space into loss intervals. If a loss interval, A, is determined to have started with packet sequence number S_A and the next loss interval, B, started with packet sequence number S_B, then the number of packets in loss interval A is given by (S_B - S_A). Thus, loss interval A contains all of the packets transmitted by the sender starting with the first packet transmitted in loss interval A and ending with but not including the first packet transmitted in loss interval B. The current loss interval I_0 is defined as the loss interval containing the most recent loss event. If that loss event started with packet sequence number S_A, and S_C is the highest received sequence number so far, then the size of I_0 is S_C - S_A + 1. As an example, if the current loss interval consists of a single ECN- marked packet, then S_A == S_C, and the size of the loss interval is one.

5.4. Average Loss Interval

To calculate the loss event rate, p, we first calculate the average loss interval. This is done using a filter that weights the n most recent loss event intervals in such a way that the measured loss event rate changes smoothly. If the receiver has not yet seen a lost or marked packet, then the receiver does not calculate the average loss interval.
Top   ToC   RFC5348 - Page 23
   Weights w_0 to w_(n-1) are calculated as:

        If (i < n/2) {
            w_i = 1;
        } Else {
            w_i = 2 * (n-i)/(n+2);
        }

   Thus, if n=8, the values of w_0 to w_7 are:

      1.0, 1.0, 1.0, 1.0, 0.8, 0.6, 0.4, 0.2

   The value n for the number of loss intervals used in calculating the
   loss event rate determines TFRC's speed in responding to changes in
   the level of congestion.  It is RECOMMENDED to set the value n to 8.
   TFRC SHOULD NOT use values of n greater than 8 for traffic that might
   compete in the global Internet with TCP.  At the very least, safe
   operation with values of n greater than 8 would require a slight
   change to TFRC's mechanisms to include a more severe response to two
   or more round-trip times with heavy packet loss.

   When calculating the average loss interval, we need to decide whether
   to include the current loss interval.  We only include the current
   loss interval if it is sufficiently large to increase the average
   loss interval.

   Let the most recent loss intervals be I_0 to I_k, where I_0 is the
   current loss interval.  If there have been at least n loss intervals,
   then k is set to n; otherwise, k is the maximum number of loss
   intervals seen so far.  We calculate the average loss interval I_mean
   as follows:

      I_tot0 = 0;
      I_tot1 = 0;
      W_tot = 0;
      for (i = 0 to k-1) {
          I_tot0 = I_tot0 + (I_i * w_i);
          W_tot = W_tot + w_i;
      }
      for (i = 1 to k) {
          I_tot1 = I_tot1 + (I_i * w_(i-1));
      }
      I_tot = max(I_tot0, I_tot1);
      I_mean = I_tot/W_tot;

   The loss event rate, p is simply:

      p = 1 / I_mean;
Top   ToC   RFC5348 - Page 24

5.5. History Discounting

As described in Section 5.4, when there have been at least n loss intervals, the most recent loss interval is only assigned 1/(0.75*n) of the total weight in calculating the average loss interval, regardless of the size of the most recent loss interval. This section describes an OPTIONAL history discounting mechanism, discussed further in [FHPW00a] and [W00], that allows the TFRC receiver to adjust the weights, concentrating more of the relative weight on the most recent loss interval, when the most recent loss interval is more than twice as large as the computed average loss interval. To carry out history discounting, we associate a discount factor, DF_i, with each loss interval, L_i, for i > 0, where each discount factor is a floating point number. The discount array maintains the cumulative history of discounting for each loss interval. At the beginning, the values of DF_i in the discount array are initialized to 1: for (i = 0 to n) { DF_i = 1; } History discounting also uses a general discount factor, DF, also a floating point number, that is also initialized to 1. First, we show how the discount factors are used in calculating the average loss interval, and then we describe, later in this section, how the discount factors are modified over time. As described in Section 5.4, the average loss interval is calculated using the n previous loss intervals I_1, ..., I_n and the current loss interval I_0. The computation of the average loss interval using the discount factors is a simple modification of the procedure in Section 5.4, as follows:
Top   ToC   RFC5348 - Page 25
      I_tot0 = I_0 * w_0;
      I_tot1 = 0;
      W_tot0 = w_0;
      W_tot1 = 0;
      for (i = 1 to n-1) {
          I_tot0 = I_tot0 + (I_i * w_i * DF_i * DF);
          W_tot0 = W_tot0 + w_i * DF_i * DF;
      }
      for (i = 1 to n) {
          I_tot1 = I_tot1 + (I_i * w_(i-1) * DF_i);
          W_tot1 = W_tot1 + w_(i-1) * DF_i;
      }
      p = min(W_tot0/I_tot0, W_tot1/I_tot1);

   The general discounting factor, DF, is updated on every packet
   arrival as follows.  First, the receiver computes the weighted
   average I_mean of the loss intervals I_1, ..., I_n:

      I_tot = 0;
      W_tot = 0;
      for (i = 1 to n) {
          W_tot = W_tot + w_(i-1) * DF_i;
          I_tot = I_tot + (I_i * w_(i-1) * DF_i);
      }
      I_mean = I_tot / W_tot;

   This weighted average I_mean is compared to I_0, the size of current
   loss interval.  If I_0 is greater than twice I_mean, then the new
   loss interval is considerably larger than the old ones, and the
   general discount factor, DF, is updated to decrease the relative
   weight on the older intervals, as follows:

      if (I_0 > 2 * I_mean) {
          DF = 2 * I_mean/I_0;
          if (DF < THRESHOLD) {
              DF = THRESHOLD;
          }
      } else {
          DF = 1;
      }

   A nonzero value for THRESHOLD ensures that older loss intervals from
   an earlier time of high congestion are not discounted entirely.  We
   recommend a THRESHOLD of 0.25.  Note that with each new packet
   arrival, I_0 will increase further, and the discount factor DF will
   be updated.
Top   ToC   RFC5348 - Page 26
   When a new loss event occurs, the current interval shifts from I_0 to
   I_1, loss interval I_i shifts to interval I_(i+1), and the loss
   interval I_n is forgotten.  The previous discount factor DF has to be
   incorporated into the discount array.  Because DF_i carries the
   discount factor associated with loss interval I_i, the DF_i array has
   to be shifted as well.  This is done as follows:

      for (i = 1 to n) {
          DF_i = DF * DF_i;
      }
      for (i = n-1 to 0 step -1) {
          DF_(i+1) = DF_i;
      }
      I_0 = 1;
      DF_0 = 1;
      DF = 1;

   This completes the description of the optional history discounting
   mechanism.  We emphasize that this is an OPTIONAL mechanism whose
   sole purpose is to allow TFRC to respond somewhat more quickly to the
   sudden absence of congestion, as represented by a long current loss
   interval.

6. Data Receiver Protocol

The receiver periodically sends feedback messages to the sender. Feedback packets SHOULD normally be sent at least once per RTT, unless the sender is sending at a rate of less than one packet per RTT, in which case a feedback packet SHOULD be sent for every data packet received. A feedback packet SHOULD also be sent whenever a new loss event is detected without waiting for the end of an RTT, and whenever an out-of-order data packet is received that removes a loss event from the history. If the sender is transmitting at a high rate (many packets per RTT), there may be some advantages to sending periodic feedback messages more than once per RTT as this allows faster response to changing RTT measurements and more resilience to feedback packet loss. If the receiver was sending k feedback packets per RTT, for k>1, step (4) of Section 6.2 would be modified to set the feedback timer to expire after R_m/k seconds. However, each feedback packet would still report the receiver rate over the last RTT, not over a fraction of an RTT. In this document, we do not specify the modifications that might be required for a receiver sending more than one feedback packet per RTT. We note that there is little gain from sending a large number of feedback messages per RTT.
Top   ToC   RFC5348 - Page 27

6.1. Receiver Behavior When a Data Packet Is Received

When a data packet is received, the receiver performs the following steps: 1) Add the packet to the packet history. 2) Check if done: If the new packet results in the detection of a new loss event, or if no feedback packet was sent when the feedback timer last expired, go to step 3. Otherwise, no action need be performed (unless the optimization in the next paragraph is used), so exit the procedure. An OPTIONAL optimization might check to see if the arrival of the packet caused a hole in the packet history to be filled, and consequently, two loss intervals were merged into one. If this is the case, the receiver might also send feedback immediately. The effects of such an optimization are normally expected to be small. 3) Calculate p: Let the previous value of p be p_prev. Calculate the new value of p as described in Section 5. 4) Expire feedback timer: If p > p_prev, cause the feedback timer to expire and perform the actions described in Section 6.2. If p <= p_prev and no feedback packet was sent when the feedback timer last expired, cause the feedback timer to expire and perform the actions described in Section 6.2. If p <= p_prev and a feedback packet was sent when the feedback timer last expired, no action need be performed.

6.2. Expiration of Feedback Timer

When the feedback timer at the receiver expires, the action to be taken depends on whether data packets have been received since the last feedback was sent. For the m-th expiration of the feedback timer, let the maximum sequence number of a packet at the receiver, so far, be S_m and the value of the RTT measurement included in packet S_m be R_m. As described in Section 3.2.1, R_m is the sender's most recent estimate of the round-trip time, as reported in data packets. If data packets have been received since the previous feedback was sent, the receiver performs the following steps: 1) Calculate the average loss event rate using the algorithm described in Section 5.
Top   ToC   RFC5348 - Page 28
   2)  Calculate the measured receive rate, X_recv, based on the packets
       received within the previous R_(m-1) seconds.  This is performed
       whether the feedback timer expired at its normal time or expired
       early due to a new lost or marked packet (i.e., step (3) in
       Section 6.1).

       In the typical case, when the receiver is sending only one
       feedback packet per round-trip time and the feedback timer did
       not expire early due to a new lost packet, then the time interval
       since the feedback timer last expired would be R_(m-1) seconds.

       We note that when the feedback timer expires early due to a new
       lost or marked packet, the time interval since the feedback timer
       last expired is likely to be smaller than R_(m-1) seconds.

       For ease of implementation, if the time interval since the
       feedback timer last expired is not R_(m-1) seconds, the receive
       rate MAY be calculated over a longer time interval, the time
       interval going back to the most recent feedback timer expiration
       that was at least R_(m-1) seconds ago.

   3)  Prepare and send a feedback packet containing the information
       described in Section 3.2.2.

   4)  Restart the feedback timer to expire after R_m seconds.

   Note that rule 2) above gives a minimum value for the measured
   receive rate X_recv of one packet per round-trip time.  If the sender
   is limited to a sending rate of less than one packet per round-trip
   time, this will be due to the loss event rate, not from a limit
   imposed by the measured receive rate at the receiver.

   If no data packets have been received since the last feedback was
   sent, then no feedback packet is sent, and the feedback timer is
   restarted to expire after R_m seconds.

6.3. Receiver Initialization

The receiver is initialized by the first data packet that arrives at the receiver. Let the sequence number of this packet be i. When the first packet is received: o Set p = 0. o Set X_recv = 0. o Prepare and send a feedback packet.
Top   ToC   RFC5348 - Page 29
   o   Set the feedback timer to expire after R_i seconds.

   If the first data packet does not contain an estimate R_i of the
   round-trip time, then the receiver sends a feedback packet for every
   arriving data packet until a data packet arrives containing an
   estimate of the round-trip time.

   If the sender is using a coarse-grained timestamp that increments
   every quarter of a round-trip time, then a feedback timer is not
   needed, and the following procedure from RFC 4342 is used to
   determine when to send feedback messages.

   o   Whenever the receiver sends a feedback message, the receiver sets
       a local variable last_counter to the greatest received value of
       the window counter since the last feedback message was sent, if
       any data packets have been received since the last feedback
       message was sent.

   o   If the receiver receives a data packet with a window counter
       value greater than or equal to last_counter + 4, then the
       receiver sends a new feedback packet.  ("Greater" and "greatest"
       are measured in circular window counter space.)

6.3.1. Initializing the Loss History after the First Loss Event

This section describes the procedure that MUST be used for initializing the loss history after the first loss event. The number of packets until the first loss cannot be used to compute the allowed sending rate directly, as the sending rate changes rapidly during this time. TFRC assumes that the correct data rate after the first loss is half of the maximum sending rate before the loss occurred. TFRC approximates this target rate, X_target, by the maximum value of X_recv so far. (For slow-start, for a particular round-trip time, the sender's sending rate is generally twice the receiver's receive rate for data sent over the previous round-trip time.) After the first loss, instead of initializing the first loss interval to the number of packets sent until the first loss, the TFRC receiver calculates the loss interval that would be required to produce the data rate X_target, and uses this synthetic loss interval to seed the loss history mechanism. TFRC does this by finding some value, p, for which the throughput equation in Section 3.1 gives a sending rate within 5% of X_target, given the round-trip time R, and the first loss interval is then set to 1/p. If the receiver knows the segment size, s, used by the
Top   ToC   RFC5348 - Page 30
   sender, then the receiver MAY use the throughput equation for X;
   otherwise, the receiver MAY measure the receive rate in packets per
   second instead of bytes per second for this purpose, and use the
   throughput equation for X_pps.  (The 5% tolerance is introduced
   simply because the throughput equation is difficult to invert, and we
   want to reduce the costs of calculating p numerically.)

   Special care is needed for initializing the first loss interval when
   the first data packet is lost or marked.  When the first data packet
   is lost in TCP, the TCP sender retransmits the packet after the
   retransmit timer expires.  If TCP's first data packet is ECN-marked,
   the TCP sender resets the retransmit timer, and sends a new data
   packet only when the retransmit timer expires [RFC3168] (Section
   6.1.2).  For TFRC, if the first data packet is lost or ECN-marked,
   then the first loss interval consists of the null interval with no
   data packets.  In this case, the loss interval length for this (null)
   loss interval SHOULD be set to give a similar sending rate to that of
   TCP, as specified in the paragraph below.

   When the first TFRC loss interval is null, meaning that the first
   data packet is lost or ECN-marked, in order to follow the behavior of
   TCP, TFRC wants the allowed sending rate to be 1 packet every two
   round-trip times, or equivalently, 0.5 packets per RTT.  Thus, the
   TFRC receiver calculates the loss interval that would be required to
   produce the target rate X_target of 0.5/R packets per second, for the
   round-trip time R, and uses this synthetic loss interval for the
   first loss interval.  The TFRC receiver uses 0.5/R packets per second
   as the minimum value for X_target when initializing the first loss
   interval.

   We note that even though the TFRC receiver reports a synthetic loss
   interval after the first loss event, the TFRC receiver still reports
   the measured receive rate X_recv, as specified in Section 6.2 above.

7. Sender-Based Variants

In a sender-based variant of TFRC, the receiver uses reliable delivery to send information about packet losses to the sender, and the sender computes the packet loss rate and the acceptable transmit rate. The main advantage of a sender-based variant of TFRC is that the sender does not have to trust the receiver's calculation of the packet loss rate. However, with the requirement of reliable delivery of loss information from the receiver to the sender, a sender-based TFRC would have much tighter constraints on the transport protocol in which it is embedded.
Top   ToC   RFC5348 - Page 31
   In contrast, the receiver-based variant of TFRC specified in this
   document is robust to the loss of feedback packets, and therefore
   does not require the reliable delivery of feedback packets.  It is
   also better suited for applications where it is desirable to offload
   work from the server to the client as much as possible.

   RFC 4340 and RFC 4342 together specify DCCP's CCID 3, which can be
   used as a sender-based variant of TFRC.  In CCID 3, each feedback
   packet from the receiver contains a Loss Intervals option, reporting
   the lengths of the most recent loss intervals.  Feedback packets may
   also include the Ack Vector option, allowing the sender to determine
   exactly which packets were dropped or marked and to check the
   information reported in the Loss Intervals options.  The Ack Vector
   option can also include ECN Nonce Echoes, allowing the sender to
   verify the receiver's report of having received an unmarked data
   packet.  The Ack Vector option allows the sender to see for itself
   which data packets were lost or ECN-marked, to determine loss
   intervals, and to calculate the loss event rate.  Section 9 of RFC
   4342 discusses issues in the sender verifying information reported by
   the receiver.

8. Implementation Issues

This document has specified the TFRC congestion control mechanism, for use by applications and transport protocols. This section mentions briefly some of the implementation issues.

8.1. Computing the Throughput Equation

For t_RTO = 4*R and b = 1, the throughput equation in Section 3.1 can be expressed as follows: s X_Bps = -------- R * f(p) for f(p) = sqrt(2*p/3) + (12*sqrt(3*p/8) * p * (1+32*p^2)). A table lookup could be used for the function f(p). Many of the multiplications (e.g., q and 1-q for the round-trip time average, a factor of 4 for the timeout interval) are or could be by powers of two, and therefore could be implemented as simple shift operations.
Top   ToC   RFC5348 - Page 32

8.2. Sender Behavior When a Feedback Packet Is Received

This section discusses implementation issues for sender behavior when a feedback packet is received, from Section 4.3.

8.2.1. Determining If an Interval Was a Data-Limited Interval

When a feedback packet is received, the sender has to determine if the entire interval covered by that feedback packet was a data- limited period. This section discusses one possible implementation for the sender to determine if the interval covered by a feedback packet was a data-limited period. If the feedback packets all report the timestamp of the last data packet received, then let t_new be the timestamp reported by this feedback packet. Because all feedback packets cover an interval of at least a round-trip time, it is sufficient for the sender to determine if there was any time in the period (t_old, t_new] when the sender was not data-limited, for R the sender's estimate of the round-trip time, and for t_old set to t_new - R. (This procedure estimates the interval covered by the feedback packet, rather than computing it exactly. This seems fine to us.) The pseudocode for determining if the sender was data-limited over the entire interval covered in a feedback packet is given below. The variables NotLimited1 and NotLimited2 both represent times when the sender was *not* data-limited. Initialization: NotLimited1 = NotLimited2 = t_new = t_next = 0; t_now = current time; After sending a segment: If (sender has sent all it is allowed to send) { // Sender is not data-limited at this instant. If NotLimited1 <= t_new // Goal: NotLimited1 > t_new. NotLimited1 = t_now; Else if (NotLimited2 <= t_next) // Goal: NotLimited2 > t_next. NotLimited2 = t_now; }
Top   ToC   RFC5348 - Page 33
   When a feedback packet is received, is this interval data-limited:
       t_new = timestamp reported in feedback packet.
       t_old = t_new - R.                         // local variable
       t_next = t_now;
       If ((t_old < NotLimited1 <= t_new) or
           (t_old < NotLimited2 <= t_new))
           This was not a data-limited interval;
       Else
           This was a data-limited interval.
       If (NotLimited1 <= t_new && NotLimited2 > t_new)
           NotLimited1 = NotLimited2;

   Transmission times refer to transmission of a segment or segments to
   the layer below.

   Between feedback packets, (t_old, t_new] gives the transmission time
   interval estimated to be covered by the most recent feedback packet,
   and t_next gives a time at least a round-trip time greater than
   t_new.  The next feedback packet can be expected to cover roughly the
   interval (t_new, t_next] (unless the receiver sends the feedback
   packet early because it is reporting a new loss event).  The goal is
   for NotLimited1 to save a non-data-limited time in (t_new, t_next],
   if there was one, and for NotLimited2 to save a non-data-limited time
   after t_next.

   When a feedback packet was received, if either NotLimited1 or
   NotLimited2 is in the time interval covered by the feedback packet,
   then the interval is not a data-limited interval; the sender was not
   data-limited at least once during that time interval.  If neither
   NotLimited1 nor NotLimited2 is in the time interval covered by a
   feedback packet, then the sender is assumed to have been data-limited
   over that time interval.

   We note that this procedure is a heuristic, and in some cases the
   sender might not determine correctly if the sender was data-limited
   over the entire interval covered by the feedback packet.  This
   heuristic does not address the possible complications of reordering.

   That seems acceptable to us.  In order to improve its accuracy in
   identifying if the entire interval covered by a feedback packet was a
   data-limited interval, the sender could save more NotLimited times.

   In some implementations of TFRC, the sender sends coarse-grained
   timestamps that increment every quarter of a round-trip time, and the
   feedback packet reports the greatest valid sequence number received
   so far instead of reporting the timestamp of the last packet
   received.  In this case, the sender can maintain per-packet state to
Top   ToC   RFC5348 - Page 34
   determine t_new (the time that the acknowledged packet was sent), or
   the sender can estimate t_new from its estimate of the round-trip
   time and the elapsed time t_delay reported by the feedback packet.

8.2.2. Maintaining X_recv_set

To reduce the complexity of maintaining X_recv_set, it is sufficient to limit X_recv_set to at most N=3 elements. In this case, the procedure Update X_recv_set() would be modified as follows: Update X_recv_set(): Add X_recv to X_recv_set; Delete from X_recv_set values older than two round-trip times. Keep only the most recent N values. Maintaining at most *two* elements in X_recv_set would be sufficient for the sender to save an old value of X_recv from before a data- limited period, and to allow the sender not to be limited by the first feedback packet after an idle period (reporting a receive rate of one packet per round-trip time). However, it is *possible* that maintaining at most two elements in X_recv_set would not give quite as good performance as maintaining at most three elements. Maintaining three elements in X_recv_set would allow X_recv_set to contain X_recv values from two successive feedback packets, plus a more recent X_recv value from a loss event.

8.3. Sending Packets before Their Nominal Send Time

This section discusses one possible scheduling mechanism for a sender in an operating system with a coarse-grained timing granularity (from Section 4.6). Let t_gran be the scheduling timer granularity of the operating system. Let t_ipi be the inter-packet interval, as specified in Section 4.6. If the operating system has a coarse timer granularity or otherwise cannot support short t_ipi intervals, then either the TFRC sender will be restricted to a sending rate of at most 1 packet every t_gran seconds, or the TFRC sender must be allowed to send short bursts of packets. In addition to allowing the sender to accumulate sending credits for past unused send times, it can be useful to allow the sender to send a packet before its scheduled send time, as described in the section below. A parameter, t_delta, may be used to allow a packet to be sent before its nominal send time. Consider an application that becomes idle and requests re-scheduling for time t_i = t_(i-1) + t_ipi, for t_(i-1) the send time for the previous packet. When the application is
Top   ToC   RFC5348 - Page 35
   rescheduled, it checks the current time, t_now.  If
   (t_now > t_i - t_delta), then packet i is sent.  When the nominal
   send time, t_i, of the next packet is calculated, it may already be
   the case that t_now > t_i - t_delta.  In such a case, the packet
   would be sent immediately.

   In order to send at most one packet before its nominal send time, and
   never to send a packet more than a round-trip time before its nominal
   send time, the parameter t_delta would be set as follows:

      t_delta = min(t_ipi, t_gran, rtt)/2;

   (The scheduling granularity t_gran is 10 ms on some older Unix
   systems.)

   As an example, consider a TFRC flow with an allowed sending rate X of
   10 packets per round-trip time (PPR), a round-trip time of 100 ms, a
   system with a scheduling granularity t_gran of 10 ms, and the ability
   to accumulate unused sending credits for a round-trip time.  In this
   case, t_ipi is 1 ms.  The TFRC sender would be allowed to send
   packets 0.5 ms before their nominal sending time, and would be
   allowed to save unused sending credits for 100 ms.  The scheduling
   granularity of 10 ms would not significantly affect the performance
   of the connection.

   As a different example, consider a TFRC flow with a scheduling
   granularity greater than the round-trip time, for example, with a
   round-trip time of 0.1 ms and a system with a scheduling granularity
   of 1 ms, and with the ability to accumulate unused sending credits
   for a round-trip time.  The TFRC sender would be allowed to save
   unused sending credits for 0.1 ms.  If the scheduling granularity
   *did not* affect the sender's response to an incoming feedback
   packet, then the TFRC sender would be able to send an RTT of data (as
   determined by the allowed sending rate) each RTT, in response to
   incoming feedback packets.  In this case, the coarse scheduling
   granularity would not significantly reduce the sending rate, but the
   sending rate would be bursty, with a round-trip time of data sent in
   response to each feedback packet.

   However, performance would be different, in this case, if the
   operating system scheduling granularity affected the sender's
   response to feedback packets as well as the general scheduling of the
   sender.  In this case, the sender's performance would be severely
   limited by the scheduling granularity being greater than the round-
   trip time, with the sender able to send an RTT of data, at the
   allowed sending rate, at most once every 1 ms.  This restriction of
   the sending rate is an unavoidable consequence of allowing burstiness
   of at most a round-trip time of data.
Top   ToC   RFC5348 - Page 36

8.4. Calculation of the Average Loss Interval

The calculation of the average loss interval in Section 5.4 involves multiplications by the weights w_0 to w_(n-1), which for n=8 are: 1.0, 1.0, 1.0, 1.0, 0.8, 0.6, 0.4, 0.2. With a minor loss of smoothness, it would be possible to use weights that were powers of two or sums of powers of two, e.g., 1.0, 1.0, 1.0, 1.0, 0.75, 0.5, 0.25, 0.25.

8.5. The Optional History Discounting Mechanism

The optional history discounting mechanism described in Section 5.5 is used in the calculation of the average loss rate. The history discounting mechanism is invoked only when there has been an unusually long interval with no packet losses. For a more efficient operation, the discount factor, DF_i, could be restricted to be a power of two.

9. Changes from RFC 3448

9.1. Overview of Changes

This section summarizes the changes from RFC 3448. At a high level, the main change is to add mechanisms to address the case of a data- limited sender. This document also explicitly allows the TFRC sender to accumulate up to a round-trip time of unused send credits, and as a result to send a burst of packets if data arrives from the application in a burst after a data-limited period. This issue was not explicitly addressed in RFC 3448. This document changes RFC 3448 to incorporate TCP's higher initial sending rates from RFC 3390. This document also changes RFC 3448 to allow RFC 4342's use of a coarse-grained timestamp on data packets instead of a more fine-grained timestamp. Other changes address corner cases involving slow-start, the response when the first data packet is dropped, and the like. This document also incorporates the items in the RFC 3448 Errata. This section is non-normative; the normative text is in the cited sections.
Top   ToC   RFC5348 - Page 37

9.2. Changes in Each Section

Section 4.1, estimating the average segment size: Section 4.1 was modified to give a specific algorithm that could be used for estimating the average segment size. Section 4.2, update to the initial sending rate: In RFC 3448, the initial sending rate was two packets per round-trip time. In this document, the initial sending rate can be as high as four packets per round-trip time, following RFC 3390. The initial sending rate was changed to be in terms of the segment size s, not in terms of the MSS. Section 4.2 now says that tld, the Time Last Doubled during slow- start, can be initialized to either 0 or to -1. Section 4.2 was also clarified to say that RTT measurements do not only come from feedback packets; they could also come from other places, such as the SYN exchange. Section 4.3, response to feedback packets: Section 4.3 was modified to change the way that the receive rate is used in limiting the sender's allowed sending rate, by using the set of receive rate values of the last two round-trip times, and initializing the set of receive rate values by a large value. The larger initial sending rate in Section 4.2 is of little use if the receiver sends a feedback packet after the first packet is received, and the sender, in response, reduces the allowed sending rate to at most two packets per RTT, which would be twice the receive rate. Because of the change in the sender's processing of the receive rate, the sender now does not reduce the allowed sending rate to twice the reported receive rate in response to the first feedback packet. During a data-limited period, the sender saves the receive rate reported from just before the data-limited period, if it is larger than the receive rate during the data-limited period. The sender also reduces the saved values in X_recv_set in response to a loss during a data-limited period. Appendix C discusses this response further. Section 4.4, response to an idle period: Following Section 5.1 from [RFC4342], this document specifies that when the sending rate is reduced after an idle period that covers the period since the nofeedback timer was set, the allowed sending rate is not reduced below the initial sending rate. (In Section 4.4, the variable recover_rate is set to the initial sending rate.)
Top   ToC   RFC5348 - Page 38
   Section 4.4, correction from [RFC3448Err].  RFC 3448 had
   contradictory text about whether the sender halved its sending rate
   after *two* round-trip times without receiving a feedback report, or
   after *four* round-trip times.  This document clarifies that the
   sender halves its sending rate after four round-trip times without
   receiving a feedback report [RFC3448Err].

   Section 4.4, clarification for slow-start: Section 4.4 was clarified
   to specify that on the expiration of the nofeedback timer, if p = 0,
   X_Bps cannot be used, because the sender does not yet have a value
   for X_Bps.  Section 4.4 was also clarified to check the case when the
   sender does not yet have an RTT sample, but has sent a packet since
   the nofeedback timer was set.

   Section 4.6: credits for unused send time:

   Section 4.6 has been clarified to say that the TFRC sender gets to
   accumulate up to an RTT of credits for unused send time.  Section 4.6
   was also rewritten to clarify what is specification and what is
   implementation.

   Section 5.4, clarification: Section 5.4 was modified to clarify the
   receiver's calculation of the average loss interval when the receiver
   has not yet seen n loss intervals.

   Section 5.5, correction: Section 5.5 was corrected to say that the
   loss interval I_0 includes all transmitted packets, including lost
   and marked packets (as defined in Section 5.3 in the general
   definition of loss intervals).

   Section 5.5, correction from [RFC3448Err]: A line in Section 5.5 was
   changed from

      for (i = 1 to n) { DF_i = 1; }

   to

      for (i = 0 to n) { DF_i = 1; }

   [RFC3448Err].

   Section 5.5, history discounting: THRESHOLD, the lower bound on the
   history discounting parameter DF, has been changed from 0.5 to 0.25,
   to allow more history discounting when the current interval is long.

   Section 6, multiple feedback packets: Section 6 now contains more
   discussion of procedures if the receiver sends multiple feedback
   packets each round-trip time.
Top   ToC   RFC5348 - Page 39
   Section 6.3, initialization of the feedback timer: Section 6.3 now
   specifies the receiver's initialization of the feedback timer if the
   first data packet received does not have an estimate of the round-
   trip time.

   Section 6.3, a coarse-grained timestamp: Section 6.3 was modified to
   incorporate, as an option, a coarse-grained timestamp from the sender
   that increments every quarter of a round-trip time, instead of a more
   fine-grained timestamp.  This follows RFC 4342.

   Section 6.3.1, after the first loss event: Section 6.3.1 now says
   that for initializing the loss history after the first loss event,
   the receiver uses the maximum receive rate so far, instead of the
   receive rate in the last round-trip time.

   Section 6.3.1, if the first data packet is dropped: Section 6.3.1 now
   contains a specification for initializing the loss history if the
   first data packet sent is lost or ECN-marked.

   Section 7, sender-based variants: Section 7's discussion of sender-
   based variants has been expanded, with reference to RFC 4342.



(page 39 continued on part 3)

Next Section