Congestion and Queuing Control for Real-Time Communication

Congestion and queuing control for Real-Time media communication (Video-conferencing, Voice over IP) over the Internet has been addressed in IETF and W3C bodies aiming at standardizing a set of inter-operable protocols and APIs to enable real-time communication between Web browsers.

The IETF working group (WG) RTP Media Congestion Avoidance Techniques (RMCAT) was established in 2012 to propose the standardization of congestion control algorithms using the RTP. A congestion control algorithm for Web Real-time Communication (WebRTC) has been developed.

The proposed algorithm is used in Google Chrome and in the WebRTC open-source framework.

Google Faculty Research Award

A description of the algorithm is provided in the IETF RMACT draft and in a paper published in the IEEE/ACM Transactions on Networking:

• S. Holmer, H. Lundin, G. Carlucci, L. De Cicco, and S. Mascolo. A Google Congestion Control Algorithm for Real-Time Communication. IETF draft RMCAT wg, draft-ietf-rmcat-gcc-01, Oct 2015 (Web: Link)
• G. Carlucci, L. De Cicco, S. Holmer, and S. Mascolo. Congestion Control for Web Real-Time Communication. IEEE/ACM Transactions on Networking, vol. 25, no. 5, pp. 2629-2642, Oct. 2017. doi: 10.1109/TNET.2017.2703615 (DOI)

Google Congestion Control for WebRTC

WebRTC Sender and Receiver

Nowadays, the Internet is rapidly evolving to become an equally efficient platform for multimedia content delivery. Key examples are YouTube, Skype Audio/Video, IPTV, and P2P video distribution platforms such as Coolstreaming or Joost. While YouTube streams videos using the Transmission Control Protocol (TCP), time-sensitive applications such as Video Conferencing employ the UDP because they can tolerate small loss percentages but not delays due to TCP recovery of losses via retransmissions. Since the UDP does not implement congestion control, these applications must implement those functionalities at the application layer.

In these papers, we experimentally evaluate the Google Congestion Control (GCC) proposed in the RMCAT IETF WG. By setting up a controlled testbed, we have evaluated to what extent GCC flows can track the available bandwidth while minimizing queuing delays, and fairly share the bottleneck with other GCC or TCP flows. We have found that the algorithm works as expected when a GCC flow accesses the bottleneck in isolation. However, GCC does not provide a fair bandwidth utilization when a GCC flow shares the bottleneck with either a GCC or a TCP flow.

• L. De Cicco, G. Carlucci, and S. Mascolo. Understanding the Dynamic Behaviour of the Google Congestion Control for RTCWeb. Packet Video Workshop, San Jose, CA, USA, 2013 (DOI)
• L. De Cicco, G. Carlucci, and S. Mascolo. Experimental Investigation of the Google Congestion Control for Real-Time Flows. ACM SIGCOMM 2013 Workshop on Future Human-Centric Multimedia Networking, Hong Kong, China, August 2013 (PDF)

GCC Architecture

Experiments

Our experimental investigation has shown that the first version of GCC gets starved when a TCP flow joins the bottleneck (see Fig. below (a)). Moreover, we have found that starvation also occurs when two coexisting GCC flows share a bottleneck (see Fig. below (b) (c)).

To overcome these issues, we have proposed the adaptive threshold mechanism which sets the threshold used by the over-use detector. More details can be found in the following papers:

• G. Carlucci, L. De Cicco, S. Holmer, and S. Mascolo. Congestion Control for Web Real-Time Communication. IEEE/ACM Transactions on Networking, vol. 25, no. 5, pp. 2629-2642, Oct. 2017. doi: 10.1109/TNET.2017.2703615 (DOI)
• G. Carlucci, L. De Cicco, S. Holmer, and S. Mascolo. Analysis and Design of the Google Congestion Control for Web Real-time Communication (WebRTC). Proc. ACM Mmsys 2016, Klagenfurt, Austria, May 2016 (DOI)
• Gaetano Carlucci, Luca De Cicco, Saverio Mascolo. Modelling and Control for Web Real-Time Communication. Proc. of 53rd IEEE Conference on Decision and Control, Los Angeles, California, USA, December 2014 (DOI)

The figure below shows how rate flow dynamics along with one-way delay variations are nicely set after the introduction of the adaptive threshold.

Implementation Details

The OveruseEstimator code is available here. The method Update using a Kalman filter described in the papers above filters the one-way delay variation and the link capacity values.

void OveruseEstimator::Update(int64_t t_delta,
                              double ts_delta,
                              int size_delta,
                              BandwidthUsage current_hypothesis,
                              int64_t now_ms) {
  const double min_frame_period = UpdateMinFramePeriod(ts_delta);
  const double t_ts_delta = t_delta - ts_delta;
  double fs_delta = size_delta;

  ++num_of_deltas_;
  if (num_of_deltas_ > kDeltaCounterMax) {
    num_of_deltas_ = kDeltaCounterMax;
  }

  // Update the Kalman filter.
  E_[0][0] += process_noise_[0];
  E_[1][1] += process_noise_[1];

  if ((current_hypothesis == BandwidthUsage::kBwOverusing &&
       offset_ < prev_offset_) ||
      (current_hypothesis == BandwidthUsage::kBwUnderusing &&
       offset_ > prev_offset_)) {
    E_[1][1] += 10 * process_noise_[1];
  }

  const double h[2] = {fs_delta, 1.0};
  const double Eh[2] = {E_[0][0] * h[0] + E_[0][1] * h[1],
                        E_[1][0] * h[0] + E_[1][1] * h[1]};

  const double residual = t_ts_delta - slope_ * h[0] - offset_;

  const bool in_stable_state =
      (current_hypothesis == BandwidthUsage::kBwNormal);
  const double max_residual = 3.0 * sqrt(var_noise_);
  // We try to filter out very late frames. For instance periodic key
  // frames doesn't fit the Gaussian model well.
  if (fabs(residual) < max_residual) {
    UpdateNoiseEstimate(residual, min_frame_period, in_stable_state);
  } else {
    UpdateNoiseEstimate(residual < 0 ? -max_residual : max_residual,
                        min_frame_period, in_stable_state);
  }

  const double denom = var_noise_ + h[0] * Eh[0] + h[1] * Eh[1];

  const double K[2] = {Eh[0] / denom, Eh[1] / denom};

  const double IKh[2][2] = {{1.0 - K[0] * h[0], -K[0] * h[1]},
                            {-K[1] * h[0], 1.0 - K[1] * h[1]}};
  const double e00 = E_[0][0];
  const double e01 = E_[0][1];

  // Update state.
  E_[0][0] = e00 * IKh[0][0] + E_[1][0] * IKh[0][1];
  E_[0][1] = e01 * IKh[0][0] + E_[1][1] * IKh[0][1];
  E_[1][0] = e00 * IKh[1][0] + E_[1][0] * IKh[1][1];
  E_[1][1] = e01 * IKh[1][0] + E_[1][1] * IKh[1][1];

  // The covariance matrix must be positive semi-definite.
  bool positive_semi_definite =
      E_[0][0] + E_[1][1] >= 0 &&
      E_[0][0] * E_[1][1] - E_[0][1] * E_[1][0] >= 0 && E_[0][0] >= 0;
  RTC_DCHECK(positive_semi_definite);
  if (!positive_semi_definite) {
    RTC_LOG(LS_ERROR)
        << "The over-use estimator's covariance matrix is no longer "
           "semi-definite.";
  }

  slope_ = slope_ + K[0] * residual;
  prev_offset_ = offset_;
  offset_ = offset_ + K[1] * residual;
}

The OveruseDetector code is available here. The method Detect checks if the filtered one-way delay variation is above the threshold. These events drive the finite state machine that controls the encoding bitrate.

BandwidthUsage OveruseDetector::Detect(double offset,
                                       double ts_delta,
                                       int num_of_deltas,
                                       int64_t now_ms) {
  if (num_of_deltas < 2) {
    return BandwidthUsage::kBwNormal;
  }
  const double T = std::min(num_of_deltas, kMaxNumDeltas) * offset;
  if (T > threshold_) {
    if (time_over_using_ == -1) {
      // Initialize the timer. Assume that we've been
      // over-using half of the time since the previous
      // sample.
      time_over_using_ = ts_delta / 2;
    } else {
      // Increment timer
      time_over_using_ += ts_delta;
    }
    overuse_counter_++;
    if (time_over_using_ > kOverUsingTimeThreshold && overuse_counter_ > 1) {
      if (offset >= prev_offset_) {
        time_over_using_ = 0;
        overuse_counter_ = 0;
        hypothesis_ = BandwidthUsage::kBwOverusing;
      }
    }
  } else if (T < -threshold_) {
    time_over_using_ = -1;
    overuse_counter_ = 0;
    hypothesis_ = BandwidthUsage::kBwUnderusing;
  } else {
    time_over_using_ = -1;
    overuse_counter_ = 0;
    hypothesis_ = BandwidthUsage::kBwNormal;
  }
  prev_offset_ = offset;

  UpdateThreshold(T, now_ms);

  return hypothesis_;
}

The method UpdateThreshold adapts the threshold according to the papers above. Code is available here.

void OveruseDetector::UpdateThreshold(double modified_offset, int64_t now_ms) {
  if (last_update_ms_ == -1)
    last_update_ms_ = now_ms;

  if (fabs(modified_offset) > threshold_ + kMaxAdaptOffsetMs) {
    // Avoid adapting the threshold to big latency spikes, caused e.g.,
    // by a sudden capacity drop.
    last_update_ms_ = now_ms;
    return;
  }

  const double k = fabs(modified_offset) < threshold_ ? kDown : kUp;
  const int64_t kMaxTimeDeltaMs = 100;
  int64_t time_delta_ms = std::min(now_ms - last_update_ms_, kMaxTimeDeltaMs);
  threshold_ += k * (fabs(modified_offset) - threshold_) * time_delta_ms;
  threshold_ = rtc::SafeClamp(threshold_, 6.f, 600.f);
  last_update_ms_ = now_ms;
}

Chromium Patches

These are the patches we have made to the chromium code base.

• https://codereview.webrtc.org/1151603008
• https://codereview.chromium.org/1383813003

Get Involved

Here are some ways you can get involved with Chromium:

• Life of a Chromium Developer
• For Developers