to X_r at an increase rate of no more than 8s/R_max bits/s every
R_max seconds.
2. If receiver r is not the CLR but a CLR is present, then receiver
r becomes the current limiting receiver if X_r is less than the
current sending rate X and the receiver_leave flag of that
receiver’s report is not set. Furthermore, the sending rate is
reduced to X_r.
3. If receiver r is not the CLR but a CLR is present and the
receiver_leave flag of the CLR’s last report was set, then
receiver r becomes the current limiting receiver. However, if
X_r > X, the sending rate is not increased to X_r for the
duration of a feedback round to allow other (lower rate)
receivers to give feedback and be selected as CLR.
4. If receiver r is the CLR, the sending rate is set to the minimum
of X_r and X + 8s/R_max bits/s.
If the receiver has not yet measured its RTT but already experienced
packet loss (indicated by the corresponding flags in the receiver
report), the receiver report will include a desired rate that is
based on the maximum RTT rather than the actual RTT to that receiver.
In this case, the sender adjusts the desired rate using its
measurement of the instantaneous RTT R_r to that receiver:
X_r’ = X_r * R_max / R_r
X_r’ is then used instead of X_r to detect whether to switch to a new
CLR.
If the TFMCC sender receives no reports from the CLR for 4 RTTs, the
sending rate is cut in half unless the CLR was selected less than 10
RTTs ago. In addition, if the sender receives no reports from the
CLR for at least 10 RTTs, it assumes that the CLR crashed or left the
group. A new CLR is selected from the feedback that subsequently
arrives at the sender, and we increase as in case 3, above.
If no new CLR can be selected (i.e., in the absence of any feedback
from any of the receivers) it is necessary to reduce the sending rate
further. For every 10 consecutive RTTs without feedback, the sending
rate is cut in half. The rate is at most reduced to one packet every
8 seconds.
Note that when receivers stop receiving data packets, they will stop
sending feedback. This eventually causes the sending rate to be
reduced in the case of network failure. If the network subsequently
recovers, a linear increase to the calculated rate of the CLR will
occur at 8s/R_max bits/s every R_max.
An application using TFMCC may have a minimum sending rate
requirement, where the application becomes unusable if the sending
rate continuously falls below this minimum rate. The application
should exclude receivers that report such a low rate from the
multicast group. The specific mechanism to do this is application
dependent and beyond the scope of this document.
3.4. Controlling Receiver Feedback
The receivers allowed to send a receiver report are determined in so-
called feedback rounds. Feedback rounds have a duration T of six
times the maximum RTT. In case the multicast model is ASM (i.e.,
receiver feedback is multicast to the whole group) the duration of a
feedback round may be reduced to four times the maximum RTT.
Only receivers wishing to report a rate that is lower than the
suppression rate X_supp or those with a higher RTT than R_max may
send feedback. At the beginning of each feedback round, X_supp is
set to the highest possible value that can be represented. When
feedback arrives at the sender over the course of a feedback round,
X_supp is decreased such that more and more feedback is suppressed
towards the end of the round. How receiver feedback is spread out
over the feedback round is discussed in Section 4.5.
Whenever non-CLR feedback for the current round arrives at the
sender, X_supp is reduced to
X_supp = (1-g) * X_r
if X_supp > X_r. Feedback that causes the corresponding receiver to
be selected as CLR, but that was from a non-CLR receiver at the time
of sending, also contributes to the feedback suppression. Note that
X_r must not be adjusted by the sender to reflect the receiver’s real
RTT in case X_r was calculated using the maximum RTT, as is done for
setting the sending rate (Section 3.3); otherwise, a feedback
implosion is possible. The parameter g determines to what extent
higher rate feedback can suppress lower rate feedback. This
mechanism guarantees that the lowest calculated rate reported lies
within a factor of g of the actual lowest calculated rate of the
receiver set (see [13]). A value of g of 0.1 is recommended.
To allow receivers to suppress their feedback, the sender’s
suppression rate needs to be updated whenever feedback is received.
This suppression rate has to be communicated to the receivers in a
timely manner, either by including it in the data packet header or,
if separate congestion control messages are used, by sending a
message with the suppression rate whenever the rate changes
significantly (i.e., when it is reduced to less than (1-g) times the
previously advertised suppression rate).
After a time span of T, the feedback round ends if non-CLR feedback
was received during that time. Otherwise, the feedback round ends as
soon as the first non-CLR feedback message arrives at the sender but
at most after 2T. The feedback round counter is incremented by one,
and the suppression rate X_supp is reset to the highest representable
value. The feedback round counter restarts with round 0 after a
wrap-around.
3.5. Assisting Receiver-Side RTT Measurements
Receivers measure their RTT by sending a timestamp with a receiver
report, which is echoed by the sender. If congestion control
information is piggybacked onto data packets, usually only one
receiver ID and timestamp can be included. If multiple feedback
messages from different receivers arrive at the sender during the
time interval between two data packets, the sender has to decide
which receiver to allow to measure the RTT. The same applies if
separate congestion control messages allow echoing multiple receiver
timestamps simultaneously, but the number of receivers that gave
feedback since the last congestion control message exceeds the list
size.
The sender’s timestamp echoes are prioritized in the following order:
1. a new CLR (after a change of CLR’s) or a CLR without any previous
RTT measurements
2. receivers without any previous RTT measurements in the order of
the feedback round echo of the corresponding receiver report
(i.e., older feedback first)
3. non-CLR receivers with previous RTT measurements, again in
ascending order of the feedback round echo of the report
4. the CLR
Ties are broken in favor of the receiver with the lowest reported
rate.
It is necessary to account for the time that elapses between
receiving a report and sending the next data packet. This time needs
to be deducted from the RTT and thus has to be added to the
receiver’s timestamp value.
Whenever no feedback packets arrive in the interval between two data
packets, the CLR’s last timestamp, adjusted by the appropriate
offset, is echoed. When the number of packets per RTT is so low that
all packets carry a non-CLR receiver’s timestamp, the CLR’s timestamp
and ID are included in a data packet at least once per feedback
round.
3.6. Slowstart
TFMCC uses a slowstart mechanism to quickly approach its fair
bandwidth share at the start of a session. During slowstart, the
sending rate increases exponentially. The rate increase is limited
to the minimum of the rates included in the receiver reports, and
receivers report twice the rate at which they currently receive data.
As in normal congestion control mode, the receiver with the smallest
reported rate becomes CLR. Since a receiver can never receive data
at a rate higher than its link bandwidth, this effectively limits the
overshoot to twice this bandwidth. In case the resulting increase
over R_max is less than 8s/R_max bits/s, the sender may choose to
increase the rate by up to 8s/R_max bits/s every R_max. The current
sending rate is gradually adjusted to the target rate reported in the
receiver reports over the course of an RTT. Slowstart is terminated
as soon as any one of the receivers experiences its first packet
loss. Since that receiver’s calculated rate will be lower than the
current sending rate, the receiver will be selected as CLR.
During slowstart, the upper bound on the rate increase of 8s/R_max
bits/s every RTT does not apply. Only after the TFMCC sender
receives the first report with the have_loss flag set is the rate
increase limited in this way.
Slowstart may also be used after the sender has been idle for some
time, to quickly reach the previous sending rate. When the sender
stops sending data packets, it records the current sending rate X’ =
X. Every 10 RTTs, the allowed sending rate will be halved due to
lack of receiver feedback, as specified in Section 3.3. This halving
may take place multiple times. When the sender resumes, it may
perform a slowstart from the current allowed rate up to the recorded
rate X’. Slowstart ends after the first packet loss by any of the
receivers or as soon as X’ is reached.
To this end, receivers have to clear the have_loss flag after 10 RTTs
without data packets as specified in Section 4.3.1. The have_loss
flag is only used during slowstart. Therefore, clearing the flag has
no effect if no packets arrived due to network partitioning or packet
loss.
3.7. Scheduling of Packet Transmissions
As TFMCC is rate-based, and as operating systems typically cannot
schedule events precisely, it is necessary to be opportunistic about
sending data packets so that the correct average rate is maintained
despite the coarse-grain or irregular scheduling of the operating
system. Thus, a typical sending loop will calculate the correct
inter-packet interval, ts_ipi, as follows:
ts_ipi = 8s/X
When a sender first starts sending at time t_0, it calculates ts_ipi
and calculates a nominal send time, t_1 = t_0 + ts_ipi, for packet 1.
When the application becomes idle, it checks the current time,
ts_now, and then requests re-scheduling after (ts_ipi - (ts_now -
t_0)) seconds. When the application is re-scheduled, it checks the
current time, ts_now, again. If (ts_now > t_1 - delta) then packet 1
is sent (see below for delta).
Now, a new ts_ipi may be calculated and used to calculate a nominal
send time, t_2, for packet 2: t_2 = t_1 + ts_ipi. The process then
repeats with each successive packet’s send time being calculated from
the nominal send time of the previous packet. Note that the actual
send time ts_i, and not the nominal send time, is included as
timestamp in the packet header.
In some cases, when the nominal send time, t_i, of the next packet is
calculated, it may already be the case that ts_now > t_i - delta. In
such a case, the packet should be sent immediately. Thus, if the
operating system has coarse timer granularity and the transmit rate
is high, then TFMCC may send short bursts of several packets
separated by intervals of the OS timer granularity.
The parameter delta is to allow a degree of flexibility in the send
time of a packet. If the operating system has a scheduling timer
granularity of ts_gran seconds, then delta would typically be set to:
delta = min(ts_ipi/2, ts_gran/2)
ts_gran is 10 milliseconds on many Unix systems. If ts_gran is not
known, a value of 10 milliseconds can be safely assumed.
4. Data Receiver Protocol
Receivers measure the current network conditions (namely, RTT and
loss event rate) and use this information to calculate a rate that is
fair to competing traffic. The rate is then communicated to the
sender in receiver reports. Due to the potentially large number of
receivers, it is undesirable that all receivers send reports,
especially not at the same time.
In the description of the receiver functionality, we will first
address how the receivers measure the network parameters and then
discuss the feedback process.
4.1. Receiver Initialization
The receiver is initialized when it receives the first data packet.
The RTT is set to the maximum RTT value contained in the data packet.
This initial value is used as the receiver’s RTT until the first real
RTT measurement is made. The loss event rate is initialized to 0.
Also, the flags receiver_leave, have_RTT, and have_loss are cleared.
4.2. Receiver Leave
A receiver that sends feedback but wishes to leave the TFMCC session
within the next feedback round may indicate the pending leave by
setting the receiver_leave flag in its report. If the leaving
receiver is the CLR, the receiver_leave flag should be set for all
the reports within the feedback round before the leave takes effect.
4.3. Measurement of the Network Conditions
Receivers have to update their estimate of the network parameters
with each new data packet they receive.
4.3.1. Updating the Loss Event Rate
When a data packet is received, the receiver adds the packet to the
packet history. It then recalculates the new value of the loss event
rate p. The loss event rate measurement mechanism is described
separately in Section 5.
When a loss event is detected, the flag have_loss is set. In case no
data packets are received for 10 consecutive RTTs, the flag is
cleared to allow the sender to slowstart. It is set again when new
data packets arrive and a loss event is detected.
4.3.2. Basic Round-Trip Time Measurement
When a receiver gets a data packet that carries the receiver’s own ID
in the r field, the receiver updates its RTT estimate.
1. The current RTT is calculated as:
R_sample = tr_now - tr_r’
where tr_now is the time the data packet arrives at the receiver
and tr_r’ is the receiver report timestamp echoed in the data
packet. If the actual RTT is smaller than the resolution of the
timestamps and tr_now equals tr_r’, then R_sample is set to the
smallest positive RTT value larger than 0 (i.e., 1 millisecond in
our case).
2. The smoothed RTT estimate R is updated:
If no feedback has been received before
R = R_sample
Else
R = q*R + (1-q)*R_sample
A filter parameter q of 0.5 is recommended for non-CLR receivers.
The CLR performs RTT measurements much more frequently and hence
should use a higher filter value. We recommend using q=0.9.
Note that TFMCC is not sensitive to the precise value for the
filter constant.
Optionally, sender-based RTT measurements may be used instead of
receiver-based ones. The sender already determines the RTT to a
receiver from the receiver’s echo of the sender’s own timestamp for
the calculation of the maximum RTT. For sender-based RTT
measurements, this RTT measurement needs to be communicated to the
receiver. Instead of including an echo of the receiver’s timestamp,
the sender includes the receiver’s RTT in the next data packet, using
the prioritization rules described in Section 3.5.
To simplify sender operation, smoothing of RTT samples as described
above should still be done at the receiver.
4.3.3. One-Way Delay Adjustments
When an RTT measurement is performed, the receiver also determines
the one-way delay D_r from itself to the sender:
D_r = tr_r’ - ts_i
where ts_i and tr_r’ are the timestamp and receiver report timestamp
echo contained in the data packet. With each new data packet j, the
receiver can now calculate an updated RTT estimate as:
R’ = max(D_r + tr_now - ts_j, 1 millisecond)
In between RTT measurements, the updated R’ is used instead of the
smoothed RTT R. Like the RTT samples, R’ must be strictly positive.
When a new measurement is made, all interim one-way delay
measurements are discarded (i.e., the smoothed RTT is updated
according to Section 4.3.2 without taking the interim one-way delay
adjustments into account).
For the one-way delay measurements, the clocks of sender and
receivers need not be synchronized. Clock skew will cancel itself
out when both one-way measurements are added to form an RTT estimate,
as long as clock drift between real RTT measurements is negligible.
The same one-way delay adjustments should be applied to the RTT
supplied by the sender when using sender-based RTT measurements.
4.3.4. Receive Rate Measurements
When a receiver has not experienced any loss events, it cannot
calculate a TCP-friendly rate to include in the receiver reports.
Instead, the receiver measures the current receive rate and sets the
desired rate X_r to twice the receive rate.
The receive rate in bits/s is measured as the number of bits received
over the last k RTTs, taking into account the IP and transport packet
headers, but excluding the link-layer packet headers. A value for k
between 2 and 4 is recommended.
4.4. Setting the Desired Rate
When a receiver measures a non-zero loss event rate, it calculates
the desired rate using Equation (1). In case no RTT measurement is
available yet, the maximum RTT is used instead of the receiver’s RTT.
The desired rate X_r is updated whenever the loss event rate or the
RTT changes.
A receiver may decide not to report desired rates that are below 1
packet per 8 seconds, since a sender is very slow to recover from
such low sending rates. In this case, the receiver reports a desired
rate of 1 packet per 8 seconds. However, it must leave the multicast
group if for more than 120 seconds, the calculated rate falls below
the reported rate and the current sending rate is higher than the
receiver’s calculated rate.
As mentioned above, calculation of the desired rate is not possible
before the receiver experiences the first loss event. In that case,
twice the rate at which data is received is included in the receiver
reports as X_r to allow the sender to slowstart as described in
Section 3.6. This is also done when the sender resumes sending data
packets after the have_loss flag was cleared due to the sender being
idle.
4.5. Feedback and Feedback Suppression
Let fb_nr be the highest feedback round counter value received by a
receiver. When a new data packet arrives with a higher feedback
round counter than fb_nr, a new feedback round begins and fb_nr is
updated. Outstanding feedback for the old round is canceled. In
case a feedback number with a value that is more than half the
feedback number space lower than fb_nr is received, the receiver
assumes that the feedback round counter wrapped and also cancels the
feedback timer and updates fb_nr.
The CLR sends its feedback independently from all the other receivers
once per RTT. Its feedback does not suppress other feedback and
cannot be suppressed by other receiver’s feedback.
Non-CLR receivers set a feedback timer at the beginning of a feedback
round. Using an exponentially weighted random timer mechanism, the
feedback timer is set to expire after
t = max(T * (1 + log(x)/log(N)), 0)
where
x is a random variable uniformly distributed in (0,1],
T is the duration of a feedback round (i.e., 6 * R_max),
N is an estimated upper bound on the number of receivers.
N is a constant specific to the TFMCC protocol. Since TFMCC scales
to up to thousands of receivers, setting N to 10,000 for all
receivers (and limiting the TFMCC session to at most 10,000
receivers) is recommended.
A feedback packet is sent when the feedback timer expires, unless the
timer is canceled beforehand. When the multicast model is ASM,
feedback is multicast to the whole group; otherwise, the feedback is
unicast to the sender. The feedback packet includes the calculated
rate valid at the time the feedback packet is sent (not the rate at
the point of time when the feedback timer is set). The copy of the
timestamp ts_i of the last data packet received, which is included in
the feedback packet, needs to be adjusted by the time interval
between receiving the data packet and sending the report to allow the
sender to correctly infer the instantaneous RTT (i.e., that time
interval has to be added to the timestamp value).
The timer is canceled if a data packet is received that has a lower
suppression rate than the receiver’s calculated rate and a higher or
equal maximum RTT than the receiver’s RTT. Likewise, a data packet
indicating the beginning of a new feedback round cancels all feedback
for older rounds. In case of ASM, the timer is also canceled if a
feedback packet is received from another non-CLR receiver reporting a
lower rate.
The feedback suppression process is complicated by the fact that the
calculated rates of the receivers will change during a feedback
round. If the calculated rates decrease rapidly for all receivers,
feedback suppression can no longer prevent a feedback implosion,
since earlier feedback will always report a higher rate than current
feedback. To make the feedback suppression mechanism robust in the
face of changing rates, it is necessary to introduce X_fbr, the
calculated rate of a receiver at the beginning of a feedback round.
A receiver needs to suppress its feedback not only when the
suppression rate is less than the receiver’s current calculated rate
but also in the case that the suppression rate falls below X_fbr.
When the maximum RTT changes significantly during one feedback round,
it is necessary to reschedule the feedback timer in proportion to the
change.
t = t * R_max / R_max’
where R_max is the new maximum RTT and R_max’ is the previous maximum
RTT. The same considerations hold when the last data packets were
received more than a time interval of R_max ago. In this case, it is
necessary to add the difference of the inter-packet gap and the
maximum RTT to the feedback time to prevent a feedback implosion
(e.g., in case the sender crashed).
t = t + max(tr_now - tr_i - R_max, 0)
where tr_i is the time when the last data packet arrived at the
receiver.
More details on the characteristics of the feedback suppression
mechanism can be found in [13] and [3].
5. Calculation of the Loss Event Rate
Obtaining an accurate and stable measurement of the loss event rate
is of primary importance for TFMCC. Loss rate measurement is
performed at the receiver, based on the detection of lost or marked
packets from the sequence numbers of arriving packets.
5.1. Detection of Lost or Marked Packets
TFMCC 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, we require 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.
The receivers each maintain a data structure that keeps track of
which packets have arrived and which are missing. For the purposes
of specification, we assume that the data structure consists of a
list of packets that have arrived along with the 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 three
packets with a higher sequence number than the lost packet. The