congestion_reno.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package quic
     6  
     7  import (
     8  	"context"
     9  	"log/slog"
    10  	"math"
    11  	"time"
    12  )
    13  
    14  // ccReno is the NewReno-based congestion controller defined in RFC 9002.
    15  // https://www.rfc-editor.org/rfc/rfc9002.html#section-7
    16  type ccReno struct {
    17  	maxDatagramSize int
    18  
    19  	// Maximum number of bytes allowed to be in flight.
    20  	congestionWindow int
    21  
    22  	// Sum of size of all packets that contain at least one ack-eliciting
    23  	// or PADDING frame (i.e., any non-ACK frame), and have neither been
    24  	// acknowledged nor declared lost.
    25  	bytesInFlight int
    26  
    27  	// When the congestion window is below the slow start threshold,
    28  	// the controller is in slow start.
    29  	slowStartThreshold int
    30  
    31  	// The time the current recovery period started, or zero when not
    32  	// in a recovery period.
    33  	recoveryStartTime time.Time
    34  
    35  	// Accumulated count of bytes acknowledged in congestion avoidance.
    36  	congestionPendingAcks int
    37  
    38  	// When entering a recovery period, we are allowed to send one packet
    39  	// before reducing the congestion window. sendOnePacketInRecovery is
    40  	// true if we haven't sent that packet yet.
    41  	sendOnePacketInRecovery bool
    42  
    43  	// inRecovery is set when we are in the recovery state.
    44  	inRecovery bool
    45  
    46  	// underutilized is set if the congestion window is underutilized
    47  	// due to insufficient application data, flow control limits, or
    48  	// anti-amplification limits.
    49  	underutilized bool
    50  
    51  	// ackLastLoss is the sent time of the newest lost packet processed
    52  	// in the current batch.
    53  	ackLastLoss time.Time
    54  
    55  	// Data tracking the duration of the most recently handled sequence of
    56  	// contiguous lost packets. If this exceeds the persistent congestion duration,
    57  	// persistent congestion is declared.
    58  	//
    59  	// https://www.rfc-editor.org/rfc/rfc9002#section-7.6
    60  	persistentCongestion [numberSpaceCount]struct {
    61  		start time.Time    // send time of first lost packet
    62  		end   time.Time    // send time of last lost packet
    63  		next  packetNumber // one plus the number of the last lost packet
    64  	}
    65  }
    66  
    67  func newReno(maxDatagramSize int) *ccReno {
    68  	c := &ccReno{
    69  		maxDatagramSize: maxDatagramSize,
    70  	}
    71  
    72  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.2-1
    73  	c.congestionWindow = min(10*maxDatagramSize, max(14720, c.minimumCongestionWindow()))
    74  
    75  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.1-1
    76  	c.slowStartThreshold = math.MaxInt
    77  
    78  	for space := range c.persistentCongestion {
    79  		c.persistentCongestion[space].next = -1
    80  	}
    81  	return c
    82  }
    83  
    84  // canSend reports whether the congestion controller permits sending
    85  // a maximum-size datagram at this time.
    86  //
    87  // "An endpoint MUST NOT send a packet if it would cause bytes_in_flight [...]
    88  // to be larger than the congestion window [...]"
    89  // https://www.rfc-editor.org/rfc/rfc9002#section-7-7
    90  //
    91  // For simplicity and efficiency, we don't permit sending undersized datagrams.
    92  func (c *ccReno) canSend() bool {
    93  	if c.sendOnePacketInRecovery {
    94  		return true
    95  	}
    96  	return c.bytesInFlight+c.maxDatagramSize <= c.congestionWindow
    97  }
    98  
    99  // setUnderutilized indicates that the congestion window is underutilized.
   100  //
   101  // The congestion window is underutilized if bytes in flight is smaller than
   102  // the congestion window and sending is not pacing limited; that is, the
   103  // congestion controller permits sending data, but no data is sent.
   104  //
   105  // https://www.rfc-editor.org/rfc/rfc9002#section-7.8
   106  func (c *ccReno) setUnderutilized(log *slog.Logger, v bool) {
   107  	if c.underutilized == v {
   108  		return
   109  	}
   110  	oldState := c.state()
   111  	c.underutilized = v
   112  	if logEnabled(log, QLogLevelPacket) {
   113  		logCongestionStateUpdated(log, oldState, c.state())
   114  	}
   115  }
   116  
   117  // packetSent indicates that a packet has been sent.
   118  func (c *ccReno) packetSent(now time.Time, log *slog.Logger, space numberSpace, sent *sentPacket) {
   119  	if !sent.inFlight {
   120  		return
   121  	}
   122  	c.bytesInFlight += sent.size
   123  	if c.sendOnePacketInRecovery {
   124  		c.sendOnePacketInRecovery = false
   125  	}
   126  }
   127  
   128  // Acked and lost packets are processed in batches
   129  // resulting from either a received ACK frame or
   130  // the loss detection timer expiring.
   131  //
   132  // A batch consists of zero or more calls to packetAcked and packetLost,
   133  // followed by a single call to packetBatchEnd.
   134  //
   135  // Acks may be reported in any order, but lost packets must
   136  // be reported in strictly increasing order.
   137  
   138  // packetAcked indicates that a packet has been newly acknowledged.
   139  func (c *ccReno) packetAcked(now time.Time, sent *sentPacket) {
   140  	if !sent.inFlight {
   141  		return
   142  	}
   143  	c.bytesInFlight -= sent.size
   144  
   145  	if c.underutilized {
   146  		// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.8
   147  		return
   148  	}
   149  	if sent.time.Before(c.recoveryStartTime) {
   150  		// In recovery, and this packet was sent before we entered recovery.
   151  		// (If this packet was sent after we entered recovery, receiving an ack
   152  		// for it moves us out of recovery into congestion avoidance.)
   153  		// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2
   154  		return
   155  	}
   156  	c.congestionPendingAcks += sent.size
   157  }
   158  
   159  // packetLost indicates that a packet has been newly marked as lost.
   160  // Lost packets must be reported in increasing order.
   161  func (c *ccReno) packetLost(now time.Time, space numberSpace, sent *sentPacket, rtt *rttState) {
   162  	// Record state to check for persistent congestion.
   163  	// https://www.rfc-editor.org/rfc/rfc9002#section-7.6
   164  	//
   165  	// Note that this relies on always receiving loss events in increasing order:
   166  	// All packets prior to the one we're examining now have either been
   167  	// acknowledged or declared lost.
   168  	isValidPersistentCongestionSample := (sent.ackEliciting &&
   169  		!rtt.firstSampleTime.IsZero() &&
   170  		!sent.time.Before(rtt.firstSampleTime))
   171  	if isValidPersistentCongestionSample {
   172  		// This packet either extends an existing range of lost packets,
   173  		// or starts a new one.
   174  		if sent.num != c.persistentCongestion[space].next {
   175  			c.persistentCongestion[space].start = sent.time
   176  		}
   177  		c.persistentCongestion[space].end = sent.time
   178  		c.persistentCongestion[space].next = sent.num + 1
   179  	} else {
   180  		// This packet cannot establish persistent congestion on its own.
   181  		// However, if we have an existing range of lost packets,
   182  		// this does not break it.
   183  		if sent.num == c.persistentCongestion[space].next {
   184  			c.persistentCongestion[space].next = sent.num + 1
   185  		}
   186  	}
   187  
   188  	if !sent.inFlight {
   189  		return
   190  	}
   191  	c.bytesInFlight -= sent.size
   192  	if sent.time.After(c.ackLastLoss) {
   193  		c.ackLastLoss = sent.time
   194  	}
   195  }
   196  
   197  // packetBatchEnd is called at the end of processing a batch of acked or lost packets.
   198  func (c *ccReno) packetBatchEnd(now time.Time, log *slog.Logger, space numberSpace, rtt *rttState, maxAckDelay time.Duration) {
   199  	if logEnabled(log, QLogLevelPacket) {
   200  		oldState := c.state()
   201  		defer func() { logCongestionStateUpdated(log, oldState, c.state()) }()
   202  	}
   203  	if !c.ackLastLoss.IsZero() && !c.ackLastLoss.Before(c.recoveryStartTime) {
   204  		// Enter the recovery state.
   205  		// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2
   206  		c.recoveryStartTime = now
   207  		c.slowStartThreshold = c.congestionWindow / 2
   208  		c.congestionWindow = max(c.slowStartThreshold, c.minimumCongestionWindow())
   209  		c.sendOnePacketInRecovery = true
   210  		// Clear congestionPendingAcks to avoid increasing the congestion
   211  		// window based on acks in a frame that sends us into recovery.
   212  		c.congestionPendingAcks = 0
   213  		c.inRecovery = true
   214  	} else if c.congestionPendingAcks > 0 {
   215  		// We are in slow start or congestion avoidance.
   216  		c.inRecovery = false
   217  		if c.congestionWindow < c.slowStartThreshold {
   218  			// When the congestion window is less than the slow start threshold,
   219  			// we are in slow start and increase the window by the number of
   220  			// bytes acknowledged.
   221  			d := min(c.slowStartThreshold-c.congestionWindow, c.congestionPendingAcks)
   222  			c.congestionWindow += d
   223  			c.congestionPendingAcks -= d
   224  		}
   225  		// When the congestion window is at or above the slow start threshold,
   226  		// we are in congestion avoidance.
   227  		//
   228  		// RFC 9002 does not specify an algorithm here. The following is
   229  		// the recommended algorithm from RFC 5681, in which we increment
   230  		// the window by the maximum datagram size every time the number
   231  		// of bytes acknowledged reaches cwnd.
   232  		for c.congestionPendingAcks > c.congestionWindow {
   233  			c.congestionPendingAcks -= c.congestionWindow
   234  			c.congestionWindow += c.maxDatagramSize
   235  		}
   236  	}
   237  	if !c.ackLastLoss.IsZero() {
   238  		// Check for persistent congestion.
   239  		// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.6
   240  		//
   241  		// "A sender [...] MAY use state for just the packet number space that
   242  		// was acknowledged."
   243  		// https://www.rfc-editor.org/rfc/rfc9002#section-7.6.2-5
   244  		//
   245  		// For simplicity, we consider each number space independently.
   246  		const persistentCongestionThreshold = 3
   247  		d := (rtt.smoothedRTT + max(4*rtt.rttvar, timerGranularity) + maxAckDelay) *
   248  			persistentCongestionThreshold
   249  		start := c.persistentCongestion[space].start
   250  		end := c.persistentCongestion[space].end
   251  		if end.Sub(start) >= d {
   252  			c.congestionWindow = c.minimumCongestionWindow()
   253  			c.recoveryStartTime = time.Time{}
   254  			rtt.establishPersistentCongestion()
   255  		}
   256  	}
   257  	c.ackLastLoss = time.Time{}
   258  }
   259  
   260  // packetDiscarded indicates that the keys for a packet's space have been discarded.
   261  func (c *ccReno) packetDiscarded(sent *sentPacket) {
   262  	// https://www.rfc-editor.org/rfc/rfc9002#section-6.2.2-3
   263  	if sent.inFlight {
   264  		c.bytesInFlight -= sent.size
   265  	}
   266  }
   267  
   268  func (c *ccReno) minimumCongestionWindow() int {
   269  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.2-4
   270  	return 2 * c.maxDatagramSize
   271  }
   272  
   273  func logCongestionStateUpdated(log *slog.Logger, oldState, newState congestionState) {
   274  	if oldState == newState {
   275  		return
   276  	}
   277  	log.LogAttrs(context.Background(), QLogLevelPacket,
   278  		"recovery:congestion_state_updated",
   279  		slog.String("old", oldState.String()),
   280  		slog.String("new", newState.String()),
   281  	)
   282  }
   283  
   284  type congestionState string
   285  
   286  func (s congestionState) String() string { return string(s) }
   287  
   288  const (
   289  	congestionSlowStart           = congestionState("slow_start")
   290  	congestionCongestionAvoidance = congestionState("congestion_avoidance")
   291  	congestionApplicationLimited  = congestionState("application_limited")
   292  	congestionRecovery            = congestionState("recovery")
   293  )
   294  
   295  func (c *ccReno) state() congestionState {
   296  	switch {
   297  	case c.inRecovery:
   298  		return congestionRecovery
   299  	case c.underutilized:
   300  		return congestionApplicationLimited
   301  	case c.congestionWindow < c.slowStartThreshold:
   302  		return congestionSlowStart
   303  	default:
   304  		return congestionCongestionAvoidance
   305  	}
   306  }
   307
View as plain text