Home | History | Annotate | Download | only in congestion_control 
      1 // Copyright 2014 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "net/quic/congestion_control/rtt_stats.h"
      6 
      7 namespace net {
      8 
      9 namespace {
     10 
     11 // Default initial rtt used before any samples are received.
     12 const int kInitialRttMs = 100;
     13 const float kAlpha = 0.125f;
     14 const float kOneMinusAlpha = (1 - kAlpha);
     15 const float kBeta = 0.25f;
     16 const float kOneMinusBeta = (1 - kBeta);
     17 const float kHalfWindow = 0.5f;
     18 const float kQuarterWindow = 0.25f;
     19 
     20 }  // namespace
     21 
     22 RttStats::RttStats()
     23     : latest_rtt_(QuicTime::Delta::Zero()),
     24       min_rtt_(QuicTime::Delta::Zero()),
     25       smoothed_rtt_(QuicTime::Delta::Zero()),
     26       mean_deviation_(QuicTime::Delta::Zero()),
     27       initial_rtt_us_(kInitialRttMs * base::Time::kMicrosecondsPerMillisecond),
     28       num_min_rtt_samples_remaining_(0),
     29       recent_min_rtt_window_(QuicTime::Delta::Infinite()) {}
     30 
     31 bool RttStats::HasUpdates() const {
     32   return !smoothed_rtt_.IsZero();
     33 }
     34 
     35 void RttStats::SampleNewRecentMinRtt(uint32 num_samples) {
     36   num_min_rtt_samples_remaining_ = num_samples;
     37   new_min_rtt_ = RttSample();
     38 }
     39 
     40 // Updates the RTT based on a new sample.
     41 void RttStats::UpdateRtt(QuicTime::Delta send_delta,
     42                          QuicTime::Delta ack_delay,
     43                          QuicTime now) {
     44   QuicTime::Delta rtt_sample(QuicTime::Delta::Zero());
     45   if (send_delta > ack_delay) {
     46     rtt_sample = send_delta.Subtract(ack_delay);
     47   } else if (!HasUpdates()) {
     48     // Even though we received information from the peer suggesting
     49     // an invalid (negative) RTT, we can use the send delta as an
     50     // approximation until we get a better estimate.
     51     rtt_sample = send_delta;
     52   }
     53 
     54   if (rtt_sample.IsInfinite() || rtt_sample.IsZero()) {
     55     DVLOG(1) << "Ignoring rtt, because it's "
     56              << (rtt_sample.IsZero() ? "Zero" : "Infinite");
     57     return;
     58   }
     59   // RTT can't be negative.
     60   DCHECK_LT(0, rtt_sample.ToMicroseconds());
     61 
     62   latest_rtt_ = rtt_sample;
     63   // First time call or link delay decreases.
     64   if (min_rtt_.IsZero() || min_rtt_ > rtt_sample) {
     65     min_rtt_ = rtt_sample;
     66   }
     67   UpdateRecentMinRtt(rtt_sample, now);
     68   // First time call.
     69   if (!HasUpdates()) {
     70     smoothed_rtt_ = rtt_sample;
     71     mean_deviation_ = QuicTime::Delta::FromMicroseconds(
     72         rtt_sample.ToMicroseconds() / 2);
     73   } else {
     74     mean_deviation_ = QuicTime::Delta::FromMicroseconds(
     75         kOneMinusBeta * mean_deviation_.ToMicroseconds() +
     76         kBeta * std::abs(smoothed_rtt_.Subtract(rtt_sample).ToMicroseconds()));
     77     smoothed_rtt_ = smoothed_rtt_.Multiply(kOneMinusAlpha).Add(
     78         rtt_sample.Multiply(kAlpha));
     79     DVLOG(1) << "Cubic; smoothed_rtt(us):" << smoothed_rtt_.ToMicroseconds()
     80              << " mean_deviation(us):" << mean_deviation_.ToMicroseconds();
     81   }
     82 }
     83 
     84 void RttStats::UpdateRecentMinRtt(QuicTime::Delta rtt_sample, QuicTime now) {
     85   // Recent min_rtt update.
     86   if (num_min_rtt_samples_remaining_ > 0) {
     87     --num_min_rtt_samples_remaining_;
     88     if (new_min_rtt_.rtt.IsZero() || rtt_sample <= new_min_rtt_.rtt) {
     89       new_min_rtt_ = RttSample(rtt_sample, now);
     90     }
     91     if (num_min_rtt_samples_remaining_ == 0) {
     92       quarter_window_rtt_ = half_window_rtt_ = recent_min_rtt_ = new_min_rtt_;
     93     }
     94   }
     95 
     96   // Update the three recent rtt samples.
     97   if (recent_min_rtt_.rtt.IsZero() || rtt_sample <= recent_min_rtt_.rtt) {
     98     recent_min_rtt_ = RttSample(rtt_sample, now);
     99     quarter_window_rtt_ = half_window_rtt_ = recent_min_rtt_;
    100   } else if (rtt_sample <= half_window_rtt_.rtt) {
    101     half_window_rtt_ = RttSample(rtt_sample, now);
    102     quarter_window_rtt_ = half_window_rtt_;
    103   } else if (rtt_sample <= quarter_window_rtt_.rtt) {
    104     quarter_window_rtt_ = RttSample(rtt_sample, now);
    105   }
    106 
    107   // Expire old min rtt samples.
    108   if (recent_min_rtt_.time < now.Subtract(recent_min_rtt_window_)) {
    109     recent_min_rtt_ = half_window_rtt_;
    110     half_window_rtt_ = quarter_window_rtt_;
    111     quarter_window_rtt_ = RttSample(rtt_sample, now);
    112   } else if (half_window_rtt_.time <
    113       now.Subtract(recent_min_rtt_window_.Multiply(kHalfWindow))) {
    114     half_window_rtt_ = quarter_window_rtt_;
    115     quarter_window_rtt_ = RttSample(rtt_sample, now);
    116   } else if (quarter_window_rtt_.time <
    117       now.Subtract(recent_min_rtt_window_.Multiply(kQuarterWindow))) {
    118     quarter_window_rtt_ = RttSample(rtt_sample, now);
    119   }
    120 }
    121 
    122 QuicTime::Delta RttStats::SmoothedRtt() const {
    123   if (!HasUpdates()) {
    124     return QuicTime::Delta::FromMicroseconds(initial_rtt_us_);
    125   }
    126   return smoothed_rtt_;
    127 }
    128 
    129 }  // namespace net
    130