blob: 982cbf4bb46a009bd55fc7b0f38bef3471a5b63e [file] [log] [blame]
// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
//go:build go1.21
package quic
import (
"math"
"time"
)
// ccReno is the NewReno-based congestion controller defined in RFC 9002.
// https://www.rfc-editor.org/rfc/rfc9002.html#section-7
type ccReno struct {
maxDatagramSize int
// Maximum number of bytes allowed to be in flight.
congestionWindow int
// Sum of size of all packets that contain at least one ack-eliciting
// or PADDING frame (i.e., any non-ACK frame), and have neither been
// acknowledged nor declared lost.
bytesInFlight int
// When the congestion window is below the slow start threshold,
// the controller is in slow start.
slowStartThreshold int
// The time the current recovery period started, or zero when not
// in a recovery period.
recoveryStartTime time.Time
// Accumulated count of bytes acknowledged in congestion avoidance.
congestionPendingAcks int
// When entering a recovery period, we are allowed to send one packet
// before reducing the congestion window. sendOnePacketInRecovery is
// true if we haven't sent that packet yet.
sendOnePacketInRecovery bool
// underutilized is set if the congestion window is underutilized
// due to insufficient application data, flow control limits, or
// anti-amplification limits.
underutilized bool
// ackLastLoss is the sent time of the newest lost packet processed
// in the current batch.
ackLastLoss time.Time
// Data tracking the duration of the most recently handled sequence of
// contiguous lost packets. If this exceeds the persistent congestion duration,
// persistent congestion is declared.
//
// https://www.rfc-editor.org/rfc/rfc9002#section-7.6
persistentCongestion [numberSpaceCount]struct {
start time.Time // send time of first lost packet
end time.Time // send time of last lost packet
next packetNumber // one plus the number of the last lost packet
}
}
func newReno(maxDatagramSize int) *ccReno {
c := &ccReno{
maxDatagramSize: maxDatagramSize,
}
// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.2-1
c.congestionWindow = min(10*maxDatagramSize, max(14720, c.minimumCongestionWindow()))
// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.1-1
c.slowStartThreshold = math.MaxInt
for space := range c.persistentCongestion {
c.persistentCongestion[space].next = -1
}
return c
}
// canSend reports whether the congestion controller permits sending
// a maximum-size datagram at this time.
//
// "An endpoint MUST NOT send a packet if it would cause bytes_in_flight [...]
// to be larger than the congestion window [...]"
// https://www.rfc-editor.org/rfc/rfc9002#section-7-7
//
// For simplicity and efficiency, we don't permit sending undersized datagrams.
func (c *ccReno) canSend() bool {
if c.sendOnePacketInRecovery {
return true
}
return c.bytesInFlight+c.maxDatagramSize <= c.congestionWindow
}
// setUnderutilized indicates that the congestion window is underutilized.
//
// The congestion window is underutilized if bytes in flight is smaller than
// the congestion window and sending is not pacing limited; that is, the
// congestion controller permits sending data, but no data is sent.
//
// https://www.rfc-editor.org/rfc/rfc9002#section-7.8
func (c *ccReno) setUnderutilized(v bool) {
c.underutilized = v
}
// packetSent indicates that a packet has been sent.
func (c *ccReno) packetSent(now time.Time, space numberSpace, sent *sentPacket) {
if !sent.inFlight {
return
}
c.bytesInFlight += sent.size
if c.sendOnePacketInRecovery {
c.sendOnePacketInRecovery = false
}
}
// Acked and lost packets are processed in batches
// resulting from either a received ACK frame or
// the loss detection timer expiring.
//
// A batch consists of zero or more calls to packetAcked and packetLost,
// followed by a single call to packetBatchEnd.
//
// Acks may be reported in any order, but lost packets must
// be reported in strictly increasing order.
// packetAcked indicates that a packet has been newly acknowledged.
func (c *ccReno) packetAcked(now time.Time, sent *sentPacket) {
if !sent.inFlight {
return
}
c.bytesInFlight -= sent.size
if c.underutilized {
// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.8
return
}
if sent.time.Before(c.recoveryStartTime) {
// In recovery, and this packet was sent before we entered recovery.
// (If this packet was sent after we entered recovery, receiving an ack
// for it moves us out of recovery into congestion avoidance.)
// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2
return
}
c.congestionPendingAcks += sent.size
}
// packetLost indicates that a packet has been newly marked as lost.
// Lost packets must be reported in increasing order.
func (c *ccReno) packetLost(now time.Time, space numberSpace, sent *sentPacket, rtt *rttState) {
// Record state to check for persistent congestion.
// https://www.rfc-editor.org/rfc/rfc9002#section-7.6
//
// Note that this relies on always receiving loss events in increasing order:
// All packets prior to the one we're examining now have either been
// acknowledged or declared lost.
isValidPersistentCongestionSample := (sent.ackEliciting &&
!rtt.firstSampleTime.IsZero() &&
!sent.time.Before(rtt.firstSampleTime))
if isValidPersistentCongestionSample {
// This packet either extends an existing range of lost packets,
// or starts a new one.
if sent.num != c.persistentCongestion[space].next {
c.persistentCongestion[space].start = sent.time
}
c.persistentCongestion[space].end = sent.time
c.persistentCongestion[space].next = sent.num + 1
} else {
// This packet cannot establish persistent congestion on its own.
// However, if we have an existing range of lost packets,
// this does not break it.
if sent.num == c.persistentCongestion[space].next {
c.persistentCongestion[space].next = sent.num + 1
}
}
if !sent.inFlight {
return
}
c.bytesInFlight -= sent.size
if sent.time.After(c.ackLastLoss) {
c.ackLastLoss = sent.time
}
}
// packetBatchEnd is called at the end of processing a batch of acked or lost packets.
func (c *ccReno) packetBatchEnd(now time.Time, space numberSpace, rtt *rttState, maxAckDelay time.Duration) {
if !c.ackLastLoss.IsZero() && !c.ackLastLoss.Before(c.recoveryStartTime) {
// Enter the recovery state.
// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2
c.recoveryStartTime = now
c.slowStartThreshold = c.congestionWindow / 2
c.congestionWindow = max(c.slowStartThreshold, c.minimumCongestionWindow())
c.sendOnePacketInRecovery = true
// Clear congestionPendingAcks to avoid increasing the congestion
// window based on acks in a frame that sends us into recovery.
c.congestionPendingAcks = 0
} else if c.congestionPendingAcks > 0 {
// We are in slow start or congestion avoidance.
if c.congestionWindow < c.slowStartThreshold {
// When the congestion window is less than the slow start threshold,
// we are in slow start and increase the window by the number of
// bytes acknowledged.
d := min(c.slowStartThreshold-c.congestionWindow, c.congestionPendingAcks)
c.congestionWindow += d
c.congestionPendingAcks -= d
}
// When the congestion window is at or above the slow start threshold,
// we are in congestion avoidance.
//
// RFC 9002 does not specify an algorithm here. The following is
// the recommended algorithm from RFC 5681, in which we increment
// the window by the maximum datagram size every time the number
// of bytes acknowledged reaches cwnd.
for c.congestionPendingAcks > c.congestionWindow {
c.congestionPendingAcks -= c.congestionWindow
c.congestionWindow += c.maxDatagramSize
}
}
if !c.ackLastLoss.IsZero() {
// Check for persistent congestion.
// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.6
//
// "A sender [...] MAY use state for just the packet number space that
// was acknowledged."
// https://www.rfc-editor.org/rfc/rfc9002#section-7.6.2-5
//
// For simplicity, we consider each number space independently.
const persistentCongestionThreshold = 3
d := (rtt.smoothedRTT + max(4*rtt.rttvar, timerGranularity) + maxAckDelay) *
persistentCongestionThreshold
start := c.persistentCongestion[space].start
end := c.persistentCongestion[space].end
if end.Sub(start) >= d {
c.congestionWindow = c.minimumCongestionWindow()
c.recoveryStartTime = time.Time{}
rtt.establishPersistentCongestion()
}
}
c.ackLastLoss = time.Time{}
}
// packetDiscarded indicates that the keys for a packet's space have been discarded.
func (c *ccReno) packetDiscarded(sent *sentPacket) {
// https://www.rfc-editor.org/rfc/rfc9002#section-6.2.2-3
if sent.inFlight {
c.bytesInFlight -= sent.size
}
}
func (c *ccReno) minimumCongestionWindow() int {
// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.2-4
return 2 * c.maxDatagramSize
}