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
9using std::max;
10
11namespace net {
12
13namespace {
14
15// Default initial rtt used before any samples are received.
16const int kInitialRttMs = 100;
17const float kAlpha = 0.125f;
18const float kOneMinusAlpha = (1 - kAlpha);
19const float kBeta = 0.25f;
20const float kOneMinusBeta = (1 - kBeta);
21const float kHalfWindow = 0.5f;
22const float kQuarterWindow = 0.25f;
23
24}  // namespace
25
26RttStats::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
35bool RttStats::HasUpdates() const {
36  return !smoothed_rtt_.IsZero();
37}
38
39void RttStats::SampleNewRecentMinRtt(uint32 num_samples) {
40  num_min_rtt_samples_remaining_ = num_samples;
41  new_min_rtt_ = RttSample();
42}
43
44void 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.
53void 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
96void 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
134QuicTime::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