4.1. Mathematical Notations

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.¶

4.2. Receiver-Side Algorithm

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 "TCP Friendly Rate Control (TFRC): Protocol Specification" [RFC5348].¶

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.¶

4.3. Sender-Side Algorithm

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.¶

5.1. Receiver-Side Operation

The receiver continuously monitors end-to-end per-packet statistics in terms of delay, loss, and/or ECN marking ratios. It then aggregates all forms of congestion indicators into the form of an equivalent delay and periodically reports this back to the sender. In addition, the receiver tracks the receiving rate of the flow and includes that in the feedback message.¶

            p_loss = ALPHA*p_inst + (1-ALPHA)*p_loss        (10)

5.2. Sender-Side Operation

Figure 2 provides a detailed view of the NADA sender. Upon receipt of an RTCP feedback report from the receiver, the NADA sender calculates the reference rate r_ref as specified in Section 4.3. It further adjusts both the target rate for the live video encoder r_vin and the sending rate r_send over the network based on the updated value of r_ref and rate-shaping buffer occupancy buffer_len.¶

The NADA sender behavior stays the same in the presence of all types of congestion indicators: delay, loss, and ECN marking. This unified approach allows a graceful transition of the scheme as the network shifts dynamically between light and heavy congestion levels.¶

                   +----------------+
                   |  Calculate     | <---- RTCP report
                   | Reference Rate |
                   -----------------+
                           | r_ref
              +------------+-------------+
              |                          |
             \|/                        \|/
      +-----------------+           +---------------+
      | Calculate Video |           |   Calculate   |
      |  Target Rate    |           | Sending Rate  |
      +-----------------+           +---------------+
          |        /|\                 /|\      |
    r_vin |         |                   |       |
         \|/        +-------------------+       |
      +----------+          | buffer_len        |  r_send
      |  Video   | r_vout  -----------+        \|/
      |  Encoder |-------->   |||||||||=================>
      +----------+         -----------+    RTP packets
      Rate-Shaping Buffer

    r_diff_v = min(0.05*r_ref, BETA_V*8*buffer_len*FPS)     (11)
    r_diff_s = min(0.05*r_ref, BETA_S*8*buffer_len*FPS)     (12)
    r_vin  = max(RMIN, r_ref - r_diff_v)                    (13)
    r_send = min(RMAX, r_ref + r_diff_s)                    (14)

5.3. Feedback Message Requirements

The following list of information is required for NADA congestion control to function properly:¶

Recommended rate adaptation mode (rmode):

A 1-bit flag indicating whether the sender should operate in accelerated ramp-up mode (rmode=0) or gradual update mode (rmode=1).¶

Aggregated congestion signal (x_curr):

The most recently updated value, calculated by the receiver according to Section 4.2. This information can be expressed with a unit of 100 microseconds (i.e., 1/10 of a millisecond) in 15 bits. This allows a maximum value of x_curr at approximately 3.27 seconds.¶

Receiving rate (r_recv):

The most recently measured receiving rate according to Section 5.1.3. This information is expressed with a unit of bits per second (bps) in 32 bits (unsigned int). This allows a maximum rate of approximately 4.3 Gbps, approximately 1000 times the streaming rate of a typical high-definition (HD) video conferencing session today. This field can be expanded further by a few more bytes if an even higher rate needs to be specified.¶

The above list of information can be accommodated by 48 bits, or 6 bytes, in total. They can be either included in the feedback report from the receiver or, in the case where all receiver-side calculations are moved to the sender, derived from per-packet information from the feedback message as defined in [RTCP-FEEDBACK]. Choosing the feedback message interval DELTA is discussed in Section 6.3. A target feedback interval of DELTA = 100 ms is recommended.¶

6.1. Choice of Delay Metrics

The current design works with relative one-way delay (OWD) as the main indication of congestion. The value of the relative OWD is obtained by maintaining the minimum value of observed OWD over a relatively long time horizon and subtracting that out from the observed absolute OWD value. Such an approach cancels out the fixed difference between the sender and receiver clocks. It has been widely adopted by other delay-based congestion control approaches such as [RFC6817]. As discussed in [RFC6817], the time horizon for tracking the minimum OWD needs to be chosen with care; it must be long enough for an opportunity to observe the minimum OWD with zero standing queue along the path, and it must be sufficiently short enough to timely reflect "true" changes in minimum OWD introduced by route changes and other rare events and to mitigate the cumulative impact of clock rate skew over time.¶

The potential drawback in relying on relative OWD as the congestion signal is that when multiple flows share the same bottleneck, the flow arriving late at the network experiencing a non-empty queue may mistakenly consider the standing queuing delay as part of the fixed path propagation delay. This will lead to slightly unfair bandwidth sharing among the flows.¶

Alternatively, one could move the per-packet statistical handling to the sender instead and use relative round-trip time (RTT) in lieu of relative OWD, assuming that per-packet acknowledgments are available. The main drawback of an RTT-based approach is the noise in the measured delay in the reverse direction.¶

Note that the choice of either delay metric (relative OWD vs. RTT) involves no change in the proposed rate adaptation algorithm. Therefore, comparing the pros and cons regarding which delay metric to adopt can be kept as an orthogonal direction of investigation.¶

6.2. Method for Delay, Loss, and Marking Ratio Estimation

Like other delay-based congestion control schemes, performance of NADA depends on the accuracy of its delay measurement and estimation module. Appendix A of [RFC6817] provides an extensive discussion on this aspect.¶

The current recommended practice of applying minimum filter with a window size of 15 samples suffices in guarding against processing delay outliers observed in wired connections. For wireless connections with a higher packet delay variation (PDV), more sophisticated techniques on denoising, outlier rejection, and trend analysis may be needed.¶

More sophisticated methods in packet loss ratio calculation, such as that adopted by [FLOYD-CCR00], will likely be beneficial. These alternatives are part of the experiments this document proposes.¶

6.3. Impact of Parameter Values

In the gradual rate update mode, the parameter TAU indicates the upper bound of round-trip time (RTT) in the feedback control loop. Typically, the observed feedback interval delta is close to the target feedback interval DELTA, and the relative ratio of delta/TAU versus ETA dictates the relative strength of influence from the aggregate congestion signal offset term (x_offset) versus its recent change (x_diff), respectively. These two terms are analogous to the integral and proportional terms in a proportional-integral (PI) controller. The recommended choice of TAU = 500 ms, DELTA = 100 ms, and ETA = 2.0 corresponds to a relative ratio of 1:10 between the gains of the integral and proportional terms. Consequently, the rate adaptation is mostly driven by the change in the congestion signal with a long-term shift towards its equilibrium value driven by the offset term. Finally, the scaling parameter KAPPA determines the overall speed of the adaptation and needs to strike a balance between responsiveness and stability.¶

The choice of the target feedback interval DELTA needs to strike the right balance between timely feedback and low RTCP feedback message counts. A target feedback interval of DELTA = 100 ms is recommended, corresponding to a feedback bandwidth of 16 Kbps with 200 bytes per feedback message -- approximately 1.6% overhead for a 1 Mbps flow. Furthermore, both simulation studies and frequency-domain analysis in [IETF-95] have established that a feedback interval below 250 ms (i.e., more frequently than 4 feedback messages per second) will not break up the feedback control loop of NADA congestion control.¶

In calculating the non-linear warping of delay in Equation (1), the current design uses fixed values of QTH for determining whether to perform the non-linear warping. Its value should be carefully tuned for different operational environments (e.g., over wired vs. wireless connections) so as to avoid the potential risk of prematurely discounting the congestion signal level. It is possible to adapt its value based on past observed patterns of queuing delay in the presence of packet losses. It needs to be noted that the non-linear warping mechanism may lead to multiple NADA streams stuck in loss-based mode when competing against each other.¶

In calculating the aggregate congestion signal x_curr, the choice of DMARK and DLOSS influence the steady-state packet loss/marking ratio experienced by the flow at a given available bandwidth. Higher values of DMARK and DLOSS result in lower steady-state loss/marking ratios but are more susceptible to the impact of individual packet loss/marking events. While the value of DMARK and DLOSS are fixed and predetermined in the current design, this document also encourages further explorations of a scheme for automatically tuning these values based on desired bandwidth sharing behavior in the presence of other competing loss-based flows (e.g., loss-based TCP).¶

6.4. Sender-Based vs. Receiver-Based Calculation

In the current design, the aggregated congestion signal x_curr is calculated at the receiver, keeping the sender operation completely independent of the form of actual network congestion indications (delay, loss, or marking) in use.¶

Alternatively, one can shift receiver-side calculations to the sender, whereby the receiver simply reports on per-packet information via periodic feedback messages as defined in [RTCP-FEEDBACK]. Such an approach enables interoperability amongst senders operating on different congestion control schemes but requires slightly higher overhead in the feedback messages. See additional discussions in [RTCP-FEEDBACK] regarding the desired format of the feedback messages and the recommended feedback intervals.¶

6.5. Incremental Deployment

One nice property of NADA is the consistent video endpoint behavior irrespective of network node variations. This facilitates gradual, incremental adoption of the scheme.¶

Initially, the proposed congestion control mechanism can be implemented without any explicit support from the network and relies solely on observed relative one-way delay measurements and packet loss ratios as implicit congestion signals.¶

When ECN is enabled at the network nodes with RED-based marking, the receiver can fold its observations of ECN markings into the calculation of the equivalent delay. The sender can react to these explicit congestion signals without any modification.¶

Ultimately, networks equipped with proactive marking based on the level of token bucket metering can reap the additional benefits of zero standing queues and lower end-to-end delay and work seamlessly with existing senders and receivers.¶

A.1. Default Behavior of Drop-Tail Queues

In a conventional network with drop-tail or RED queues, congestion is inferred from the estimation of end-to-end delay and/or packet loss. Packet drops at the queue are detected at the receiver and contribute to the calculation of the aggregated congestion signal x_curr. No special action is required at the network node.¶

A.2. RED-Based ECN Marking

In this mode, the network node randomly marks the ECN field in the IP packet header following the Random Early Detection (RED) algorithm [RFC7567]. Calculation of the marking probability involves the following steps on packet arrival:¶

1. update smoothed queue size q_avg as:¶

      q_avg = w*q + (1-w)*q_avg
   

   ¶

2. calculate marking probability p as:¶

           / 0,                    if q < q_lo
           |
           |        q_avg - q_lo
       p= <  p_max*--------------, if q_lo <= q < q_hi
           |         q_hi - q_lo
           |
           \ p = 1,                if q >= q_hi
   

   ¶

Here, q_lo and q_hi correspond to the low and high thresholds of queue occupancy. The maximum marking probability is p_max.¶

The ECN marking events will contribute to the calculation of an equivalent delay x_curr at the receiver. No changes are required at the sender.¶

A.3. Random Early Marking with Virtual Queues

Advanced network nodes may support random early marking based on a token bucket algorithm originally designed for Pre-Congestion Notification (PCN) [RFC6660]. The early congestion notification (ECN) bit in the IP header of packets is marked randomly. The marking probability is calculated based on a token bucket algorithm originally designed for PCN [RFC6660]. The target link utilization is set as 90%; the marking probability is designed to grow linearly with the token bucket size when it varies between 1/3 and 2/3 of the full token bucket limit.¶

Calculation of the marking probability involves the following steps upon packet arrival:¶

1. meter packet against token bucket (r,b)¶

2. update token level b_tk¶

3. calculate the marking probability as:¶

            / 0,                     if b-b_tk < b_lo
            |
            |          b-b_tk-b_lo
       p = <  p_max* --------------, if b_lo <= b-b_tk < b_hi
            |           b_hi-b_lo
            |
            \ 1,                     if b-b_tk >= b_hi
   

   ¶

Here, the token bucket lower and upper limits are denoted by b_lo and b_hi, respectively. The parameter b indicates the size of the token bucket. The parameter r is chosen to be below capacity, resulting in slight underutilization of the link. The maximum marking probability is p_max.¶

The ECN marking events will contribute to the calculation of an equivalent delay x_curr at the receiver. No changes are required at the sender. The virtual queuing mechanism from the PCN-based marking algorithm will lead to additional benefits such as zero standing queues.¶