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