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 // Cubic algorithm, helper class to TCP cubic. 6 // For details see http://netsrv.csc.ncsu.edu/export/cubic_a_new_tcp_2008.pdf. 7 8 #ifndef NET_QUIC_CONGESTION_CONTROL_CUBIC_H_ 9 #define NET_QUIC_CONGESTION_CONTROL_CUBIC_H_ 10 11 #include "base/basictypes.h" 12 #include "net/base/net_export.h" 13 #include "net/quic/quic_clock.h" 14 #include "net/quic/quic_time.h" 15 16 namespace net { 17 18 // TCP congestion window in QUIC is in packets, not bytes. 19 typedef uint32 QuicTcpCongestionWindow; 20 21 class NET_EXPORT_PRIVATE Cubic { 22 public: 23 explicit Cubic(const QuicClock* clock); 24 25 // Call after a timeout to reset the cubic state. 26 void Reset(); 27 28 // Compute a new congestion window to use after a loss event. 29 // Returns the new congestion window in packets. The new congestion window is 30 // a multiplicative decrease of our current window. 31 QuicTcpCongestionWindow CongestionWindowAfterPacketLoss( 32 QuicTcpCongestionWindow current); 33 34 // Compute a new congestion window to use after a received ACK. 35 // Returns the new congestion window in packets. The new congestion window 36 // follows a cubic function that depends on the time passed since last 37 // packet loss. 38 QuicTcpCongestionWindow CongestionWindowAfterAck( 39 QuicTcpCongestionWindow current, 40 QuicTime::Delta delay_min); 41 42 protected: 43 // Calculates the cubic root using a table lookup followed by one Newton- 44 // Raphson iteration. 45 uint32 CubeRoot(uint64 a); 46 47 private: MaxCubicTimeInterval()48 static const QuicTime::Delta MaxCubicTimeInterval() { 49 return QuicTime::Delta::FromMilliseconds(30); 50 } 51 52 const QuicClock* clock_; 53 54 // Time when this cycle started, after last loss event. 55 QuicTime epoch_; 56 57 // Time when we updated last_congestion_window. 58 QuicTime last_update_time_; 59 60 // Last congestion window (in packets) used. 61 QuicTcpCongestionWindow last_congestion_window_; 62 63 // Max congestion window (in packets) used just before last loss event. 64 // Note: to improve fairness to other streams an additional back off is 65 // applied to this value if the new value is below our latest value. 66 QuicTcpCongestionWindow last_max_congestion_window_; 67 68 // Number of acked packets since the cycle started (epoch). 69 uint32 acked_packets_count_; 70 71 // TCP Reno equivalent congestion window in packets. 72 QuicTcpCongestionWindow estimated_tcp_congestion_window_; 73 74 // Origin point of cubic function. 75 QuicTcpCongestionWindow origin_point_congestion_window_; 76 77 // Time to origin point of cubic function in 2^10 fractions of a second. 78 uint32 time_to_origin_point_; 79 80 // Last congestion window in packets computed by cubic function. 81 QuicTcpCongestionWindow last_target_congestion_window_; 82 83 DISALLOW_COPY_AND_ASSIGN(Cubic); 84 }; 85 86 } // namespace net 87 #endif // NET_QUIC_CONGESTION_CONTROL_CUBIC_H_ 88