Like TCP-Friendly Rate Control (TFRC) [
FLOYD-CCR00] [
RFC 5348], NADA is a rate-based congestion control algorithm. In its simplest form, the sender reacts to the collection of network congestion indicators in the form of an aggregated congestion signal and operates in one of two modes:
-
Accelerated ramp up:
-
When the bottleneck is deemed to be underutilized, the rate increasesmultiplicatively with respect to the rate of previously successfultransmissions. The rate increase multiplier (gamma) is calculated based onthe observed round-trip time and target feedback interval, so as to limitself-inflicted queuing delay.
-
Gradual rate update:
-
In the presence of a non-zero aggregate congestion signal, the sendingrateis adjusted in reaction to both its value (x_curr) and its change in value(x_diff).
This section introduces the list of mathematical notations and describes the core congestion control algorithm at the sender and receiver, respectively. Additional details on recommended practical implementations are described in Sections [
5.1] and [
5.2].
This section summarizes the list of variables and parameters used in the NADA algorithm.
Table 2 also includes the default values for choosing the algorithm parameters to represent either a typical setting in practical applications or a setting based on theoretical and simulation studies. See
Section 6.3 for some of the discussions on the impact of parameter values. Additional studies in real-world settings suggested in
Section 8 could gather further insight on how to choose and adapt these parameter values in practical deployment.
Notation |
Variable Name |
t_curr |
Current timestamp |
t_last |
Last time sending/receiving a feedback message |
delta |
Observed interval between current and previous feedback reports: delta = t_curr-t_last
|
r_ref |
Reference rate based on network congestion |
r_send |
Sending rate |
r_recv |
Receiving rate |
r_vin |
Target rate for video encoder |
r_vout |
Output rate from video encoder |
d_base |
Estimated baseline delay |
d_fwd |
Measured and filtered one-way delay |
d_queue |
Estimated queuing delay |
d_tilde |
Equivalent delay after non-linear warping |
p_mark |
Estimated packet ECN marking ratio |
p_loss |
Estimated packet loss ratio |
x_curr |
Aggregate congestion signal |
x_prev |
Previous value of aggregate congestion signal |
x_diff |
Change in aggregate congestion signal w.r.t. its previous value: x_diff = x_curr - x_prev
|
rmode |
Rate update mode: (0 = accelerated ramp up; 1 = gradual update)
|
gamma |
Rate increase multiplier in accelerated ramp-up mode
|
loss_int |
Measured average loss interval in packet count |
loss_exp |
Threshold value for setting the last observed packet loss to expiration
|
rtt |
Estimated round-trip time at sender |
buffer_len |
Rate-shaping buffer occupancy measured in bytes |
Table 1: List of Variables
Notation |
Parameter Name |
Default Value |
PRIO |
Weight of priority of the flow |
1.0 |
RMIN |
Minimum rate of application supported by media encoder
|
150 Kbps |
RMAX |
Maximum rate of application supported by media encoder
|
1.5 Mbps |
XREF |
Reference congestion level |
10 ms |
KAPPA |
Scaling parameter for gradual rate update calculation
|
0.5 |
ETA |
Scaling parameter for gradual rate update calculation
|
2.0 |
TAU |
Upper bound of RTT in gradual rate update calculation
|
500 ms |
DELTA |
Target feedback interval |
100 ms |
LOGWIN |
Observation window in time for calculating packet summary statistics at receiver
|
500 ms |
QEPS |
Threshold for determining queuing delay buildup at receiver
|
10 ms |
DFILT |
Bound on filtering delay |
120 ms |
GAMMA_MAX |
Upper bound on rate increase ratio for accelerated ramp up
|
0.5 |
QBOUND |
Upper bound on self-inflicted queuing delay during ramp up
|
50 ms |
MULTILOSS |
Multiplier for self-scaling the expiration threshold of the last observed loss (loss_exp) based on measured average loss interval (loss_int)
|
7.0 |
QTH |
Delay threshold for invoking non-linear warping |
50 ms |
LAMBDA |
Scaling parameter in the exponent of non-linear warping
|
0.5 |
PLRREF |
Reference packet loss ratio |
0.01 |
PMRREF |
Reference packet marking ratio |
0.01 |
DLOSS |
Reference delay penalty for loss when packet loss ratio is at PLRREF
|
10 ms |
DMARK |
Reference delay penalty for ECN marking when packet marking is at PMRREF
|
2 ms |
FPS |
Frame rate of incoming video |
30 |
BETA_S |
Scaling parameter for modulating outgoing sending rate
|
0.1 |
BETA_V |
Scaling parameter for modulating video encoder target rate
|
0.1 |
ALPHA |
Smoothing factor in exponential smoothing of packet loss and marking ratios
|
0.1 |
Table 2: List of Algorithm Parameters and Their Default Values
The receiver-side algorithm can be outlined as below:
-
On initialization:
-
-
set d_base = +INFINITY
-
set p_loss = 0
-
set p_mark = 0
-
set r_recv = 0
-
set both t_last and t_curr as current time in milliseconds
-
On receiving a media packet:
-
-
obtain current timestamp t_curr from system clock
-
obtain from packet header sending time stamp t_sent
-
obtain one-way delay measurement: d_fwd = t_curr - t_sent
-
update baseline delay: d_base = min(d_base, d_fwd)
-
update queuing delay: d_queue = d_fwd - d_base
-
update packet loss ratio estimate p_loss
-
update packet marking ratio estimate p_mark
-
update measurement of receiving rate r_recv
-
On time to send a new feedback report (t_curr - t_last > DELTA):
-
-
calculate non-linear warping of delay d_tilde if packet loss exists
-
calculate current aggregate congestion signal x_curr
-
determine mode of rate adaptation for sender: rmode
-
send feedback containing values of: rmode, x_curr, and r_recv
-
update t_last = t_curr
In order for a delay-based flow to hold its ground when competing against loss-based flows (e.g., loss-based TCP), it is important to distinguish between different levels of observed queuing delay. For instance, over wired connections, a moderate queuing delay value on the order of tens of milliseconds is likely self-inflicted or induced by other delay-based flows, whereas a high queuing delay value of several hundreds of milliseconds may indicate the presence of a loss-based flow that does not refrain from increased delay.
If the last observed packet loss is within the expiration window of loss_exp (measured in terms of packet counts), the estimated queuing delay follows a non-linear warping:
/ d_queue, if d_queue < QTH
|
d_tilde = < (1)
| (d_queue-QTH)
\ QTH exp(-LAMBDA ---------------) , otherwise
QTH
In Equation (1), the queuing delay value is unchanged when it is below the first threshold QTH; otherwise, it is scaled down following a non-linear curve. This non-linear warping is inspired by the delay-adaptive congestion window backoff policy in [
BUDZISZ-AIMD-CC] so as to "gradually nudge" the controller to operate based on loss-induced congestion signals when competing against loss-based flows. The exact form of the non-linear function has been simplified with respect to [
BUDZISZ-AIMD-CC]. The value of the threshold QTH should be carefully tuned for different operational environments so as to avoid potential risks of prematurely discounting the congestion signal level. Typically, a higher value of QTH is required in a noisier environment (e.g., over wireless connections or where the video stream encounters many time-varying background competing traffic) so as to stay robust against occasional non-congestion-induced delay spikes. Additional insights on how this value can be tuned or auto-tuned should be gathered from carrying out experimental studies in different real-world deployment scenarios.
The value of loss_exp is configured to self-scale with the average packet loss interval loss_int with a multiplier MULTILOSS:
loss_exp = MULTILOSS *
loss_int.
Estimation of the average loss interval loss_int, in turn, follows
Section 5.4 of
RFC 5348.
In practice, it is recommended to linearly interpolate between the warped (d_tilde) and non-warped (d_queue) values of the queuing delay during the transitional period lasting for the duration of loss_int.
The aggregate congestion signal is:
/ p_mark \^2 / p_loss \^2
x_curr = d_tilde + DMARK*|--------| + DLOSS*|--------| (2)
\ PMRREF / \ PLRREF /
Here, DMARK is prescribed a reference delay penalty associated with ECN markings at the reference marking ratio of PMRREF; DLOSS is prescribed a reference delay penalty associated with packet losses at the reference packet loss ratio of PLRREF. The value of DLOSS and DMARK does not depend on configurations at the network node. Since ECN-enabled active queue management schemes typically mark a packet before dropping it, the value of DLOSS
SHOULD be higher than that of DMARK. Furthermore, the values of DLOSS and DMARK need to be set consistently across all NADA flows sharing the same bottleneck link so that they can compete fairly.
In the absence of packet marking and losses, the value of x_curr reduces to the observed queuing delay d_queue. In that case, the NADA algorithm operates in the regime of delay-based adaptation.
Given observed per-packet delay and loss information, the receiver is also in a good position to determine whether or not the network is underutilized and then recommend the corresponding rate adaptation mode for the sender. The criteria for operating in accelerated ramp-up mode are:
-
No recent packet losses within the observation window LOGWIN; and
-
No buildup of queuing delay: d_fwd-d_base < QEPS for all previous delay samples within the observation window LOGWIN.
Otherwise, the algorithm operates in graduate update mode.
The sender-side algorithm is outlined as follows:
-
On initialization:
-
-
set r_ref = RMIN
-
set rtt = 0
-
set x_prev = 0
-
set t_last and t_curr as current system clock time
-
On receiving feedback report:
-
-
obtain current timestamp from system clock: t_curr
-
obtain values of rmode, x_curr, and r_recv from feedback report
-
update estimation of rtt
-
measure feedback interval: delta = t_curr - t_last
-
if rmode == 0:
-
-
update r_ref following accelerated ramp-up rules
-
else:
-
-
update r_ref following gradual update rules
-
clip rate r_ref within the range of minimum rate (RMIN) and maximum rate (RMAX).
-
set x_prev = x_curr
-
set t_last = t_curr
In accelerated ramp-up mode, the rate r_ref is updated as follows:
QBOUND
gamma = min(GAMMA_MAX, ------------------) (3)
rtt+DELTA+DFILT
r_ref = max(r_ref, (1+gamma) r_recv)
(4)
The rate increase multiplier gamma is calculated as a function of the upper bound of self-inflicted queuing delay (QBOUND), round-trip time (rtt), and target feedback interval (DELTA); it is bound on the filtering delay for calculating d_queue (DFILT). It has a maximum value of GAMMA_MAX. The rationale behind Equations (3)-(4) is that the longer it takes for the sender to observe self-inflicted queuing delay buildup, the more conservative the sender should be in increasing its rate and, hence, the smaller the rate increase multiplier.
In gradual update mode, the rate r_ref is updated as:
x_offset = x_curr - PRIO*XREF*RMAX/r_ref (5)
x_diff = x_curr - x_prev (6)
delta x_offset
r_ref = r_ref - KAPPA*-------*------------*r_ref
TAU TAU
x_diff
- KAPPA*ETA*---------*r_ref (7)
TAU
The rate changes in proportion to the previous rate decision. It is affected by two terms: the offset of the aggregate congestion signal from its value at equilibrium (x_offset) and its change (x_diff). The calculation of x_offset depends on the maximum rate of the flow (RMAX), its weight of priority (PRIO), as well as a reference congestion signal (XREF). The value of XREF is chosen so that the maximum rate of RMAX can be achieved when the observed congestion signal level is below PRIO*XREF.
At equilibrium, the aggregated congestion signal stabilizes at x_curr = PRIO*XREF*RMAX/r_ref. This ensures that when multiple flows share the same bottleneck and observe a common value of x_curr, their rates at equilibrium will be proportional to their respective priority levels (PRIO) and the range between minimum and maximum rate. Values of the minimum rate (RMIN) and maximum rate (RMAX) will be provided by the media codec, for instance, as outlined by [
RMCAT-CC-RTP]. In the absence of such information, the NADA sender will choose a default value of 0 for RMIN and 3 Mbps for RMAX.
As mentioned in the sender-side algorithm, the final rate is always clipped within the dynamic range specified by the application:
r_ref = min(r_ref, RMAX) (8)
r_ref = max(r_ref, RMIN) (9)
The above operations ignore many practical issues such as clock synchronization between sender and receiver, the filtering of noise in delay measurements, and base delay expiration. These will be addressed in
Section 5.