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