tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search

RFC 5348

 
 
 

TCP Friendly Rate Control (TFRC): Protocol Specification

Part 2 of 3, p. 19 to 39
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 19 
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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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 RFC Part