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