1 // Copyright (c) 2013 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/inter_arrival_bitrate_ramp_up.h"
6
7 #include <algorithm>
8
9 #include "base/basictypes.h"
10 #include "base/logging.h"
11 #include "net/quic/congestion_control/cube_root.h"
12 #include "net/quic/quic_protocol.h"
13
14 namespace {
15 // The following constants are in 2^10 fractions of a second instead of ms to
16 // allow a 10 shift right to divide.
17 const int kCubeScale = 40; // 1024*1024^3 (first 1024 is from 0.100^3)
18 // where 0.100 is 100 ms which is the scaling
19 // round trip time.
20 // TODO(pwestin): Tuning parameter, currently close to TCP cubic at 100ms RTT.
21 const int kPacedCubeScale = 6000;
22 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) / kPacedCubeScale;
23 } // namespace
24
25 namespace net {
26
InterArrivalBitrateRampUp(const QuicClock * clock)27 InterArrivalBitrateRampUp::InterArrivalBitrateRampUp(const QuicClock* clock)
28 : clock_(clock),
29 current_rate_(QuicBandwidth::Zero()),
30 channel_estimate_(QuicBandwidth::Zero()),
31 available_channel_estimate_(QuicBandwidth::Zero()),
32 halfway_point_(QuicBandwidth::Zero()),
33 epoch_(QuicTime::Zero()),
34 last_update_time_(QuicTime::Zero()) {
35 }
36
Reset(QuicBandwidth new_rate,QuicBandwidth available_channel_estimate,QuicBandwidth channel_estimate)37 void InterArrivalBitrateRampUp::Reset(QuicBandwidth new_rate,
38 QuicBandwidth available_channel_estimate,
39 QuicBandwidth channel_estimate) {
40 epoch_ = clock_->ApproximateNow();
41 last_update_time_ = epoch_;
42 available_channel_estimate_ = std::max(new_rate, available_channel_estimate);
43 channel_estimate_ = std::max(channel_estimate, available_channel_estimate_);
44
45 halfway_point_ = available_channel_estimate_.Add(
46 (channel_estimate_.Subtract(available_channel_estimate_)).Scale(0.5f));
47
48 if (new_rate < available_channel_estimate_) {
49 time_to_origin_point_ = CalcuateTimeToOriginPoint(
50 available_channel_estimate_.Subtract(new_rate));
51 } else if (new_rate >= channel_estimate_) {
52 time_to_origin_point_ = 0;
53 } else if (new_rate >= halfway_point_) {
54 time_to_origin_point_ =
55 CalcuateTimeToOriginPoint(channel_estimate_.Subtract(new_rate));
56 } else {
57 time_to_origin_point_ = CalcuateTimeToOriginPoint(
58 new_rate.Subtract(available_channel_estimate_));
59 }
60 current_rate_ = new_rate;
61 DVLOG(1) << "Reset; time to origin point:" << time_to_origin_point_;
62 }
63
UpdateChannelEstimate(QuicBandwidth channel_estimate)64 void InterArrivalBitrateRampUp::UpdateChannelEstimate(
65 QuicBandwidth channel_estimate) {
66 if (available_channel_estimate_ > channel_estimate ||
67 current_rate_ > channel_estimate ||
68 channel_estimate_ == channel_estimate) {
69 // Ignore, because one of the following reasons:
70 // 1) channel estimate is bellow our current available estimate which we
71 // value higher that this estimate.
72 // 2) channel estimate is bellow our current send rate.
73 // 3) channel estimate has not changed.
74 return;
75 }
76 if (available_channel_estimate_ == halfway_point_ &&
77 channel_estimate_ == halfway_point_) {
78 // First time we get a usable channel estimate.
79 channel_estimate_ = channel_estimate;
80 halfway_point_ = available_channel_estimate_.Add(
81 (channel_estimate_.Subtract(available_channel_estimate_).Scale(0.5f)));
82 DVLOG(1) << "UpdateChannelEstimate; first usable value:"
83 << channel_estimate.ToKBitsPerSecond() << " Kbits/s";
84 return;
85 }
86 if (current_rate_ < halfway_point_) {
87 // Update channel estimate without recalculating if we are bellow the
88 // halfway point.
89 channel_estimate_ = channel_estimate;
90 return;
91 }
92 // We are between halfway point and our channel_estimate.
93 epoch_ = clock_->ApproximateNow();
94 last_update_time_ = epoch_;
95 channel_estimate_ = channel_estimate;
96
97 time_to_origin_point_ =
98 CalcuateTimeToOriginPoint(channel_estimate_.Subtract(current_rate_));
99
100 DVLOG(1) << "UpdateChannelEstimate; time to origin point:"
101 << time_to_origin_point_;
102 }
103
GetNewBitrate(QuicBandwidth sent_bitrate)104 QuicBandwidth InterArrivalBitrateRampUp::GetNewBitrate(
105 QuicBandwidth sent_bitrate) {
106 DCHECK(epoch_.IsInitialized());
107 QuicTime current_time = clock_->ApproximateNow();
108 // Cubic is "independent" of RTT, the update is limited by the time elapsed.
109 if (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval()) {
110 return current_rate_;
111 }
112 QuicTime::Delta time_from_last_update =
113 current_time.Subtract(last_update_time_);
114
115 last_update_time_ = current_time;
116
117 if (!sent_bitrate.IsZero() &&
118 sent_bitrate.Add(sent_bitrate) < current_rate_) {
119 // Don't go up in bitrate when we are not sending.
120 // We need to update the epoch to reflect this state.
121 epoch_ = epoch_.Add(time_from_last_update);
122 DVLOG(1) << "Don't increase; our sent bitrate is:"
123 << sent_bitrate.ToKBitsPerSecond() << " Kbits/s"
124 << " current target rate is:"
125 << current_rate_.ToKBitsPerSecond() << " Kbits/s";
126 return current_rate_;
127 }
128 QuicTime::Delta time_from_epoch = current_time.Subtract(epoch_);
129
130 // Change the time unit from microseconds to 2^10 fractions per second. This
131 // is done to allow us to use shift as a divide operator.
132 int64 elapsed_time = (time_from_epoch.ToMicroseconds() << 10) /
133 kNumMicrosPerSecond;
134
135 int64 offset = time_to_origin_point_ - elapsed_time;
136 // Note: using int64 since QuicBandwidth can't be negative
137 int64 delta_pace_kbps = (kPacedCubeScale * offset * offset * offset) >>
138 kCubeScale;
139
140 bool start_bellow_halfway_point = false;
141 if (current_rate_ < halfway_point_) {
142 start_bellow_halfway_point = true;
143
144 // available_channel_estimate_ is the orgin of the cubic function.
145 QuicBandwidth current_rate = QuicBandwidth::FromBytesPerSecond(
146 available_channel_estimate_.ToBytesPerSecond() -
147 (delta_pace_kbps << 10));
148
149 if (start_bellow_halfway_point && current_rate >= halfway_point_) {
150 // We passed the halfway point, recalculate with new orgin.
151 epoch_ = clock_->ApproximateNow();
152 // channel_estimate_ is the new orgin of the cubic function.
153 if (current_rate >= channel_estimate_) {
154 time_to_origin_point_ = 0;
155 } else {
156 time_to_origin_point_ =
157 CalcuateTimeToOriginPoint(channel_estimate_.Subtract(current_rate));
158 }
159 DVLOG(1) << "Passed the halfway point; time to origin point:"
160 << time_to_origin_point_;
161 }
162 current_rate_ = current_rate;
163 } else {
164 // channel_estimate_ is the orgin of the cubic function.
165 current_rate_ = QuicBandwidth::FromBytesPerSecond(
166 channel_estimate_.ToBytesPerSecond() - (delta_pace_kbps << 10));
167 }
168 return current_rate_;
169 }
170
CalcuateTimeToOriginPoint(QuicBandwidth rate_difference) const171 uint32 InterArrivalBitrateRampUp::CalcuateTimeToOriginPoint(
172 QuicBandwidth rate_difference) const {
173 return CubeRoot::Root(kCubeFactor * rate_difference.ToKBytesPerSecond());
174 }
175
176 } // namespace net
177