1// Copyright (c) 2012 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/cubic.h"
6
7#include <algorithm>
8
9#include "base/basictypes.h"
10#include "base/logging.h"
11#include "base/time/time.h"
12#include "net/quic/congestion_control/cube_root.h"
13#include "net/quic/quic_protocol.h"
14
15using std::max;
16
17namespace net {
18
19namespace {
20
21// Constants based on TCP defaults.
22// The following constants are in 2^10 fractions of a second instead of ms to
23// allow a 10 shift right to divide.
24const int kCubeScale = 40;  // 1024*1024^3 (first 1024 is from 0.100^3)
25                            // where 0.100 is 100 ms which is the scaling
26                            // round trip time.
27const int kCubeCongestionWindowScale = 410;
28const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) /
29    kCubeCongestionWindowScale;
30
31const uint32 kNumConnections = 2;
32const float kBeta = 0.7f;  // Default Cubic backoff factor.
33// Additional backoff factor when loss occurs in the concave part of the Cubic
34// curve. This additional backoff factor is expected to give up bandwidth to
35// new concurrent flows and speed up convergence.
36const float kBetaLastMax = 0.85f;
37
38// kNConnectionBeta is the backoff factor after loss for our N-connection
39// emulation, which emulates the effective backoff of an ensemble of N TCP-Reno
40// connections on a single loss event. The effective multiplier is computed as:
41const float kNConnectionBeta = (kNumConnections - 1 + kBeta) / kNumConnections;
42
43// TCPFriendly alpha is described in Section 3.3 of the CUBIC paper. Note that
44// kBeta here is a cwnd multiplier, and is equal to 1-beta from the CUBIC paper.
45// We derive the equivalent kNConnectionAlpha for an N-connection emulation as:
46const float kNConnectionAlpha = 3 * kNumConnections * kNumConnections *
47      (1 - kNConnectionBeta) / (1 + kNConnectionBeta);
48// TODO(jri): Compute kNConnectionBeta and kNConnectionAlpha from
49// number of active streams.
50
51}  // namespace
52
53Cubic::Cubic(const QuicClock* clock, QuicConnectionStats* stats)
54    : clock_(clock),
55      epoch_(QuicTime::Zero()),
56      last_update_time_(QuicTime::Zero()),
57      stats_(stats) {
58  Reset();
59}
60
61void Cubic::Reset() {
62  epoch_ = QuicTime::Zero();  // Reset time.
63  last_update_time_ = QuicTime::Zero();  // Reset time.
64  last_congestion_window_ = 0;
65  last_max_congestion_window_ = 0;
66  acked_packets_count_ = 0;
67  estimated_tcp_congestion_window_ = 0;
68  origin_point_congestion_window_ = 0;
69  time_to_origin_point_ = 0;
70  last_target_congestion_window_ = 0;
71}
72
73void Cubic::UpdateCongestionControlStats(
74    QuicTcpCongestionWindow new_cubic_mode_cwnd,
75    QuicTcpCongestionWindow new_reno_mode_cwnd) {
76
77  QuicTcpCongestionWindow highest_new_cwnd = std::max(new_cubic_mode_cwnd,
78                                                      new_reno_mode_cwnd);
79  if (last_congestion_window_ < highest_new_cwnd) {
80    // cwnd will increase to highest_new_cwnd.
81    stats_->cwnd_increase_congestion_avoidance +=
82        highest_new_cwnd - last_congestion_window_;
83    if (new_cubic_mode_cwnd > new_reno_mode_cwnd) {
84      // This cwnd increase is due to cubic mode.
85      stats_->cwnd_increase_cubic_mode +=
86          new_cubic_mode_cwnd - last_congestion_window_;
87    }
88  }
89}
90
91QuicTcpCongestionWindow Cubic::CongestionWindowAfterPacketLoss(
92    QuicTcpCongestionWindow current_congestion_window) {
93  if (current_congestion_window < last_max_congestion_window_) {
94    // We never reached the old max, so assume we are competing with another
95    // flow. Use our extra back off factor to allow the other flow to go up.
96    last_max_congestion_window_ =
97        static_cast<int>(kBetaLastMax * current_congestion_window);
98  } else {
99    last_max_congestion_window_ = current_congestion_window;
100  }
101  epoch_ = QuicTime::Zero();  // Reset time.
102  return static_cast<int>(current_congestion_window * kNConnectionBeta);
103}
104
105QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck(
106    QuicTcpCongestionWindow current_congestion_window,
107    QuicTime::Delta delay_min) {
108  acked_packets_count_ += 1;  // Packets acked.
109  QuicTime current_time = clock_->ApproximateNow();
110
111  // Cubic is "independent" of RTT, the update is limited by the time elapsed.
112  if (last_congestion_window_ == current_congestion_window &&
113      (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) {
114    return max(last_target_congestion_window_,
115               estimated_tcp_congestion_window_);
116  }
117  last_congestion_window_ = current_congestion_window;
118  last_update_time_ = current_time;
119
120  if (!epoch_.IsInitialized()) {
121    // First ACK after a loss event.
122    DVLOG(1) << "Start of epoch";
123    epoch_ = current_time;  // Start of epoch.
124    acked_packets_count_ = 1;  // Reset count.
125    // Reset estimated_tcp_congestion_window_ to be in sync with cubic.
126    estimated_tcp_congestion_window_ = current_congestion_window;
127    if (last_max_congestion_window_ <= current_congestion_window) {
128      time_to_origin_point_ = 0;
129      origin_point_congestion_window_ = current_congestion_window;
130    } else {
131      time_to_origin_point_ = CubeRoot::Root(kCubeFactor *
132          (last_max_congestion_window_ - current_congestion_window));
133      origin_point_congestion_window_ =
134          last_max_congestion_window_;
135    }
136  }
137  // Change the time unit from microseconds to 2^10 fractions per second. Take
138  // the round trip time in account. This is done to allow us to use shift as a
139  // divide operator.
140  int64 elapsed_time =
141      (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) /
142      base::Time::kMicrosecondsPerSecond;
143
144  int64 offset = time_to_origin_point_ - elapsed_time;
145  QuicTcpCongestionWindow delta_congestion_window = (kCubeCongestionWindowScale
146      * offset * offset * offset) >> kCubeScale;
147
148  QuicTcpCongestionWindow target_congestion_window =
149      origin_point_congestion_window_ - delta_congestion_window;
150
151  DCHECK_LT(0u, estimated_tcp_congestion_window_);
152  // With dynamic beta/alpha based on number of active streams, it is possible
153  // for the required_ack_count to become much lower than acked_packets_count_
154  // suddenly, leading to more than one iteration through the following loop.
155  while (true) {
156    // Update estimated TCP congestion_window.
157    uint32 required_ack_count =
158        estimated_tcp_congestion_window_ / kNConnectionAlpha;
159    if (acked_packets_count_ < required_ack_count) {
160      break;
161    }
162    acked_packets_count_ -= required_ack_count;
163    estimated_tcp_congestion_window_++;
164  }
165
166  // Update cubic mode and reno mode stats in QuicConnectionStats.
167  UpdateCongestionControlStats(target_congestion_window,
168                               estimated_tcp_congestion_window_);
169
170  // We have a new cubic congestion window.
171  last_target_congestion_window_ = target_congestion_window;
172
173  // Compute target congestion_window based on cubic target and estimated TCP
174  // congestion_window, use highest (fastest).
175  if (target_congestion_window < estimated_tcp_congestion_window_) {
176    target_congestion_window = estimated_tcp_congestion_window_;
177  }
178
179  DVLOG(1) << "Target congestion_window: " << target_congestion_window;
180  return target_congestion_window;
181}
182
183}  // namespace net
184