Home | History | Annotate | Download | only in congestion_control 
      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:
     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