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 #include <quic/congestion_control/QuicCubic.h>
10
11 #include <quic/congestion_control/CongestionControlFunctions.h>
12 #include <quic/logging/QLoggerConstants.h>
13 #include <quic/state/QuicStateFunctions.h>
14
15 #include <folly/Chrono.h>
16
17 namespace quic {
18
Cubic(QuicConnectionStateBase & conn,uint64_t initCwndBytes,uint64_t initSsthresh,bool tcpFriendly,bool ackTrain,bool spreadAcrossRtt)19 Cubic::Cubic(
20 QuicConnectionStateBase& conn,
21 uint64_t initCwndBytes,
22 uint64_t initSsthresh,
23 bool tcpFriendly,
24 bool ackTrain,
25 bool spreadAcrossRtt)
26 : conn_(conn), ssthresh_(initSsthresh), spreadAcrossRtt_(spreadAcrossRtt) {
27 cwndBytes_ = std::min(
28 conn.transportSettings.maxCwndInMss * conn.udpSendPacketLen,
29 std::max(
30 initCwndBytes,
31 conn.transportSettings.initCwndInMss * conn.udpSendPacketLen));
32 steadyState_.tcpFriendly = tcpFriendly;
33 steadyState_.estRenoCwnd = cwndBytes_;
34 hystartState_.ackTrain = ackTrain;
35 if (conn_.qLogger) {
36 conn_.qLogger->addCongestionMetricUpdate(
37 conn_.lossState.inflightBytes,
38 cwndBytes_,
39 kCubicInit,
40 cubicStateToString(state_).str());
41 }
42 }
43
state() const44 CubicStates Cubic::state() const noexcept {
45 return state_;
46 }
47
getWritableBytes() const48 uint64_t Cubic::getWritableBytes() const noexcept {
49 return cwndBytes_ > conn_.lossState.inflightBytes
50 ? cwndBytes_ - conn_.lossState.inflightBytes
51 : 0;
52 }
53
handoff(uint64_t newCwnd,uint64_t newInflight)54 void Cubic::handoff(uint64_t newCwnd, uint64_t newInflight) noexcept {
55 cwndBytes_ = newCwnd;
56 // inflightBytes_ = newInflight;
57 conn_.lossState.inflightBytes = newInflight;
58 state_ = CubicStates::Steady;
59 }
60
getCongestionWindow() const61 uint64_t Cubic::getCongestionWindow() const noexcept {
62 return cwndBytes_;
63 }
64
65 /**
66 * TODO: onPersistentCongestion entirely depends on how long a loss period is,
67 * not how much a sender sends during that period. If the connection is app
68 * limited and loss happens after that, it looks like a long loss period but it
69 * may not really be a persistent congestion. However, to keep this code simple,
70 * we decide to just ignore app limited state right now.
71 */
onPersistentCongestion()72 void Cubic::onPersistentCongestion() {
73 auto minCwnd = conn_.transportSettings.minCwndInMss * conn_.udpSendPacketLen;
74 ssthresh_ = std::max(cwndBytes_ / 2, minCwnd);
75 cwndBytes_ = minCwnd;
76 if (steadyState_.tcpFriendly) {
77 steadyState_.estRenoCwnd = 0;
78 }
79 steadyState_.lastReductionTime = folly::none;
80 steadyState_.lastMaxCwndBytes = folly::none;
81 quiescenceStart_ = folly::none;
82 hystartState_.found = Cubic::HystartFound::No;
83 hystartState_.inRttRound = false;
84
85 state_ = CubicStates::Hystart;
86
87 if (conn_.qLogger) {
88 conn_.qLogger->addCongestionMetricUpdate(
89 conn_.lossState.inflightBytes,
90 getCongestionWindow(),
91 kPersistentCongestion,
92 cubicStateToString(state_).str());
93 }
94 }
95
onPacketSent(const OutstandingPacket & packet)96 void Cubic::onPacketSent(const OutstandingPacket& packet) {
97 if (std::numeric_limits<uint64_t>::max() - conn_.lossState.inflightBytes <
98 packet.metadata.encodedSize) {
99 throw QuicInternalException(
100 "Cubic: inflightBytes overflow",
101 LocalErrorCode::INFLIGHT_BYTES_OVERFLOW);
102 }
103 conn_.lossState.inflightBytes += packet.metadata.encodedSize;
104 }
105
onPacketLoss(const LossEvent & loss)106 void Cubic::onPacketLoss(const LossEvent& loss) {
107 quiescenceStart_ = folly::none;
108 DCHECK(
109 loss.largestLostPacketNum.has_value() &&
110 loss.largestLostSentTime.has_value());
111 onRemoveBytesFromInflight(loss.lostBytes);
112 // If the loss occurred past the endOfRecovery then we need to move the
113 // endOfRecovery back and invoke the state machine, otherwise ignore the loss
114 // as it was already accounted for in a recovery period.
115 if (*loss.largestLostSentTime >=
116 recoveryState_.endOfRecovery.value_or(*loss.largestLostSentTime)) {
117 recoveryState_.endOfRecovery = Clock::now();
118 cubicReduction(loss.lossTime);
119 if (state_ == CubicStates::Hystart || state_ == CubicStates::Steady) {
120 state_ = CubicStates::FastRecovery;
121 }
122 ssthresh_ = cwndBytes_;
123 if (conn_.pacer) {
124 conn_.pacer->refreshPacingRate(
125 cwndBytes_ * pacingGain(), conn_.lossState.srtt);
126 }
127 if (conn_.qLogger) {
128 conn_.qLogger->addCongestionMetricUpdate(
129 conn_.lossState.inflightBytes,
130 getCongestionWindow(),
131 kCubicLoss,
132 cubicStateToString(state_).str());
133 }
134
135 } else {
136 if (conn_.qLogger) {
137 conn_.qLogger->addCongestionMetricUpdate(
138 conn_.lossState.inflightBytes,
139 getCongestionWindow(),
140 kCubicSkipLoss,
141 cubicStateToString(state_).str());
142 }
143 }
144
145 if (loss.persistentCongestion) {
146 onPersistentCongestion();
147 }
148 }
149
onRemoveBytesFromInflight(uint64_t bytes)150 void Cubic::onRemoveBytesFromInflight(uint64_t bytes) {
151 DCHECK_LE(bytes, conn_.lossState.inflightBytes);
152 conn_.lossState.inflightBytes -= bytes;
153 if (conn_.qLogger) {
154 conn_.qLogger->addCongestionMetricUpdate(
155 conn_.lossState.inflightBytes,
156 getCongestionWindow(),
157 kRemoveInflight,
158 cubicStateToString(state_).str());
159 }
160 }
161
setAppIdle(bool idle,TimePoint eventTime)162 void Cubic::setAppIdle(bool idle, TimePoint eventTime) noexcept {
163 if (conn_.qLogger) {
164 conn_.qLogger->addAppIdleUpdate(kAppIdle, idle);
165 }
166 bool currentAppIdle = isAppIdle();
167 if (!currentAppIdle && idle) {
168 quiescenceStart_ = eventTime;
169 }
170 if (!idle && currentAppIdle && *quiescenceStart_ <= eventTime &&
171 steadyState_.lastReductionTime) {
172 *steadyState_.lastReductionTime +=
173 folly::chrono::ceil<std::chrono::milliseconds>(
174 eventTime - *quiescenceStart_);
175 }
176 if (!idle) {
177 quiescenceStart_ = folly::none;
178 }
179 }
180
setAppLimited()181 void Cubic::setAppLimited() {
182 // we use app-idle for Cubic
183 }
184
isAppLimited() const185 bool Cubic::isAppLimited() const noexcept {
186 // Or maybe always false. This doesn't really matter for Cubic. Channeling
187 // isAppIdle() makes testing easier.
188 return isAppIdle();
189 }
190
isAppIdle() const191 bool Cubic::isAppIdle() const noexcept {
192 return quiescenceStart_.has_value();
193 }
194
updateTimeToOrigin()195 void Cubic::updateTimeToOrigin() noexcept {
196 // TODO: is there a faster way to do cbrt? We should benchmark a few
197 // alternatives.
198 // TODO: there is a tradeoff between precalculate and cache the result of
199 // kDefaultCubicReductionFactor / kTimeScalingFactor, and calculate it every
200 // time, as multiplication before division may be a little more accurate.
201 // TODO: both kDefaultCubicReductionFactor and kTimeScalingFactor are <1.
202 // The following calculation can be converted to pure integer calculation if
203 // we change the equation a bit to remove all decimals. It's also possible
204 // to remove the cbrt calculation by changing the equation.
205 if (conn_.qLogger) {
206 conn_.qLogger->addTransportStateUpdate(kRecalculateTimeToOrigin);
207 }
208 if (*steadyState_.lastMaxCwndBytes <= cwndBytes_) {
209 steadyState_.timeToOrigin = 0.0;
210 steadyState_.originPoint = steadyState_.lastMaxCwndBytes;
211 return;
212 }
213 // TODO: instead of multiplying by 1000 three times, Chromium shifts by 30
214 // for this calculation, which loss a little bit of precision. We probably
215 // should also consider that tradeoff.
216 /**
217 * The unit of timeToOrigin result from the the Cubic paper is in seconds.
218 * We want milliseconds, thus multiply by 1000 ^ 3 before take cbrt.
219 * We tweak Cubic a bit here. In this code, timeToOrigin is defined as time it
220 * takes to grow cwnd from backoffTarget to lastMaxCwndBytes * reductionFactor
221 */
222 // 2500 = kTimeScalingFactor * 1000
223 auto bytesToOrigin = *steadyState_.lastMaxCwndBytes - cwndBytes_;
224 if (bytesToOrigin * 1000 * 1000 / conn_.udpSendPacketLen * 2500 >
225 std::numeric_limits<double>::max()) {
226 LOG(WARNING) << "Quic Cubic: timeToOrigin calculation overflow";
227 steadyState_.timeToOrigin = std::numeric_limits<double>::max();
228 } else {
229 steadyState_.timeToOrigin =
230 ::cbrt(bytesToOrigin * 1000 * 1000 / conn_.udpSendPacketLen * 2500);
231 }
232 steadyState_.originPoint = *steadyState_.lastMaxCwndBytes;
233 }
234
calculateCubicCwndDelta(TimePoint ackTime)235 int64_t Cubic::calculateCubicCwndDelta(TimePoint ackTime) noexcept {
236 // TODO: should we also add a rttMin to timeElapsed?
237 if (ackTime < *steadyState_.lastReductionTime) {
238 LOG(WARNING) << "Cubic ackTime earlier than reduction time";
239 return 0;
240 }
241 auto timeElapsed = folly::chrono::ceil<std::chrono::milliseconds>(
242 ackTime - *steadyState_.lastReductionTime);
243 int64_t delta = 0;
244 double timeElapsedCount = static_cast<double>(timeElapsed.count());
245 if (std::pow((timeElapsedCount - steadyState_.timeToOrigin), 3) >
246 std::numeric_limits<double>::max()) {
247 // (timeElapsed - timeToOrigin) ^ 3 will overflow/underflow, cut delta
248 // to numeric_limit
249 LOG(WARNING) << "Quic Cubic: (t-K) ^ 3 overflows";
250 delta = timeElapsedCount > steadyState_.timeToOrigin
251 ? std::numeric_limits<int64_t>::max()
252 : std::numeric_limits<uint64_t>::min();
253 } else {
254 delta = static_cast<int64_t>(std::floor(
255 conn_.udpSendPacketLen * kTimeScalingFactor *
256 std::pow((timeElapsedCount - steadyState_.timeToOrigin), 3.0) / 1000 /
257 1000 / 1000));
258 }
259 VLOG(15) << "Cubic steady cwnd increase: current cwnd=" << cwndBytes_
260 << ", timeElapsed=" << timeElapsed.count()
261 << ", timeToOrigin=" << steadyState_.timeToOrigin
262 << ", origin=" << *steadyState_.lastMaxCwndBytes
263 << ", cwnd delta=" << delta;
264 if (conn_.qLogger) {
265 conn_.qLogger->addCongestionMetricUpdate(
266 conn_.lossState.inflightBytes,
267 getCongestionWindow(),
268 kCubicSteadyCwnd,
269 cubicStateToString(state_).str());
270 }
271 return delta;
272 }
273
calculateCubicCwnd(int64_t delta)274 uint64_t Cubic::calculateCubicCwnd(int64_t delta) noexcept {
275 // TODO: chromium has a limit on targetCwnd to be no larger than half of acked
276 // packet size. Linux also has a limit the cwnd increase to 1 MSS per 2 ACKs.
277 if (delta > 0 &&
278 (std::numeric_limits<uint64_t>::max() - *steadyState_.lastMaxCwndBytes <
279 folly::to<uint64_t>(delta))) {
280 LOG(WARNING) << "Quic Cubic: overflow cwnd cut at uint64_t max";
281 return conn_.transportSettings.maxCwndInMss * conn_.udpSendPacketLen;
282 } else if (
283 delta < 0 &&
284 (folly::to<uint64_t>(std::abs(delta)) > *steadyState_.lastMaxCwndBytes)) {
285 LOG(WARNING) << "Quic Cubic: underflow cwnd cut at minCwndBytes_ " << conn_;
286 return conn_.transportSettings.minCwndInMss * conn_.udpSendPacketLen;
287 } else {
288 return boundedCwnd(
289 delta + *steadyState_.lastMaxCwndBytes,
290 conn_.udpSendPacketLen,
291 conn_.transportSettings.maxCwndInMss,
292 conn_.transportSettings.minCwndInMss);
293 }
294 }
295
cubicReduction(TimePoint lossTime)296 void Cubic::cubicReduction(TimePoint lossTime) noexcept {
297 if (cwndBytes_ >= steadyState_.lastMaxCwndBytes.value_or(cwndBytes_)) {
298 steadyState_.lastMaxCwndBytes = cwndBytes_;
299 } else {
300 // We need to reduce cwnd before it goes back to previous reduction point.
301 // In this case, reduce the steadyState_.lastMaxCwndBytes as well:
302 steadyState_.lastMaxCwndBytes =
303 cwndBytes_ * steadyState_.lastMaxReductionFactor;
304 }
305 steadyState_.lastReductionTime = lossTime;
306 lossCwndBytes_ = cwndBytes_;
307 lossSsthresh_ = ssthresh_;
308 cwndBytes_ = boundedCwnd(
309 cwndBytes_ * steadyState_.reductionFactor,
310 conn_.udpSendPacketLen,
311 conn_.transportSettings.maxCwndInMss,
312 conn_.transportSettings.minCwndInMss);
313 if (steadyState_.tcpFriendly) {
314 steadyState_.estRenoCwnd = cwndBytes_;
315 }
316 }
317
onPacketAckOrLoss(folly::Optional<AckEvent> ackEvent,folly::Optional<LossEvent> lossEvent)318 void Cubic::onPacketAckOrLoss(
319 folly::Optional<AckEvent> ackEvent,
320 folly::Optional<LossEvent> lossEvent) {
321 // TODO: current code in detectLossPackets only gives back a loss event when
322 // largestLostPacketNum isn't a folly::none. But we should probably also check
323 // against it here anyway just in case the loss code is changed in the
324 // furture.
325 if (lossEvent) {
326 onPacketLoss(*lossEvent);
327 if (conn_.pacer) {
328 conn_.pacer->onPacketsLoss();
329 }
330 }
331 if (ackEvent && ackEvent->largestAckedPacket.has_value()) {
332 CHECK(!ackEvent->ackedPackets.empty());
333 onPacketAcked(*ackEvent);
334 }
335 }
336
onPacketAcked(const AckEvent & ack)337 void Cubic::onPacketAcked(const AckEvent& ack) {
338 auto currentCwnd = cwndBytes_;
339 DCHECK_LE(ack.ackedBytes, conn_.lossState.inflightBytes);
340 conn_.lossState.inflightBytes -= ack.ackedBytes;
341 if (recoveryState_.endOfRecovery.has_value() &&
342 *recoveryState_.endOfRecovery >= ack.largestAckedPacketSentTime) {
343 if (conn_.qLogger) {
344 conn_.qLogger->addCongestionMetricUpdate(
345 conn_.lossState.inflightBytes,
346 getCongestionWindow(),
347 kCubicSkipAck,
348 cubicStateToString(state_).str());
349 }
350 return;
351 }
352 switch (state_) {
353 case CubicStates::Hystart:
354 onPacketAckedInHystart(ack);
355 break;
356 case CubicStates::Steady:
357 onPacketAckedInSteady(ack);
358 break;
359 case CubicStates::FastRecovery:
360 onPacketAckedInRecovery(ack);
361 break;
362 }
363 if (conn_.pacer) {
364 conn_.pacer->refreshPacingRate(
365 cwndBytes_ * pacingGain(), conn_.lossState.srtt);
366 }
367 if (cwndBytes_ == currentCwnd) {
368 if (conn_.qLogger) {
369 conn_.qLogger->addCongestionMetricUpdate(
370 conn_.lossState.inflightBytes,
371 getCongestionWindow(),
372 kCwndNoChange,
373 cubicStateToString(state_).str());
374 }
375 }
376 if (conn_.qLogger) {
377 conn_.qLogger->addCongestionMetricUpdate(
378 conn_.lossState.inflightBytes,
379 getCongestionWindow(),
380 kCongestionPacketAck,
381 cubicStateToString(state_).str());
382 }
383 }
384
startHystartRttRound(TimePoint time)385 void Cubic::startHystartRttRound(TimePoint time) noexcept {
386 VLOG(20) << "Cubic Hystart: Start a new RTT round";
387 hystartState_.roundStart = hystartState_.lastJiffy = time;
388 hystartState_.ackCount = 0;
389 hystartState_.lastSampledRtt = hystartState_.currSampledRtt;
390 hystartState_.currSampledRtt = folly::none;
391 hystartState_.rttRoundEndTarget = Clock::now();
392 hystartState_.inRttRound = true;
393 hystartState_.found = HystartFound::No;
394 }
395
isRecovered(TimePoint packetSentTime)396 bool Cubic::isRecovered(TimePoint packetSentTime) noexcept {
397 CHECK(recoveryState_.endOfRecovery.has_value());
398 return packetSentTime > *recoveryState_.endOfRecovery;
399 }
400
type() const401 CongestionControlType Cubic::type() const noexcept {
402 return CongestionControlType::Cubic;
403 }
404
pacingGain() const405 float Cubic::pacingGain() const noexcept {
406 double pacingGain = 1.0f;
407 if (state_ == CubicStates::Hystart) {
408 pacingGain = kCubicHystartPacingGain;
409 } else if (state_ == CubicStates::FastRecovery) {
410 pacingGain = kCubicRecoveryPacingGain;
411 }
412 return pacingGain;
413 }
414
onPacketAckedInHystart(const AckEvent & ack)415 void Cubic::onPacketAckedInHystart(const AckEvent& ack) {
416 if (!hystartState_.inRttRound) {
417 startHystartRttRound(ack.ackTime);
418 }
419
420 // TODO: Should we not increase cwnd if inflight is less than half of cwnd?
421 // Note that we take bytes out of inflightBytes before invoke the state
422 // machine. So the inflightBytes here is already reduced.
423 if (std::numeric_limits<decltype(cwndBytes_)>::max() - cwndBytes_ <
424 ack.ackedBytes) {
425 throw QuicInternalException(
426 "Cubic Hystart: cwnd overflow", LocalErrorCode::CWND_OVERFLOW);
427 }
428 VLOG(15) << "Cubic Hystart increase cwnd=" << cwndBytes_ << ", by "
429 << ack.ackedBytes;
430 cwndBytes_ = boundedCwnd(
431 cwndBytes_ + ack.ackedBytes,
432 conn_.udpSendPacketLen,
433 conn_.transportSettings.maxCwndInMss,
434 conn_.transportSettings.minCwndInMss);
435
436 folly::Optional<Cubic::ExitReason> exitReason;
437 SCOPE_EXIT {
438 if (hystartState_.found != Cubic::HystartFound::No &&
439 cwndBytes_ >= kLowSsthreshInMss * conn_.udpSendPacketLen) {
440 exitReason = Cubic::ExitReason::EXITPOINT;
441 }
442 if (exitReason.has_value()) {
443 VLOG(15) << "Cubic exit slow start, reason = "
444 << (*exitReason == Cubic::ExitReason::SSTHRESH
445 ? "cwnd > ssthresh"
446 : "found exit point");
447 hystartState_.inRttRound = false;
448 ssthresh_ = cwndBytes_;
449 /* Now we exit slow start, reset currSampledRtt to be maximal value so
450 * that next time we go back to slow start, we won't be using a very old
451 * sampled RTT as the lastSampledRtt:
452 */
453 hystartState_.currSampledRtt = folly::none;
454 steadyState_.lastMaxCwndBytes = folly::none;
455 steadyState_.lastReductionTime = folly::none;
456 quiescenceStart_ = folly::none;
457 state_ = CubicStates::Steady;
458 } else {
459 // No exit yet, but we may still need to end this RTT round
460 VLOG(20) << "Cubic Hystart, mayEndHystartRttRound, largestAckedPacketNum="
461 << *ack.largestAckedPacket << ", rttRoundEndTarget="
462 << hystartState_.rttRoundEndTarget.time_since_epoch().count();
463 if (ack.largestAckedPacketSentTime > hystartState_.rttRoundEndTarget) {
464 hystartState_.inRttRound = false;
465 }
466 }
467 };
468
469 if (cwndBytes_ >= ssthresh_) {
470 exitReason = Cubic::ExitReason::SSTHRESH;
471 return;
472 }
473
474 DCHECK_LE(cwndBytes_, ssthresh_);
475 if (hystartState_.found != Cubic::HystartFound::No) {
476 return;
477 }
478 if (hystartState_.ackTrain) {
479 hystartState_.delayMin = std::min(
480 hystartState_.delayMin.value_or(conn_.lossState.srtt),
481 conn_.lossState.srtt);
482 // Within kAckCountingGap since lastJiffy:
483 // TODO: we should experiment with subtract ackdelay from
484 // (ackTime - lastJiffy) as well
485 if (ack.ackTime - hystartState_.lastJiffy <= kAckCountingGap) {
486 hystartState_.lastJiffy = ack.ackTime;
487 if ((ack.ackTime - hystartState_.roundStart) * 2 >=
488 hystartState_.delayMin.value()) {
489 hystartState_.found = Cubic::HystartFound::FoundByAckTrainMethod;
490 }
491 }
492 }
493 // If AckTrain wasn't used or didn't find the exit point, continue with
494 // DelayIncrease.
495 if (hystartState_.found == Cubic::HystartFound::No) {
496 if (hystartState_.ackCount < kAckSampling) {
497 hystartState_.currSampledRtt = std::min(
498 conn_.lossState.srtt,
499 hystartState_.currSampledRtt.value_or(conn_.lossState.srtt));
500 // We can return early if ++ackCount not meeting kAckSampling:
501 if (++hystartState_.ackCount < kAckSampling) {
502 VLOG(20) << "Cubic, AckTrain didn't find exit point. ackCount also "
503 << "smaller than kAckSampling. Return early";
504 return;
505 }
506 }
507
508 if (!hystartState_.lastSampledRtt.has_value() ||
509 (*hystartState_.lastSampledRtt >=
510 std::chrono::microseconds::max() - kDelayIncreaseLowerBound)) {
511 return;
512 }
513 auto eta = std::min(
514 kDelayIncreaseUpperBound,
515 std::max(
516 kDelayIncreaseLowerBound,
517 std::chrono::microseconds(
518 hystartState_.lastSampledRtt.value().count() >> 4)));
519 // lastSampledRtt + eta may overflow:
520 if (*hystartState_.lastSampledRtt >
521 std::chrono::microseconds::max() - eta) {
522 // No way currSampledRtt can top this either, return
523 // TODO: so our rtt is within 8us (kDelayIncreaseUpperBound) of the
524 // microseconds::max(), should we just shut down the connection?
525 return;
526 }
527 VLOG(20) << "Cubic Hystart: looking for DelayIncrease, with eta="
528 << eta.count() << "us, currSampledRtt="
529 << hystartState_.currSampledRtt.value().count()
530 << "us, lastSampledRtt="
531 << hystartState_.lastSampledRtt.value().count()
532 << "us, ackCount=" << (uint32_t)hystartState_.ackCount;
533 if (hystartState_.ackCount >= kAckSampling &&
534 *hystartState_.currSampledRtt >= *hystartState_.lastSampledRtt + eta) {
535 hystartState_.found = Cubic::HystartFound::FoundByDelayIncreaseMethod;
536 }
537 }
538 }
539
540 /**
541 * Note: The Cubic paper, and linux/chromium implementation differ on the
542 * definition of "time to origin", or the variable K in the paper. In the paper,
543 * K represents how much time it takes to grow an empty cwnd to Wmax. In Linux
544 * implementation, to follow Linux's congestion control interface used by other
545 * algorithm as well, "time to origin" is the time it takes to grow cwnd back to
546 * Wmax from its current value. Chromium follows Linux implementation. It
547 * affects timeElapsed as well. If we want to follow the Linux/Chromium
548 * implemetation, then
549 * timeElapsed = now() - time of the first Ack since last window reduction.
550 * Alternatively, the paper's definition,
551 * timeElapsed = now() - time of last window reduction.
552 * Theoretically, both paper and Linux/Chromium should result to the same cwnd.
553 */
onPacketAckedInSteady(const AckEvent & ack)554 void Cubic::onPacketAckedInSteady(const AckEvent& ack) {
555 if (isAppLimited()) {
556 if (conn_.qLogger) {
557 conn_.qLogger->addCongestionMetricUpdate(
558 conn_.lossState.inflightBytes,
559 getCongestionWindow(),
560 kAckInQuiescence,
561 cubicStateToString(state_).str());
562 }
563 return;
564 }
565 // TODO: There is a tradeoff between getting an accurate Cwnd by frequently
566 // calculating it, and the CPU usage cost. This is worth experimenting. E.g.,
567 // Chromium has an option to skips the cwnd calculation if it's configured to
568 // NOT to update cwnd after every ack, and cwnd hasn't changed since last ack,
569 // and time elapsed is smaller than 30ms since last Ack.
570 // TODO: It's worth experimenting to use the larger one between cwndBytes_ and
571 // lastMaxCwndBytes as the W_max, i.e., always refresh Wmax = cwnd during max
572 // probing
573 if (!steadyState_.lastMaxCwndBytes) {
574 // lastMaxCwndBytes won't be set when we transit from Hybrid to Steady. In
575 // that case, we are at the "origin" already.
576 if (conn_.qLogger) {
577 conn_.qLogger->addCongestionMetricUpdate(
578 conn_.lossState.inflightBytes,
579 getCongestionWindow(),
580 kResetTimeToOrigin,
581 cubicStateToString(state_).str());
582 }
583 steadyState_.timeToOrigin = 0.0;
584 steadyState_.lastMaxCwndBytes = cwndBytes_;
585 steadyState_.originPoint = cwndBytes_;
586 if (steadyState_.tcpFriendly) {
587 steadyState_.estRenoCwnd = cwndBytes_;
588 }
589 } else if (
590 !steadyState_.originPoint ||
591 *steadyState_.originPoint != *steadyState_.lastMaxCwndBytes) {
592 updateTimeToOrigin();
593 }
594 if (!steadyState_.lastReductionTime) {
595 steadyState_.lastReductionTime = ack.ackTime;
596 if (conn_.qLogger) {
597 conn_.qLogger->addCongestionMetricUpdate(
598 conn_.lossState.inflightBytes,
599 getCongestionWindow(),
600 kResetLastReductionTime,
601 cubicStateToString(state_).str());
602 }
603 }
604 uint64_t newCwnd = calculateCubicCwnd(calculateCubicCwndDelta(ack.ackTime));
605
606 if (newCwnd < cwndBytes_) {
607 VLOG(10) << "Cubic steady state calculates a smaller cwnd than last round"
608 << ", new cnwd = " << newCwnd << ", current cwnd = " << cwndBytes_;
609 } else {
610 cwndBytes_ = newCwnd;
611 }
612 // Reno cwnd estimation for TCP friendly.
613 if (steadyState_.tcpFriendly && ack.ackedBytes) {
614 /* If tcpFriendly is false, we don't keep track of estRenoCwnd. Right now we
615 don't provide an API to change tcpFriendly in the middle of a connection.
616 If you change that and start to provide an API to mutate tcpFriendly, you
617 should calculate estRenoCwnd even when tcpFriendly is false. */
618 steadyState_.estRenoCwnd += steadyState_.tcpEstimationIncreaseFactor *
619 ack.ackedBytes * conn_.udpSendPacketLen / steadyState_.estRenoCwnd;
620 steadyState_.estRenoCwnd = boundedCwnd(
621 steadyState_.estRenoCwnd,
622 conn_.udpSendPacketLen,
623 conn_.transportSettings.maxCwndInMss,
624 conn_.transportSettings.minCwndInMss);
625 cwndBytes_ = std::max(cwndBytes_, steadyState_.estRenoCwnd);
626 if (conn_.qLogger) {
627 conn_.qLogger->addCongestionMetricUpdate(
628 conn_.lossState.inflightBytes,
629 getCongestionWindow(),
630 kRenoCwndEstimation,
631 cubicStateToString(state_).str());
632 }
633 }
634 }
635
onPacketAckedInRecovery(const AckEvent & ack)636 void Cubic::onPacketAckedInRecovery(const AckEvent& ack) {
637 CHECK_EQ(cwndBytes_, ssthresh_);
638 if (isRecovered(ack.largestAckedPacketSentTime)) {
639 state_ = CubicStates::Steady;
640
641 // We do a Cubic cwnd pre-calculation here so that all Ack events from
642 // this point on in the Steady state will only increase cwnd. We can check
643 // this invariant in the Steady handler easily with this extra calculation.
644 // Note that we don't to the tcpFriendly calculation here.
645 // lastMaxCwndBytes and lastReductionTime are only cleared when Hystart
646 // transits to Steady. For state machine to be in FastRecovery, a Loss
647 // should have happened, and set values to them.
648 DCHECK(steadyState_.lastMaxCwndBytes.has_value());
649 DCHECK(steadyState_.lastReductionTime.has_value());
650 updateTimeToOrigin();
651 cwndBytes_ = calculateCubicCwnd(calculateCubicCwndDelta(ack.ackTime));
652 if (conn_.qLogger) {
653 conn_.qLogger->addCongestionMetricUpdate(
654 conn_.lossState.inflightBytes,
655 getCongestionWindow(),
656 kPacketAckedInRecovery,
657 cubicStateToString(state_).str());
658 }
659 }
660 }
661
getStats(CongestionControllerStats & stats) const662 void Cubic::getStats(CongestionControllerStats& stats) const {
663 stats.cubicStats.state = static_cast<uint8_t>(state_);
664 stats.cubicStats.ssthresh = ssthresh_;
665 }
666
cubicStateToString(CubicStates state)667 folly::StringPiece cubicStateToString(CubicStates state) {
668 switch (state) {
669 case CubicStates::Steady:
670 return "Steady";
671 case CubicStates::Hystart:
672 return "Hystart";
673 case CubicStates::FastRecovery:
674 return "Recovery";
675 }
676 folly::assume_unreachable();
677 }
678
679 } // namespace quic
680