1 /*
2  * Copyright (c) Facebook, Inc. and its affiliates.
3  *
4  * This source code is licensed under the MIT license found in the
5  * LICENSE file in the root directory of this source tree.
6  *
7  */
8 
9 #pragma once
10 
11 #include <quic/QuicException.h>
12 #include <quic/congestion_control/CongestionControlFunctions.h>
13 
14 #include <quic/state/StateData.h>
15 
16 namespace quic {
17 
18 constexpr float kCubicHystartPacingGain = 2.0f;
19 constexpr float kCubicRecoveryPacingGain = 1.25f;
20 
21 enum class CubicStates : uint8_t {
22   Hystart,
23   Steady,
24   FastRecovery,
25 };
26 
27 /**
28  *
29  *  |--------|                              |-----|
30  *  |      [Ack]                          [Ack]   |
31  *  |        |                              |     |
32  *  -->Hystart------------[Ack]---------->Cubic<--|
33  *        |                                 |     |
34  *        |                                 |     |
35  *        |                ->[ACK/Loss]     |     |
36  *        |                |     |          |     |
37  *        |                |     |          |     |
38  *        -[Loss]---->Fast Recovery<--[Loss]-     |
39  *                             |                  |
40  *                             |                  |
41  *                             |                  |
42  *                             |->-----[Ack]------|
43  *
44  */
45 
46 class Cubic : public CongestionController {
47  public:
48   static constexpr uint64_t INIT_SSTHRESH =
49       std::numeric_limits<uint64_t>::max();
50   /**
51    * initSsthresh:      the initial value of ssthresh
52    * ssreduction:       how should cwnd be reduced when loss happens during slow
53    *                    start
54    * tcpFriendly:       if cubic cwnd calculation should be friendly to Reno TCP
55    * spreadacrossRtt:   if the pacing bursts should be spread across RTT or all
56    *                    close to the beginning of an RTT round
57    */
58   explicit Cubic(
59       QuicConnectionStateBase& conn,
60       uint64_t initCwndBytes = 0,
61       uint64_t initSsthresh = INIT_SSTHRESH,
62       bool tcpFriendly = true,
63       bool ackTrain = false,
64       bool spreadAcrossRtt = false);
65 
66   CubicStates state() const noexcept;
67 
68   enum class ExitReason : uint8_t {
69     SSTHRESH,
70     EXITPOINT,
71   };
72 
73   // if hybrid slow start exit point is found
74   enum class HystartFound : uint8_t {
75     No,
76     FoundByAckTrainMethod,
77     FoundByDelayIncreaseMethod
78   };
79 
80   void onPacketAckOrLoss(folly::Optional<AckEvent>, folly::Optional<LossEvent>)
81       override;
82   void onRemoveBytesFromInflight(uint64_t) override;
83   void onPacketSent(const OutstandingPacket& packet) override;
84 
85   uint64_t getWritableBytes() const noexcept override;
86   uint64_t getCongestionWindow() const noexcept override;
87   void setAppIdle(bool idle, TimePoint eventTime) noexcept override;
88   void setAppLimited() override;
89 
setBandwidthUtilizationFactor(float)90   void setBandwidthUtilizationFactor(
91       float /*bandwidthUtilizationFactor*/) noexcept override {}
92 
isInBackgroundMode()93   bool isInBackgroundMode() const noexcept override {
94     return false;
95   }
96 
97   bool isAppLimited() const noexcept override;
98 
99   void getStats(CongestionControllerStats& stats) const override;
100 
101   void handoff(uint64_t newCwnd, uint64_t newInflight) noexcept;
102 
103   CongestionControlType type() const noexcept override;
104 
105  protected:
106   CubicStates state_{CubicStates::Hystart};
107 
108  private:
109   bool isAppIdle() const noexcept;
110   void onPacketAcked(const AckEvent& ack);
111   void onPacketAckedInHystart(const AckEvent& ack);
112   void onPacketAckedInSteady(const AckEvent& ack);
113   void onPacketAckedInRecovery(const AckEvent& ack);
114 
115   void onPacketLoss(const LossEvent& loss);
116   void onPacketLossInRecovery(const LossEvent& loss);
117   void onPersistentCongestion();
118 
119   float pacingGain() const noexcept;
120 
121   void startHystartRttRound(TimePoint time) noexcept;
122 
123   void cubicReduction(TimePoint lossTime) noexcept;
124   void updateTimeToOrigin() noexcept;
125   int64_t calculateCubicCwndDelta(TimePoint timePoint) noexcept;
126   uint64_t calculateCubicCwnd(int64_t delta) noexcept;
127 
128   bool isRecovered(TimePoint packetSentTime) noexcept;
129 
130   QuicConnectionStateBase& conn_;
131   uint64_t cwndBytes_;
132   // the value of cwndBytes_ at last loss event
133   folly::Optional<uint64_t> lossCwndBytes_;
134   // the value of ssthresh_ at the last loss event
135   folly::Optional<uint64_t> lossSsthresh_;
136   uint64_t ssthresh_;
137 
138   struct HystartState {
139     // If AckTrain method will be used to exit SlowStart
140     bool ackTrain{false};
141     // If we are currently in a RTT round
142     bool inRttRound{false};
143     // If we have found the exit point
144     HystartFound found{HystartFound::No};
145     // The starting timestamp of a RTT round
146     TimePoint roundStart;
147     // Last timestamp when closed space Ack happens
148     TimePoint lastJiffy;
149     // The minimal of sampled RTT in current RTT round. Hystart only samples
150     // first a few RTTs in a round
151     folly::Optional<std::chrono::microseconds> currSampledRtt;
152     // End value of currSampledRtt at the end of a RTT round:
153     folly::Optional<std::chrono::microseconds> lastSampledRtt;
154     // Estimated minimal delay of a path
155     folly::Optional<std::chrono::microseconds> delayMin;
156     // Ack sampling count
157     uint8_t ackCount{0};
158     // When a packet with sent time >= rttRoundEndTarget is acked, end the
159     // current RTT round
160     TimePoint rttRoundEndTarget;
161   };
162 
163   struct SteadyState {
164     // time takes for cwnd to increase to lastMaxCwndBytes
165     double timeToOrigin{0.0};
166     // The cwnd value that timeToOrigin is calculated based on
167     folly::Optional<uint64_t> originPoint;
168     bool tcpFriendly{true};
169     folly::Optional<TimePoint> lastReductionTime;
170     // This is Wmax, it could be different from lossCwndBytes if cwnd never
171     // reaches last lastMaxCwndBytes before loss event:
172     folly::Optional<uint64_t> lastMaxCwndBytes;
173     uint64_t estRenoCwnd;
174     // cache reduction/increase factors based on numEmulatedConnections_
175     float reductionFactor{kDefaultCubicReductionFactor};
176     float lastMaxReductionFactor{kDefaultLastMaxReductionFactor};
177     float tcpEstimationIncreaseFactor{kCubicTCPFriendlyEstimateIncreaseFactor};
178   };
179 
180   struct RecoveryState {
181     // The time point after which Quic will no longer be in current recovery
182     folly::Optional<TimePoint> endOfRecovery;
183   };
184 
185   // if quiescenceStart_ has a value, then the connection is app limited
186   folly::Optional<TimePoint> quiescenceStart_;
187 
188   HystartState hystartState_;
189   SteadyState steadyState_;
190   RecoveryState recoveryState_;
191 
192   // When spreadAcrossRtt_ is set to true, the pacing writes will be distributed
193   // evenly across an RTT. Otherwise, we will use the first N number of pacing
194   // intervals to send all N bursts.
195   bool spreadAcrossRtt_{false};
196 };
197 
198 folly::StringPiece cubicStateToString(CubicStates state);
199 
200 } // namespace quic
201