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 13 namespace net { 14 15 // Constants based on TCP defaults. 16 // The following constants are in 2^10 fractions of a second instead of ms to 17 // allow a 10 shift right to divide. 18 const int kCubeScale = 40; // 1024*1024^3 (first 1024 is from 0.100^3) 19 // where 0.100 is 100 ms which is the scaling 20 // round trip time. 21 const int kCubeCongestionWindowScale = 410; 22 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) / 23 kCubeCongestionWindowScale; 24 const uint32 kBetaSPDY = 939; // Back off factor after loss for SPDY, reduces 25 // the CWND by 1/12th. 26 const uint32 kBetaLastMax = 871; // Additional back off factor after loss for 27 // the stored max value. 28 29 namespace { 30 // Find last bit in a 64-bit word. 31 int FindMostSignificantBit(uint64 x) { 32 if (!x) { 33 return 0; 34 } 35 int r = 0; 36 if (x & 0xffffffff00000000ull) { 37 x >>= 32; 38 r += 32; 39 } 40 if (x & 0xffff0000u) { 41 x >>= 16; 42 r += 16; 43 } 44 if (x & 0xff00u) { 45 x >>= 8; 46 r += 8; 47 } 48 if (x & 0xf0u) { 49 x >>= 4; 50 r += 4; 51 } 52 if (x & 0xcu) { 53 x >>= 2; 54 r += 2; 55 } 56 if (x & 0x02u) { 57 x >>= 1; 58 r++; 59 } 60 if (x & 0x01u) { 61 r++; 62 } 63 return r; 64 } 65 66 // 6 bits table [0..63] 67 const uint32 cube_root_table[] = { 68 0, 54, 54, 54, 118, 118, 118, 118, 123, 129, 134, 138, 143, 147, 151, 69 156, 157, 161, 164, 168, 170, 173, 176, 179, 181, 185, 187, 190, 192, 194, 70 197, 199, 200, 202, 204, 206, 209, 211, 213, 215, 217, 219, 221, 222, 224, 71 225, 227, 229, 231, 232, 234, 236, 237, 239, 240, 242, 244, 245, 246, 248, 72 250, 251, 252, 254 73 }; 74 } // namespace 75 76 Cubic::Cubic(const QuicClock* clock) 77 : clock_(clock), 78 epoch_(QuicTime::Zero()), 79 last_update_time_(QuicTime::Zero()) { 80 Reset(); 81 } 82 83 // Calculate the cube root using a table lookup followed by one Newton-Raphson 84 // iteration. 85 uint32 Cubic::CubeRoot(uint64 a) { 86 uint32 msb = FindMostSignificantBit(a); 87 DCHECK_LE(msb, 64u); 88 89 if (msb < 7) { 90 // MSB in our table. 91 return ((cube_root_table[static_cast<uint32>(a)]) + 31) >> 6; 92 } 93 // MSB 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ... 94 // cubic_shift 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ... 95 uint32 cubic_shift = (msb - 4); 96 cubic_shift = ((cubic_shift * 342) >> 10); // Div by 3, biased high. 97 98 // 4 to 6 bits accuracy depending on MSB. 99 uint32 down_shifted_to_6bit = (a >> (cubic_shift * 3)); 100 uint64 root = ((cube_root_table[down_shifted_to_6bit] + 10) << cubic_shift) 101 >> 6; 102 103 // Make one Newton-Raphson iteration. 104 // Since x has an error (inaccuracy due to the use of fix point) we get a 105 // more accurate result by doing x * (x - 1) instead of x * x. 106 root = 2 * root + (a / (root * (root - 1))); 107 root = ((root * 341) >> 10); // Div by 3, biased low. 108 return static_cast<uint32>(root); 109 } 110 111 void Cubic::Reset() { 112 epoch_ = QuicTime::Zero(); // Reset time. 113 last_update_time_ = QuicTime::Zero(); // Reset time. 114 last_congestion_window_ = 0; 115 last_max_congestion_window_ = 0; 116 acked_packets_count_ = 0; 117 estimated_tcp_congestion_window_ = 0; 118 origin_point_congestion_window_ = 0; 119 time_to_origin_point_ = 0; 120 last_target_congestion_window_ = 0; 121 } 122 123 QuicTcpCongestionWindow Cubic::CongestionWindowAfterPacketLoss( 124 QuicTcpCongestionWindow current_congestion_window) { 125 if (current_congestion_window < last_max_congestion_window_) { 126 // We never reached the old max, so assume we are competing with another 127 // flow. Use our extra back off factor to allow the other flow to go up. 128 last_max_congestion_window_ = 129 (kBetaLastMax * current_congestion_window) >> 10; 130 } else { 131 last_max_congestion_window_ = current_congestion_window; 132 } 133 epoch_ = QuicTime::Zero(); // Reset time. 134 return (current_congestion_window * kBetaSPDY) >> 10; 135 } 136 137 QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck( 138 QuicTcpCongestionWindow current_congestion_window, 139 QuicTime::Delta delay_min) { 140 acked_packets_count_ += 1; // Packets acked. 141 QuicTime current_time = clock_->ApproximateNow(); 142 143 // Cubic is "independent" of RTT, the update is limited by the time elapsed. 144 if (last_congestion_window_ == current_congestion_window && 145 (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) { 146 return std::max(last_target_congestion_window_, 147 estimated_tcp_congestion_window_); 148 } 149 last_congestion_window_ = current_congestion_window; 150 last_update_time_ = current_time; 151 152 if (!epoch_.IsInitialized()) { 153 // First ACK after a loss event. 154 DVLOG(1) << "Start of epoch"; 155 epoch_ = current_time; // Start of epoch. 156 acked_packets_count_ = 1; // Reset count. 157 // Reset estimated_tcp_congestion_window_ to be in sync with cubic. 158 estimated_tcp_congestion_window_ = current_congestion_window; 159 if (last_max_congestion_window_ <= current_congestion_window) { 160 time_to_origin_point_ = 0; 161 origin_point_congestion_window_ = current_congestion_window; 162 } else { 163 time_to_origin_point_ = CubeRoot(kCubeFactor * 164 (last_max_congestion_window_ - current_congestion_window)); 165 origin_point_congestion_window_ = 166 last_max_congestion_window_; 167 } 168 } 169 // Change the time unit from microseconds to 2^10 fractions per second. Take 170 // the round trip time in account. This is done to allow us to use shift as a 171 // divide operator. 172 int64 elapsed_time = 173 (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) / 174 base::Time::kMicrosecondsPerSecond; 175 176 int64 offset = time_to_origin_point_ - elapsed_time; 177 QuicTcpCongestionWindow delta_congestion_window = (kCubeCongestionWindowScale 178 * offset * offset * offset) >> kCubeScale; 179 180 QuicTcpCongestionWindow target_congestion_window = 181 origin_point_congestion_window_ - delta_congestion_window; 182 183 // We have a new cubic congestion window. 184 last_target_congestion_window_ = target_congestion_window; 185 186 // Update estimated TCP congestion_window. 187 // Note: we do a normal Reno congestion avoidance calculation not the 188 // calculation described in section 3.3 TCP-friendly region of the document. 189 while (acked_packets_count_ >= estimated_tcp_congestion_window_) { 190 acked_packets_count_ -= estimated_tcp_congestion_window_; 191 estimated_tcp_congestion_window_++; 192 } 193 // Compute target congestion_window based on cubic target and estimated TCP 194 // congestion_window, use highest (fastest). 195 if (target_congestion_window < estimated_tcp_congestion_window_) { 196 target_congestion_window = estimated_tcp_congestion_window_; 197 } 198 DVLOG(1) << "Target congestion_window:" << target_congestion_window; 199 return target_congestion_window; 200 } 201 202 } // namespace net 203
